Re: 好像中国人特别爱拍照？ (转载) - 未名空间MITBBS历史存档

Re: 好像中国人特别爱拍照？ (转载)# PhotoGear - 摄影器材

h*y2010-12-10 08:12

1 楼

2个月前面的, 现在来攒攒人品
电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
1. from 1 to N one number appear twice, others once, find that number, (how
about two numbers? 500 numbers appear twice?)
2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
也可以linear搞定, 真汗
3. how DNS return IP lookup request.
4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
not, how to fix it?
onsite
1. 一个矩阵, 把所有非0元素按connected component分组打印出来, 4-neighbors算连通
2. thesis presentation
3. design spreadsheet, 每个单元格可以是int, 可以是对其他单元格的引用, 可以是
算术表达式, 加减乘除, 表达式中可以有对其他单元格的引用, 要能把值求出来, 这题
居然是lunch interview, 真啃爹, 饭都没吃完
4. design chess game, 人机对战
5. print matrix in spiral order. 这个简单, 但是follow up搞不定, how to
minimize cache misses when you go downward and upward?
6. leetcode, jump game II
onsite六轮面试之间连break都没有

l*e2010-12-10 08:12

2 楼

【以下文字转载自 ebiz 讨论区】
发信人: ethan555 (Urban Millionaire), 信区: ebiz
标题: Re: 好像中国人特别爱拍照？ (转载)
发信站: BBS 未名空间站 (Fri Dec 10 08:15:59 2010, 美东)
发信人: HaOgallery (HaO), 信区: NewYork
标题: Re: 好像中国人特别爱拍照？
发信站: BBS 未名空间站 (Fri Dec 10 01:36:55 2010, 美东)

l*a2010-12-10 08:12

3 楼

onsite 5的followup翻译成汉语贝？

how

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

a*a2010-12-10 08:12

4 楼

veli nice！veli good！
无灯，无闪，无引闪，自然光大师！
c user又丢人了。。。

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

: 【以下文字转载自 ebiz 讨论区】
: 发信人: ethan555 (Urban Millionaire), 信区: ebiz
: 标题: Re: 好像中国人特别爱拍照？ (转载)
: 发信站: BBS 未名空间站 (Fri Dec 10 08:15:59 2010, 美东)
: 发信人: HaOgallery (HaO), 信区: NewYork
: 标题: Re: 好像中国人特别爱拍照？
: 发信站: BBS 未名空间站 (Fri Dec 10 01:36:55 2010, 美东)

h*y2010-12-10 08:12

5 楼

横向移动access的是连续的空间, 不会cache miss,
纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
求牛人解答一下

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

: onsite 5的followup翻译成汉语贝？
:
: how

v*a2010-12-10 08:12

6 楼

在床上拍妞，这穿得太多啊

d*e2010-12-10 08:12

7 楼

电面2真的不知道，可以说说吗？谢谢。

how
memory

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

a*a2010-12-10 08:12

8 楼

慢慢脱

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

: 在床上拍妞，这穿得太多啊

h*y2010-12-10 08:12

9 楼

double find_kth_largest_unknown_length(istringstream &sin, int k)
{
vector vec;
double x;
while (sin >> x)
{
vec.emplace_back(x);
if (vec.size() == (k << 1) - 1)
{
nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater
());
vec.resize(k);
}
}
nth_element(vec.begin(), vec.begin()+k-1, vec.end(), greater());
return vec[k-1];
}

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

: 电面2真的不知道，可以说说吗？谢谢。
:
: how
: memory

k*n2010-12-10 08:12

10 楼

这些都不是必须的
内容是决定性的

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

: veli nice！veli good！
: 无灯，无闪，无引闪，自然光大师！
: c user又丢人了。。。

d*e2010-12-10 08:12

11 楼

nth_element()是什么函数？greater又是什么？
另外你原题说的是返回k个数字，但你下面是返回第k个数字?

greater

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

