问两几个EBAY的题 - 未名空间(mitbbs.com)
前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如"is bad"。这种 要怎么
做。
第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每有一个元素，worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
Read full article from 问两几个EBAY的题 - 未名空间(mitbbs.com)
前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如"is bad"。这种 要怎么
做。
第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每有一个元素，worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
Read full article from 问两几个EBAY的题 - 未名空间(mitbbs.com)
