logo
Redian新闻
>未名空间
>EB23 - 劳工卡
>
绿卡已经批了，如果还没有拿到就要出国怎么办
avatar
绿卡已经批了，如果还没有拿到就要出国怎么办# EB23 - 劳工卡
l*3
1 楼
刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
cc150
闲话不说，上面经：
前两天面的。三哥面试官
面试开始，直接上题。给了一个Quack的类，里面有三个方法：
pop(): 随机从头或者尾扔出一个元素；
peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
个元素；
push()：向尾部插入一个元素
问题是：给一个排序好的Quack,怎么把里面的元素原封不动的放到一个Array里面。
follow-up：如果quack里面有重复的元素，怎么处理
拿到题之后，完全没思路，基本是在面试官的指导下才做出来的。而且follow-up的题
目也没想到该怎么做。最后只写了没有重复元素的代码。
希望对大家有用，祝大家能拿到称心的offer。
avatar
O*h
2 楼
是不是用AP回来
已经收到 approval notice in mail
但是没收到塑料卡
avatar
s*x
3 楼
感觉 EPI (elements programing interview) 还是值得一读，
题目量很大， 光看给答案的就行了， 有些题很难， 略过。
这本书编排可真差， 内容还不错，有几道经典题。
avatar
l*4
4 楼
You are now a permanent resident and can no longer depart the U.S. and
return pursuant to any non-immigrant status (e.g. H-1B, L-1) or based on the
Advance Parole. If you plan to travel abroad prior to receiving the
physical permanent resident card, you must first obtain an ADIT stamp in
your passport prior to departing the U.S.

【在 O*********h 的大作中提到】
: 是不是用AP回来
: 已经收到 approval notice in mail
: 但是没收到塑料卡
avatar
q*c
5 楼
peek()告诉你是头还是尾吗，还是只返回那个元素？
avatar
l*3
6 楼
只返回元素。
只是peek了之后，再pop的话就一定是之前peek的元素

【在 q********c 的大作中提到】
: peek()告诉你是头还是尾吗，还是只返回那个元素？
avatar
l*3
7 楼
谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
写的，我只会java，看起来感觉有点吃力。
请问还有别的建议吗？

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
f*e
8 楼
是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*3
9 楼
如果quack里面的元素是unique的话, 是不是可以一直pop. pop出来的元素都先依次放
在输出数组的前面, 如果发现比前一个元素小的话, 说明前一个元素是尾元素, 把这个
尾元素挪数组尾就行了.
avatar
l*3
10 楼
从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
比如说1,2,3,4,5
peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
不知道我是不是看懂你的思路了

【在 f*****e 的大作中提到】
: 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
avatar
l*d
11 楼
可不可以先 pop, 然后 peek， 然后比大小决定往前放还是往后放？数组维护两个
index：begin and end
public int[] solve() {
int[] result = new int[list.size()];
int beg = 0, end = result.length-1;
int last = list.pop();
while (!list.isEmpty()) {
int next = list.peek();
if (last > next) result[end--] = last;
else result[beg++] = last;
last = list.pop();
}
result[beg] = last;
return result;
}
avatar
f*e
12 楼
那你不停pop到一个数组，然后排序不就行了？

【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
avatar
f*e
13 楼
什么时间复杂度？

