一亩三分地论坛

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

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

uber 电面, 已跪

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

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

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

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

x
. 鍥磋鎴戜滑@1point 3 acres
电面连续被放两次鸽子,第三次跪了。。。

面的Infrastructure组

聊了下project
然后问会不会数据库, Nosql (不会)
用过cloud service吗,AWS之类的 (没有)
用过哪些语言
不知道是不是这些和组不match,所以挂的

就一道题:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
         给定: [“a“,1], ["b",2],  ["c",3]  . 1point3acres.com/bbs
         返回一个string, ”a“的概率1/6, b的概率,2/6, c的概率 3/6

follow up,怎么确定结果是不是对的



鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

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. from: 1point3acres.com/bbs
解决思路应该就是随机数吧, 写一个累积数组,然后随机数(1~6),如果是[1,1],返回a,如果是[2,3],返回b ...

如果数据很大的话,随机生成的是[2,3],你怎么确定对应的是b? 存放的是interval到char的mapping?. Waral 鍗氬鏈夋洿澶氭枃绔,
其实可以换个角度,存放数字到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.         static class  Node {
  3.                 String val;
  4.                 int weight;. visit 1point3acres.com for more.
  5.                 public Node(String val, int i) {
  6.                         this.val = val;
  7.                         this.weight = i;. 鍥磋鎴戜滑@1point 3 acres
  8.                 }
  9.         }
  10.         public static String getRandomWithWeight(Node[] nodes) {
  11.                 for (int i = 1; i < nodes.length; i++) {
  12.                         nodes[i].weight = nodes[i - 1].weight + nodes[i].weight;
  13.                 }
  14.                 int len = nodes.length; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                 double index = Math.random() * nodes[len - 1].weight;
  16.                 int res = binarySearch(index, nodes);
  17.                 return nodes[res].val;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.         }
  19.         private static int binarySearch(double index, Node[] nodes) {. 1point 3acres 璁哄潧
  20.                 int start = 0;
  21.                 int end = nodes.length;
  22.                 while (start + 1 < end) {. 1point3acres.com/bbs
  23.                         int mid = (end - start) / 2 + start;
  24.                         if (nodes[mid].weight  <= index) {
  25.                                 start = mid;
  26.                         } else {
  27.                                 end = mid;
  28.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                 }
  30.                 if (nodes[start].weight > index) {
  31.                         return start;
  32.                 } else {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  33.                         return end;
  34.                 }. 1point 3acres 璁哄潧
  35.         }
  36.        
  37.         public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.                 int countA = 0;
  39.                 int countB = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  40.                 int countC = 0;
  41.                 for (int i = 0; i < 6000; i++) {
  42.                         Node[] nodes = {new Node("a", 1), new Node("b", 2), new Node("c", 3)};
  43.                         String res = getRandomWithWeight(nodes);
  44.                         if (res.equals("a")) {
  45.                                 countA++;
  46.                         } else if (res.equals("b")) {
  47.                                 countB++;
  48.                         } else if (res.equals("c")) {. from: 1point3acres.com/bbs
  49.                                 countC++;
  50.                         }
  51.                 }
  52.                 System.out.println(countA + " " + countB + " " + countC);
  53.         }
  54. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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