50个包子求A&F的25%的店里能用的coupon - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

50个包子求A&F的25%的店里能用的coupon

50个包子求A&F的25%的店里能用的coupon# Fashion - 美丽时尚

w*42012-02-23 08:02

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，挺简单的。
最后是挂。

s*42012-02-23 08:02

2 楼

如题，有没有JMS有多余的code能转给我一个
站内联系谢谢

e*02012-02-23 08:02

3 楼

多谢分享

【在 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*a2012-02-23 08:02

4 楼

第二题，我怎们感觉数组2就是数组一降序排序完后的index？

w*42012-02-23 08:02

5 楼

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*42012-02-23 08:02

6 楼

不一定是index，请看我回帖。

【在 s*a 的大作中提到】

: 第二题，我怎们感觉数组2就是数组一降序排序完后的index？

d*72012-02-23 08:02

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;
另外网上不是说不提倡秒过吗？要么说见过，要么思考推理一下。
电面那题到是挺难的。

w*42012-02-23 08:02

8 楼

数组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*a2012-02-23 08:02

9 楼

我感觉他题叙述错了，“数组2代表这个人之前有多少人比他高”应该是“数组2代表比
他高的其他人的个数”

d*72012-02-23 08:02

10 楼

你这个，我对题目理解有误，另外，最后那个
确定有且仅有一个元素的出现次数>= 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*42012-02-23 08:02

11 楼

不是，是“之前”。之前是关键词。我表述有问题。数组a和数组b要同时排序，排好之
后b[i] = count a[k] where k < i && a[k] > a[i]

【在 s*a 的大作中提到】

: 我感觉他题叙述错了，“数组2代表这个人之前有多少人比他高”应该是“数组2代表比
: 他高的其他人的个数”

w*42012-02-23 08:02

12 楼

可能是吧，我一时没想到用2分法浪费了点时间。

【在 d******7 的大作中提到】

: 你这个，我对题目理解有误，另外，最后那个
: 确定有且仅有一个元素的出现次数>= 25%
: 感觉就是majority-number-ii的变形啊，majority-number-ii是找出次数　> 1/3的。

f*g2012-02-23 08:02

13 楼

第二和第五个都很难啊。看来要通过G的onsite，不仅要实力，还要运气。一旦遇到陌
生的问题，很容易卡住。稍微卡个几分钟，就完了。

s*a2012-02-23 08:02

14 楼

老中的题为何这么难？黑三都放水，老中反而卡的这么死？

【在 f********g 的大作中提到】

: 第二和第五个都很难啊。看来要通过G的onsite，不仅要实力，还要运气。一旦遇到陌
: 生的问题，很容易卡住。稍微卡个几分钟，就完了。

s*a2012-02-23 08:02

15 楼

二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。

【在 w*********4 的大作中提到】

:
: 可能是吧，我一时没想到用2分法浪费了点时间。

w*42012-02-23 08:02

16 楼

你说的那个我还没看，我这个可以用二分法。这个数组是排序了的。

【在 s*a 的大作中提到】

: 二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。

w*42012-02-23 08:02

17 楼

其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。

【在 s*a 的大作中提到】

: 老中的题为何这么难？黑三都放水，老中反而卡的这么死？

s*a2012-02-23 08:02

18 楼

调戏有意义吗？不是纯粹找误解么。。。

【在 w*********4 的大作中提到】

:
: 其实不一定，老中的题目虽然难但是不一定评价就差。当然我也只是猜测。我自己也面
: 试过别人，有时候看到小中喜欢调戏一下出个歪题，最后还是给推荐的。报应啊。。。

f*g2012-02-23 08:02

19 楼

没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
只能说是天才了。

【在 s*a 的大作中提到】

: 二分查找不行吧？majority-number-ii用的是Boyer-Moore, O(N)的算法。

s*a2012-02-23 08:02

20 楼

所以他们这些面试也就是看看是否见过，很多算法如果没见过，当时想不出来的。
答不出来不代表水平差，只能代表自己的路子不够野。

【在 f********g 的大作中提到】

: 没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
: 只能说是天才了。

d*72012-02-23 08:02

21 楼

这个，要是实在想不到，最后１０分钟，写个hash_map计数的，可以过么？

【在 f********g 的大作中提到】

: 没错。要是之前没看过Boyer-Moore's algorithm的话，当场几分钟想出这个算法，我
: 只能说是天才了。

w*12012-02-23 08:02

22 楼

我感觉现在想进G必需要每轮都答好才行
一般国人的题其实还是好做一些，思路对的话肯定能做
像第一题哪种都是特别不好办的，细节太多，我面的时候也有类似这种题，答的不好，
也是挂

