Ebay onsite question

前些天面的EBay, onsite。 有几个问题感觉回答的不是很好,在这求教:

1. 两个输入,一个是description(String), 另一个是Negative Words(List).

description 是一个非常长的String, 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。

回答 把description分成每一个word,然后比对 negative words (this is what I thought of in the first place)

followup: 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
(Using KMP algorithm?, linear search time)
AC automation. This deal with multiple words, should be an overshot
http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

2. 给一个数组,从1到n, 打乱顺序。 其中有个一元素是错的,求那个元素的index。
例如 531226.

O(1)空间。 回答了用 bit运算 (XOR方法)。 followup 有没有其他方法,就想不
出来了。

XOR algorithm? This is very like one of the leetcode question, using counting sort can be solved easily, scan it once, and put A[i] to index i, then scan again to find the one that is out of place.

3.给一个很大的数组,取前k个最小的数。

我回答 建一个priority queue, 长度为k, 然后遍历整个数组,每次都维护priority
queue。 但是每有一个元素,worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。

The algorithm runs O(nlogk) becuase maintaining a priority queue (heap) takes logk time. (The heap containing k elements has a height of log k).

面试官 不满意。

感觉这1,3两道题比较类似,都是有一个是大数据, 然后进行比较。 遇到这样的就歇
菜,完全没啥思路。

顺便问一下 第一题能用 suffix树吗? 个人感觉那样是不是更复杂了呢?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s