【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
avatar
q*c
14 楼
稍微想了一下，每 个iteration pop两次，再比较就可以了。
avatar
e*3
15 楼
这个我感觉挺简单的呀：
1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
里面所有元素的上限和下限。
2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
array index保持当前在array中的位置。
3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
排序。
上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
空间复杂度是O(n).
更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
果是最大的元素，push到stack里面，所有Quack里面的元素取出来以后，合并queue和
stack，queue是已经从小到大排好序的，直接放进array，stack最上面的是最小的，所
以也是pop出来直接放到array。
queue里面最大的元素小于stack里面最小的元素，所以需要先把queue里面的元素放到
array里面，然后再把stack里面的元素放到array里面，这个程序的实现很简单，基本
的数据结构操作，我就不具体写了。
这个唯一的不好就是排序不是stable的，重复的元素可能在array里面和在quack里面的
排序不一样。
这个的时间复杂度是O(n),空间复杂度是O(2*n),因为需要额外的保存stack和queue，如
果具体实现是用单链表的话，那空间复杂度是O(n),因为需要保存的元素上限恒定为O(n
).
我举个例子，假设初始数据是[1,2,2,3],那首先peek找到1最小，3最大，然后peek开始
，假设第一次peak是1，那把1加入queue，当前的最小值还是记录为1，然后继续peek，
如果结果是3的话那放到stack里面，如果是2的话放到queue里面，同时更新最小值为2
，继续peek，重复直到所有元素全部入queue或者stack。
那如果首先1和3都被分别加入queue和stack，那现在剩下【2，2】，记录的最小值1，
最大值3，这个时候peek就会stuck，因为2和2不知道是因为peek同一个元素还是有两个
相同的元素，这种情况下要特殊处理，不着急进queue或者stack，pop出来以后保存到
一个local变量，再找下一个，如果peek出来的比2小，那说明2是被重复peek而且是在
大的一端，push到stack里面，如果peak出来的比2大，push到queue里面，然后周而复
始。有可能第二个2被放到queue里面最后在array里面反而在第一个2的前面。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
f*e
16 楼
想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
s*x
17 楼
我只会C++,也有好多code 看不懂，不过还是有收获的。

++

【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
avatar
e*3
18 楼
假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
，这种edge case别人要看你有没有想到。

【在 f*****e 的大作中提到】
: 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
: 对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
avatar
t*2
19 楼
可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
次peek都是int_max为止
avatar
f*e
20 楼
有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。

【在 e********3 的大作中提到】
: 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
: ，这种edge case别人要看你有没有想到。
avatar
e*3
21 楼
+1

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
f*e
22 楼
作为电面确实太难了。

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
e*3
23 楼
目测应该是正常on site的题目的难度。

【在 f*****e 的大作中提到】
: 作为电面确实太难了。
avatar
e*3
24 楼
说句实话，看多少书没有看透只是看看答案对你一点帮助都没有，其实这道题在CC150
和leetcode上真心不算难的，顶了天中等难度的题目，你看了150道题目的答案，不如
自己完全不查书写10道中等难度，不同范畴的题目的实际解决答案出来（能编译运行并
且输出正确的答案）。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
b*a
25 楼

Co ask, why the organization of this book is bad? The organization right now
is based on patterns of solving problems which seems reasonable.
Thanks for your answer.

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
g*7
26 楼
你说的这个原始解法,如果里面全是重复元素有办法处理吗

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
e*3
27 楼
和第二种解法的处理方法类似，如果两次peek都是同一个值，先取出来存为temp
variable。

【在 g*******7 的大作中提到】
: 你说的这个原始解法,如果里面全是重复元素有办法处理吗
:
: collection
avatar
g*y
28 楼
其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
y*n
29 楼
只做过leetcode和 cc150, 这个还不够吗？小伙伴惊呆了。
avatar
e*3
30 楼
对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
h*d
31 楼
尾部push NULL(INT_MAX,INT_MIN)之类的，如果peek是尾部就继续peek，不是尾部就
pop()，这样就能保证每次是从头部pop。
之后把尾部的NULL pop了，把头元素push到尾部，然后把NULL重新push到尾部继续。
这样可以么？

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*i
32 楼
我觉得光靠看面试书刷题想进google只能是撞大运，google也不傻，他们是想找聪明人
，如果是个人靠刷题就能进，google也就快完了

++

【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
avatar
d*e
33 楼
但quack没有size()函数，所以不知道要分配多大的array.
我觉得stack是需要的。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
q*c
34 楼
任何container都应该有size(), 这不是问题。

【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
avatar
d*e
35 楼
但给出来的就是只有三个，没有size。
或者好吧，follow up,没有size()，怎么做。

【在 q********c 的大作中提到】
: 任何container都应该有size(), 这不是问题。
avatar
h*d
36 楼
先搞到一个vector然后转到array？反正还是O(n)

【在 d**e 的大作中提到】
: 但给出来的就是只有三个，没有size。
: 或者好吧，follow up,没有size()，怎么做。
avatar
l*3
37 楼
说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
知道size。
如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
，这样还不如全pop（）出来，在排序，只要O（nlogn）
面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
queue或者stack就行了。
对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
另外如何能更好的应对这种题目尼？谢谢

