n****r
发帖数: 10 | 1 国内fresh master，英语不好，有时交流是个问题。
电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
面。
第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
近15分钟，面试官开始让我问问题，随便聊了聊。
第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
些模糊。很艰难的交流着，不停让对方repeat，我都不好意思了。题是设计题，连蒙带
猜的做，最后也没写出个啥名堂，时间就到了。
第三面：HM，基本就聊天，research，project，然后behavior问题，比如why amazon
等～最后问了个查询的题：就讲了hash，hash函数，冲突处理等等都讲了，最后又讲了
内存不够如何处理等等。
第四面：这次倒好，没有问我project，几句之后开始编程，第一问是反转matrix，
CC150原题。给她讲了半天思路，在collabedit上描述真是又慢又痛苦，最后很快写完
程序。第二问是找一个given string的longest common substring：我用了后缀数组排
序后找longest common prefix。
第五面：HR，问了20分钟左右general的问题，第6个面试官就来了～
第六面：设计题，设计一个家具系统，要求能模拟比如加多少力，用多少时间一个塑料
椅子会坏；用火烧一个木桌子多少时间桌子会坏等等。没能很好的catch到他的point，
也做得不好。最后结束。
总的来说编程题都比较顺利，写完code也没说我有bug，但设计题都做得不好，交流也
比较不顺畅。
两天后如愿收到据信～feedback也不给。更悲剧的是，今天接到手机电信公司电话，说
我前几天打了很多国际长途，问我手机是不是被别人用了和我确认一下。我才知道原来
我打电话去建立连接也是收费的，780块～最终收费还要月底结帐才知道。当是一个教
训吧，自己想当然以为这种conference call是免费的。
最后，再求版上大牛内推Twitter，eBay，Yahoo，以及那些愿意从美国之外招人的
startup，感激不尽～ |
w*****t
发帖数: 485 | 2 多谢分享~
跟你情况类似，也是在国内准备找美国工作的。 |
x*****0
发帖数: 452 | |
p*****2
发帖数: 21240 | 4 我用了后缀数组排
序后找longest common prefix。
这个时间复杂度多少呢？ |
n****r
发帖数: 10 | 5 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
(n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
(nmlg(n))～
【在 p*****2 的大作中提到】
: 我用了后缀数组排
: 序后找longest common prefix。
: 这个时间复杂度多少呢？
|
l*****a
发帖数: 14598 | 6 why not use n instead of m?
nmlg
是O
【在 n****r 的大作中提到】
: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～
|
B********t
发帖数: 147 | 7 找一个given string的longest common substring
是什么意思啊。。。就一个string怎么common
quick
call
【在 n****r 的大作中提到】
: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
|
l*****a
发帖数: 14598 | 8 感觉是最long重复子串
【在 B********t 的大作中提到】
: 找一个given string的longest common substring
: 是什么意思啊。。。就一个string怎么common
:
: quick
: call
|
p*****p
发帖数: 379 | 9 我记得这个是错的，但是一时想不出反例了
【在 p*****2 的大作中提到】
: 我用了后缀数组排
: 序后找longest common prefix。
: 这个时间复杂度多少呢？
|
P*******b
发帖数: 1001 | 10 这个设计题比较恶心啊
quick
call
【在 n****r 的大作中提到】
: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
|
|
|
p*****2
发帖数: 21240 | 11
nmlg
是O
这样的话是不是不如trie好使？
【在 n****r 的大作中提到】
: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～
|
A*********8
发帖数: 513 | 12 这跟买彩票有啥区别？老美应聘中国移动，你们要不？什么文化背景都不了解，就这样
找工作，阿 三直接在印度找都比国人在国内找要容易些，别人交流没有问题，又是软
件大国，老美又招多少？
quick
call
【在 n****r 的大作中提到】
: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
|
p*****2
发帖数: 21240 | 13
不过感觉LZ水平还不错
【在 A*********8 的大作中提到】
: 这跟买彩票有啥区别？老美应聘中国移动，你们要不？什么文化背景都不了解，就这样
: 找工作，阿 三直接在印度找都比国人在国内找要容易些，别人交流没有问题，又是软
: 件大国，老美又招多少？
:
: quick
: call
|
A*********8
发帖数: 513 | 14 水平是次要的，你觉得一个懂中文的老美应聘电信，你觉得是他的专业水平重要？还是
文化交流重要？最关键的在工作中与同事的交流，做事风格，文化氛围，想的也太容易
啦，你想一个维族，或哈萨克族，汉语无任何交流，国内一本大学，软件编程水平中上
，比如去个重庆这种地方语言文化比较重的地方进当地名企工作，你要是总经理，或是
人事部的，你感觉怎么样？要吗？维族软件工程师，重庆华为想要不？搞研发。。。
【在 p*****2 的大作中提到】
:
: 不过感觉LZ水平还不错
|
p*****2
发帖数: 21240 | 15
你这话说的。
【在 A*********8 的大作中提到】
: 水平是次要的，你觉得一个懂中文的老美应聘电信，你觉得是他的专业水平重要？还是
: 文化交流重要？最关键的在工作中与同事的交流，做事风格，文化氛围，想的也太容易
: 啦，你想一个维族，或哈萨克族，汉语无任何交流，国内一本大学，软件编程水平中上
: ，比如去个重庆这种地方语言文化比较重的地方进当地名企工作，你要是总经理，或是
: 人事部的，你感觉怎么样？要吗？维族软件工程师，重庆华为想要不？搞研发。。。
|
A*********8
发帖数: 513 | 16 想的太容易啦，文化语言的障碍，你们太小瞧了，连当年的所谓的“北大四君子”之一
的乌尔凯西，汉语那么好，英文也不错，为什么在台湾带着，怎么不在美国生活？好歹
汉语是他的半个母语。。。
quick
call
【在 n****r 的大作中提到】
: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
|
l******t
发帖数: 55733 | 17
除了民主他会啥
【在 A*********8 的大作中提到】
: 想的太容易啦，文化语言的障碍，你们太小瞧了，连当年的所谓的“北大四君子”之一
: 的乌尔凯西，汉语那么好，英文也不错，为什么在台湾带着，怎么不在美国生活？好歹
: 汉语是他的半个母语。。。
:
: quick
: call
|
d**********x
发帖数: 4083 | 18 要是真会这个可以去教书啊，写书啊，只要不在大陆哪都能混
【在 l******t 的大作中提到】
:
: 除了民主他会啥
|
g*********n
发帖数: 43 | 19 This uses O(n) space. trie 需要更多的空间.
【在 p*****2 的大作中提到】
:
: 你这话说的。
|
p*****2
发帖数: 21240 | 20
n是什么呀？
【在 g*********n 的大作中提到】
: This uses O(n) space. trie 需要更多的空间.
|
|
|
g*********n
发帖数: 43 | 21 n is length of the string |
s**x
发帖数: 7506 | 22
Right. 这个应该是programming pearl 上的一道题， 用一个长度为n 的指针数组分别
指到string 的每个字符的位置， 这样就得到了 n 个substring, 然后 quick sort,
然后相近的两两比较。
【在 g*********n 的大作中提到】
: n is length of the string
|
p*****2
发帖数: 21240 | 23
quick sort (n^2logn)吧？
【在 s**x 的大作中提到】
:
: Right. 这个应该是programming pearl 上的一道题， 用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置， 这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。
|
d**********x
发帖数: 4083 | 24 suffix array的标准做法 :)
【在 s**x 的大作中提到】
:
: Right. 这个应该是programming pearl 上的一道题， 用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置， 这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。
|
g*********n
发帖数: 43 | 25 Right. I think this is a space/time tradeoff. Trie uses more space but is
faster. Suffix array uses less space but is slower.
【在 p*****2 的大作中提到】
:
: quick sort (n^2logn)吧？
|
j*****y
发帖数: 1071 | 26 trie (prefix tree) 不是用来处理多个 string 的 common prefix 用的吗？
这里是一个 string, 找这个string 里面重复出现的最长的 substring, 看不出来
如何使用 trie来解决这个问题阿
nmlg
是O
这样的话是不是不如trie好使
【在 p*****2 的大作中提到】
:
: quick sort (n^2logn)吧？
|
n****r
发帖数: 10 | 27
嗯，就是这样的，相对于trie会更节省空间，时间复杂度为O(n^2lgn).
【在 s**x 的大作中提到】
:
: Right. 这个应该是programming pearl 上的一道题， 用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置， 这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。
|
n****r
发帖数: 10 | 28 想起第一个设计题了，是说一个系统会不停接收query（每个query有一个唯一的ID，
query总数也不确定），然后run这个query得到一些结果并记录running time。不同
query可能会被运行很多次。要求系统在任意时刻能返回平均运行时间最快的5个query
和平均运行时间最慢的5个query。设计数据结构和算法～题大概可能就是这个意思，因
为当时交流起来真的很费劲。
当时说用hashmap来map query ID和一个pair，pair是query运行次数和当前平均运行时
间，这样每次更新很快，但是求最快的5个和最慢的5个比较费时，也想用最大堆和最小
堆，但每个query的平均运行时间是动态的～也不好弄。在纠结中时间就到了～ |
t*******e
发帖数: 274 | |
p*****2
发帖数: 21240 | 30
query
HashMap+TreeMap是不是就行了？
【在 n****r 的大作中提到】
: 想起第一个设计题了，是说一个系统会不停接收query（每个query有一个唯一的ID，
: query总数也不确定），然后run这个query得到一些结果并记录running time。不同
: query可能会被运行很多次。要求系统在任意时刻能返回平均运行时间最快的5个query
: 和平均运行时间最慢的5个query。设计数据结构和算法～题大概可能就是这个意思，因
: 为当时交流起来真的很费劲。
: 当时说用hashmap来map query ID和一个pair，pair是query运行次数和当前平均运行时
: 间，这样每次更新很快，但是求最快的5个和最慢的5个比较费时，也想用最大堆和最小
: 堆，但每个query的平均运行时间是动态的～也不好弄。在纠结中时间就到了～
|
|
|
n****r
发帖数: 10 | 31
TreeMap的key和vaule是什么呢？
【在 p*****2 的大作中提到】
:
: query
: HashMap+TreeMap是不是就行了？
|
n****r
发帖数: 10 | 32
基本是大公司比如G，F，A愿意从国内直接招吧
【在 t*******e 的大作中提到】
: 现在有哪些公司可以直接从中国招人？
|
p*****2
发帖数: 21240 | 33
TreeSet就行了吧。key就是放query的信息，平均和次数。用平均做hash
【在 n****r 的大作中提到】
:
: 基本是大公司比如G，F，A愿意从国内直接招吧
|
c********t
发帖数: 5706 | 34 把这个string看成2个， 用dp解,i!=j 似乎容易很多, O(n^2)
nmlg
是O
【在 n****r 的大作中提到】
: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～
|
c********t
发帖数: 5706 | 35 二爷，一直没弄懂一件事情。
我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
treemap一样问题。
【在 p*****2 的大作中提到】
:
: TreeSet就行了吧。key就是放query的信息，平均和次数。用平均做hash
|
p*****2
发帖数: 21240 | 36 不能 要remove and add
【在 c********t 的大作中提到】
: 二爷，一直没弄懂一件事情。
: 我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
: query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
: treemap一样问题。
|
a*******n
发帖数: 36 | 37 query那题可以用hash map结合max/min heap. hash map记录每个查询ID的平均时间，
每次来了一个query,更新hash map，并使用新的平均值更新max/min heap |
j*****y
发帖数: 1071 | 38 nice
【在 c********t 的大作中提到】
: 把这个string看成2个， 用dp解,i!=j 似乎容易很多, O(n^2)
:
: nmlg
: 是O
|
p*****2
发帖数: 21240 | 39
这个貌似时空最优吧。
【在 c********t 的大作中提到】
: 把这个string看成2个， 用dp解,i!=j 似乎容易很多, O(n^2)
:
: nmlg
: 是O
|
c********t
发帖数: 5706 | 40 多谢！
【在 p*****2 的大作中提到】
: 不能 要remove and add
|
