G家电面 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家电面

G家电面# JobHunting - 待字闺中

m*n2013-07-18 07:07

1 楼

这周面的，一道coding一道open question。coding题一个隐藏的小bug被提醒才发现，
已经歇菜了。
1. 有一个item set a，和里面每个item出现的probability p，写一个function，每次
调用返回一个item，很多次调用后，各个item返回的频率要符合其概率。可以调用一个
random number generator。
e.g. a = {'A', 'B', 'C'}, p = {0.3, 0.4, 0.3}
题目简单，把p转换成cumulative的，再做binary search。我是忘了preprocess p将其
转换成cumulative，开始写的一个就是O（n）。问是否可以优化，我再指出可以对p做
binary search。估计问题出在这里。
2. 有很大一个电子图书馆，里面每本书的每一页都是OCR转换出来的text，所有每页大
约有5%的error（转换错误，错误分割单词，跳脱。。。）。设计一个方法判定图书馆
里是否有完全一样的书（duplicate），或者将来有书进来时判定同样的书是否已存在。
这个问题有点类似face recognition，要自己extract features，自己做predictive
modeling。
总的感觉第二题答的还可以，第一题太简单大意了，与G无缘啊。

J*32013-07-18 07:07

2 楼

赞面经！pat LZ! 看来面G一点都不能大意啊

l*c2013-07-18 07:07

3 楼

LZ加油，这儿有个第一题详细一点的解答，供楼下参考。
http://www.geeksforgeeks.org/random-number-generator-in-arbitra
当时面G的时候，电面两题都是跟随机有关的code题。

u*o2013-07-18 07:07

4 楼

LZ牛啊，能当场想出这两题的答案很不容易啊。
LZ能分享一下第二题怎么答的吗？

m*n2013-07-18 07:07

5 楼

牛啥，G的电面都过不了，丢死人了。
第二题没写code，就是不停问你问题，不停的延伸。
这题需要点machine learning的背景。每页都有error，word-by-word比较肯定是不行
的，而且全文比较也太expensive了。有时候一个单词被错误的分为两个，有时候单词
有脱漏，所以要做alignment，有点象DNA sequence alignment一样，找出两页之间概
率最大的alignment，看看mismatch rate多大，大于某个threshold就认为这两页不同
。随机抽取若干页，比如随机从两本页数相同的书里抽取相应的十页，如果有9页被判
定相同，可以认为这两本书相同。
当然，实际上要做supervised learning，用一些label的sample来train model，调整
里面的threshold和其他参数，以得到最大的accuracy。

【在 u*****o 的大作中提到】

: LZ牛啊，能当场想出这两题的答案很不容易啊。
: LZ能分享一下第二题怎么答的吗？

m*n2013-07-18 07:07

6 楼

第一题其实很简单，我没见过，但是解法和那个一样。
p转换成prefix sum，然后每次生成一个0～1间的随机数，再在p里面做binary search
看属于那个区间，就输出相应的item。我解释过prefix sum，但是写code的时候忘了加
进去，被指出来才发现。
要是一开始注意细节，然后写成binary search的版本就好了。

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

: LZ加油，这儿有个第一题详细一点的解答，供楼下参考。
: http://www.geeksforgeeks.org/random-number-generator-in-arbitra
: 当时面G的时候，电面两题都是跟随机有关的code题。

u*o2013-07-18 07:07

7 楼

LZ你写的我竟然全部看懂了, LZ既然知道DNA SEQUENCE ALIGNMENT，是不是也是生物信
息背景的？

【在 m*****n 的大作中提到】

: 牛啥，G的电面都过不了，丢死人了。
: 第二题没写code，就是不停问你问题，不停的延伸。
: 这题需要点machine learning的背景。每页都有error，word-by-word比较肯定是不行
: 的，而且全文比较也太expensive了。有时候一个单词被错误的分为两个，有时候单词
: 有脱漏，所以要做alignment，有点象DNA sequence alignment一样，找出两页之间概
: 率最大的alignment，看看mismatch rate多大，大于某个threshold就认为这两页不同
: 。随机抽取若干页，比如随机从两本页数相同的书里抽取相应的十页，如果有9页被判
: 定相同，可以认为这两本书相同。
: 当然，实际上要做supervised learning，用一些label的sample来train model，调整
: 里面的threshold和其他参数，以得到最大的accuracy。