【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
avatar
e*3
38 楼
答案全在这个thread里面了。。。

N2)

【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
avatar
y*n
39 楼
唉，这个烙印肯定在他们的 Hindu 论坛上发，今天我有砍了一个老中， 这个礼拜已经
第十个了。
avatar
w*i
40 楼
1
我觉得总共元素个数应该是已知的，不然输出的数组长度都确定不了。所以这里弄个计
数器记录pop出的数目就可以了。
另外一个edge case是里面元素全为int_max，这个时候得把一开始就有的int_max都输
出到数组尾部。

100

【在 t********2 的大作中提到】
: 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
: 次peek都是int_max为止
avatar
w*i
41 楼
当有重复元素的时候不可行。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
s*i
42 楼
没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
后把链表拷贝到数组。
有重复元素就全部插后面然后保存重复部分的头和尾。
不知道是不是大脑短路了，大家看看有啥问题么？
avatar
l*3
43 楼
好方法！
我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
据结构，想想别的数据结构，所以我就没再往下想。

pop

【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
avatar
w*i
44 楼
想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
的事。
面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
非是你自己定义的双向链表。

【在 l********3 的大作中提到】
: 好方法！
: 我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
: 据结构，想想别的数据结构，所以我就没再往下想。
:
: pop
avatar
h*l
45 楼
祝大牛onsite顺利。
avatar
P*A
46 楼
两个容器分别从两头开始存，最后merge到一起
vector copy(Quack& q) {
vector v1, v2;
int a,b,c;
while (!q.empty()) {
a = q.peek();
q.pop();
c = 1;
while (!q.empty()) {
b = q.peek();
if (b == a) {
++c;
q.pop();
}
else
break;
}
if (q.empty()) {
v1.insert(v1.end(), c, a);
break;
}
if (av1.insert(v1.end(), c, a);
}
else {
v2.insert(v2.end(), c, a);
}
}
while (!v2.empty()) {
v1.push_back(v2.back());
v2.pop_back();
}
return v1;
}

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*0
47 楼
mark

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
c*0
48 楼
我倒觉得是用linkedlist开销太大。。。

【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
avatar
z*e
49 楼
是排好序的话，直接找一个自定义的结构堵住尾
比如里面都是integer，那我就用一个string
然后peek，只要是string，就重新peek
如果不是，则是head，pop出来，拷贝到array里面去
这样就可以绕开各种比较的陷阱
java里面有instanceof关键字，所以……

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
z*e
50 楼
如果他的类用了generic的话
你自己extends出一个自定义类
一样用instanceof判断
avatar
g*y
51 楼
两指针一个指array头一个指尾，
Peek
Pop
Peek
如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
后移。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
g*y
52 楼
你这个时间复杂度O(n^2)，别人O(n)

pop

【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
avatar
g*4
53 楼
这个也是O(n)

【在 g*****y 的大作中提到】
: 你这个时间复杂度O(n^2)，别人O(n)
:
: pop
avatar
b*f
54 楼
Mark
avatar
G*n
55 楼
我觉得难度中上吧，不过比我面试的难多了。首先，class 实现的话就是 一个random
判断 头还是尾。
第二， 1 如果 数组只剩一位的话，直接拷贝进去
2. 如果是第一次操作的话，先pop 一个出来
3. 如果lastPop < currentPop的话， 那么 lastPop 一定是在array remaining 部分
的head
如果 lastPop > current Pop 的话， 那么 lastPop 一定是在 array Remaining
的 tail
Put lastPop， update head and tail of that array, lastPop = currentPop;
第三，如果用重复的话，就会麻烦点，有点像 leetcode 上面 search in rotated
array II 。 我觉得可以考虑用 buffer hold 住 重复的数知道不重复，这样一次放入
buffer 进数组
主要还是 分类思考，一步步地想。就跟leetcode的oj一样，第一步测试空数组， 第二
步长度=1 的数组 第三步长度 = 2 的数组。。这样一步步考虑
avatar
s*i
56 楼
你这个方法原理上跟我的是一样的。
不同的是你这个方法需要事先知道数组大小。
而且你这个里面也用不着peek，第一个peek没用，第二次的peek换成pop是一样的。

