一亩三分地论坛

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

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

Pure Storage面经

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

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

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

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

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). 1point 3acres 璁哄潧

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
...
. more info on 1point3acres.come.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>();
. visit 1point3acres.com for more.
void register(Callback cb) {
  if (!isFired) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    q.enqueue(cb);
  } else {
    cb.invoke();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  }
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
void fire() {
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();
    cb.invoke();
  }

  isFired = true;
}

// 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();
  if (!isFired) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    q.enqueue(cb);
  } else {. 1point3acres.com/bbs
    cb.invoke();
  }
  m.release();
}. 1point 3acres 璁哄潧

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

  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();. Waral 鍗氬鏈夋洿澶氭枃绔,
    q.enqueue(cb);.鐣欏璁哄潧-涓浜-涓夊垎鍦
    m.release(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  } else {
    cb.invoke();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  }

}
. from: 1point3acres.com/bbs
// 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.. visit 1point3acres.com for more.

void register(Callback cb) {
  m.acquire();. From 1point 3acres bbs
  if (!isFired) {
    q.enqueue(cb);
    m.release();
  } else {
    m.release();
    cb.invoke();
  }.鏈枃鍘熷垱鑷1point3acres璁哄潧

}

// 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() {. 鍥磋鎴戜滑@1point 3 acres
  m.acquire();. 鍥磋鎴戜滑@1point 3 acres
  while(!q.isEmpty()) {
    Callback cb = q.dequeue();
    m.release();
    cb.invoke();
    m.acquire();
  }. more info on 1point3acres.com

  isFired = true;
  m.release();
}. from: 1point3acres.com/bbs

// 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 1point 3acres bbs
. from: 1point3acres.com/bbs

评分

3

查看全部评分

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
You said "because Mutex is not reentrant "
. more info on 1point3acres.com
Actually most Mutex is reentrant.  Is it an assumption ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Sorry, 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什么的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-20 03:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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