[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 8114|回复: 8
收起左侧

Pure Storage面经

[复制链接] |试试Instant~ |关注本帖
faceeater 发表于 2016-5-1 02:26:04 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类General 硕士 全职@PureStorage - 猎头 - Onsite  | Fail | 在职跳槽

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

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

x
挂了 反正也没签NDA 报复性回报社会 把自己总结的面经po出来 这些题目mitbbs和本版上都讨论过 就那四道题 我只做了两道就挂了 就把这两道的解法贡献出来
Q: Implement set with integers in range {1…N}, implements five operations, add, remove, contains, clear, iterate. There are 3 versions to solve this                   0, 1, 2
v1: using only bucket array with size N+1, the operation costs are:        O(1),O(1),    O(1),     O(N), O(N)    for example: if we add, 2, 0, 1, it will become list:[1, 1, 1]
v2: using only sequential array(store them sequentially in array):         O(1),O(count),O(count),O(1),  O(count)for example: if we add, 2, 0, 1, it will become map: [2, 0, 1] you need to keep an count
v3: achieve best of v1 and v2’s performance:                               O(1),O(1)     O(1),     O(1), O(count)
. 牛人云集,一亩三分地
Note: I was thinking similar to LRU, using array + linkedlist. So that would make add, remove, contains and iterates optimal. But it doesn’t handle clear with O(1).                                                   0, 1, 2       0, 1, 2. visit 1point3acres for more.
The right answer is to use the two array given. For bucket array value, it will be the index in the sequential array. The sequential array value will be the actually value. in the above example it will become list:[1, 2, 0], map[2, 0, 1]
A couple of things to notice: 1) how to remove? remove will not shift the rest of the array front, instead, it will pick the map[toRemove] = map[count - 1]; count—; 2) how to clear: map just need to set count to 0. 3) after clear, because we don’t clear list, how do we know if the list pointer to the map are invalidate or not(this will affect contains and add)? there are two things to consider, #1. if list[x] >= count - 1, then it is definitely invalid; #2 if list[x] < count but it still possible that it’s replaced by other element(e.g. add 2, clear, add 1, now list[2] and list[1] both points to map[0]). So you should also check if map[list[x]] == x.. 1point3acres

Q: Multi thread question: Event class has two methods, void register(Callback cb); void fire(); it should run like this:

Event e = new Event();. 留学申请论坛-一亩三分地
e.register(cb1);// Not invoke until event is fired.
e.register(cb2);// Same
...
e.fire(); // cb1.invoke(); cb2.invoke();. more info on 1point3acres
.... Waral 博客有更多文章,
e.register(cb3); // cb3.invoke() right away since event has been fired.
. visit 1point3acres for more.. 牛人云集,一亩三分地
Implement the two methods in both single-thread and multi-thread scenario with mutex;
Single thread:.1point3acres网

boolean isFired = false;
Queue<Callback> q = new Queue<Callback>();. From 1point 3acres bbs

void register(Callback cb) {
  if (!isFired) {
    q.enqueue(cb);
  } else {
    cb.invoke();
  }
}. 一亩-三分-地,独家发布
. more info on 1point3acres
void fire() {
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();
    cb.invoke();-google 1point3acres
  }.留学论坛-一亩-三分地

  isFired = true;
}
. From 1point 3acres bbs
// if this is used in multi-thread condition, there are a couple of problems: 1) if say register finished if check(isFired = false) and then fire is run and finished(isFired = true), then cb in register is left in the queue without anyone running. Our next iteration can be:
boolean isFired = false;
Queue<Callback> q = new Queue<Callback>();
Mutex m = new Mutex();
void register(Callback cb) {
  m.acquire();. visit 1point3acres for more.
  if (!isFired) {
    q.enqueue(cb);
  } else {
    cb.invoke();
  }
  m.release();
}. visit 1point3acres for more.