【在 g*****y 的大作中提到】
: 两指针一个指array头一个指尾，
: Peek
: Pop
: Peek
: 如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
: 后移。
avatar
l*3
57 楼
刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
cc150
闲话不说，上面经：
前两天面的。三哥面试官
面试开始，直接上题。给了一个Quack的类，里面有三个方法：
pop(): 随机从头或者尾扔出一个元素；
peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
个元素；
push()：向尾部插入一个元素
问题是：给一个排序好的Quack,怎么把里面的元素原封不动的放到一个Array里面。
follow-up：如果quack里面有重复的元素，怎么处理
拿到题之后，完全没思路，基本是在面试官的指导下才做出来的。而且follow-up的题
目也没想到该怎么做。最后只写了没有重复元素的代码。
希望对大家有用，祝大家能拿到称心的offer。
avatar
s*x
58 楼
感觉 EPI (elements programing interview) 还是值得一读，
题目量很大， 光看给答案的就行了， 有些题很难， 略过。
这本书编排可真差， 内容还不错，有几道经典题。
avatar
q*c
59 楼
peek()告诉你是头还是尾吗，还是只返回那个元素？
avatar
l*3
60 楼
只返回元素。
只是peek了之后，再pop的话就一定是之前peek的元素

【在 q********c 的大作中提到】
: peek()告诉你是头还是尾吗，还是只返回那个元素？
avatar
l*3
61 楼
谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
写的，我只会java，看起来感觉有点吃力。
请问还有别的建议吗？

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
f*e
62 楼
是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*3
63 楼
如果quack里面的元素是unique的话, 是不是可以一直pop. pop出来的元素都先依次放
在输出数组的前面, 如果发现比前一个元素小的话, 说明前一个元素是尾元素, 把这个
尾元素挪数组尾就行了.
avatar
l*3
64 楼
从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
比如说1,2,3,4,5
peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
不知道我是不是看懂你的思路了

【在 f*****e 的大作中提到】
: 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
avatar
l*d
65 楼
可不可以先 pop, 然后 peek， 然后比大小决定往前放还是往后放？数组维护两个
index：begin and end
public int[] solve() {
int[] result = new int[list.size()];
int beg = 0, end = result.length-1;
int last = list.pop();
while (!list.isEmpty()) {
int next = list.peek();
if (last > next) result[end--] = last;
else result[beg++] = last;
last = list.pop();
}
result[beg] = last;
return result;
}
avatar
f*e
66 楼
那你不停pop到一个数组，然后排序不就行了？

【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
avatar
f*e
67 楼
什么时间复杂度？

【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
avatar
q*c
68 楼
稍微想了一下，每 个iteration pop两次，再比较就可以了。
avatar
e*3
69 楼
这个我感觉挺简单的呀：
1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
里面所有元素的上限和下限。
2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
array index保持当前在array中的位置。
3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
排序。
上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
空间复杂度是O(n).
更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
果是最大的元素，push到stack里面，所有Quack里面的元素取出来以后，合并queue和
stack，queue是已经从小到大排好序的，直接放进array，stack最上面的是最小的，所
以也是pop出来直接放到array。
queue里面最大的元素小于stack里面最小的元素，所以需要先把queue里面的元素放到
array里面，然后再把stack里面的元素放到array里面，这个程序的实现很简单，基本
的数据结构操作，我就不具体写了。
这个唯一的不好就是排序不是stable的，重复的元素可能在array里面和在quack里面的
排序不一样。
这个的时间复杂度是O(n),空间复杂度是O(2*n),因为需要额外的保存stack和queue，如
果具体实现是用单链表的话，那空间复杂度是O(n),因为需要保存的元素上限恒定为O(n
).
我举个例子，假设初始数据是[1,2,2,3],那首先peek找到1最小，3最大，然后peek开始
，假设第一次peak是1，那把1加入queue，当前的最小值还是记录为1，然后继续peek，
如果结果是3的话那放到stack里面，如果是2的话放到queue里面，同时更新最小值为2
，继续peek，重复直到所有元素全部入queue或者stack。
那如果首先1和3都被分别加入queue和stack，那现在剩下【2，2】，记录的最小值1，
最大值3，这个时候peek就会stuck，因为2和2不知道是因为peek同一个元素还是有两个
相同的元素，这种情况下要特殊处理，不着急进queue或者stack，pop出来以后保存到
一个local变量，再找下一个，如果peek出来的比2小，那说明2是被重复peek而且是在
大的一端，push到stack里面，如果peak出来的比2大，push到queue里面，然后周而复
始。有可能第二个2被放到queue里面最后在array里面反而在第一个2的前面。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
f*e
70 楼
想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
s*x
71 楼
我只会C++,也有好多code 看不懂，不过还是有收获的。

