Uber 面试经验【一亩三分地论坛面经版】 - Powered by Discuz!
int random_node(vector<pair<int, int> >& node_array)
{
int total_weight = 0;
int ret = 0;
for (auto node : node_array)
{
total_weight += node.second;
int rand_weight = rand() % total_weight;
// this makes the possibility to select the current node to be (node.second / total_weight)
if (rand_weight >= 0 && rand_weight < node.second)
{. more info on 1point3acres.com
ret = node.first;
}
}
return ret;
}
感觉这种题现在好常考啊，解法好像是建array,然后再用binary search
他后来告诉我不能用额外空间的
我的感觉是先遍历一下list，然后记录总的weights， 然后产生一个random number， 代表weight_th， 最后从头遍历找到weight_th落在哪个node，然后就返回那个node。不知道这样行不行的
Read full article from Uber 面试经验【一亩三分地论坛面经版】 - Powered by Discuz!
| Uber店面. 问了什么是RPC, 怎么实现的. Linux的file system的结构, 最后让我自己设计一个结构可以存很大的file. 接下来是算法题: 有一个很长的list<pair<int, int> > 第一个int 的这个node的序号，第二个int 是这个node 的weight。 写一个函数返回node的序号， 比如 (2, 3)->(3, 5)->(1, 7). 那么返回2的概率是（3／15）， 3的概率是：（5／15），1 的概率 . 1point3acres.com/bbs 补充内容 (2015-9-4 13:12): 算法题，我后来琢磨了一下： Basically divide the input list into two parts. weight = (weithtUntilNow + thisNode.weight), so generate a random number, randWeight = [1, weight]. if this randWeight > |
{
int total_weight = 0;
int ret = 0;
for (auto node : node_array)
{
total_weight += node.second;
int rand_weight = rand() % total_weight;
// this makes the possibility to select the current node to be (node.second / total_weight)
if (rand_weight >= 0 && rand_weight < node.second)
{. more info on 1point3acres.com
ret = node.first;
}
}
return ret;
}
感觉这种题现在好常考啊，解法好像是建array,然后再用binary search
他后来告诉我不能用额外空间的
我的感觉是先遍历一下list，然后记录总的weights， 然后产生一个random number， 代表weight_th， 最后从头遍历找到weight_th落在哪个node，然后就返回那个node。不知道这样行不行的
Read full article from Uber 面试经验【一亩三分地论坛面经版】 - Powered by Discuz!
