一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 445|回复: 21
收起左侧

Apple on-site面试

[复制链接] |试试Instant~ |关注本帖
james9102 发表于 5 天前 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 博士 全职@Apple - 校园招聘会 - Onsite |Failfresh grad应届毕业生

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

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

x
Apple on-site面试,主要过程是先问项目经历,然后面试官问一些奇奇怪怪的题目...这里是其中印象最深的几道题目:

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1  推导Convolutional Neural Network以及BackwardPropagation
2. 给定一个32-bit integer,实现打印其binary形式。要求从左向右扫描,只扫一遍。
void print_binary( int num )
3. linkedlistinsert一个node,要求thread-safe

刚收到邮件,题主跪了...求大米!求安慰!

chuck1212 发表于 5 天前 | 显示全部楼层
LZ面的是哪个组啊?看起来像machine learning engineer?
回复 支持 1 反对 0

使用道具 举报

 楼主| james9102 发表于 5 天前 | 显示全部楼层
GPU Software team
回复 支持 反对

使用道具 举报

say543 发表于 5 天前 | 显示全部楼层
neural network 是 要白板推倒backwardpropagation 吗...... 要thread safe的话 是要insert 到list 任何位置?
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
say543 发表于 2017-12-6 16:19
neural network 是 要白板推倒backwardpropagation 吗...... 要thread safe的话 是要insert 到list 任何位 ...

1. 是白板推导,但是可以用一个非常简单的example来demo。
3. 是insert到任何位置。但这个不是重点,你可以就实现一个
void insert( ListNode* cur, ListNode* new_node ) 这样的routine。重点是如何保证多线程insert仍然是safe的
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
james9102 发表于 2017-12-7 00:23
1. 是白板推导,但是可以用一个非常简单的example来demo。
3. 是insert到任何位置。但这个不是重点,你 ...

直接吧整个list都锁起来在操作不行么
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 09:46
直接吧整个list都锁起来在操作不行么
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我就这么答的,面试官说这样不efficient...
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
james9102 发表于 2017-12-7 09:51
我就这么答的,面试官说这样不efficient...

他想每个node都弄个锁么?这个东西都是trade off,每个都加个锁也不现实
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 10:00
他想每个node都弄个锁么?这个东西都是trade off,每个都加个锁也不现实

肯定是有trade-off。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
insert一个node时,有两步:
new_node->next = cur->next;
cur->next = new_node;
第二步是要考虑多线程的地方(可能有多个node改cur), 第一步肯定是单线程操作.
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
第一步不加锁也有风险的

你刚assign 了 cur->next, 执行下一步之前, cur这个node就被删掉了
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 10:15
第一步不加锁也有风险的
. 1point 3acres 璁哄潧
你刚assign 了 cur->next, 执行下一步之前, cur这个node就被删掉了

这是这道题比较tricky的地方,insert一个new_node B在cur后面, cur不会被删掉(这里只有insert操作,没有delete).
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你要保证如果同时另一个线程也想insert一个new_node B在cur后面,上面的第二步能保证new_node A和new_node B无干扰, 能形成. visit 1point3acres.com for more.
cur->new_node_A->new_node_B-> (cur_node->next)
或者. From 1point 3acres bbs
cur->new_node_B->new_node_A-> (cur_node->next)
这样的链表
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
就算不删吧

node A执行了第一行,.鐣欏璁哄潧-涓浜-涓夊垎鍦
node B也执行了第一行

然后node A才开始执行第二行
执行完 nodeB也开始执行第二行,直接把nodeA的覆盖了

最后变成 cur->node B->next, memory leak了

所以这两行都得放进临界区才行
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 10:43
就算不删吧.鐣欏璁哄潧-涓浜-涓夊垎鍦

node A执行了第一行,

如果有一个满足某些条件就会atomic的swap操作,那就不需要这样了. 这种操作一般硬件会支持.
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
james9102 发表于 2017-12-7 11:44
如果有一个满足某些条件就会atomic的swap操作,那就不需要这样了. 这种操作一般硬件会支持.

网上有用linked list实现lock free的queue,不过用到了compare and swap的 操作
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 11:48
网上有用linked list实现lock free的queue,不过用到了compare and swap的 操作

bingo!同学真是犀利
回复 支持 反对

使用道具 举报

hello_ 发表于 4 天前 | 显示全部楼层
james9102 发表于 2017-12-7 09:51
我就这么答的,面试官说这样不efficient...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
只要求你实现insert( ListNode* cur, ListNode* new_node ),其实是thread-safe list几个操作里最简单的一个,因为给定了插入位置,其实如何找到插入位置,比insert本身要复杂。

给两种思路
1. per-node lock
先lock住cur,再lock住cur->next 如果不是NULL,然后把new_node 插入,最后unlock(cur), unlock(cur->next) 如果不是NULL. from: 1point3acres.com/bbs
关键点是lock的顺序,一定是先cur,再cur->next
如果要找到插入位置,需要hand-over-hand locking

2. lock-free
需要CAS(compare and swap)。基本思路是,
  while(true) {
    next = cur->next;
    new_node->next = next;. 鍥磋鎴戜滑@1point 3 acres
    if (CAS(cur->next, next, new_node)) {
      // succeed, break the retry loop. more info on 1point3acres.com
      break;
    }
    // CAS failed, retry
  }
如果要找到插入位置,从list的头开始traverse就好了,某些特定的architecture里需要加fence,具体情况具体分析
回复 支持 反对

使用道具 举报

hychin 发表于 4 天前 | 显示全部楼层
hello_ 发表于 2017-12-7 12:30
只要求你实现insert( ListNode* cur, ListNode* new_node ),其实是thread-safe list几个操作里最简单的 ...

牛,这个回答不错的,应该能get到面试官的点. From 1point 3acres bbs

第一个如果是循环链表的话,会不会有死锁的风险?
回复 支持 反对

使用道具 举报

 楼主| james9102 发表于 4 天前 | 显示全部楼层
hello_ 发表于 2017-12-7 12:30. 1point 3acres 璁哄潧
只要求你实现insert( ListNode* cur, ListNode* new_node ),其实是thread-safe list几个操作里最简单的 ...
. 1point3acres.com/bbs
大神!敢问大神是做哪个方向research的?在地里看到你报了个Apple的package。

next = cur->next;. Waral 鍗氬鏈夋洿澶氭枃绔,
new_node->next = next;

可以放在loop前面,而不是loop里面
回复 支持 反对

使用道具 举报

hello_ 发表于 4 天前 | 显示全部楼层
james9102 发表于 2017-12-7 12:48
大神!敢问大神是做哪个方向research的?在地里看到你报了个Apple的package。

next = cur->next;

这个应该是必须放在loop里面的,放在前面会有错误. 1point3acres.com/bbs

你想这样一种情况,两个人同时在试图插入,只有一个能成功,而成功之后cur->next会被更新,这时候失败的那一个如果不重新读取cur->next的值,之前成功插入的那个node会丢失,你可以拿纸画一下,就明白是什么情况了

大神不敢当,PhD是做系统相关的,不过好像没什么用,从来没人面试问我这个我问题
回复 支持 反对

使用道具 举报

hello_ 发表于 4 天前 | 显示全部楼层
hychin 发表于 2017-12-7 12:39
牛,这个回答不错的,应该能get到面试官的点
. more info on 1point3acres.com
第一个如果是循环链表的话,会不会有死锁的风险?

不会的,因为所有的lock都是按照同一个顺序来获取的,即使是循环链表,也是同一个方向(比如始终顺时针)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-11 21:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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