++

【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
avatar
e*3
72 楼
假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
，这种edge case别人要看你有没有想到。

【在 f*****e 的大作中提到】
: 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
: 对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
avatar
t*2
73 楼
可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
次peek都是int_max为止
avatar
f*e
74 楼
有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。

【在 e********3 的大作中提到】
: 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
: ，这种edge case别人要看你有没有想到。
avatar
e*3
75 楼
+1

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
f*e
76 楼
作为电面确实太难了。

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
e*3
77 楼
目测应该是正常on site的题目的难度。

【在 f*****e 的大作中提到】
: 作为电面确实太难了。
avatar
e*3
78 楼
说句实话，看多少书没有看透只是看看答案对你一点帮助都没有，其实这道题在CC150
和leetcode上真心不算难的，顶了天中等难度的题目，你看了150道题目的答案，不如
自己完全不查书写10道中等难度，不同范畴的题目的实际解决答案出来（能编译运行并
且输出正确的答案）。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
b*a
79 楼

Co ask, why the organization of this book is bad? The organization right now
is based on patterns of solving problems which seems reasonable.
Thanks for your answer.

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
g*7
80 楼
你说的这个原始解法,如果里面全是重复元素有办法处理吗

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
e*3
81 楼
和第二种解法的处理方法类似，如果两次peek都是同一个值，先取出来存为temp
variable。

【在 g*******7 的大作中提到】
: 你说的这个原始解法,如果里面全是重复元素有办法处理吗
:
: collection
avatar
g*y
82 楼
其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
y*n
83 楼
只做过leetcode和 cc150, 这个还不够吗？小伙伴惊呆了。
avatar
e*3
84 楼
对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
h*d
85 楼
尾部push NULL(INT_MAX,INT_MIN)之类的，如果peek是尾部就继续peek，不是尾部就
pop()，这样就能保证每次是从头部pop。
之后把尾部的NULL pop了，把头元素push到尾部，然后把NULL重新push到尾部继续。
这样可以么？

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*i
86 楼
我觉得光靠看面试书刷题想进google只能是撞大运，google也不傻，他们是想找聪明人
，如果是个人靠刷题就能进，google也就快完了

++

【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
avatar
d*e
87 楼
但quack没有size()函数，所以不知道要分配多大的array.
我觉得stack是需要的。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
q*c
88 楼
任何container都应该有size(), 这不是问题。

【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
avatar
d*e
89 楼
但给出来的就是只有三个，没有size。
或者好吧，follow up,没有size()，怎么做。

【在 q********c 的大作中提到】
: 任何container都应该有size(), 这不是问题。
avatar
h*d
90 楼
先搞到一个vector然后转到array？反正还是O(n)

【在 d**e 的大作中提到】
: 但给出来的就是只有三个，没有size。
: 或者好吧，follow up,没有size()，怎么做。
avatar
l*3
91 楼
说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
知道size。
如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
，这样还不如全pop（）出来，在排序，只要O（nlogn）
面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
queue或者stack就行了。
对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
另外如何能更好的应对这种题目尼？谢谢

【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
avatar
e*3
92 楼
答案全在这个thread里面了。。。

N2)

【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
avatar
y*n
93 楼
唉，这个烙印肯定在他们的 Hindu 论坛上发，今天我有砍了一个老中， 这个礼拜已经
第十个了。
avatar
w*i
94 楼
1
我觉得总共元素个数应该是已知的，不然输出的数组长度都确定不了。所以这里弄个计
数器记录pop出的数目就可以了。
另外一个edge case是里面元素全为int_max，这个时候得把一开始就有的int_max都输
出到数组尾部。

