a***e
发帖数: 413 | 1 终于有个不让我那么抓狂的题了，我的code如下，从后往前扫，两个指针，只扫一遍，
但不算inplace.
看到的其他inplace的好像要scan两遍，有只扫一遍的inplace的做法吗？
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
class Solution {
public:
void reverseWords(string &s) {
int len=s.size();
if (len==0) return;
int start=len-1,end=len-1;
while(s[end]==' '&&s[start]==' ')
{
end--;
start--;
}
strin... 阅读全帖 |
|
j**l
发帖数: 2911 | 2 要求inplace对栈内的元素重新排序，你可以使用的方法
Push
Pop(不返回值)
Top
IsEmpty
是否应该递归，利用操作系统的隐含堆栈空间，得到一个伪inplace的算法？
假定栈元素是int，代码如下：
void Sort(Stack& s)
{
// 栈为空，无需排序
if (s.IsEmpty())
return;
// 先弹出栈顶元素x，对剩下的栈元素递归排序
int x = s.Top();
s.Pop();
Sort(s);
// 如果排好序的栈为空，把x送回栈即可，排序完成
if (s.IsEmpty())
{
s.Push(x);
return;
}
// 如果x不小于栈顶元素，同样把x送回栈即可，排序完成
int y = s.Top();
if (x >= y)
{
s.Push(x);
return;
}
// 否则, 令x归栈后，栈顶还是最大元素... 阅读全帖 |
|
c******o
发帖数: 534 | 3 看了几个，recursion函数里面对left child和right child进行递归，
请问这个能是inplace的吗？
最多tail recursion不算空间，
但是里面2个recursion能是inplace的吗？ |
|
m******9
发帖数: 968 | 4 有个关于inplace merge的题目没想明白：
two sorted arrays A and B，size 分别为m和n，需要in place merge它们，不能用
extra space
一个常见的题目是：A中有足够的空间可以另外容纳下整个B。这个题目可以用的方法是
： 用merge sort中merge的办法，都从A和B的最后一个元素开始往前scan，A[i] B[j]
哪个大，就将大的放置在A的尾端，下次比较将大的放置在次尾端，依次进行下去。O(m+n)
比如：
A: 1 3 5 _ _ _ _
B: 2 4 6 8
output: A: 1 2 3 4 5 6 8
但是另外一个变形的题目是： A就是A，没有另外的空间可以容纳B。
即：
A: 1 3 5
B: 2 4 6 8
结果应当是：
A: 1 2 3
B: 4 5 6 8
我知道的一个方法是利用selection sort的思想，每次都从A B中select一个min放在最
左端，然后下次选择sec min放在次左端，依次下去。O(n^2)
这种题目，大家有什么好办法吗？ 谢了 |
|
v*******7
发帖数: 187 | 5
Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
到parent
指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。 |
|
p*****2
发帖数: 21240 | 6 都是immutable的数据结构，inplace违反了FP的原则，因此这类问题都不需要准备了吧
？面试变简单了。 |
|
|
f****4
发帖数: 1359 | 8 这里就用树的中续遍历来说好了
如果是用stack的话，stack最长要能存储树的最长路径
最坏情况长度为n，最优为lgn
那么用递归的话，如果空间需要考虑stack的话，递归算不算inplace？
如果我们认为递归的stack开销不考虑，那么，我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下，同一时间最多被调用n次，最少lgn次。那么这个算法
算是inplace么？（毕竟这里用到的额外内存为lgn ~ n 个）
还有，书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort |
|
d*k
发帖数: 207 | 9 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个... 阅读全帖 |
|
d*k
发帖数: 207 | 10 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个... 阅读全帖 |
|
y*********e
发帖数: 518 | 11 O(nlogn):
qsort 和 mergesort 都可以达到O(nlogn)，但是 qsort 的常数因子比 mergesort 低
很多。所以，一般情况下 qsort 会更快。
O(n^2):
虽然 qsort 的最坏情况是 O(n^2)，但是要达到这个最坏情况不容易。对于实现的较好
randomized qsort，达到这个最坏情况的几率接近于 1 / n^logn。这个数值是非常低
的。
stable vs unstable:
通常 qsort 的实现是 unstable的，mergesort 的实现是 stable 的。
还有一点，qsort 一般是 inplace 的，mergesort 一般的实现不是 inplace 的。
random access:
qsort 要求可以对排序对象进行 random access。对于排序主内存中的 array 就很实
用。但是，遇到排序的对象不支持 random access，那么 qosrt 就不行了。比如排序
linked list，或者做磁盘文件排序。。利用这一点，可以很容易的用 mergesort 实现
并发排序。 |
|
f*******4
发帖数: 1401 | 12 2. m*n矩阵inplace rotation怎么做？如果用二维数组表示
的矩阵inplace rotation过后怎么保存？
1. n个城市之间的距离要存下来，怎么存最省空间？
二维数组就是O(n^2)的空间了吧 如果牺牲一点access时间的话
会不会和minimum spanning tree有关系？
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
不理解这个题，“用一个表记录0~255的1个数”不是成了用空间换时间了么
2. p*q的matrix,从左下到右上路径数？
这个我觉得用C(p,q)最简洁 就是从p里选q个 |
|
f***g
发帖数: 214 | 13 0.02
如果不是inplace，就找个数组临时存一下。
要排序，所以O(nlogn)
如果是inplace，就先变成linked list
排序，再变回来。O(n^2)
复杂度都不低，楼主要不咱私下讨论讨论？ |
|
f*********i
发帖数: 197 | 14 A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bianry tree找两个节点的最
小公共父亲, 一开始是允许有父节点的,然后扩展到没有父亲节点,我给了O(nlogn)解法
public static BinaryTree tree_least_comm... 阅读全帖 |
|
S**I
发帖数: 15689 | 15 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
w****x
发帖数: 2483 | 16 我想问一下第一题怎么inplace??
有inplace的要求吗?? |
|
p*****2
发帖数: 21240 | 17
应该不用inplace吧，不过inplace也不算麻烦吧。 |
|
S**I
发帖数: 15689 | 18 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 19 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
d**e
发帖数: 6098 | 20 inplace is not required.
if a inplace method exists, i don't think it would be easy. |
|
i*********7
发帖数: 348 | 21 我明白你的意思。
我只是考虑到一个问题
实际上string 是 Immutable的，也就是你对它做任何改动，都不是inplace的，只是产
生一个新的改动过的复制品。
这样比能实际inplace操作的char数组要慢的多和浪费空间的多。
所以我先从char array操作，最后直接通过操作得来的char array直接创造一个string
。这样应该会效率很多。 |
|
h****n
发帖数: 1093 | 22 1 inplace reverse the whole string O(n) space O 1
2 inplace reverse each word O(n) space O 1 |
|
l********5
发帖数: 230 | 23 先祝大家新春快乐~~~新年新气象~~
本人cs master刚毕业，OPT中，Feb.1开始的，至今未找到工作，，，近期连续浪费三
个onsite实在伤感。。。眼瞅着3个月期限一天一天过去。。。。。
接下来是BB的onsite，给recruiter发了我的schedule尚未有回复，，看到有人约好了
onsite也被cancel，表示十分慌张。。。在此先报一下之前几个onsite的情况攒攒人品
了。。。
comScore Dec.10,2012
算是比较著名的市场调研数据分析公司，总部在Reston,VA，算是DC郊区。公司不大但
是各方面都挺正规，订机票酒店也不需要自己操心。工作环境看起来也不错，乒乓球桌
桌球台啥的也都有。。
先是学校的oncampus skype面试，一个戴眼镜的小印，大部分时间是问简历，project
啥的，穿插地问了些基本SQL，问了个1-100 missing number，然后介绍他们的情况，
在介绍的时候还不忘穿插小问题：“ blablabla，你说这个情况应该怎么办呢？“ 幸
好没走神，基本都回答出来了。
后来两周要我去onsite，跟我确认了下时间... 阅读全帖 |
|
V*********r
发帖数: 666 | 24 堆排序很常用啊。之所以在“面试”中不常出，准确的说法是不常考其实现，无非两个
原因：
1. 白板篇幅有限，heapify/siftup/siftdown全写完白板容不下。
2. quicksort/mergesort变种很多，可inplace可外借空间，可迭代可递归（比如考你
非inplace的迭代式mergesort），是分治思想的典型代表，容易形成考点。而且其思想
适用于任何线性表（不管是数组还是链式存储），也可扩展到树形存储。考点密集不奇
怪。
? |
|
b**********5
发帖数: 7881 | 25 我连原题都没懂？ 原题是不是就是一个counting sort， 然后用inplace counting
sort就可以了？
如果我用inplace counting sort， 那原题和follow up有什么区别呢？ |
|
|
g****t
发帖数: 31659 | 27 输出为(previous表的地址，diff）
这样旧表仍然是immutable的。这样可以吗？
Fp和imperative确实很多时候其实就是时域信号以及频域类似的关系。但是也有非常多
corner cases.
例如矩阵求逆写FP我觉得难度极大。fortran的库有
太多利用inplace改变矩阵元素的挖内存技巧了。
(我本科毕业设计本想沿着大三的课题
做AI,结果老板给
了本fortran数值计算书让改写成c plus plus。弄得我丢了半条命）
: 在语言层面可以做到纯函数。各种树都能做别说哈希表了。比如哈希表插
入函数
，输入
: 为哈希表和需要插入的对象，输出为一个*新的*哈希表。因为建了一个新
的表，
所以不
: 存在inplace
: 更新这个操作。但是从实现上，新表和老表通过reference共享了绝大部
分内容
，所以
: 空间代价还是O(1). 有点像docker用的那个洋葱文件系统。所有更新操作
都通过
包洋葱
: 实现。
: 一路摊过去。gc在背后收拾没用了的东西。
: 纯fp和imperati... 阅读全帖 |
|
d**a
发帖数: 84 | 28 来自主题: JobHunting版 - 一道面试题 这个就是inplace merge吧，递归是可以，但是要用implicit stack, 不知有无别的办
法。
].
the |
|
|
l***i
发帖数: 1309 | 30 For your second problem, why not dump the smallest numbers to A and the rest
to B(swap max in A with min in B), then sort A, B separately to get O(nlogn
). Heap sort can do this since you do not have O(n) extra storage. |
|
g*******y
发帖数: 1930 | 31 分冶可以做到nlogn的in place merge
简单说就是在B中binary 搜索A的median的位置，然后交换两段，然后分冶
不过肯定不是最优了，不过我觉得对于面试的要求也许还行。
(m+n) |
|
|
g*******y
发帖数: 1930 | 33 yes,
but, then, what's point of the problem?
I don't think this is a good interview problem after all. |
|
m******9
发帖数: 968 | 34 先用scan的方法，比如用2 pointer都从A B的左端开始scan，将smaller numbers都
swap到A
中，然后再sort B，例如用heap sort， quick sort
整体上是O(nlgn)
rest
O(nlogn |
|
m******9
发帖数: 968 | 35 小尾羊，能再具体一下吗？我没跟上你的思路，尤其是“交换两段”那部分？
多谢 |
|
B**r
发帖数: 42 | 36 昨天MS intern的电话面试，然后24小时后收到据信，效率非常之高，虽然我有别的
offer，但是还是不爽，上来抱怨下。
其实安排的是2周前的面试，当天放我鸽子，我忍，他们说给重新安排，结果杳无音信
，期间我拿到别家的offer，所以也不惦记着。1周多后终于发信催他们，结果安排了昨
天的电话面试。
第一题，我SB了，上来问我申的是他家三个position的那一个，我申的是SDE，但是他
突然一问，我没弄懂他说的是啥，以为是preference表里面的那几个。结果被鄙视，才
想起是SDE，SDET，PM之分，八成栽在这上面了。
第二题，问我之前challenge的project，我讲的一般，感觉没解释清楚，早知道弄个简
单的讲。
第三题，斐波纳契数列，recursion 和 iteration呗，我说了recursion 怎么做
dynamic programming怎么做，DP可以inplace做。结果他心不在焉，问我我后面讲的那
个算法是不是就是iteration，我说那个iteration的就是DP的啊。然后分析时间空间复
杂度。。。。
第四题，test计算器，不过我没有申te |
|
s****t
发帖数: 36 | 37 RP很高，被问了2个很简单的题。一个是inplace reverse linklist，另一个是
strcmp的implementation。不是local的，不知道是不是还要第三轮电面。 |
|
l*******e
发帖数: 309 | 38 inplace sort算不算不要extra空间？ |
|
|
|
|
p******r
发帖数: 2999 | 42 。。。
牛啊，能写出inplace的O(n)的selection algo |
|
p********7
发帖数: 549 | 43 转成双链表，然后再转balanced tree，保证了inplace
际上已经在 |
|
y*********e
发帖数: 518 | 44 下午刚面完Google Mountain View，趁记忆还在，把经历写下来。
因为签署了NDA，所以不方便把题目直接贴在这里。只能说个大概。若是有兴趣的筒子
，可以私下交流。
早上10点半开始。面第一位阿三哥，开始侃项目，谈跟专业相关的东西，追问的很深，
最后还有15分钟的时候要求写代码，要求inplace对一个数据结构内的元素重新排序，
昏倒啊。在白板上画了简单的结构，讨论后获得首肯，然后开始写代码。
我把笔记本电脑带了过去，所以在键盘上敲。大概一会就写出来了。（若是在白板上写
，怎么死的都不知道阿）。然后三哥问，are you done？我说跑几个测试案例试试看。
然后在纸上写了5个案例，一行一行的检查。立马发现2个bug，更正之。三哥看到快没
时间了，说你跑这个案例试试。遂发现一个新的bug，更正之。最后代码写出来完整。
三哥满意的走了。
第二位是个白人。一上来就做题。开始我理解以为是一个DP，后来沟通之后发觉可以有
很简单的解法。直接奔向O(n)的解法。跟面官沟通完想法，最后获得同意后在笔记本上
敲键盘。很快写了出来。面官随后问测试案例。我直接在笔记本电脑里面写测试代码，
写 |
|
y*******g
发帖数: 6599 | 45 heapsort就是inplace nlogn |
|
j********x
发帖数: 2330 | 46 估计跟inplace shuffling有关系
one pass scan可以得到正数和负数的分界，然后直接shuffle到指定位置好了 |
|
|
J********a
发帖数: 5208 | 48 he is looking for using randomized quicksort. (not full sort, just use the
partition routine)
just use inplace quicksort, use the new value as pivot value and while the
final placement is not in the middle, call the partition routine on the
larger portion.
This should be as fast as the heap method, but no additional space needed.
For more information you can watch MIT opencourse for algorithm
Lecture 4: Quicksort, Randomized Algorithms
and
Lecture 6: Order Statistics, Median
median |
|
v******y
发帖数: 22 | 49 来自主题: JobHunting版 - 问一算法题 Re-arrange array inplace from "a0a1..anb0b1..bn" to "a0b0a1b1..anbn".
Is there any solution better than O(n^2) ? |
|
f*z
发帖数: 34 | 50 careercup上看到的，没有想到好的办法。
题目：
Convert a min heap to BST without changing its structure and
of course no extra space |
|
