一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1225|回复: 5
收起左侧

uber 电面, 已跪

[复制链接] |试试Instant~ |关注本帖
caigaa 发表于 2015-11-8 06:35:34 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Uber - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
-google 1point3acres
电面连续被放两次鸽子,第三次跪了。。。

面的Infrastructure组
. from: 1point3acres.com/bbs
聊了下project
然后问会不会数据库, Nosql (不会)
用过cloud service吗,AWS之类的 (没有)
用过哪些语言
不知道是不是这些和组不match,所以挂的
. 鍥磋鎴戜滑@1point 3 acres
就一道题:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
         给定: [“a“,1], ["b",2],  ["c",3]  
         返回一个string, ”a“的概率1/6, b的概率,2/6, c的概率 3/6

follow up,怎么确定结果是不是对的. visit 1point3acres.com for more.




评分

1

查看全部评分

rayord 发表于 2015-11-8 06:42:59 | 显示全部楼层
解决思路应该就是随机数吧, 写一个累积数组,然后随机数(1~6),如果是[1,1],返回a,如果是[2,3],返回b,如果是[4,6],返回c. follow up: 运行10000次,统计输出结果,计算下概率看符合不应该就可以了。Uber好像都是算法+测试用例。
回复 支持 反对

使用道具 举报

 楼主| caigaa 发表于 2015-11-8 06:46:17 | 显示全部楼层
rayord 发表于 2015-11-8 06:42. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
解决思路应该就是随机数吧, 写一个累积数组,然后随机数(1~6),如果是[1,1],返回a,如果是[2,3],返回b ...

我就是这个思路做的。中间编译程序发现了两个typo。。。汗,太大意了
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-11-29 01:10:15 | 显示全部楼层
啥都不会真的是蛋疼,LZ后来如哪儿了
回复 支持 反对

使用道具 举报

returning 发表于 2016-1-27 14:28:10 | 显示全部楼层
rayord 发表于 2015-11-8 06:42
解决思路应该就是随机数吧, 写一个累积数组,然后随机数(1~6),如果是[1,1],返回a,如果是[2,3],返回b ...
. 鍥磋鎴戜滑@1point 3 acres
如果数据很大的话,随机生成的是[2,3],你怎么确定对应的是b? 存放的是interval到char的mapping?
其实可以换个角度,存放数字到char的mapping,1->a, 3->b,6->c, 然后随机生成float数,如果在0-1之间就返回a, 1-3之间就返回b,3-6之间就返回c,所以就是binary search了。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-7 11:39:34 | 显示全部楼层
写了下code,
  1. public class RandomWithWeight {
  2. -google 1point3acres
  3.         static class  Node {
  4.                 String val;
  5.                 int weight;. 鍥磋鎴戜滑@1point 3 acres
  6.                 public Node(String val, int i) {
  7.                         this.val = val;
  8.                         this.weight = i;. visit 1point3acres.com for more.
  9.                 }
  10.         }
  11.         public static String getRandomWithWeight(Node[] nodes) {
  12.                 for (int i = 1; i < nodes.length; i++) {
  13.                         nodes[i].weight = nodes[i - 1].weight + nodes[i].weight;
  14.                 }
  15.                 int len = nodes.length;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.                 double index = Math.random() * nodes[len - 1].weight;
  17.                 int res = binarySearch(index, nodes);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.                 return nodes[res].val;
  19.         }
  20.         private static int binarySearch(double index, Node[] nodes) {
  21.                 int start = 0;
  22.                 int end = nodes.length;
  23.                 while (start + 1 < end) {
  24.                         int mid = (end - start) / 2 + start;
  25.                         if (nodes[mid].weight  <= index) {
  26.                                 start = mid;
  27.                         } else {
  28.                                 end = mid;
  29.                         }
  30.                 }
  31.                 if (nodes[start].weight > index) {
  32.                         return start;
  33.                 } else {. From 1point 3acres bbs
  34.                         return end;
  35.                 }
  36.         }
  37.        
  38.         public static void main(String[] args) {. 鍥磋鎴戜滑@1point 3 acres
  39.                 int countA = 0;
  40.                 int countB = 0;. visit 1point3acres.com for more.
  41.                 int countC = 0;
  42.                 for (int i = 0; i < 6000; i++) {
  43.                         Node[] nodes = {new Node("a", 1), new Node("b", 2), new Node("c", 3)};
  44.                         String res = getRandomWithWeight(nodes);
  45.                         if (res.equals("a")) {
  46.                                 countA++;
    . 1point 3acres 璁哄潧
  47.                         } else if (res.equals("b")) {
  48.                                 countB++;
  49.                         } else if (res.equals("c")) {
  50.                                 countC++;
  51.                         }
  52.                 }.1point3acres缃
  53.                 System.out.println(countA + " " + countB + " " + countC);. from: 1point3acres.com/bbs
  54.         }
  55. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-22 22:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表