得到Google面试通知，悉尼的C++岗位真难找啊【得到.NET offer】

tristone

原帖由 kuafu 于 27-11-2012 13:16 发表

                               
登录/注册后可看大图

俗话说一个巴掌拍不响。
通常感觉“内部斗争”激烈之人，往往就是斗争的一方。
安分守己、恪守职责，对“斗争”充耳不闻，你还能处在争斗之中吗？

没用。你不算计别人，别人会算计你。这个是我的亲身经历。

guangyang

你要有在Linux or Unix下编程的经验则C++还是好找些的

yangarnet

是的，你说的没错，之所以难，根本原因是我的C++水平的确不行，Linux下的GCC也知道一些，简单makefile也知道怎么写，但是杯具的是知道得都不精深，这个我最大的不足，现在就专门focus在一个方向上干了，不想东想西，到头来什么掌握得都不深就很操蛋了
谢谢你

原帖由 guangyang 于 4-12-2012 04:55 发表

                               
登录/注册后可看大图

你要有在Linux or Unix下编程的经验则C++还是好找些的

Whistler

只能确定 8. 是快速排序变种。。。见 STL std::nth_element。。。

绚丽梦想

偶个人还是认为C＋＋比较牛， 当然一门计算机语言通，其他的都差不多通的，都是自然语言类型的，不是汇编啊。而且google很好啊，如果google要我，我考虑重现编程，貌似N多年木有编程了。提供的面试题目有空看看，偶喜欢啊。谢谢楼主分享

绚丽梦想

1. How do you sort 10 million 7-digit phone numbers with ~1MB RAM? How would you solve this using one pass and no intermediate files? What if 1MB RAM was a firm limit?

10485760＊2＝  2097152
4*7*10000000 ＝470000000   
7位电话号码正好1000万个是从0000000－9999999

思路 10M的7位电话号码，按照数字的2进制的位数需要共为4*7*10M bite（按道理是8位，不过到9么4位也够啊，这个偶随便想想， 1M Ram 的存储空间是 1048576*8bits 数据全部存储进去差不多是内存的35倍，所以一次全放进去的可能性为0。

那么只有一种可能，就是这个10M的电话号码，假如没有重号，就是从0000000－9999999,排序就好了。

[ 本帖最后由 绚丽梦想 于 1-1-2013 00:09 编辑 ]

timebirds

这都是算法题啊。跟啥语言无关。如果你做不好，不是你方向选择错了的问题，也不是你用什么语言编程的问题，是你自己算法和数学弱了一点，米办法，加强吧。话说我这个压根地没搞过计算机的人貌似也有思路的。不过俺是爱好数学建模的人。。。。。

绚丽梦想

2. Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing...why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?
32位整数是-2147483648到2147 483 647
第一问，从头还是循环到最后一个数字，找到的整数做标记，最后留下来的数字就是了。跑死这台计算机  
第二问，把所有数字相加，最后的结果应该是-2147483648 ，如果少掉了的数字，就是相加结果－（－2147483648）

Whistler

强。。。

俺是想的用每一个二进制位表示这个数是否出现过。。。不过 10 million 个二进制位也超过 1MB 了，且不能处理重复情况

[ 本帖最后由 Whistler 于 30-12-2012 13:28 编辑 ]

cais

原帖由 Whistler 于 30-12-2012 13:26 发表

                               
登录/注册后可看大图

强。。。

俺是想的用每一个二进制位表示这个数是否出现过。。。不过 10 million 个二进制位也超过 1MB 了，且不能处理重复情况

7位数，如果算是0-9的话，刚好是10million的不同的组合。这种问题，如果被问到，应该向对方问清楚assumption。看看有没有重复。
1MB通常是指1M bytes，也就是(2^10^10)*256 bits 1024*1024*256。按二进制位数，是够10million个数的。
土一点，大概每个数可以重复16次。就是如果某个数重复太多，可能需要一点技巧处理一下。
估计如果面试时做到这个地步，面试官会提示你一下的。
关键是要提问题的，问清楚假设，再解答的时候，要think aloud，边想边说。

绚丽梦想

Cais,你的回答有误导， 1 byte 只有8个bits,可以表示 0－255的数值。
差之毫厘，失之千里。

cais

嗯，是我没想清楚。8个bits，用了一个来表示有无，只剩下7个bits，最多能代表1M*128个数。差了一半。
这样对吗？

绚丽梦想

cais 还需要解释的清楚一些， 8个bits为什么需要一个Bit来代表有无呢？ 因为是需要排序，所以有无好像不是特别有用的呢。
7个Bit都是2进制的，所以虽然能记数记到127这个值，实际的情况下要表述一个7位的电话号码，一个byte是绝对不够的,一个7位的电话号码，最少也需要24bits ,即3个Bytes 所以1M内存，最多只能存 1M／3  的7位电话号码，最少基本差30倍。

