求问一道G家Onsite题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求问一道G家Onsite题

求问一道G家Onsite题# JobHunting - 待字闺中

l*92015-01-04 08:01

1 楼

【以下文字转载自 Military 讨论区】
发信人: lqm1989 (Jeremy Lin), 信区: Military
标题: 带两斤干大枣过美国海关没事吧？
发信站: BBS 未名空间站 (Wed Feb 20 10:23:55 2013, 美东)
多谢

e*y2015-01-04 08:01

2 楼

Given millions of lines of strings, each of which have a length of 1000
characters without spaces. Among of these strings, only one of them is real
English consisting of valid English words. All others and just random
letter combinations that is not real English. Also, bear in mind that the
English may contains several mismatches. Your task is to identify the only
string that is English.

b*l2015-01-04 08:01

3 楼

当然没事，我父母带过。

l*a2015-01-04 08:01

4 楼

这是题吗？
你怎么知道所谓的那些不是英文的就不是mismatch呢
那你说ab,ac这两个词哪个是English with mismatch,哪个是random letter
combination?

real

【在 e**********y 的大作中提到】

: Given millions of lines of strings, each of which have a length of 1000
: characters without spaces. Among of these strings, only one of them is real
: English consisting of valid English words. All others and just random
: letter combinations that is not real English. Also, bear in mind that the
: English may contains several mismatches. Your task is to identify the only
: string that is English.

r*t2015-01-04 08:01

5 楼

没事，刚带回干红枣，木耳，干桂圆，小米。

e*y2015-01-04 08:01

6 楼

这是题。这种题目，只需要大致的跟面试官交流思路怎么做。
random letter combination的话，1000个字都是这样，没有能在字典里找到的词
English with mismatch是1000个字里面大部分你都能在字典里面找到，少部分不能。

【在 l*****a 的大作中提到】

: 这是题吗？
: 你怎么知道所谓的那些不是英文的就不是mismatch呢
: 那你说ab,ac这两个词哪个是English with mismatch,哪个是random letter
: combination?
:
: real

s*62015-01-04 08:01

7 楼

查查海关规定？

【在 l*****9 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: lqm1989 (Jeremy Lin), 信区: Military
: 标题: 带两斤干大枣过美国海关没事吧？
: 发信站: BBS 未名空间站 (Wed Feb 20 10:23:55 2013, 美东)
: 多谢

h*c2015-01-04 08:01

8 楼

sum of the lengths is 1000.

h*c2015-01-04 08:01

9 楼

Is the dictionary given?

h*c2015-01-04 08:01

10 楼

Ok, approximately,
Suppose you have the dictionary in a hashed structure O(m)
So the maxim len of one word possilble is known.
start a with the first character with max length window, hash search in the
dictionary. Not found window size minus one.
Found, slide the window.
Iterate through.
Time complexity N * (1000/min_word_length) * m

real

【在 e**********y 的大作中提到】

r*72015-01-04 08:01

11 楼

难道是建一个后缀树数组？复杂度也不低啊。。。

real

【在 e**********y 的大作中提到】

p*t2015-01-04 08:01

12 楼

假设random strings是uniform的统计下每行里各字母出现的次数
大概就可以大致找到哪行是英文单词组成的了吧。。。
毕竟英语单词各字母频率是有很大bias的。。。

real

【在 e**********y 的大作中提到】

j*r2015-01-04 08:01

13 楼

可以计算每一行的q-gram分布，再计算熵，熵最小的就是real English，线性时间可以
完成。

s*d2015-01-04 08:01

14 楼

这个题怎么搞？

real

【在 e**********y 的大作中提到】

B*L2015-01-04 08:01

15 楼

for each line, randomly sample a few segments of 10 chars and then check if
these segments contain valid English words or not. If none of them does,
then the corresponding line is not valid English. The time complexity could
be sublinear.

real

【在 e**********y 的大作中提到】