100

【在 t********2 的大作中提到】
: 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
: 次peek都是int_max为止
avatar
w*i
95 楼
当有重复元素的时候不可行。

的。

【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
avatar
s*i
96 楼
没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
后把链表拷贝到数组。
有重复元素就全部插后面然后保存重复部分的头和尾。
不知道是不是大脑短路了，大家看看有啥问题么？
avatar
l*3
97 楼
好方法！
我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
据结构，想想别的数据结构，所以我就没再往下想。

pop

【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
avatar
w*i
98 楼
想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
的事。
面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
非是你自己定义的双向链表。

【在 l********3 的大作中提到】
: 好方法！
: 我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
: 据结构，想想别的数据结构，所以我就没再往下想。
:
: pop
avatar
h*l
99 楼
祝大牛onsite顺利。
avatar
P*A
100 楼
两个容器分别从两头开始存，最后merge到一起
vector copy(Quack& q) {
vector v1, v2;
int a,b,c;
while (!q.empty()) {
a = q.peek();
q.pop();
c = 1;
while (!q.empty()) {
b = q.peek();
if (b == a) {
++c;
q.pop();
}
else
break;
}
if (q.empty()) {
v1.insert(v1.end(), c, a);
break;
}
if (av1.insert(v1.end(), c, a);
}
else {
v2.insert(v2.end(), c, a);
}
}
while (!v2.empty()) {
v1.push_back(v2.back());
v2.pop_back();
}
return v1;
}

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
l*0
101 楼
mark

【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
avatar
c*0
102 楼
我倒觉得是用linkedlist开销太大。。。

【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
avatar
z*e
103 楼
是排好序的话，直接找一个自定义的结构堵住尾
比如里面都是integer，那我就用一个string
然后peek，只要是string，就重新peek
如果不是，则是head，pop出来，拷贝到array里面去
这样就可以绕开各种比较的陷阱
java里面有instanceof关键字，所以……

collection

【在 e********3 的大作中提到】
: 这个我感觉挺简单的呀：
: 1.Peek多次，直到找到两个不同的元素，因为是排序好的，这样你知道整个collection
: 里面所有元素的上限和下限。
: 2.然后开始peek,只要不是最大的元素，一律pop出来按照顺序放到array里面，用一个
: array index保持当前在array中的位置。
: 3.重复元素一样按照在原来Quack中的顺序放到array里面，这样你的算法就是stable的
: 排序。
: 上面是原始的解法。这个时间的复杂度是O(n*m),m是平均需要多少次找到最小的元素，
: 空间复杂度是O(n).
: 更加高效的是新建一个stack和一个queue，如果是最小的元素，push到queue里面，如
avatar
z*e
104 楼
如果他的类用了generic的话
你自己extends出一个自定义类
一样用instanceof判断
avatar
g*y
105 楼
两指针一个指array头一个指尾，
Peek
Pop
Peek
如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
后移。

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
g*y
106 楼
你这个时间复杂度O(n^2)，别人O(n)

pop

【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
avatar
g*4
107 楼
这个也是O(n)

【在 g*****y 的大作中提到】
: 你这个时间复杂度O(n^2)，别人O(n)
:
: pop
avatar
b*f
108 楼
Mark
avatar
G*n
109 楼
我觉得难度中上吧，不过比我面试的难多了。首先，class 实现的话就是 一个random
判断 头还是尾。
第二， 1 如果 数组只剩一位的话，直接拷贝进去
2. 如果是第一次操作的话，先pop 一个出来
3. 如果lastPop < currentPop的话， 那么 lastPop 一定是在array remaining 部分
的head
如果 lastPop > current Pop 的话， 那么 lastPop 一定是在 array Remaining
的 tail
Put lastPop， update head and tail of that array, lastPop = currentPop;
第三，如果用重复的话，就会麻烦点，有点像 leetcode 上面 search in rotated
array II 。 我觉得可以考虑用 buffer hold 住 重复的数知道不重复，这样一次放入
buffer 进数组
主要还是 分类思考，一步步地想。就跟leetcode的oj一样，第一步测试空数组， 第二
步长度=1 的数组 第三步长度 = 2 的数组。。这样一步步考虑
avatar
s*i
110 楼
你这个方法原理上跟我的是一样的。
不同的是你这个方法需要事先知道数组大小。
而且你这个里面也用不着peek，第一个peek没用，第二次的peek换成pop是一样的。

