t****m
发帖数: 140 | 1 Fresh Grad, 两轮电面， onsite四轮
先说几条onsite的tips：
1.如果宾馆离面试地点比较远，一定要早点走，弯曲的交通不是盖的
2.面试的时候用水笔写错的code不要用手擦，即使用手擦也记得不要往脸上抹，今天我
就看面
试官一直对我的大花猫脸笑
3.中午不要吃太多
第一轮国人小哥，人很nice
（1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
而index 1 上 s1和s2都是b，则不是difference.现在只许你swap一次 S2
的两个字母，问如何才能
最大程度的减少difference， 需要return swap的两个index，比如上面的例子， 我们
swap s2的 0 和 2， 就会把s2变成 abc， 和 s1的 difference 是 0.
这题我用hashmap 做的，注意考虑difference最多只能减少1的情况
（2）小哥很nice的问我咱是来个简单的还是难的，我自信的花样作死说咱要来就来
难的，小哥说好。
桌子上有3n个object围成一个圈， 每个object都有一个value， 你和你的两个好朋友
每次各从桌子上拿一个，你先选，之后你的朋友再选，而且你的朋友只能拿你拿的那个
object的左右相邻的两个。问如何才能让你自己拿的objects的value的总和最大
？（注意不是总和比朋友大，而是在自己所有不同拿法中总和的值最大）
这题就卡住了，我只能勉强总结出自己拿的两个object不能相邻，但是不能证明
面完这轮后小哥很nice的跟我说做不出来没关系，这题没人做出来，接下来好好面就行
了，感谢啊！
第二轮白人小哥
new grad面system design也是醉了，问有个服务器，如果有用户短时间内向服务器发
送大量的request如何处理
这题只能闭着眼睛瞎说了，扯扯sampling，last request time，呵呵呵。。。
lunch
第三轮南美小哥
问如果找一棵树里面所有和为target的path，path可以从任何node开始，不一定要从
root开始
follow up，如果不是和为target，而是乘积为target呢？
follow up， 如果树很大，如何distributed 处理？
第四轮白人大叔
（1）有一个数列，数列中的数range在0-100之间，而且每个数最多只出现一次
如何找出这个数列中的missing range？
如果不用hashmap，用其他数据结构怎么做？大叔提示说用一个101bits的数来表示
（2）有个string， 找出第一个出现的unique char，比如google，return“l”
面试感慨，瞎准备了半天range tree， binary indexed tree， sweep line，结果还是
白忙了
顺便求个referral，本人fresh master， leetcode，lintcode各两遍，自学前端和
system design |
h****3
发帖数: 89 | |
h****3
发帖数: 89 | |
t****m
发帖数: 140 | 4 第一轮第一题只考虑lowercase letters
【在 h****3 的大作中提到】
: 第一题两个string 是任意字符可以重复吗？
|
y*****e
发帖数: 712 | |
d*******n
发帖数: 44 | 6 第一轮(2)是不是用DP啊？
f(3N) = max{f_i(3N-3) + k_i} for i = 1, ..., 3N
f_i(3N-3) 是去掉 i-1, i, i+1 三个value之后的解
这样就等于构造f这个3N * N的矩阵，用f_i(3) = max{last 3 values} 逆推回去 |
e*******7
发帖数: 347 | |
z*****m
发帖数: 119 | |
t****m
发帖数: 140 | 9 大牛说对了，面试官最后也是这么说的
【在 d*******n 的大作中提到】
: 第一轮(2)是不是用DP啊？
: f(3N) = max{f_i(3N-3) + k_i} for i = 1, ..., 3N
: f_i(3N-3) 是去掉 i-1, i, i+1 三个value之后的解
: 这样就等于构造f这个3N * N的矩阵，用f_i(3) = max{last 3 values} 逆推回去
|
t****m
发帖数: 140 | 10 其实我觉得挺好的
逼格比较高
【在 y*****e 的大作中提到】
: lz狗家食堂到底怎样啊？好吃否？
|
|
|
b********a
发帖数: 70 | 11 请教大牛：
如果f_i(3N-3)是去掉 i-1, i, i+1 三个value之后的解，
f_j(3N-18)是不是去掉j-1,j,j+1三个value之后的解？
那么
f_j(3N-18) = max{f_i(3N-21)+k_i} for i=?
请问这里i的范围是什么？能给出一个f_i(3N-3k)的通式么？
【在 d*******n 的大作中提到】
: 第一轮(2)是不是用DP啊？
: f(3N) = max{f_i(3N-3) + k_i} for i = 1, ..., 3N
: f_i(3N-3) 是去掉 i-1, i, i+1 三个value之后的解
: 这样就等于构造f这个3N * N的矩阵，用f_i(3) = max{last 3 values} 逆推回去
|
n******n
发帖数: 12088 | 12 这题有点文字游戏。自己拿过朋友拿，听起来像博弈的问题，但其实没有关系。就是一
次拿三个，左右的不算。
【在 t****m 的大作中提到】
: 大牛说对了，面试官最后也是这么说的
|
c******n
发帖数: 4965 | 13 1.1. 就比较所有的pair 可以么？ 还是有快点的办法？
多谢
【在 t****m 的大作中提到】
: Fresh Grad, 两轮电面， onsite四轮
: 先说几条onsite的tips：
: 1.如果宾馆离面试地点比较远，一定要早点走，弯曲的交通不是盖的
: 2.面试的时候用水笔写错的code不要用手擦，即使用手擦也记得不要往脸上抹，今天我
: 就看面
: 试官一直对我的大花猫脸笑
: 3.中午不要吃太多
: 第一轮国人小哥，人很nice
: （1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
: 们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
|
g*********5
发帖数: 1145 | |
l*k
发帖数: 10 | 15 第三题path怎么定义？是任意node开始到任意node结束都可以？
可以有负数吗？
【在 t****m 的大作中提到】
: Fresh Grad, 两轮电面， onsite四轮
: 先说几条onsite的tips：
: 1.如果宾馆离面试地点比较远，一定要早点走，弯曲的交通不是盖的
: 2.面试的时候用水笔写错的code不要用手擦，即使用手擦也记得不要往脸上抹，今天我
: 就看面
: 试官一直对我的大花猫脸笑
: 3.中午不要吃太多
: 第一轮国人小哥，人很nice
: （1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
: 们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
|
b******s
发帖数: 5329 | |
n*****d
发帖数: 6 | |
w***y
发帖数: 6251 | 18 预祝拿offer！
顺便问下第三轮的题咋做 😓
“问如果找一棵树里面所有和为target的path，path可以从任何node开始，不一定要从
root开始”
cc150似乎有一个类似的，但是我看那里的解法，感觉还是从root或者说从ancestor开
始的，只是起止不限于root／leaf
如果是类似Binary Tree Maximum Path Sum里面那种，可以从left--node--right这样
任意path，怎么做呢？ |
n*****d
发帖数: 6 | 19
【在 w***y 的大作中提到】
: 预祝拿offer！
: 顺便问下第三轮的题咋做 😓
: “问如果找一棵树里面所有和为target的path，path可以从任何node开始，不一定要从
: root开始”
: cc150似乎有一个类似的，但是我看那里的解法，感觉还是从root或者说从ancestor开
: 始的，只是起止不限于root／leaf
: 如果是类似Binary Tree Maximum Path Sum里面那种，可以从left--node--right这样
: 任意path，怎么做呢？
|
h****3
发帖数: 89 | 20 第一次hashmap没想明白，因为如果有大量重复出现我不晓得该存哪个。
感觉还是遍历所有的diff更简单一点， 不知道有没有更好的办法，或者谁能解释一下
hashmap怎么搞？ |
|
|
h**********n
发帖数: 897 | 21 就四轮还没遇到烙印你已经够运气的了，new grad为啥不能问system design？居然还
敢说醉了……
国内master intern面试都要问system design，system design和whiteboard是必须的。
看了这帖子才觉得，现在G的面试题目真特么水，三哥上台果然是一个套路，先降门槛
扩招，然后搞过头了就裁人外包劳动力到南亚。 |
s***y
发帖数: 12419 | |
c********w
发帖数: 308 | 23 da niu, if you think these are too easy, please help people out answering
some of the questions mentioned.
的。
【在 h**********n 的大作中提到】
: 就四轮还没遇到烙印你已经够运气的了，new grad为啥不能问system design？居然还
: 敢说醉了……
: 国内master intern面试都要问system design，system design和whiteboard是必须的。
: 看了这帖子才觉得，现在G的面试题目真特么水，三哥上台果然是一个套路，先降门槛
: 扩招，然后搞过头了就裁人外包劳动力到南亚。
|
z***b
发帖数: 127 | 24 这题感觉得用2个hash table 吧。
abc cba
第一遍放在第一个hash table 1里
a 0,2
b 1,1
c 0,2
然后遍历这个hash table1, 把 (0, 2)做成key放进第二个hash table里，能找到a, c
是应该交换的。
【在 h****3 的大作中提到】
: 第一次hashmap没想明白，因为如果有大量重复出现我不晓得该存哪个。
: 感觉还是遍历所有的diff更简单一点， 不知道有没有更好的办法，或者谁能解释一下
: hashmap怎么搞？
|
s*********y
发帖数: 10 | 25 同问第一题怎么做。
只想到了brute-force swap所有的pair, then choose that one yielding min diff.
Further optimize: stop when difference is reduced by 2. But still O(n^2). |
t****m
发帖数: 140 | 26 第一题我的做法是把index相同的两个字母合起来组成key
比如s1=abc， s2=cba， 那么index 0存的key就是ac，每次找字母顺序相反的key.
过两边，第一遍找能减少2 difference的，找不到再找能减少一个difference的
o(n)
.
【在 s*********y 的大作中提到】
: 同问第一题怎么做。
: 只想到了brute-force swap所有的pair, then choose that one yielding min diff.
: Further optimize: stop when difference is reduced by 2. But still O(n^2).
|
q*c
发帖数: 9453 | 27 建一个 mismatch table.
position， changed_value>
直接扫描一遍， 遇到不同的就加进去, 看看需要的 swap 有没有已经出现过 (检查
the_other_mismatched value set of mismatched_table)， 如果有就加进来。
纪录最大 changed_value 就行了。
.
【在 s*********y 的大作中提到】
: 同问第一题怎么做。
: 只想到了brute-force swap所有的pair, then choose that one yielding min diff.
: Further optimize: stop when difference is reduced by 2. But still O(n^2).
|
j*****o
发帖数: 394 | 28 第（2)题想了半天。。。我一直以为是一个“朋友“而那个朋友可以挑两边的任一个
obj...
orz...原来有“两个“好朋友。。。。
【在 t****m 的大作中提到】
: Fresh Grad, 两轮电面， onsite四轮
: 先说几条onsite的tips：
: 1.如果宾馆离面试地点比较远，一定要早点走，弯曲的交通不是盖的
: 2.面试的时候用水笔写错的code不要用手擦，即使用手擦也记得不要往脸上抹，今天我
: 就看面
: 试官一直对我的大花猫脸笑
: 3.中午不要吃太多
: 第一轮国人小哥，人很nice
: （1）有两个string， 比如 s1 = "abc", s2 = "cba",相同index下的字母不同，我
: 们叫一个difference，比如在index 0 上 s1是 a 而s2 是 c，这就是一个differnce，
|
w**********h
发帖数: 31 | 29
Map里面存个list就行吧，把所有重复的index都存进去。不知道你说的遍历所有diff怎
么做，复杂度多少？
这是我的思路， time复杂度为O(L),L 为字符串长。
只考虑有difference的index,否则交换无意义。交换后最多可以使difference减少2，
最少是0.
1.遍历s1，构建一个Map>.key 是s1的字符，value是s1包
含该字符的所有index.
2.遍历s2,如果map.containsKey(s2.charAt(i))， 遍历map.get(s2.charAt(i)), 其中
每个index记为j. 尝试swap(i,j),看difference 减少多少（至少减少1）. 如果发现减
少2的，返回。
【在 h****3 的大作中提到】
: 第一次hashmap没想明白，因为如果有大量重复出现我不晓得该存哪个。
: 感觉还是遍历所有的diff更简单一点， 不知道有没有更好的办法，或者谁能解释一下
: hashmap怎么搞？
|
