w*********4
发帖数: 832 | 1 Google
电面：LC 340
Onsite：很诡异的onsite
1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
有可能组合。貌似不难，但是代码量很大，写的很屎。
2. 老中。先一个detect cycle in graph，秒过。接下来是一道怪题，有两个数组a, b
长度
一样，要求同时排序，排序之后要求b[i] = a[k] where a[k] > a[i] && k < i 这题
完全没思路。
3. 吃饭。
4. 不知哪国的黑哥们，都是巨简单的字符串操作，不说了。
5. 老中。一个排序数组，确定有且仅有一个元素的出现次数>= 25%，找到这个元素。
这题蒙了一会才明白能用2分法，时间紧张代码量大，好歹写完但是肯定有虫。
6. 老白，Validate Balanced BST，挺简单的。
最后是挂。 |
e**********0
发帖数: 502 | 2
多谢分享
【在 w*********4 的大作中提到】
: Google
: 电面：LC 340
: Onsite：很诡异的onsite
: 1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
: 有可能组合。貌似不难，但是代码量很大，写的很屎。
: 2. 老中。先一个detect cycle in graph，秒过。接下来是一道怪题，有两个数组a, b
: 长度
: 一样，要求同时排序，排序之后要求b[i] = a[k] where a[k] > a[i] && k < i 这题
: 完全没思路。
: 3. 吃饭。
|
s*a
发帖数: 267 | 3 第二题，我怎们感觉数组2就是数组一降序排序完后的index？ |
w*********4
发帖数: 832 | 4 Bloomberg Senior Dev
简历很难过，投了四五个位置连简历都过不了，最后唯一一个能到电面。
所有的都是在hackerrank上写代码
电面1：
写了几个SQL query，都比较简单。然后是给一个字符串判断有没有重复的，比较简单。
电面2：
一个很简单的SQL设计题，写几个query。
代码题1：给一个数组找出第一小和第二小的两个数。
代码题2：给两个数组a, b找出Max a[i] - b[j] 要求i != j。其实是第一题的增强，
想通了很容易。
Onsite：网上都是校招的面经，和senior的差别很大。也是在HackerRank上写代码。具
体题目没什么好说的，SQL + 简单OO编程，中午也不是吃lunch box而是外面下馆子。 |
w*********4
发帖数: 832 | 5
不一定是index，请看我回帖。
【在 s*a 的大作中提到】
: 第二题，我怎们感觉数组2就是数组一降序排序完后的index？
|
d******7
发帖数: 44 | 6 什么时候面的，是在Mountain View面的吗？是SWE吗？你是new graduate还是有工作经
验的啊。
第二题，个人理解是。数组一，排序。用数组二做Index再重新Re order数组一就可以
了好像。
qsort(array1.begin(), array1.end());
for (int i = 0; i < array2.size(); i++) {
out[i] = array1[array2[i]];
}
array1 = out;
另外网上不是说不提倡秒过吗？要么说见过，要么思考推理一下。
电面那题到是挺难的。 |
w*********4
发帖数: 832 | 7
数组2不能直接做index吧，可以全是0的。给你个例子：
数组1 3 5 1 6 4 2
数组2 0 0 0 0 0 0
这个结果是把数组1排成 1 2 3 4 5 6
【在 d******7 的大作中提到】
: 什么时候面的，是在Mountain View面的吗？是SWE吗？你是new graduate还是有工作经
: 验的啊。
: 第二题，个人理解是。数组一，排序。用数组二做Index再重新Re order数组一就可以
: 了好像。
: qsort(array1.begin(), array1.end());
: for (int i = 0; i < array2.size(); i++) {
: out[i] = array1[array2[i]];
: }
: array1 = out;
: 另外网上不是说不提倡秒过吗？要么说见过，要么思考推理一下。
|
s*a
发帖数: 267 | 8 我感觉他题叙述错了，“数组2代表这个人之前有多少人比他高”应该是“数组2代表比
他高的其他人的个数” |
d******7
发帖数: 44 | 9 你这个，我对题目理解有误，另外，最后那个
确定有且仅有一个元素的出现次数>= 25%
感觉就是majority-number-ii的变形啊，majority-number-ii是找出 次数 > 1/3的。
【在 w*********4 的大作中提到】
:
: 数组2不能直接做index吧，可以全是0的。给你个例子：
: 数组1 3 5 1 6 4 2
: 数组2 0 0 0 0 0 0
: 这个结果是把数组1排成 1 2 3 4 5 6
|
w*********4
发帖数: 832 | 10
不是，是“之前”。之前是关键词。我表述有问题。数组a和数组b要同时排序，排好之
后b[i] = count a[k] where k < i && a[k] > a[i]
【在 s*a 的大作中提到】
: 我感觉他题叙述错了，“数组2代表这个人之前有多少人比他高”应该是“数组2代表比
: 他高的其他人的个数”
|
|
|
w*********4
发帖数: 832 | 11
可能是吧，我一时没想到用2分法浪费了点时间。
【在 d******7 的大作中提到】
: 你这个，我对题目理解有误，另外，最后那个
: 确定有且仅有一个元素的出现次数>= 25%
: 感觉就是majority-number-ii的变形啊，majority-number-ii是找出 次数 > 1/3的。
|
f********g
发帖数: 157 | 12 第二和第五个都很难啊。看来要通过G的onsite，不仅要实力，还要运气。一旦遇到陌
生的问题，很容易卡住。稍微卡个几分钟，就完了。 |
s*a
发帖数: 267 | 13 老中的题为何这么难？黑三都放水，老中反而卡的这么死？
【在 f********g 的大作中提到】
: 第二和第五个都很难啊。看来要通过G的onsite，不仅要实力，还要运气。一旦遇到陌
: 生的问题，很容易卡住。稍微卡个几分钟，就完了。
|
s*a
发帖数: 267 | 14 二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。
【在 w*********4 的大作中提到】
:
: 可能是吧，我一时没想到用2分法浪费了点时间。
|
w*********4
发帖数: 832 | 15
你说的那个我还没看，我这个可以用二分法。这个数组是排序了的。
【在 s*a 的大作中提到】
: 二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。
|
w*********4
发帖数: 832 | 16
其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。
【在 s*a 的大作中提到】
: 老中的题为何这么难？黑三都放水，老中反而卡的这么死？
|
s*a
发帖数: 267 | 17 调戏有意义吗？不是纯粹找误解么。。。
【在 w*********4 的大作中提到】
:
: 其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
: 试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。
|
f********g
发帖数: 157 | 18 没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
只能说是天才了。
【在 s*a 的大作中提到】
: 二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。
|
s*a
发帖数: 267 | 19 所以他们这些面试也就是看看是否见过，很多算法如果没见过，当时想不出来的。
答不出来不代表水平差，只能代表自己的路子不够野。
【在 f********g 的大作中提到】
: 没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
: 只能说是天才了。
|
d******7
发帖数: 44 | 20 这个，要是实在想不到，最后１０分钟，写个hash_map计数的，可以过么？
【在 f********g 的大作中提到】
: 没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
: 只能说是天才了。
|
|
|
w*****1
发帖数: 6807 | 21 我感觉现在想进G必需要每轮都答好才行
一般国人的题其实还是好做一些，思路对的话肯定能做
像第一题哪种都是特别不好办的，细节太多，我面的时候也有类似这种题，答的不好，
也是挂 |
f********g
发帖数: 157 | 22 不知道。。。估计是过不了的，太简单了，人人都可以做出来。
【在 d******7 的大作中提到】
: 这个，要是实在想不到，最后１０分钟，写个hash_map计数的，可以过么？
|
s******9
发帖数: 4623 | 23 Google
电面：LC 340
hard 级别，还是lock的，没看过
Onsite：很诡异的onsite
1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
有可能组合。貌似不难，但是代码量很大，写的很屎。
变相的permutation，难度medium，想把代码写漂亮了不容易
2. 老中。先一个detect cycle in graph，秒过。
这是什么题？leetcode有类似的吗？
接下来是一道怪题，有两个数组a, b
长度
一样，要求同时排序，排序之后要求b[i] = a[k] where a[k] > a[i] && k < i 这题
完全没思路。
同时排序？这题没看明白
3. 吃饭。
4. 不知哪国的黑哥们，都是巨简单的字符串操作，不说了。
5. 老中。一个排序数组，确定有且仅有一个元素的出现次数>= 25%，找到这个元素。
这题蒙了一会才明白能用2分法，时间紧张代码量大，好歹写完但是肯定有虫。
6. 老白，Validate Balanced BST，挺简单的。
b
【在 w*********4 的大作中提到】
: Google
: 电面：LC 340
: Onsite：很诡异的onsite
: 1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
: 有可能组合。貌似不难，但是代码量很大，写的很屎。
: 2. 老中。先一个detect cycle in graph，秒过。接下来是一道怪题，有两个数组a, b
: 长度
: 一样，要求同时排序，排序之后要求b[i] = a[k] where a[k] > a[i] && k < i 这题
: 完全没思路。
: 3. 吃饭。
|
s******9
发帖数: 4623 | 24 这是什么心态啊？
显得自己智商高吗？
【在 w*********4 的大作中提到】
:
: 其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
: 试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。
|
G******n
发帖数: 572 | 25 赞，不过这道题你没有说清楚啊。排序到底是按照什么排序，如果按照大小排好之后，
这个乱序的count不应该都是零吗？能举个例子吗？
【在 w*********4 的大作中提到】
:
: 其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
: 试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。
|
B*******g
发帖数: 1593 | 26
这个就是字面意思吧，应该没什么陷阱
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
【在 s******9 的大作中提到】
: Google
: 电面：LC 340
: hard 级别，还是lock的，没看过
: Onsite：很诡异的onsite
: 1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
: 有可能组合。貌似不难，但是代码量很大，写的很屎。
: 变相的permutation，难度medium，想把代码写漂亮了不容易
: 2. 老中。先一个detect cycle in graph，秒过。
: 这是什么题？leetcode有类似的吗？
: 接下来是一道怪题，有两个数组a, b
|
p****9
发帖数: 1 | 27
排序了直接O(n)扫一遍数组就可以了。二分法是怎么个做法？
【在 w*********4 的大作中提到】
:
: 其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
: 试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。
|
c******3
发帖数: 6509 | 28 1. 只有两个可变域，用两层循环？
2. 貌似a降序，b升序
5. 虽然是排序数组，可能第一个就是次数大于25%的，你用二分？既然仅有1个，用线
性扫描就完事了。
b
【在 w*********4 的大作中提到】
: Google
: 电面：LC 340
: Onsite：很诡异的onsite
: 1. 印度。给一个xxx{xxx}xxx{xx}字符串，括号里面每次只能选一个字符，要求给出所
: 有可能组合。貌似不难，但是代码量很大，写的很屎。
: 2. 老中。先一个detect cycle in graph，秒过。接下来是一道怪题，有两个数组a, b
: 长度
: 一样，要求同时排序，排序之后要求b[i] = a[k] where a[k] > a[i] && k < i 这题
: 完全没思路。
: 3. 吃饭。
|
c******3
发帖数: 6509 | 29 比majority-number-ii简单，因为数组是排序过的，所有相同的数字必然连续，只要一
个简单的计数就行了
【在 d******7 的大作中提到】
: 你这个，我对题目理解有误，另外，最后那个
: 确定有且仅有一个元素的出现次数>= 25%
: 感觉就是majority-number-ii的变形啊，majority-number-ii是找出 次数 > 1/3的。
|
w*********4
发帖数: 832 | 30
你这个不够好，线性谁不会啊。。。两分法能到log N的，25%是关键词，你再好好想想
吧。
【在 c******3 的大作中提到】
: 比majority-number-ii简单，因为数组是排序过的，所有相同的数字必然连续，只要一
: 个简单的计数就行了
|
|
|
w*********4
发帖数: 832 | 31
线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
找，如果小于预期值就往左找。
【在 p****9 的大作中提到】
:
: 排序了直接O(n)扫一遍数组就可以了。二分法是怎么个做法？
|
l***p
发帖数: 358 | |
p**********i
发帖数: 276 | 33 先按1/8分点，找到一段覆盖某段1/8的数。分别往前和往后跳1/16，再跳1/32，....
【在 w*********4 的大作中提到】
:
: 线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
: ：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
: ，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
: 找，如果小于预期值就往左找。
|
E********e
发帖数: 63 | 34 支持啊支持，版上需要多一些象lz一样的人，
那道两个数组同时排序的题不会，要我就直接permutation ary a 然后rearrage ary b
accodingly |
l***x
发帖数: 21 | 35 有给定0-N这个范围吗？似乎要做一次O(n)的扫描拿到总数n，才能定位25%，50%和75%
，复杂度还是O(n)。另外一个做法是从25%，50%和75%这三点分别向两侧做logn搜索，
搜索复杂度3logn，但需要O(n)先拿到n。
【在 w*********4 的大作中提到】
:
: 线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
: ：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
: ，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
: 找，如果小于预期值就往左找。
|
a********8
发帖数: 1625 | 36 多谢楼主分享。
这道题看得不是太懂，能举个具体的例子吗？
比如输入是什么
要求得到什么
【在 w*********4 的大作中提到】
:
: 线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
: ：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
: ，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
: 找，如果小于预期值就往左找。
|
a****x
发帖数: 93 | 37 我觉得直接用数学 num of vertices < num of edges + 1 就表示有环吧
又想了下，必须是连通图才行
出所
【在 B*******g 的大作中提到】
:
: 这个就是字面意思吧，应该没什么陷阱
: http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
|
a****x
发帖数: 93 | 38 你又没说数组是连续的
我想到的就是先分8份，查每份边缘两个值，>=25%必然边缘值相同
如果找到多余1个，那么继续对边缘外边2分，>=25%必然至少占一个
如此分下去，直到结果唯一
【在 w*********4 的大作中提到】
:
: 线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
: ：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
: ，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
: 找，如果小于预期值就往左找。
|
k******a
发帖数: 44 | 39 第5题可以这样做吧？
把数组分为4段，那个5个端点为1，2，3，4，5.
先判断1-2，2-3，3-4，4-5是否头尾为同一数字，如果是那么就是答案
如果不是，那么答案为2，3，或者4的点。分别从2，3，4开始向左右进行二分查找，找
边界。找到边界后，总体长度大于25%的就是答案。 |
