<
查看: 12792|回复: 8
收起左侧

Pure Storage面经

|只看干货
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (26)
 
 
0% (0)    👎

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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
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.

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();
...
e.register(cb3); // cb3.invoke() right away since event has been fired.

Implement the two methods in both single-thread and multi-thread scenario with mutex;
Single thread:

boolean isFired = false;
Queue<Callback> q = new Queue<Callback>();

void register(Callback cb) {
  if (!isFired) {
    q.enqueue(cb);
  } else {
    cb.invoke();
  }
}

void fire() {
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();
    cb.invoke();
  }

  isFired = true;
}

// if
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
  cb.invoke();
  }

}

// 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();
    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.



评分

参与人数 16大米 +147 收起 理由
beer + 3 The solution is buggy.
phw + 3 很有用的信息!
carol987 + 5 很有用的信息!
slayeraxx + 3 很有用的信息!
lee2009jian + 5 很有用的信息!
ohshout + 3 给你点个赞!
winniecow + 5 很有用的信息!
瑞瑞66 + 10 很有用的信息!

查看全部评分


上一篇:Amazon/AWS@Palo Alto, onsite-4-29-2016
下一篇:FB电面

本帖被以下淘专辑推荐:

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (11)
 
 
8% (1)    👎
You said "because Mutex is not reentrant "

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

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (11)
 
 
8% (1)    👎
jill_8668 发表于 2016-5-18 06:26
You said "because Mutex is not reentrant "

Actually most Mutex is reentrant.  Is it an assumption ...

Sorry, just make it clear. I mean Mutex is recursive lock. (NOT REENTANT)
回复

使用道具 举报

 楼主| faceeater 2016-5-23 12:18:13 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (26)
 
 
0% (0)    👎
Mutex is not reentrant. You can assume that is given by the interviewer.
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (42)
 
 
2% (1)    👎
请问是不是可以问HR考题的大方向?比如concurrency什么的?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
感谢楼主的分享
回复

使用道具 举报

wajch 2017-10-12 13:05:42 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (44)
 
 
0% (0)    👎
多谢lz 紫薯紫薯
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (278)
 
 
2% (7)    👎
不知道楼主还记得吗?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
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (278)
 
 
2% (7)    👎
请问楼主是java选手吗 我在API文档里查不到 mutex 嘞? 这是面试官要求的吗 还是可以用lock这样的? 谢谢!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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