问两几个EBAY的题# JobHunting - 待字闺中
r*7
1 楼
前些天面的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”。这种 要怎么
做。
2. 给一个数组,从1到n, 打乱顺序。 其中有个一元素是错的,求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 (XOR方法)。 followup 有没有其他方法,就想不
出来了。
3.给一个很大的数组,取前k个最小的数。
我回答 建一个priority queue, 长度为k, 然后遍历整个数组,每次都维护priority
queue。 但是每有一个元素,worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
感觉这1,3两道题比较类似,都是有一个是大数据, 然后进行比较。 遇到这样的就歇
菜,完全没啥思路。
顺便问一下 第一题能用 suffix树吗? 个人感觉那样是不是更复杂了呢?
1. 两个输入,一个是description(String), 另一个是Negative Words(List<
String>).
description 是一个非常长的String, 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word,然后比对 negative words
followup: 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
2. 给一个数组,从1到n, 打乱顺序。 其中有个一元素是错的,求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 (XOR方法)。 followup 有没有其他方法,就想不
出来了。
3.给一个很大的数组,取前k个最小的数。
我回答 建一个priority queue, 长度为k, 然后遍历整个数组,每次都维护priority
queue。 但是每有一个元素,worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
感觉这1,3两道题比较类似,都是有一个是大数据, 然后进行比较。 遇到这样的就歇
菜,完全没啥思路。
顺便问一下 第一题能用 suffix树吗? 个人感觉那样是不是更复杂了呢?