【在 g*****y 的大作中提到】
: 两指针一个指array头一个指尾，
: Peek
: Pop
: Peek
: 如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
: 后移。
avatar
b*r
111 楼
to deal with dup numbers, can we add a count to each number in the queue,
stack? every time when peek is called, check the value against the queue end
and/or stack top, then if dup just increase the number count by 1.

N2)

【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
avatar
s*j
112 楼
+1

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
t*n
113 楼
def copyQuack(q):
result =[]
last =0
while q.peek():
x = q.pop()
result.insert(last, x)
y = q.peek()
if y > x:
last +=1
return result
重复的我再想想

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
t*n
114 楼
如果有重复的，不直接插入元素，而是
while x > result[last]:
last +=1
while x < result[last]:
last -=1
然后再插入就可以了。
不占额外空间，时间复杂度n^2
avatar
y*a
115 楼
可以用 ListIterator

【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
avatar
y*a
116 楼
public List quack(Queue q) {
DoublyListNode head=new DoublyListNode(Integer.MIN_VALUE);
DoublyListNode tail=new DoublyListNode(Integer.MAX_VALUE);
DoublyListNode first=head;
DoublyListNode last=tail;
while (!q.isEmpty()) {
int v=q.poll();
DoublyListNode node=new DoublyListNode(v);
if (first.val>v) {
head.after=node;
node.after=first;
node.before=head;
first.before=node;
first=node;
} else if (last.valnode.before=last;
node.after=tail;
last.after=node;
tail.before=node;
last=node;
} else {
if (first.val<=v&&first.after.val>=v) {
node.before=first;
node.after=first.after;
first.after.before=node;
first.after=node;
} else {
node.after=last;
node.before=last.before;
last.before.after=node;
last.before=node;
}
}
}
List rel=new ArrayList<>();
DoublyListNode node=head.after;
while (node!=tail) rel.add(node.val);
return rel;
}
avatar
a*y
117 楼
假设Quack的顺序是递增
我的思路是，想办法找到最大的元素（尾），然后push进一个标志（如MIN_INT）;下次
peek的时候，只pop非MIN_INT的元素，直到再次遇到最大的那个元素，此时可以pop标
志，直至空
void PopQuackToArray(Quack& quack, vector& array) {
vector tmp;
int last = quack.pop();
tmp.push_back(last);
int curr;
while (!quack.empty()) {
curr = quack.pop();
if (curr != last) {
break;
}
tmp.push_back(last);
}
if (quack.empty()) {
if (curr < last) {
array.push_back(curr);
for (int i = 0; i < tmp.size(); ++i) {
array.push_back(tmp[i]);
}
} else {
array = tmp;
if (curr > last) {
array.push_back(curr);
}
}
return;
}
int mark = MIN_INT;
int max;
if (curr < last) {
array.push_back(curr);
quack.push(last);
quack.push(mark);
max = last;
tmp.pop_back();
} else {
array = tmp;
tmp.clear();
quack.push(curr);
quack.push(mark);
max = curr;
}
bool could_pop_mark = false;
while (!quack.empty()) {
curr = quack.peek();
if (curr == mark) {
if (could_pop_mark) {
quack.pop();
}
continue;
}
if (curr == max) {
could_pop_mark = true;
}
array.push_back(curr);
quack.pop();
}
// merge:
for (int i = 0; i < tmp.size(); ++i) {
array.push_back(tmp[i]);
}
}
注： 如果头元素恰好是MIN_INT，那么本方法失败（还没想好如何改。）
avatar
b*r
118 楼
to deal with dup numbers, can we add a count to each number in the queue,
stack? every time when peek is called, check the value against the queue end
and/or stack top, then if dup just increase the number count by 1.

N2)

【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
avatar
s*j
119 楼
+1

【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
avatar
t*n
120 楼
def copyQuack(q):
result =[]
last =0
while q.peek():
x = q.pop()
result.insert(last, x)
y = q.peek()
if y > x:
last +=1
return result
重复的我再想想

