A9 second round interview intern

A9 advertisement group:
interviewer: Chinese male

5 min introduction and talk about research

50 min data coding

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lly being selected.

5 min for me to ask him questions.

请问第二题怎么做呢？是什么蓄水池算法吗？

神罗天征 发表于 2015-12-16 07:13
请问第二题怎么做呢？是什么蓄水池算法吗？

at the beginning, the one I wrote has high complexity as follows:

您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Then I came up a random.shuffle algorithm.

Permute-By-Sorting(employee_list):
[/i][/i]

kobe24 发表于 2015-12-16 07:28
at the beginning, the one I wrote has high complexity as follows:

def sample(N, M):

Permute-By-Sorting(employee_list):
   n = employee_list.length;
  let P[1...n] be a new array
  for i = 1 to n
     P[i] = RANDOM(1,n^{3});
  sorting employee_list using P as sort keys.

The algorithm is in "Introduction to Algorithm" Book, chapter 5.3 randomized algorithm. you can take a look at it.

kobe24 发表于 2015-12-16 07:31
Permute-By-Sorting(employee_list):
   n = employee_list.length;
  let P[1...n] be a new array

十分感谢！

补充内容 (2015-12-16 07:37):
祝楼主offer~

感谢楼主！请问第一题是 MapReduce 的解法（因为 huge file）还是干算？

I didn't use map-reduce framework. don't save data into array. otherwise it will cost lots of memory