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 这个,要是实在想不到,最后10分钟,写个hash_map计数的,可以过么?
【在 f********g 的大作中提到】 : 没错。要是之前没看过Boyer-Moore's algorithm的话,当场几分钟想出这个算法,我 : 只能说是天才了。
|
|
|
w*****1 发帖数: 6807 | 21 我感觉现在想进G必需要每轮都答好才行
一般国人的题其实还是好做一些,思路对的话肯定能做
像第一题哪种都是特别不好办的,细节太多,我面的时候也有类似这种题,答的不好,
也是挂 |
f********g 发帖数: 157 | 22 不知道。。。估计是过不了的,太简单了,人人都可以做出来。
【在 d******7 的大作中提到】 : 这个,要是实在想不到,最后10分钟,写个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%的就是答案。 |