f*g2012-02-23 08:02

23 楼

不知道。。。估计是过不了的，太简单了，人人都可以做出来。

【在 d******7 的大作中提到】

: 这个，要是实在想不到，最后１０分钟，写个hash_map计数的，可以过么？

s*92012-02-23 08:02

24 楼

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 的大作中提到】

s*92012-02-23 08:02

25 楼

这是什么心态啊？
显得自己智商高吗？

【在 w*********4 的大作中提到】

G*n2012-02-23 08:02

26 楼

赞，不过这道题你没有说清楚啊。排序到底是按照什么排序，如果按照大小排好之后，
这个乱序的count不应该都是零吗？能举个例子吗？

【在 w*********4 的大作中提到】

B*g2012-02-23 08:02

27 楼

这个就是字面意思吧，应该没什么陷阱
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*92012-02-23 08:02

28 楼

排序了直接O(n)扫一遍数组就可以了。二分法是怎么个做法？

【在 w*********4 的大作中提到】

c*32012-02-23 08:02

29 楼

1. 只有两个可变域，用两层循环？
2. 貌似a降序，b升序
5. 虽然是排序数组，可能第一个就是次数大于25%的，你用二分？既然仅有1个，用线
性扫描就完事了。

b

【在 w*********4 的大作中提到】

c*32012-02-23 08:02

30 楼

比majority-number-ii简单，因为数组是排序过的，所有相同的数字必然连续，只要一
个简单的计数就行了

【在 d******7 的大作中提到】

w*42012-02-23 08:02

31 楼

你这个不够好，线性谁不会啊。。。两分法能到log N的，25%是关键词，你再好好想想
吧。

【在 c******3 的大作中提到】

: 比majority-number-ii简单，因为数组是排序过的，所有相同的数字必然连续，只要一
: 个简单的计数就行了

w*42012-02-23 08:02

32 楼

线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
找，如果小于预期值就往左找。

【在 p****9 的大作中提到】

:
: 排序了直接O(n)扫一遍数组就可以了。二分法是怎么个做法？

l*p2012-02-23 08:02

33 楼

这两个老中太SB

p*i2012-02-23 08:02

34 楼

先按1/8分点，找到一段覆盖某段1/8的数。分别往前和往后跳1/16，再跳1/32，....

【在 w*********4 的大作中提到】

:
: 线性的我也会，写出来就被鄙视了。两分法能到logN时间复杂度。具体思路大概是这样
: ：占25%的元素必然会出现在下面几个位置中的一个: 25%, 50% 和 75%。对于每个位置
: ，比较实际值和预期值（0-N的话位置i的预期值就是i）；如果大于等于预期值就往右
: 找，如果小于预期值就往左找。

E*e2012-02-23 08:02

35 楼

支持啊支持，版上需要多一些象lz一样的人，
那道两个数组同时排序的题不会，要我就直接permutation ary a 然后rearrage ary b
accodingly

l*x2012-02-23 08:02

36 楼

有给定0-N这个范围吗？似乎要做一次O(n)的扫描拿到总数n，才能定位25%，50%和75%
，复杂度还是O(n)。另外一个做法是从25%，50%和75%这三点分别向两侧做logn搜索，
搜索复杂度3logn，但需要O(n)先拿到n。

【在 w*********4 的大作中提到】

a*82012-02-23 08:02

37 楼

多谢楼主分享。
这道题看得不是太懂，能举个具体的例子吗？
比如输入是什么
要求得到什么

【在 w*********4 的大作中提到】

a*x2012-02-23 08:02

38 楼

我觉得直接用数学 num of vertices < num of edges + 1 就表示有环吧
又想了下，必须是连通图才行

出所

【在 B*******g 的大作中提到】

:
: 这个就是字面意思吧，应该没什么陷阱
: http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

a*x2012-02-23 08:02

39 楼

你又没说数组是连续的
我想到的就是先分8份，查每份边缘两个值，>=25%必然边缘值相同
如果找到多余1个，那么继续对边缘外边2分，>=25%必然至少占一个
如此分下去，直到结果唯一

【在 w*********4 的大作中提到】

k*a2012-02-23 08:02

40 楼

第5题可以这样做吧？
把数组分为4段，那个5个端点为1，2，3，4，5.
先判断1-2，2-3，3-4，4-5是否头尾为同一数字，如果是那么就是答案
如果不是，那么答案为2，3，或者4的点。分别从2，3，4开始向左右进行二分查找，找
边界。找到边界后，总体长度大于25%的就是答案。