【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
avatar
t*n
121 楼
如果有重复的，不直接插入元素，而是
while x > result[last]:
last +=1
while x < result[last]:
last -=1
然后再插入就可以了。
不占额外空间，时间复杂度n^2
avatar
y*a
122 楼
可以用 ListIterator

【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
avatar
y*a
123 楼
public List quack(Queue q) {
DoublyListNode head=new DoublyListNode(Integer.MIN_VALUE);
DoublyListNode tail=new DoublyListNode(Integer.MAX_VALUE);
DoublyListNode first=head;
DoublyListNode last=tail;
while (!q.isEmpty()) {
int v=q.poll();
DoublyListNode node=new DoublyListNode(v);
if (first.val>v) {
head.after=node;
node.after=first;
node.before=head;
first.before=node;
first=node;
} else if (last.valnode.before=last;
node.after=tail;
last.after=node;
tail.before=node;
last=node;
} else {
if (first.val<=v&&first.after.val>=v) {
node.before=first;
node.after=first.after;
first.after.before=node;
first.after=node;
} else {
node.after=last;
node.before=last.before;
last.before.after=node;
last.before=node;
}
}
}
List rel=new ArrayList<>();
DoublyListNode node=head.after;
while (node!=tail) rel.add(node.val);
return rel;
}
avatar
a*y
124 楼
假设Quack的顺序是递增
我的思路是，想办法找到最大的元素（尾），然后push进一个标志（如MIN_INT）;下次
peek的时候，只pop非MIN_INT的元素，直到再次遇到最大的那个元素，此时可以pop标
志，直至空
void PopQuackToArray(Quack& quack, vector& array) {
vector tmp;
int last = quack.pop();
tmp.push_back(last);
int curr;
while (!quack.empty()) {
curr = quack.pop();
if (curr != last) {
break;
}
tmp.push_back(last);
}
if (quack.empty()) {
if (curr < last) {
array.push_back(curr);
for (int i = 0; i < tmp.size(); ++i) {
array.push_back(tmp[i]);
}
} else {
array = tmp;
if (curr > last) {
array.push_back(curr);
}
}
return;
}
int mark = MIN_INT;
int max;
if (curr < last) {
array.push_back(curr);
quack.push(last);
quack.push(mark);
max = last;
tmp.pop_back();
} else {
array = tmp;
tmp.clear();
quack.push(curr);
quack.push(mark);
max = curr;
}
bool could_pop_mark = false;
while (!quack.empty()) {
curr = quack.peek();
if (curr == mark) {
if (could_pop_mark) {
quack.pop();
}
continue;
}
if (curr == max) {
could_pop_mark = true;
}
array.push_back(curr);
quack.pop();
}
// merge:
for (int i = 0; i < tmp.size(); ++i) {
array.push_back(tmp[i]);
}
}
注： 如果头元素恰好是MIN_INT，那么本方法失败（还没想好如何改。）
avatar
w*a
125 楼
这个靠谱。

end

【在 b********r 的大作中提到】
: to deal with dup numbers, can we add a count to each number in the queue,
: stack? every time when peek is called, check the value against the queue end
: and/or stack top, then if dup just increase the number count by 1.
:
: N2)
avatar
j*3
126 楼
mark
相关阅读
Renew EAD/AP timeline and Ref Update【EB3 2015年七月第8绿】PD March 2011有人PP 两个140的么？有人是XM1390处理的吗？H4-EAD超过(含)55天未批的请进【发完了谢谢】本月已经破150绿了，历史记录这是什么情况, So Strange【EB2 2015七月第153绿】NSC PD 2013年4月2号，RD2015年6月1号，【EB2 2015七月第150绿】TSC 2012.03 EB2h4 ead超过75天，也可以send service request了。2011年3月的原装EB2，今年还有可能绿吗？还是要等到明年啊？律师要绿卡的copy, 要给吗？【EB2 2015七月第139绿】TSC 11.6 请问 Welcome notice package里面有绿工作时间和visa时间对不上????????有了EAD后，可以干任何工吗？不解啊落在NSC0678的来聚会吧！感觉我要放弃了infopass 不能process绿卡7/25寄出来，到现在还没有收到
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。