l********3
发帖数: 33 | 1 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
cc150
闲话不说，上面经：
前两天面的。三哥面试官
面试开始，直接上题。给了一个Quack的类，里面有三个方法：
pop(): 随机从头或者尾扔出一个元素；
peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
个元素；
push()：向尾部插入一个元素
问题是：给一个排序好的Quack,怎么把里面的元素原封不动的放到一个Array里面。
follow-up：如果quack里面有重复的元素，怎么处理
拿到题之后，完全没思路，基本是在面试官的指导下才做出来的。而且follow-up的题
目也没想到该怎么做。最后只写了没有重复元素的代码。
希望对大家有用，祝大家能拿到称心的offer。 |
s**x
发帖数: 7506 | 2 感觉 EPI (elements programing interview) 还是值得一读，
题目量很大， 光看给答案的就行了， 有些题很难， 略过。
这本书编排可真差， 内容还不错，有几道经典题。 |
q********c
发帖数: 1774 | 3 peek()告诉你是头还是尾吗，还是只返回那个元素？ |
l********3
发帖数: 33 | 4 只返回元素。
只是peek了之后，再pop的话就一定是之前peek的元素
【在 q********c 的大作中提到】
: peek()告诉你是头还是尾吗，还是只返回那个元素？
|
l********3
发帖数: 33 | 5 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
写的，我只会java，看起来感觉有点吃力。
请问还有别的建议吗？
【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
f*****e
发帖数: 2992 | 6 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
l*****3
发帖数: 32 | 7 如果quack里面的元素是unique的话, 是不是可以一直pop. pop出来的元素都先依次放
在输出数组的前面, 如果发现比前一个元素小的话, 说明前一个元素是尾元素, 把这个
尾元素挪数组尾就行了. |
l********3
发帖数: 33 | 8 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
比如说1,2,3,4,5
peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
不知道我是不是看懂你的思路了
【在 f*****e 的大作中提到】
: 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
|
l*********d
发帖数: 78 | 9 可不可以先 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;
} |
f*****e
发帖数: 2992 | 10 那你不停pop到一个数组，然后排序不就行了？
【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
|
|
|
f*****e
发帖数: 2992 | 11 什么时间复杂度？
【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
|
q********c
发帖数: 1774 | 12 稍微想了一下，每 个iteration pop两次，再比较就可以了。 |
e********3
发帖数: 18578 | 13 这个我感觉挺简单的呀：
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()：向尾部插入一个元素
|
f*****e
发帖数: 2992 | 14 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
s**x
发帖数: 7506 | 15 我只会C++,也有好多code 看不懂，不过还是有收获的。
++
【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
|
e********3
发帖数: 18578 | 16 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
，这种edge case别人要看你有没有想到。
【在 f*****e 的大作中提到】
: 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
: 对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
|
t********2
发帖数: 28 | 17 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
次peek都是int_max为止 |
f*****e
发帖数: 2992 | 18 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。
【在 e********3 的大作中提到】
: 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
: ，这种edge case别人要看你有没有想到。
|
e********3
发帖数: 18578 | 19 +1
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
f*****e
发帖数: 2992 | 20 作为电面确实太难了。
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
|
|
e********3
发帖数: 18578 | 21 目测应该是正常on site的题目的难度。
【在 f*****e 的大作中提到】
: 作为电面确实太难了。
|
e********3
发帖数: 18578 | 22 说句实话，看多少书没有看透只是看看答案对你一点帮助都没有，其实这道题在CC150
和leetcode上真心不算难的，顶了天中等难度的题目，你看了150道题目的答案，不如
自己完全不查书写10道中等难度，不同范畴的题目的实际解决答案出来（能编译运行并
且输出正确的答案）。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
b*****a
发帖数: 70 | 23
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) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
g*******7
发帖数: 32 | 24 你说的这个原始解法,如果里面全是重复元素有办法处理吗
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里面，如
|
e********3
发帖数: 18578 | 25 和第二种解法的处理方法类似，如果两次peek都是同一个值，先取出来存为temp
variable。
【在 g*******7 的大作中提到】
: 你说的这个原始解法,如果里面全是重复元素有办法处理吗
:
: collection
|
g******y
发帖数: 143 | 26 其实可以不用多余的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里面，如
|
y***n
发帖数: 1594 | 27 只做过leetcode和 cc150, 这个还不够吗？小伙伴惊呆了。 |
e********3
发帖数: 18578 | 28 对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
h*d
发帖数: 19309 | 29 尾部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()：向尾部插入一个元素
|
l******i
发帖数: 880 | 30 我觉得光靠看面试书刷题想进google只能是撞大运，google也不傻，他们是想找聪明人
，如果是个人靠刷题就能进，google也就快完了
++
【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
|
|
|
d**e
发帖数: 6098 | 31 但quack没有size()函数，所以不知道要分配多大的array.
我觉得stack是需要的。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
q********c
发帖数: 1774 | 32 任何container都应该有size(), 这不是问题。
【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
|
d**e
发帖数: 6098 | 33 但给出来的就是只有三个，没有size。
或者好吧，follow up,没有size()，怎么做。
【在 q********c 的大作中提到】
: 任何container都应该有size(), 这不是问题。
|
h*d
发帖数: 19309 | 34 先搞到一个vector然后转到array？反正还是O(n)
【在 d**e 的大作中提到】
: 但给出来的就是只有三个，没有size。
: 或者好吧，follow up,没有size()，怎么做。
|
l********3
发帖数: 33 | 35 说的很对，当时我想用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是需要的。
:
: 的。
|
e********3
发帖数: 18578 | 36 答案全在这个thread里面了。。。
N2)
【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
|
y***n
发帖数: 1594 | 37 唉，这个烙印肯定在他们的 Hindu 论坛上发，今天我有砍了一个老中， 这个礼拜已经
第十个了。 |
w*******i
发帖数: 186 | 38 1
我觉得总共元素个数应该是已知的，不然输出的数组长度都确定不了。所以这里弄个计
数器记录pop出的数目就可以了。
另外一个edge case是里面元素全为int_max，这个时候得把一开始就有的int_max都输
出到数组尾部。
100
【在 t********2 的大作中提到】
: 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
: 次peek都是int_max为止
|
w*******i
发帖数: 186 | 39 当有重复元素的时候不可行。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
s********i
发帖数: 74 | 40 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
后把链表拷贝到数组。
有重复元素就全部插后面然后保存重复部分的头和尾。
不知道是不是大脑短路了，大家看看有啥问题么？ |
|
|
l********3
发帖数: 33 | 41 好方法！
我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
据结构，想想别的数据结构，所以我就没再往下想。
pop
【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
|
w*******i
发帖数: 186 | 42 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
的事。
面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
非是你自己定义的双向链表。
【在 l********3 的大作中提到】
: 好方法！
: 我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
: 据结构，想想别的数据结构，所以我就没再往下想。
:
: pop
|
h*******l
发帖数: 9 | |
P*A
发帖数: 189 | 44 两个容器分别从两头开始存，最后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 (a
v1.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()：向尾部插入一个元素
|
l********0
发帖数: 642 | 45 mark
【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
c******0
发帖数: 260 | 46 我倒觉得是用linkedlist开销太大。。。
【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
|
z****e
发帖数: 54598 | 47 是排好序的话，直接找一个自定义的结构堵住尾
比如里面都是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里面，如
|
z****e
发帖数: 54598 | 48 如果他的类用了generic的话
你自己extends出一个自定义类
一样用instanceof判断 |
g*****y
发帖数: 1120 | 49 两指针一个指array头一个指尾，
Peek
Pop
Peek
如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
后移。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
g*****y
发帖数: 1120 | 50 你这个时间复杂度O(n^2)，别人O(n)
pop
【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
|
|
|
g**4
发帖数: 863 | 51 这个也是O(n)
【在 g*****y 的大作中提到】
: 你这个时间复杂度O(n^2)，别人O(n)
:
: pop
|
b****f
发帖数: 138 | |
G*********n
发帖数: 53 | 53 我觉得难度中上吧，不过比我面试的难多了。首先，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 的数组。。这样一步步考虑 |
s********i
发帖数: 74 | 54 你这个方法原理上跟我的是一样的。
不同的是你这个方法需要事先知道数组大小。
而且你这个里面也用不着peek，第一个peek没用，第二次的peek换成pop是一样的。
【在 g*****y 的大作中提到】
: 两指针一个指array头一个指尾，
: Peek
: Pop
: Peek
: 如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
: 后移。
|
l********3
发帖数: 33 | 55 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
cc150
闲话不说，上面经：
前两天面的。三哥面试官
面试开始，直接上题。给了一个Quack的类，里面有三个方法：
pop(): 随机从头或者尾扔出一个元素；
peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
个元素；
push()：向尾部插入一个元素
问题是：给一个排序好的Quack,怎么把里面的元素原封不动的放到一个Array里面。
follow-up：如果quack里面有重复的元素，怎么处理
拿到题之后，完全没思路，基本是在面试官的指导下才做出来的。而且follow-up的题
目也没想到该怎么做。最后只写了没有重复元素的代码。
希望对大家有用，祝大家能拿到称心的offer。 |
s**x
发帖数: 7506 | 56 感觉 EPI (elements programing interview) 还是值得一读，
题目量很大， 光看给答案的就行了， 有些题很难， 略过。
这本书编排可真差， 内容还不错，有几道经典题。 |
q********c
发帖数: 1774 | 57 peek()告诉你是头还是尾吗，还是只返回那个元素？ |
l********3
发帖数: 33 | 58 只返回元素。
只是peek了之后，再pop的话就一定是之前peek的元素
【在 q********c 的大作中提到】
: peek()告诉你是头还是尾吗，还是只返回那个元素？
|
l********3
发帖数: 33 | 59 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
写的，我只会java，看起来感觉有点吃力。
请问还有别的建议吗？
【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
f*****e
发帖数: 2992 | 60 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
|
|
l*****3
发帖数: 32 | 61 如果quack里面的元素是unique的话, 是不是可以一直pop. pop出来的元素都先依次放
在输出数组的前面, 如果发现比前一个元素小的话, 说明前一个元素是尾元素, 把这个
尾元素挪数组尾就行了. |
l********3
发帖数: 33 | 62 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
比如说1,2,3,4,5
peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
不知道我是不是看懂你的思路了
【在 f*****e 的大作中提到】
: 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。
|
l*********d
发帖数: 78 | 63 可不可以先 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;
} |
f*****e
发帖数: 2992 | 64 那你不停pop到一个数组，然后排序不就行了？
【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
|
f*****e
发帖数: 2992 | 65 什么时间复杂度？
【在 l********3 的大作中提到】
: 从哪里复制没有规定，只要生成的array和quack里面的信息一样就行。
: 比如说1,2,3,4,5
: peek n 次得到的元素就是1,或者5. 可能一直都是5，怎么得到int_max尼
: 不知道我是不是看懂你的思路了
|
q********c
发帖数: 1774 | 66 稍微想了一下，每 个iteration pop两次，再比较就可以了。 |
e********3
发帖数: 18578 | 67 这个我感觉挺简单的呀：
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()：向尾部插入一个元素
|
f*****e
发帖数: 2992 | 68 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
s**x
发帖数: 7506 | 69 我只会C++,也有好多code 看不懂，不过还是有收获的。
++
【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
|
e********3
发帖数: 18578 | 70 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
，这种edge case别人要看你有没有想到。
【在 f*****e 的大作中提到】
: 想出来了，每pop一个，peek一次就行了。对于distinct elements而言。
: 对于有重复的继续pop，并记载次数，直到peek到不同元素或为空为止。
|
|
|
t********2
发帖数: 28 | 71 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
次peek都是int_max为止 |
f*****e
发帖数: 2992 | 72 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
1变为2。然后stack为空，populate array啦。很简单的。
其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
尾还是放到头。中间有个gap。
【在 e********3 的大作中提到】
: 假设最后两个元素是[2,2],那你peek永远都是同一个元素，这就形成infinite loop了
: ，这种edge case别人要看你有没有想到。
|
e********3
发帖数: 18578 | 73 +1
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
f*****e
发帖数: 2992 | 74 作为电面确实太难了。
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
e********3
发帖数: 18578 | 75 目测应该是正常on site的题目的难度。
【在 f*****e 的大作中提到】
: 作为电面确实太难了。
|
e********3
发帖数: 18578 | 76 说句实话，看多少书没有看透只是看看答案对你一点帮助都没有，其实这道题在CC150
和leetcode上真心不算难的，顶了天中等难度的题目，你看了150道题目的答案，不如
自己完全不查书写10道中等难度，不同范畴的题目的实际解决答案出来（能编译运行并
且输出正确的答案）。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
b*****a
发帖数: 70 | 77
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) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
g*******7
发帖数: 32 | 78 你说的这个原始解法,如果里面全是重复元素有办法处理吗
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里面，如
|
e********3
发帖数: 18578 | 79 和第二种解法的处理方法类似，如果两次peek都是同一个值，先取出来存为temp
variable。
【在 g*******7 的大作中提到】
: 你说的这个原始解法,如果里面全是重复元素有办法处理吗
:
: collection
|
g******y
发帖数: 143 | 80 其实可以不用多余的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里面，如
|
|
|
y***n
发帖数: 1594 | 81 只做过leetcode和 cc150, 这个还不够吗？小伙伴惊呆了。 |
e********3
发帖数: 18578 | 82 对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
h*d
发帖数: 19309 | 83 尾部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()：向尾部插入一个元素
|
l******i
发帖数: 880 | 84 我觉得光靠看面试书刷题想进google只能是撞大运，google也不傻，他们是想找聪明人
，如果是个人靠刷题就能进，google也就快完了
++
【在 l********3 的大作中提到】
: 谢谢，我也看到有其他几个版上的筒子推荐这本书。正打算读一下。 就是解法是用c++
: 写的，我只会java，看起来感觉有点吃力。
: 请问还有别的建议吗？
|
d**e
发帖数: 6098 | 85 但quack没有size()函数，所以不知道要分配多大的array.
我觉得stack是需要的。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
q********c
发帖数: 1774 | 86 任何container都应该有size(), 这不是问题。
【在 d**e 的大作中提到】
: 但quack没有size()函数，所以不知道要分配多大的array.
: 我觉得stack是需要的。
:
: 的。
|
d**e
发帖数: 6098 | 87 但给出来的就是只有三个，没有size。
或者好吧，follow up,没有size()，怎么做。
【在 q********c 的大作中提到】
: 任何container都应该有size(), 这不是问题。
|
h*d
发帖数: 19309 | 88 先搞到一个vector然后转到array？反正还是O(n)
【在 d**e 的大作中提到】
: 但给出来的就是只有三个，没有size。
: 或者好吧，follow up,没有size()，怎么做。
|
l********3
发帖数: 33 | 89 说的很对，当时我想用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是需要的。
:
: 的。
|
e********3
发帖数: 18578 | 90 答案全在这个thread里面了。。。
N2)
【在 l********3 的大作中提到】
: 说的很对，当时我想用arraylist，或者先定好数组的长度，面试官制止了我，说是不
: 知道size。
: 如果强行用arraylist的话，插入中间的复杂度可能是O(n)，这样的话总的复杂度O(N2)
: ，这样还不如全pop（）出来，在排序，只要O（nlogn）
: 面试官的方法是：用queue存小的数，stack存大的数，先pop()一个数，再peek一下，
: 比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入
: queue或者stack就行了。
: 对于有repeated number的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
|
|
|
y***n
发帖数: 1594 | 91 唉，这个烙印肯定在他们的 Hindu 论坛上发，今天我有砍了一个老中， 这个礼拜已经
第十个了。 |
w*******i
发帖数: 186 | 92 1
我觉得总共元素个数应该是已知的，不然输出的数组长度都确定不了。所以这里弄个计
数器记录pop出的数目就可以了。
另外一个edge case是里面元素全为int_max，这个时候得把一开始就有的int_max都输
出到数组尾部。
100
【在 t********2 的大作中提到】
: 可不可以就先push一个int_max 然后不断peek 只要不等于int_max就pop 直到连续100
: 次peek都是int_max为止
|
w*******i
发帖数: 186 | 93 当有重复元素的时候不可行。
的。
【在 g******y 的大作中提到】
: 其实可以不用多余的stack和queue。就用一个array，一头一尾分别两个index，如果是
: 最小元素，就把其放在头部指针的位置，头部index++；如果是最大元素，就放在尾部
: 指针的位置，尾部index--。这样，和你用stack和queue，然后再合并的效果是一样的。
:
: collection
|
s********i
发帖数: 74 | 94 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
后把链表拷贝到数组。
有重复元素就全部插后面然后保存重复部分的头和尾。
不知道是不是大脑短路了，大家看看有啥问题么？ |
l********3
发帖数: 33 | 95 好方法！
我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
据结构，想想别的数据结构，所以我就没再往下想。
pop
【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
|
w*******i
发帖数: 186 | 96 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
的事。
面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
非是你自己定义的双向链表。
【在 l********3 的大作中提到】
: 好方法！
: 我当时也提了linkedlist（猜的，并没有想清楚），面试官直接说：我们不要用那个数
: 据结构，想想别的数据结构，所以我就没再往下想。
:
: pop
|
h*******l
发帖数: 9 | |
P*A
发帖数: 189 | 98 两个容器分别从两头开始存，最后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 (a
v1.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()：向尾部插入一个元素
|
l********0
发帖数: 642 | 99 mark
【在 s**x 的大作中提到】
: 感觉 EPI (elements programing interview) 还是值得一读，
: 题目量很大， 光看给答案的就行了， 有些题很难， 略过。
: 这本书编排可真差， 内容还不错，有几道经典题。
|
c******0
发帖数: 260 | 100 我倒觉得是用linkedlist开销太大。。。
【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
|
|
|
z****e
发帖数: 54598 | 101 是排好序的话，直接找一个自定义的结构堵住尾
比如里面都是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里面，如
|
z****e
发帖数: 54598 | 102 如果他的类用了generic的话
你自己extends出一个自定义类
一样用instanceof判断 |
g*****y
发帖数: 1120 | 103 两指针一个指array头一个指尾，
Peek
Pop
Peek
如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
后移。
【在 l********3 的大作中提到】
: 刚经历了google的电面，深刻感到自己思路不够开阔，遇到没见过的题完全无从下手，
: 所以想请教版上的同学有什么书籍适合面试准备。 本人使用java，只做过leetcode和
: cc150
: 闲话不说，上面经：
: 前两天面的。三哥面试官
: 面试开始，直接上题。给了一个Quack的类，里面有三个方法：
: pop(): 随机从头或者尾扔出一个元素；
: peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那
: 个元素；
: push()：向尾部插入一个元素
|
g*****y
发帖数: 1120 | 104 你这个时间复杂度O(n^2)，别人O(n)
pop
【在 s********i 的大作中提到】
: 没想清楚为什么要用peak，直接就pop就行了。 先来个双向链表，然后记录上一次pop
: 的结果，如果当前pop的比之pop的大就插到之前那个后面，如果小就插到那个前面。最
: 后把链表拷贝到数组。
: 有重复元素就全部插后面然后保存重复部分的头和尾。
: 不知道是不是大脑短路了，大家看看有啥问题么？
|
g**4
发帖数: 863 | 105 这个也是O(n)
【在 g*****y 的大作中提到】
: 你这个时间复杂度O(n^2)，别人O(n)
:
: pop
|
b****f
发帖数: 138 | |
G*********n
发帖数: 53 | 107 我觉得难度中上吧，不过比我面试的难多了。首先，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 的数组。。这样一步步考虑 |
s********i
发帖数: 74 | 108 你这个方法原理上跟我的是一样的。
不同的是你这个方法需要事先知道数组大小。
而且你这个里面也用不着peek，第一个peek没用，第二次的peek换成pop是一样的。
【在 g*****y 的大作中提到】
: 两指针一个指array头一个指尾，
: Peek
: Pop
: Peek
: 如果pop出来的数比第二次peek的大，放数组尾，尾指针前移，否则放数组头，头指针
: 后移。
|
b********r
发帖数: 620 | 109 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的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
|
s****j
发帖数: 5 | 110 +1
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
|
|
t********n
发帖数: 611 | 111 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()：向尾部插入一个元素
|
t********n
发帖数: 611 | 112 如果有重复的，不直接插入元素，而是
while x > result[last]:
last +=1
while x < result[last]:
last -=1
然后再插入就可以了。
不占额外空间，时间复杂度n^2 |
y**********a
发帖数: 824 | 113 可以用 ListIterator
【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
|
y**********a
发帖数: 824 | 114 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.val
node.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;
} |
a*****y
发帖数: 22 | 115 假设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，那么本方法失败（还没想好如何改。） |
b********r
发帖数: 620 | 116 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的话，我实在是没想出来怎么弄。坐等大神吧。
: 另外如何能更好的应对这种题目尼？谢谢
|
s****j
发帖数: 5 | 117 +1
【在 f*****e 的大作中提到】
: 有重复元素继续pop啊。比如你pop个2出来了，就peek，发现一个2，继续pop，count由
: 1变为2。然后stack为空，populate array啦。很简单的。
: 其实这个有点recursive的意思，每次都面对同样的局面，每次决定pop出的元素是放到
: 尾还是放到头。中间有个gap。
|
t********n
发帖数: 611 | 118 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()：向尾部插入一个元素
|
t********n
发帖数: 611 | 119 如果有重复的，不直接插入元素，而是
while x > result[last]:
last +=1
while x < result[last]:
last -=1
然后再插入就可以了。
不占额外空间，时间复杂度n^2 |
y**********a
发帖数: 824 | 120 可以用 ListIterator
【在 w*******i 的大作中提到】
: 想法的确不错，因为双向链表本来就既可以用来做stack做的事，也可以用来做queue做
: 的事。
: 面试官当时否定你的想法是因为你用的java，类库里的linked list是无法支持给出一
: 个中间元素（即上次pop的元素），在这个元素的前面或者后面插入另一个元素的。除
: 非是你自己定义的双向链表。
|
|
|
y**********a
发帖数: 824 | 121 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.val
node.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;
} |
a*****y
发帖数: 22 | 122 假设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，那么本方法失败（还没想好如何改。） |
w****a
发帖数: 710 | 123 这个靠谱。
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)
|
j**********3
发帖数: 3211 | |