: double find_kth_largest_unknown_length(istringstream &sin, int k)
: {
: vector vec;
: double x;
: while (sin >> x)
: {
: vec.emplace_back(x);
: if (vec.size() == (k << 1) - 1)
: {
: nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater

r*n2010-12-10 08:12

12 楼

卡大经验太丰富了，佩服佩服。

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

: 这些都不是必须的
: 内容是决定性的

m*u2010-12-10 08:12

13 楼

用长度为k的minheap？

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

: nth_element()是什么函数？greater又是什么？
: 另外你原题说的是返回k个数字，但你下面是返回第k个数字?
:
: greater

k*n2010-12-10 08:12

14 楼

不敢不敢
我这个是对陈老师片子的感悟

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

: 卡大经验太丰富了，佩服佩服。

h*y2010-12-10 08:12

15 楼

那是nlogk, 可以做到和k无关的

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

: 用长度为k的minheap？

f*p2010-12-10 08:12

16 楼

这个确实是这样啊，如果床上坐着的是凤姐。。。

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

: 不敢不敢
: 我这个是对陈老师片子的感悟

h*y2010-12-10 08:12

17 楼

我贴的是EPI上求最大第K个数的答案, 本质是一样的

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

: nth_element()是什么函数？greater又是什么？
: 另外你原题说的是返回k个数字，但你下面是返回第k个数字?
:
: greater

d*02010-12-10 08:12

18 楼

两个妞轮流上场？

p*u2010-12-10 08:12

19 楼

用快速排序的思想，解决求第k大数或者前k大数之类的问题。
算法导论上有说

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

: 电面2真的不知道，可以说说吗？谢谢。
:
: how
: memory

z*62010-12-10 08:12

20 楼

这是什么相机和镜头？

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

: 【以下文字转载自 ebiz 讨论区】
: 发信人: ethan555 (Urban Millionaire), 信区: ebiz
: 标题: Re: 好像中国人特别爱拍照？ (转载)
: 发信站: BBS 未名空间站 (Fri Dec 10 08:15:59 2010, 美东)
: 发信人: HaOgallery (HaO), 信区: NewYork
: 标题: Re: 好像中国人特别爱拍照？
: 发信站: BBS 未名空间站 (Fri Dec 10 01:36:55 2010, 美东)

r*92010-12-10 08:12

21 楼

用两个矩阵如何？ A和A's transpose.
横向的时候用A，纵向的时候iterate rows in A's transpose

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

: 横向移动access的是连续的空间, 不会cache miss,
: 纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
: 求牛人解答一下

f*p2010-12-10 08:12

22 楼

无敌兔？2470？24105？

【在 z****6 的大作中提到】

: 这是什么相机和镜头？

d*e2010-12-10 08:12

23 楼

quickselect我知道，但我直觉一直觉得quickselect是O(N log N)的算法，不过我没仔
细算，可能用master theorem算出来是O(n)

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

: 用快速排序的思想，解决求第k大数或者前k大数之类的问题。
: 算法导论上有说

H*y2010-12-10 08:12

24 楼

A*o2010-12-10 08:12

25 楼

这个access pattern都知道了，怎么读就怎么存，有什么问题吗？

横向移动access的是连续的空间, 不会cache miss,纵向移动access的是不连续的空间,
会cache miss, 怎样minimize求牛人解答一下

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

: 横向移动access的是连续的空间, 不会cache miss,
: 纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
: 求牛人解答一下

H*y2010-12-10 08:12

26 楼

h*y2010-12-10 08:12

27 楼

我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

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

: 用两个矩阵如何？ A和A's transpose.
: 横向的时候用A，纵向的时候iterate rows in A's transpose

H*y2010-12-10 08:12

28 楼

A*o2010-12-10 08:12

29 楼

记得算法课教的是划分程block，按block转置，一个block可以放进cache. 还有一种递
归cache oblivious的方法，思想是一样的

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

: 我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

A*h2010-12-10 08:12

30 楼

like the 3rd one.

p*y2010-12-10 08:12

31 楼

我觉得他想要的答案是建立二维数组的时候用线性空间。
A[0][0],A[1][0]...A[n][0]地址相邻的那种。

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

: 我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

l*a2010-12-10 08:12

32 楼

dislike the 3rd. like the 2nd

【在 A****h 的大作中提到】

: like the 3rd one.

a*e2010-12-10 08:12

33 楼

请问500 numbers appear twice怎么做？ hash table?

how
memory

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

h*s2010-12-10 08:12

34 楼

I like 3

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

: dislike the 3rd. like the 2nd

p*u2010-12-10 08:12

35 楼

感觉这个答案挺好的

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

: 记得算法课教的是划分程block，按block转置，一个block可以放进cache. 还有一种递
: 归cache oblivious的方法，思想是一样的

C*y2010-12-10 08:12

36 楼

头是2470

c*p2010-12-10 08:12

37 楼

为什么我觉得你的题目有点难呢？特殊的组么？

h*y2010-12-10 08:12

38 楼

恩, 多于2个就只能hash了吧

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

: 请问500 numbers appear twice怎么做？ hash table?
:
: how
: memory

h*y2010-12-10 08:12

39 楼

AWS面的, 最后的offer是可以自己选组的的

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

: 为什么我觉得你的题目有点难呢？特殊的组么？

c*p2010-12-10 08:12

40 楼

可是感觉你的题好难啊。。。

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

: AWS面的, 最后的offer是可以自己选组的的

h*y2010-12-10 08:12

41 楼

2个月前面的, 现在来攒攒人品
电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
1. from 1 to N one number appear twice, others once, find that number, (how
about two numbers? 500 numbers appear twice?)
2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
也可以linear搞定, 真汗
3. how DNS return IP lookup request.
4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
not, how to fix it?
onsite
1. 一个矩阵, 把所有非0元素按connected component分组打印出来, 4-neighbors算连通
2. thesis presentation
3. design spreadsheet, 每个单元格可以是int, 可以是对其他单元格的引用, 可以是
算术表达式, 加减乘除, 表达式中可以有对其他单元格的引用, 要能把值求出来, 这题
居然是lunch interview, 真啃爹, 饭都没吃完
4. design chess game, 人机对战
5. print matrix in spiral order. 这个简单, 但是follow up搞不定, how to
minimize cache misses when you go downward and upward?
6. leetcode, jump game II
onsite六轮面试之间连break都没有
BTW: 因为根本没有网申阿妈总, 本来以为是2月份campus job fair投的, 结果一看他
们手里的简历才知道, 2011年2月找实习的时候投的...

l*a2010-12-10 08:12

42 楼

onsite 5的followup翻译成汉语贝？

how

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

h*y2010-12-10 08:12

43 楼

横向移动access的是连续的空间, 不会cache miss,
纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
求牛人解答一下

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

: onsite 5的followup翻译成汉语贝？
:
: how

d*e2010-12-10 08:12

44 楼

电面2真的不知道，可以说说吗？谢谢。

how
memory

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

h*y2010-12-10 08:12

45 楼

double find_kth_largest_unknown_length(istringstream &sin, int k)
{
vector vec;
double x;
while (sin >> x)
{
vec.emplace_back(x);
if (vec.size() == (k << 1) - 1)
{
nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater
());
vec.resize(k);
}
}
nth_element(vec.begin(), vec.begin()+k-1, vec.end(), greater());
return vec[k-1];
}

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

: 电面2真的不知道，可以说说吗？谢谢。
:
: how
: memory

d*e2010-12-10 08:12

46 楼

nth_element()是什么函数？greater又是什么？
另外你原题说的是返回k个数字，但你下面是返回第k个数字?

greater

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

: double find_kth_largest_unknown_length(istringstream &sin, int k)
: {
: vector vec;
: double x;
: while (sin >> x)
: {
: vec.emplace_back(x);
: if (vec.size() == (k << 1) - 1)
: {
: nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater

m*u2010-12-10 08:12

47 楼

用长度为k的minheap？

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

: nth_element()是什么函数？greater又是什么？
: 另外你原题说的是返回k个数字，但你下面是返回第k个数字?
:
: greater

h*y2010-12-10 08:12

48 楼

那是nlogk, 可以做到和k无关的

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

: 用长度为k的minheap？

h*y2010-12-10 08:12

49 楼

我贴的是EPI上求最大第K个数的答案, 本质是一样的

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

: nth_element()是什么函数？greater又是什么？
: 另外你原题说的是返回k个数字，但你下面是返回第k个数字?
:
: greater

p*u2010-12-10 08:12

50 楼

用快速排序的思想，解决求第k大数或者前k大数之类的问题。
算法导论上有说

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

: 电面2真的不知道，可以说说吗？谢谢。
:
: how
: memory

r*92010-12-10 08:12

51 楼

用两个矩阵如何？ A和A's transpose.
横向的时候用A，纵向的时候iterate rows in A's transpose

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

: 横向移动access的是连续的空间, 不会cache miss,
: 纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
: 求牛人解答一下

d*e2010-12-10 08:12

52 楼

quickselect我知道，但我直觉一直觉得quickselect是O(N log N)的算法，不过我没仔
细算，可能用master theorem算出来是O(n)

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

: 用快速排序的思想，解决求第k大数或者前k大数之类的问题。
: 算法导论上有说

A*o2010-12-10 08:12

53 楼

这个access pattern都知道了，怎么读就怎么存，有什么问题吗？

横向移动access的是连续的空间, 不会cache miss,纵向移动access的是不连续的空间,
会cache miss, 怎样minimize求牛人解答一下

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

: 横向移动access的是连续的空间, 不会cache miss,
: 纵向移动access的是不连续的空间, 会cache miss, 怎样minimize
: 求牛人解答一下

h*y2010-12-10 08:12

54 楼

我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

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

: 用两个矩阵如何？ A和A's transpose.
: 横向的时候用A，纵向的时候iterate rows in A's transpose

A*o2010-12-10 08:12

55 楼

记得算法课教的是划分程block，按block转置，一个block可以放进cache. 还有一种递
归cache oblivious的方法，思想是一样的

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

: 我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

p*y2010-12-10 08:12

56 楼

我觉得他想要的答案是建立二维数组的时候用线性空间。
A[0][0],A[1][0]...A[n][0]地址相邻的那种。

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

: 我就是这么答的, 面试官说好吧, 那讲讲做转置时怎么minimize cache miss

a*e2010-12-10 08:12

57 楼

请问500 numbers appear twice怎么做？ hash table?

how
memory

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

: 2个月前面的, 现在来攒攒人品
: 电面(45分钟, 前3题描述算法就行, 只有最后一题写code)
: 1. from 1 to N one number appear twice, others once, find that number, (how
: about two numbers? 500 numbers appear twice?)
: 2. a billion number, find K smallest numbers . 面试官居然不知道不fit memory
: 也可以linear搞定, 真汗
: 3. how DNS return IP lookup request.
: 4. write atoi, allow input 1200.00, not 1200.01, can you handle -2^31? if
: not, how to fix it?
: onsite

p*u2010-12-10 08:12

58 楼

感觉这个答案挺好的

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

: 记得算法课教的是划分程block，按block转置，一个block可以放进cache. 还有一种递
: 归cache oblivious的方法，思想是一样的

c*p2010-12-10 08:12

59 楼

为什么我觉得你的题目有点难呢？特殊的组么？

h*y2010-12-10 08:12

60 楼

恩, 多于2个就只能hash了吧

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

: 请问500 numbers appear twice怎么做？ hash table?
:
: how
: memory

h*y2010-12-10 08:12

61 楼

AWS面的, 最后的offer是可以自己选组的的

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

: 为什么我觉得你的题目有点难呢？特殊的组么？

c*p2010-12-10 08:12

62 楼

可是感觉你的题好难啊。。。

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

: AWS面的, 最后的offer是可以自己选组的的

q*w2010-12-10 08:12

63 楼

如果输入是数组都话感觉可以inplace做．
因为所有数都是属于１－N的，假设k个数twice，输入数组都长度肯定是N + Ｋ．然后
就想变换方法让最后k的数都是出现２次的数。

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

: 恩, 多于2个就只能hash了吧

s*d2010-12-10 08:12

64 楼

A[i] != i的话就和 A[A[i]] 如果不相等的话互换，直到相等，或者越界，或者 A[A[i
]] == A[i]
最后再扫描一次如果A[i] ！= A[A[i]] 就输出
时间O(N) 空间 O(1)

【在 q*****w 的大作中提到】

: 如果输入是数组都话感觉可以inplace做．
: 因为所有数都是属于１－N的，假设k个数twice，输入数组都长度肯定是N + Ｋ．然后
: 就想变换方法让最后k的数都是出现２次的数。

s*d2010-12-10 08:12

65 楼

也要面A，不是Apple，攒人品
#define N 1000
// 多少个重复的都可以
#define DU 7
int _tmain(int argc, _TCHAR* argv[])
{
vector v;
int i,j;
for(i = 0; i<=N; i++)
v.push_back(i);
for(i = 0; i<=DU; i++)
v.push_back(i);
random_shuffle(v.begin(), v.end());
copy(v.begin(), v.end(), ostream_iterator(std::cout, " "));
cout<for(i=0;i{
while(v[i] != i && v[v[i]] != v[i])
swap(v[i], v[v[i]]);
}
copy(v.begin()+N+1, v.end(), ostream_iterator(std::cout, " "));
cout<return 0;
}
关键就是
for(i=0;i{
while(v[i] != i && v[v[i]] != v[i])
swap(v[i], v[v[i]]);
}

b*r2010-12-10 08:12

66 楼

多谢！

b*f2010-12-10 08:12

67 楼

Mark