cais

我的想法是用类似于bucket sort或 counting sort的算法。
http://en.wikipedia.org/wiki/Bucket_sort
http://en.wikipedia.org/wiki/Counting_sort
1Mbytes的内存，就是1024*1024*256bits, 用来表示0000000~9999999 (一共10M个不同的值），是足够的。
大概可以用1024*1024*16，就是说每一个byte的地址，加上该byte的前半段（4个bits），就可以表示一个号码。
（其实还多出来1024*1024*4个空位）
这样每个号码就剩下4个bits的空间来做counting (如果是用counting sort的话）。只能表示0～15。
如果这些号码里面，重复不超过15个的话，直接套用counting sort就行了。
如果这个假设不成立，估计要利用到那个多出来的1024*1024*4，还有那些count是0的地址。
怎么样利用，还没想好。大概思路就是用一个1024*1024*10个bits来表示哪一个号码是0个count。
如果是0，那该号码的那个4个bits的空间就可以用来给其它需要额外空间来储存count的号码。
然后，应该有一个具体的规则，从当前号码的值，推出下一个可以利用的空间的值的地址。（这个好像比较麻烦）
希望这个半吊子解答没有误导大家。

这个题，如果是面试当天当场被问到，估计只能说个思路。要完整的用某种语言写出实现，我是不太可能了。
另外，我那天面试，碰到的题目，不像lz列出来的那些那么偏门。算法题都是比较不难的。
大概都是看一下能有个思路，然后剩下的时间都是用来讨论实现的那种。

关键还是我上面说的，要think aloud，问清楚assumption。其实assumption可以朝自己有利的方向问。
比如说，你已经想到一个方法，但是有特殊的assumption, 比如说不重复。你就问这些数是不是不重复。
一般对方会说，不重复怎么做。你就可以开始了。
最后有时间，对方应该会问，如果出现重复呢？这时，如果通过解答过程，你已经想到办法了，就说出来，
想不到的话，也没办法了，但是你最少答出来一部分了。

rickxbx

原帖由 cais 于 1-1-2013 14:52 发表

                               
登录/注册后可看大图

我的想法是用类似于bucket sort或 counting sort的算法。
http://en.wikipedia.org/wiki/Bucket_sort
http://en.wikipedia.org/wiki/Counting_sort
1Mbytes的内存，就是1024*1024*256bits, 用来表示0000000~ ...

为什么是 1024*1024*256？
如果我们把数据缩小1M倍，可能能看的清楚一点：10个只有一位的电话号码，给你一个字节左右的空间，你如何排序？

cais

唉。我想歪了。上面说的不对。
再想想看。

cais

看起来，大家没有一个只读一遍就能解决的办法。bucket sort也要读两遍。
http://www.bing.com/search?q=sort+10+million+phone+numbers

rickxbx

原帖由 cais 于 1-1-2013 17:17 发表

                               
登录/注册后可看大图

看起来，大家没有一个只读一遍就能解决的办法。bucket sort也要读两遍。
http://www.bing.com/search?q=sort+10+million+phone+numbers

The following is what I want to say(in short, it's possible for non-duplicated items, but can't if there's duplication):

http://stackoverflow.com/questio ... m-high-speed-severa

So, there are ~8,000,000 bits in 1MB but if you have arbitrary 7 digit numbers (up to 9,999,999) using a bit vector to do the sort won't work. Similarly, it won't work if some numbers can be repeated because you can only store {0,1} in a bit vector.

But assuming, (what I think your problem is asking) that you have a sequence of integers between 0 and 8,000,000 with no duplicates, you can simply allocate a zeroed array of 8,000,000 bits and then for each number, tick off the corresponding bit in the array. Then outputting the sorted list is simply reading through that array in sequence and outputting the index for each 1 value.

If you are asking the more complex version of the question (0 - 10 million, repeats allowed), then you will need to to sort chunks that fit in ram, store them on disk, and then you can merge these chunks in linear time and streaming (so you don't ever have to store the whole thing in memory).

PS: I don't think there're duplicated phone numbers, so...

cais

原帖由 rickxbx 于 1-1-2013 17:27 发表

                               
登录/注册后可看大图

The following is what I want to say(in short, it's possible for non-duplicated items, but can't if there's duplication):

http://stackoverflow.com/questio ... most-10-million-7-d ...

还是rickxbx看得仔细。phone number的确是已经说明是没有重复的了。
重新看了一下lz的题目，要求只读一遍的，是～1MB，算一下10m/1024/1024/8~=1.19MB，应该也能算是～1MB，符合要求吧。
第二问，是如果1MB是个firm limit，那就只能按那个stackoverflow上说的读两次了。

freespirit

All the best for your new job !!