[合集] 绿卡名字写错了,俺怎么就这么糊涂呢。。。# Immigration - 落地生根
Z*Z
1 楼
电话筛选
前缀树: 情景是命令行下做自动完成提示,就是用前缀树把所有可能的命令先存起来,
然后用户打跳格键的时候返回所有可能的命令。
树有两个操作,存储和查询。
我跟这题很有缘:
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
昂赛特
他们搬家后还没立牌子。楼里各种安全措施,我在进去之前还被要求出示证件,进去之
后上厕所都得有人陪着刷卡。
面试开始,第一个,纯种国人,问了两个问题,算一个二叉树的直径。二叉树的直径定
义为树上任意选两个点的距离的最大值。第二个问题是给了一个整数随机数生成器零到
甲,和另外一个正整数乙,让生成一个零到乙之间的随机数。
第二个,原面试官救火去了,来个临时的。上来问排序,两个大文件,全是整数,内存
装不下,怎么办。答,把每个文件分成块,逐个排序,输出到临时文件,然后归并所有
临时文件。归并的时候详细讨论了两路归并和多路归并的区别,主要是读写次数的区别
。然后,主要问题是实现一个缓存。我说在爪哇里用链接的哈希表巨简单。说,不用那
东西自己写一个怎么办。遂从头写了一个。假设哈希表和链表都实现好了。然后稍微讨
论了一下多线程。
老美,说话挺快。先问如何判断一个树是否是二叉查找树。然后设计一个分布式随机数
生成器。其实他要的是序列号生成器,不需要随机。具体要求是: 1. 在某一时间段里
生成某个范围的随机数,多个机器协作,但是随机数必须不能有重复。2. 在某一时间段
里的数,一定要比下一个时间段里生成的数小。我的做法就是把整数所有的比特分成三
份,高位的那份代表机器爱迪,接下来是时间段,低位是一个简单计数器。然后扩展了
一下,问在某一时间段里,某一台机器的计数器满了怎么办。答,不要重置,要重定向
收到的请求。最后5分钟问了一个很简单的有障碍网格有多少种走法。口德之。
然后吃饭,带我吃饭的人就是电面我的人,很自豪的带我去他们楼顶的新食堂。
下一个,曾经是架构师,现在做性能优化,问了个问题是如何把微博里的特殊意义的表
达式变成超文本。最后实际需要口德的问题是这样的。假设有一个字符串表示原始的微
博,例如 “大家快来看@叫兽 的新作,链接在这里http://abc!!”.其中有一些特殊
表达式,例如 @叫兽 表示应该跳转到叫兽的主页上,在超文本语言里,这个可以表示为
@叫兽.这些特殊表达式可以表示成实体类,例如:
class 实体{
int 开始,结束;
String 超文本;
}
其中开始和结束表示在原始微博里的起始位置,超文本表示那段位置之间的完整的超文
本。写一个函数,接受一个原始的微博和一个实体的集合,返回转义后的完整的超文本
代码。
String 转换(String 原始微博, Set 实体的集合);
这个题目直白且容易。做法就是先对那个实体的集合按照开始排序,然后一个个的替换
。有两个地方可以出彩:1)用爪哇里的树集合写,这样就不用排序了。2)面试官说有
一次一个人用树做的,他被震精了。后来他还亲自编码测试了一下性能。不过现在我也
没想明白他是什么意思。
最后一个,很温和的美国人,上来他写了一段求最大子数组和
的代码,暴力的那种,复杂度分析。我说三次方的。问优化,我说可以弄个数组把和记
下来,这样是二次方的。又问空间复杂度多少,说线性,问能不能做到常数空间,保持
时间复杂度。想了一下,大概可以。最后要最优解。坦言知道答案。就没让写代码,描
述一下就好。然后问了一个哲学问题,这个问题分明有三次方那么多的可能性要考虑,
为什么最优解只用线性的。然后问了一个开房问题,一个有缓存的歪脖 系统,请求多了
或者某块坏了,会有什么现象,以及什么应对措施。
福利
他家最近搬了新楼,一切设施都是新的,记得哪位发过一个非死不可办公室的照片,所
有编程师都是挤在一张桌子上,他家大概也是那样,只不过空间大得多。食堂在楼顶,
早、中、晚饭全管,风景不错,食物也不错,不是外卖,在我面的这几家里,他家的饭
最好。每天有两班班车从谷子里经过接送上下班。现在没有死另一开匹配,没有奖金。
将来可能在谷子里开一个卫星办公室。给的钱不少,股票也不少,数字参见前面五个卧
佛那帖子。我没有永久性脑残,所以低个零头 :)
技术上他家原来是啊欧啊,后来性能有问题,现在改用爪哇和死开啦,算是主流技术吧
。有很多很挑战的性能上的问题,包括现在即将开幕的奥运会,让我们对它拭目以待。
最后在热情称赞一下他家的锐酷入特,是我见过的最酷,最有耐心的一个。我跟他讲我
在面其他家,他就耐心的等,也不推我,也没有那种“劳资公司天下第一”的屁气。在
他的帮助下我还和公司里另外一些人通过话,包括经理的经理,灵家和狗家跳过去的等
等。抛开政治因素不看,觉得他家的技术和商业策略很有钱途。
前缀树: 情景是命令行下做自动完成提示,就是用前缀树把所有可能的命令先存起来,
然后用户打跳格键的时候返回所有可能的命令。
树有两个操作,存储和查询。
我跟这题很有缘:
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
昂赛特
他们搬家后还没立牌子。楼里各种安全措施,我在进去之前还被要求出示证件,进去之
后上厕所都得有人陪着刷卡。
面试开始,第一个,纯种国人,问了两个问题,算一个二叉树的直径。二叉树的直径定
义为树上任意选两个点的距离的最大值。第二个问题是给了一个整数随机数生成器零到
甲,和另外一个正整数乙,让生成一个零到乙之间的随机数。
第二个,原面试官救火去了,来个临时的。上来问排序,两个大文件,全是整数,内存
装不下,怎么办。答,把每个文件分成块,逐个排序,输出到临时文件,然后归并所有
临时文件。归并的时候详细讨论了两路归并和多路归并的区别,主要是读写次数的区别
。然后,主要问题是实现一个缓存。我说在爪哇里用链接的哈希表巨简单。说,不用那
东西自己写一个怎么办。遂从头写了一个。假设哈希表和链表都实现好了。然后稍微讨
论了一下多线程。
老美,说话挺快。先问如何判断一个树是否是二叉查找树。然后设计一个分布式随机数
生成器。其实他要的是序列号生成器,不需要随机。具体要求是: 1. 在某一时间段里
生成某个范围的随机数,多个机器协作,但是随机数必须不能有重复。2. 在某一时间段
里的数,一定要比下一个时间段里生成的数小。我的做法就是把整数所有的比特分成三
份,高位的那份代表机器爱迪,接下来是时间段,低位是一个简单计数器。然后扩展了
一下,问在某一时间段里,某一台机器的计数器满了怎么办。答,不要重置,要重定向
收到的请求。最后5分钟问了一个很简单的有障碍网格有多少种走法。口德之。
然后吃饭,带我吃饭的人就是电面我的人,很自豪的带我去他们楼顶的新食堂。
下一个,曾经是架构师,现在做性能优化,问了个问题是如何把微博里的特殊意义的表
达式变成超文本。最后实际需要口德的问题是这样的。假设有一个字符串表示原始的微
博,例如 “大家快来看@叫兽 的新作,链接在这里http://abc!!”.其中有一些特殊
表达式,例如 @叫兽 表示应该跳转到叫兽的主页上,在超文本语言里,这个可以表示为
@叫兽.这些特殊表达式可以表示成实体类,例如:
class 实体{
int 开始,结束;
String 超文本;
}
其中开始和结束表示在原始微博里的起始位置,超文本表示那段位置之间的完整的超文
本。写一个函数,接受一个原始的微博和一个实体的集合,返回转义后的完整的超文本
代码。
String 转换(String 原始微博, Set 实体的集合);
这个题目直白且容易。做法就是先对那个实体的集合按照开始排序,然后一个个的替换
。有两个地方可以出彩:1)用爪哇里的树集合写,这样就不用排序了。2)面试官说有
一次一个人用树做的,他被震精了。后来他还亲自编码测试了一下性能。不过现在我也
没想明白他是什么意思。
最后一个,很温和的美国人,上来他写了一段求最大子数组和
的代码,暴力的那种,复杂度分析。我说三次方的。问优化,我说可以弄个数组把和记
下来,这样是二次方的。又问空间复杂度多少,说线性,问能不能做到常数空间,保持
时间复杂度。想了一下,大概可以。最后要最优解。坦言知道答案。就没让写代码,描
述一下就好。然后问了一个哲学问题,这个问题分明有三次方那么多的可能性要考虑,
为什么最优解只用线性的。然后问了一个开房问题,一个有缓存的歪脖 系统,请求多了
或者某块坏了,会有什么现象,以及什么应对措施。
福利
他家最近搬了新楼,一切设施都是新的,记得哪位发过一个非死不可办公室的照片,所
有编程师都是挤在一张桌子上,他家大概也是那样,只不过空间大得多。食堂在楼顶,
早、中、晚饭全管,风景不错,食物也不错,不是外卖,在我面的这几家里,他家的饭
最好。每天有两班班车从谷子里经过接送上下班。现在没有死另一开匹配,没有奖金。
将来可能在谷子里开一个卫星办公室。给的钱不少,股票也不少,数字参见前面五个卧
佛那帖子。我没有永久性脑残,所以低个零头 :)
技术上他家原来是啊欧啊,后来性能有问题,现在改用爪哇和死开啦,算是主流技术吧
。有很多很挑战的性能上的问题,包括现在即将开幕的奥运会,让我们对它拭目以待。
最后在热情称赞一下他家的锐酷入特,是我见过的最酷,最有耐心的一个。我跟他讲我
在面其他家,他就耐心的等,也不推我,也没有那种“劳资公司天下第一”的屁气。在
他的帮助下我还和公司里另外一些人通过话,包括经理的经理,灵家和狗家跳过去的等
等。抛开政治因素不看,觉得他家的技术和商业策略很有钱途。