发信人: akak4648 (victor), 信区: JobHunting 标 题: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 15:16:40 2013, 美东) 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap） followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不work, 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个 query的occurrence, 1 2 3 20 10 30 获得第一个数的概率是 20/60. 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（ constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也 有很直接的方法，把累加做个数组就行了，用bst搜素log(n)，当时面试就是有点一根 筋。最后问了问组的情况，听口音感觉是同胞里的一个大牛，希望能水过。（突然想起 来介绍的时候他的名字不像是同胞的） -- ※ 修改:·akak4648 於 Jan 28 16:16:16 2013 修改本文·[FROM: 50.] ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 50.]
发信人: bejing (), 信区: JobHunting 标 题: Re: g电面，上午10点半 发信站: BBS 未名空间站 (Mon Jan 28 15:34:54 2013, 美东) 谢谢分享，第一题是什么意思？ 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？ 【 在 akak4648 (victor) 的大作中提到: 】 : 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap） : followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不 work, : 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。 : 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个 : query的occurrence, : 1 2 3 : 20 10 30 : 获得第一个数的概率是 20/60. : 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（ : constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 130.]
发信人: akak4648 (victor), 信区: JobHunting 标 题: Re: g电面，上午10点半 发信站: BBS 未名空间站 (Mon Jan 28 16:14:47 2013, 美东) 嗯，是的 【 在 bejing () 的大作中提到: 】 : 谢谢分享，第一题是什么意思？ : 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？ : work, -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 50.]
发信人: bejing (), 信区: JobHunting 标 题: Re: g电面，上午10点半 发信站: BBS 未名空间站 (Mon Jan 28 17:07:48 2013, 美东) 谢谢 第二题： 我看你用了binary search找那个数，耗时O（lg n），但是前面把数组累加已经耗时O （n）了， 有没有办法耗时O（lg n）？ 【 在 akak4648 (victor) 的大作中提到: 】 : 嗯，是的 -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 130.]
发信人: justtry (bug free), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 17:21:25 2013, 美东) 第二题: 对于小的 case怎么做阿 比如 1 2 3 20 10 30 那么 frequence 的sum 是 60 那么产生一个 [1 60] 之间的随机数 r 如果 r <= 20 , 返回 1 否则如果 r <=30 ， 返回 2 否则 返回 3 问题是出来一个随机数 r, 怎么有效判断它所在的区间呢？ 【 在 akak4648 (victor) 的大作中提到: 】 : 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap） : followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不 work, : 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。 : 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个 : query的occurrence, : 1 2 3 : 20 10 30 : 获得第一个数的概率是 20/60. : 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（ : constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也 : ................... -- ※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: etpacino (etpacino), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 18:41:45 2013, 美东) 那么多的数累加不会overflow 么？ -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 208.]
发信人: justtry (bug free), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 18:42:17 2013, 美东) 怎么解决阿？ 多谢 【 在 etpacino (etpacino) 的大作中提到: 】 : 那么多的数累加不会overflow 么？ -- ※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: akak4648 (victor), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 19:43:20 2013, 美东) 这是我当场写的，类似的思想是resevior sampling 1 2 3 4 40 30 20 10 int getO(int A[], int n) { //check n <= 1 int ret = 0; int totalweight = A[0]; for(int i = 1; i < n; i++) { totalwieght += A[i]; int p = rand()%totalweight; if(p <= A[i]) ret = i;// } return A[ret]; } 这个方法好处是不需要O（n)的空间，如果是支持多次查询，可以做一个array存累加值 ，比如： 1 2 3 4 40 30 20 10 new array: 40 70 90 100 这样直接rand()%100,判断数落的空间，新建这个array要O(n),后面用binary search查 询,时间复杂度log(n). 大数据确实存在累加over flow,假如total weight远超过int size,而有一个weight就 是1，没法用正常方法取到。有个优化的方法就是对所有weight平均分下，先随机取出 期中一个，然后再进行上面的算法。在计算weight总值的时候要用到大数加减。不过面 试时间有限，这些都是后来想的。。。 【 在 justtry (bug free) 的大作中提到: 】 : 第二题: 对于小的 case怎么做阿 : 比如 : 1 2 3 : 20 10 30 : 那么 frequence 的sum 是 60 : 那么产生一个 [1 60] 之间的随机数 r : 如果 r <= 20 , 返回 1 : 否则如果 r <=30 ， 返回 2 : 否则 返回 3 : 问题是出来一个随机数 r, 怎么有效判断它所在的区间呢？ : ................... -- ※ 修改:·akak4648 於 Jan 28 19:47:45 2013 修改本文·[FROM: 50.] ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 50.]
发信人: pitstop (NSF_xNx), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 19:54:07 2013, 美东) for循环里每次rand一下和for外面rand一次应该概率不同吧？感觉p应该放到外面？ 【 在 akak4648 (victor) 的大作中提到: 】 : 这是我当场写的，类似的思想是resevior sampling : 1 2 3 4 : 40 30 20 10 : int getO(int A[], int n) : { : //check n <= 1 : int ret = 0; : int totalweight = A[0]; : for(int i = 1; i < n; i++) : { : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 76.]
发信人: chym (出远门), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 19:59:39 2013, 美东) 1. Find 1000 popular URLs in a log. 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的 frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个 size为k的min_heap，O（nlogk）。 Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个 machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all URL frequency。这里个人感觉opt 1好一些。 2. Return a query based on the occurrence from a big table。 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是 吧？那个这个其实跟“从一个大文件里随机取出一行”是一样道理的，只不过是加了 occurrence这个条件。思路就是依次从头开始取，然后统计，并且同时计算当前概率， 然后继续下一行。只需要扫描一遍即可。Pseudocode: all_occur = 0; chosen = “”; for (query in table) { this_occur = query.occurence; all_occur += this_occur; if (random(0, all_occur) <= this_occur) chosen = query; } return chosen; 还望大家指点～～ -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 169.]
发信人: chym (出远门), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 20:04:56 2013, 美东) 恩，你这个跟我想的一样。 【 在 akak4648 (victor) 的大作中提到: 】 : 这是我当场写的，类似的思想是resevior sampling : 1 2 3 4 : 40 30 20 10 : int getO(int A[], int n) : { : //check n <= 1 : int ret = 0; : int totalweight = A[0]; : for(int i = 1; i < n; i++) : { : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 169.]
发信人: justtry (bug free), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 20:05:04 2013, 美东) thanks 【 在 chym (出远门) 的大作中提到: 】 : 1. Find 1000 popular URLs in a log. : 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的 : frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个 : size为k的min_heap，O（nlogk）。 : Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每 : 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个 : machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all : URL frequency。这里个人感觉opt 1好一些。 : 2. Return a query based on the occurrence from a big table。 : 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是 : ................... -- ※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: justtry (bug free), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 20:05:40 2013, 美东) thanks. 【 在 akak4648 (victor) 的大作中提到: 】 : 这是我当场写的，类似的思想是resevior sampling : 1 2 3 4 : 40 30 20 10 : int getO(int A[], int n) : { : //check n <= 1 : int ret = 0; : int totalweight = A[0]; : for(int i = 1; i < n; i++) : { : ................... -- ※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: etpacino (etpacino), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 20:13:58 2013, 美东) I think keeping track of the average should solve this problem 【 在 justtry (bug free) 的大作中提到: 】 : 怎么解决阿？ 多谢 -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 208.]
发信人: justtry (bug free), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 20:24:37 2013, 美东) 能更仔细点吗？ thanks. 【 在 etpacino (etpacino) 的大作中提到: 】 I think keeping track of the average should solve this problem 【 在 justtry (bug free) 的大作中提到: 】 : 怎么解决阿？ 多谢 -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: peking2 (scala), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 21:50:53 2013, 美东) 第二题纪录一个总数就可以了吧？ -- http://blog.sina.com.cn/leetcode ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 8.]
发信人: GAGAMA (GAGA), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 22:41:39 2013, 美东) 第2题应该不是你理解的那个意思。 【 在 chym (出远门) 的大作中提到: 】 : 1. Find 1000 popular URLs in a log. : 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的 : frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个 : size为k的min_heap，O（nlogk）。 : Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每 : 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个 : machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all : URL frequency。这里个人感觉opt 1好一些。 : 2. Return a query based on the occurrence from a big table。 : 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 174.]
发信人: runPython (凸-.-), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 23:05:53 2013, 美东) 第一题的followup， 我认为每个machine维持一个大小为K的heap， 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。 【 在 chym (出远门) 的大作中提到: 】 : 1. Find 1000 popular URLs in a log. : 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的 : frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个 : size为k的min_heap，O（nlogk）。 : Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每 : 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个 : machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all : URL frequency。这里个人感觉opt 1好一些。 : 2. Return a query based on the occurrence from a big table。 : 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.]
发信人: YooY (abcdefg), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 23:06:09 2013, 美东) 第一题同一个页面可能在多个机器里吗？ 比如说，一个页面在机器1里有1000个，在机器2里有2000个。所以这个页面的访问数是 3000. 【 在 akak4648 (victor) 的大作中提到: 】 : 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap） : followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不 work, : 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。 : 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个 : query的occurrence, : 1 2 3 : 20 10 30 : 获得第一个数的概率是 20/60. : 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（ : constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 76.]
发信人: YooY (abcdefg), 信区: JobHunting 标 题: Re: g电面，新鲜面经 发信站: BBS 未名空间站 (Mon Jan 28 23:12:23 2013, 美东) 找top K可以用randomized partition, 可以average O(n)吧？ 【 在 chym (出远门) 的大作中提到: 】 : 1. Find 1000 popular URLs in a log. : 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的 : frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个 : size为k的min_heap，O（nlogk）。 : Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每 : 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个 : machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all : URL frequency。这里个人感觉opt 1好一些。 : 2. Return a query based on the occurrence from a big table。 : 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是 : ................... -- ※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 76.]
Site Map - Contact Us - Terms and Conditions - Privacy Policy 版权所有，未名空间（mitbbs.com），since 1996