m*n2013-07-18 07:07

8 楼

不算，不过你学习Hidden Markov和一些DP算法的时候，alignment是很常见的例子吧。

【在 u*****o 的大作中提到】

: LZ你写的我竟然全部看懂了, LZ既然知道DNA SEQUENCE ALIGNMENT，是不是也是生物信
: 息背景的？

r*72013-07-18 07:07

9 楼

请教下大牛们，第一题可不可以这样：
用random generator 产生0~9的随机数，如果是0~2,则输出itme 1, 3~5输出 item3，6
~9输出 item2
还是说我题意理解错了？

r*c2013-07-18 07:07

10 楼

第一题要用binary search？
试写了一下，借用二爷的原代码
#include "stdafx.h" //cause I am using VC++
#include
#include
#include
using namespace std;
class Solution{
public:
Solution(unordered_mapmap){
_map = map;
_size = _map.size();
unordered_map::iterator it = _map.begin();
while(it != _map.end())
_vec.push_back(it++->first);
}

bool Prob() //borrowed from LeetCode
{
return rand()%2 == 0;
}
bool Prob2(double p, bool expected) //borrowed from LeetCode
{
if(p<0.5)
return Prob2(1-p,!expected);
if(Prob()==expected)
return expected;
else
return Prob2((p-0.5)*2, expected);
}
char getItem()
{
do{
char ch = _vec[rand() % _size];
if(Prob2(_map[ch], true))
return ch;
}while(true);
}
vector_vec;
unordered_map _map;
int _size;
};
int _tmain(int argc, _TCHAR* argv[])
{
unordered_map mp;
mp['A'] = 0.3;
mp['B'] = 0.4;
mp['C'] = 0.3;
Solution sol(mp);
int result[3] = {0, 0, 0};
result[0] = result[1] = result[2] = 0;
int nCount = 0, nMax = 10000;
do{
switch(sol.getItem())
{
case 'A':
result[0]++; break;
case 'B':
result[1]++; break;
case 'C':
result[2]++; break;
default:break;
}
nCount++;
}while (nCount < nMax);
cout<double)result[1]/nCount
<return 0;
}

【在 m*****n 的大作中提到】

: 这周面的，一道coding一道open question。coding题一个隐藏的小bug被提醒才发现，
: 已经歇菜了。
: 1. 有一个item set a，和里面每个item出现的probability p，写一个function，每次
: 调用返回一个item，很多次调用后，各个item返回的频率要符合其概率。可以调用一个
: random number generator。
: e.g. a = {'A', 'B', 'C'}, p = {0.3, 0.4, 0.3}
: 题目简单，把p转换成cumulative的，再做binary search。我是忘了preprocess p将其
: 转换成cumulative，开始写的一个就是O（n）。问是否可以优化，我再指出可以对p做
: binary search。估计问题出在这里。
: 2. 有很大一个电子图书馆，里面每本书的每一页都是OCR转换出来的text，所有每页大

r*c2013-07-18 07:07

11 楼

楼主牛人！
我的做法不足取，因为速度太慢了。做了个1000000次测试，geeksforgeeks的(权当
是楼主的方法的实现)耗时1.55秒，我的24.23秒。

【在 r*c 的大作中提到】

: 第一题要用binary search？
: 试写了一下，借用二爷的原代码
: #include "stdafx.h" //cause I am using VC++
: #include
: #include
: #include
: using namespace std;
: class Solution{
: public:
: Solution(unordered_mapmap){

d*n2013-07-18 07:07

12 楼

The following is incorrect:
char getItem()
{
do{
char ch = _vec[rand() % _size];
if(Prob2(_map[ch], true))
return ch;
}while(true);
}
You lose the expected distribution.
In the first round in your program, 'A' has prob of 0.3, 'B' has prob of 0.7
*0.4, 'C' has prob of 0.7*0.6*0.3. You didn't get the 0.3, 0.4, 0.3
distribution.

【在 r*c 的大作中提到】