[M$] onsite面经

上个月月底去面了一下 M$的 onsite..

1st 轮:
Third Max in Array, Skip List

2nd轮:
strStr(), 用 rolling 优化到 o(n). LRU cach

3rd轮:
设计一个log

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

starvation了怎么办. 那就说加time-out。

Counting Sort.

明天就要onsite了, 攒人品！！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求问楼主strstr这怎么rolling hash呀。。。dna的那个dna可以用一个integer表示，这个string如果很长就没办法用integer表示了吧。如果就存个string的话，rolling window要删除最前面的char加上新的一个char，这个每次效率不都得是n吗（n为needle的长度）

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢楼主分享！想问下那个StrStr() 用rolling是什么意思，能细说说吗，和KMP区别在哪里？ 谢谢啦！

qxr 发表于 2017-2-13 04:51
谢谢楼主分享！想问下那个StrStr() 用rolling是什么意思，能细说说吗，和KMP区别在哪里？ 谢谢啦！

rolling hash,参见 Leetcode DNA sequence那题.. 我不会KMP..

wangyuesong2 发表于 2017-2-13 06:02
求问楼主strstr这怎么rolling hash呀。。。dna的那个dna可以用一个integer表示，这个string如果很长就没办 ...

恩？你会hashing DNA的string,就应该会hashing needle吧

感谢！LZ牛啊，一手offer～

wangyuesong2 发表于 2017-2-13 07:02
dna的char就几种，sequence最多为10个，所以可以用integer表示，位操作效率constant，但是如果needle是一 ...

建议你看下how to hash a string :)

donnice 发表于 2017-2-13 07:10
感谢！LZ牛啊，一手offer～

....攒人品攒人品..

strStr() 这个只要检查substring 存在就好吗? 还是要输出 所有的string, 如果要所有的string 感觉rolling hash 仍然不能达到o(n)?