void fire() {.本文原创自1point3acres论坛
  m.acquire();
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();-google 1point3acres
    cb.invoke();
  }. from: 1point3acres

  isFired = true;
  m.release();
}.留学论坛-一亩-三分地

// This is good. it will protect the atomicity. But it is slow because invoke could take a long time. But, if we change register to below it won’t work because fire() can be called after if (isFired) check and before m.acquire(); cb is left in the queue again.. 留学申请论坛-一亩三分地

Mutex m = new Mutex();
void register(Callback cb) {
  if (!isFired) {
    m.acquire();
    q.enqueue(cb);. Waral 博客有更多文章,
    m.release();
  } else {
    cb.invoke();
  }
. Waral 博客有更多文章,
}

// Next iteration on register. The reason we put m.release() before cb.invoke() is because invoke() we have no control and it could call this.register again and because Mutex is not reentrant we are going to have a deadlock and b) invoke can take a long time which make everything slower.

void register(Callback cb) {
  m.acquire();
  if (!isFired) {
.1point3acres网    q.enqueue(cb);
    m.release();. 牛人云集,一亩三分地
  } else { 来源一亩.三分地论坛.
    m.release();
    cb.invoke();
  }-google 1point3acres
. 围观我们@1point 3 acres
}

// Now this looks good. We move on to fire(). Same as register, non-reentrant mutex can cause problem again with invoke(). So we should move invoke() outside.
void fire() {
  m.acquire();. 一亩-三分-地,独家发布
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();
    m.release();
    cb.invoke();. Waral 博客有更多文章,
    m.acquire();
  }

  isFired = true;
  m.release();
}

// Summary: exclude invoke() since we have no control; keep boolean isFired consistent with q status(q.isEmpty()), which is achieved by the last acquire and release.
. from: 1point3acres

. 围观我们@1point 3 acres

评分

10

查看全部评分

本帖被以下淘专辑推荐:

jill_8668 发表于 2016-5-18 06:26:09 | 显示全部楼层
You said "because Mutex is not reentrant "

Actually most Mutex is reentrant.  Is it an assumption of the question?

回复 支持 反对

使用道具 举报

jill_8668 发表于 2016-5-18 07:20:07 | 显示全部楼层
jill_8668 发表于 2016-5-18 06:26. 围观我们@1point 3 acres
You said "because Mutex is not reentrant "
. From 1point 3acres bbs-google 1point3acres
Actually most Mutex is reentrant.  Is it an assumption ...

. From 1point 3acres bbsSorry, just make it clear. I mean Mutex is recursive lock. (NOT REENTANT)
回复 支持 反对

使用道具 举报

 楼主| faceeater 发表于 2016-5-23 12:18:13 | 显示全部楼层
Mutex is not reentrant. You can assume that is given by the interviewer.
回复 支持 反对

使用道具 举报

Urumic 发表于 2016-6-2 09:50:18 | 显示全部楼层
请问是不是可以问HR考题的大方向?比如concurrency什么的?
回复 支持 反对

使用道具 举报

jzysheep 发表于 2017-10-12 07:08:59 | 显示全部楼层
感谢楼主的分享
回复 支持 反对

使用道具 举报

changming927 发表于 2017-10-12 13:05:42 | 显示全部楼层
多谢lz 紫薯紫薯
回复 支持 反对

使用道具 举报

瑞瑞66 发表于 2018-3-27 11:28:10 | 显示全部楼层
不知道楼主还记得吗?lol
想请问一下 楼主面的是 java吗
第一步加mutex之后说 “ if we change register to below it won’t work because fire() can be called after if (isFired) check and before m.acquire(); cb is left in the queue again.” 是什么意思吖?

补充内容 (2018-3-30 13:10):
below哦 明白了 sorry
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

瑞瑞66 发表于 2018-3-29 13:24:50 | 显示全部楼层
请问楼主是java选手吗 我在API文档里查不到 mutex 嘞? 这是面试官要求的吗 还是可以用lock这样的? 谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-25 02:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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