一亩三分地论坛

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

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

Uber挂经

[复制链接] |试试Instant~ |关注本帖
liurudahai 发表于 2016-9-14 10:02:42 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Uber - 内推 - Onsite |Fail在职跳槽

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

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

x
第二个ONSITE,第一个TABLEAU已挂
面的西雅图OFFICE
R1,白人大哥,感觉很活跃很多话,人也很NICE,一开始聊PROJECT,然后问了两个超级简单的题,第一个是LEETCODE上的DECODE WAYS, 第二个是NEXT LARGER NODE IN A BST
R2,中国人大哥,感觉话比较少,不太笑,问了一个题,要实现add(key), remove(key), max(),三个函数,add key就是增加这个KEY在你的数据结构里的COUNT, REMOVE(KEY)就是REMOVE掉一个COUNT,MAX就是求目前最大的COUNT,如果有多个值的COUNT都等于最大的COUNT,就要RETURN多个,这个最后用了两个MAP和一个HEAP做,勉强实现插入Ologn,MAX O1感觉不是很好,不知道大家有没有什么好的方法
R3,三哥,问的DESIGN, DESIGN FILE SYstem,要实现GETFILE(PATH)和PUTFILE(PATH, CONTENT)两个API,我对这个经验不是很多,感觉这一轮面的不好,很可能是他黑我了,他一直在跟我纠结如果是大FILE,然后网速不够那么从CLIENT到SERVICE LAYER,这个FILE要怎么传输,我说把他分成很多小份依次传输,然后他说万一其中某一小份传输失败了,那怎么办,我说RETRY,然后他说到底是RETRY全部的还是RETRY其中一部分的,我把大数据估算完,画好框架图之后,后面有一多半时间都在纠结这个,不知道大家有没有什么好的建议
R4,三哥MANAGER, 问设计一个UBER SERVICE,包括一个API top(string city),要求RETURN这个CITY的过去7天完成TRIP总数TOP 10个DRIVER。给你的包括一个已经实现的DRIVER SERVICE,里面DRIVER和对应的城市,且已经有INDEX,也就是给一个城市,然后RETURN他所有的DRIVER速度会比较快,另外给一个TRIP SERVICE,里面包括所有的TRIP的所有信息,但是没有任何INDEX,我的做法是用一个DISTRIBUTED MAP,然后TRIP SERVICE可以SUBSCRIBE,然后每完成一个TRIP,在对应的城市对应的DRIVER 对应的天的TRIP+1,然后超过7天老数据就EXPIRE,然后用这个DISTRIBUTED HASHMAP统计,从他的表情我没看出来他认为我对还是不对,但就转移到聊其他的,感觉聊得挺开心,他还问我TIMELINE是怎么样的,有没有其他公司的DEADLINE,我感觉他好像是想要我,没想到FAIL了
R5,白人大哥,比较严肃,完全问BEHAVIOR和项目
. 鍥磋鎴戜滑@1point 3 acres
R2, R3, R4我觉得大家可以讨论讨论

评分

2

查看全部评分

wtcupup 发表于 2016-9-14 10:54:46 | 显示全部楼层
楼主讲讲第二轮 的那个 两个hashmap分别有啥作用?
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-9-14 23:39:13 | 显示全部楼层
wtcupup 发表于 2016-9-14 10:54
楼主讲讲第二轮 的那个 两个hashmap分别有啥作用?

这题当时比较纠结,然后他提示我用HEAP做,然后就一个HASHMAP存KEY和(KEY, COUNT)的HEAP NODE,然后放入HEAP里去,但是有一个问题,就是如果有多个相同的COUNT都是最大COUNT怎么办,因为HEAP只有看TOP的功能,没有说看TOP K的功能,然后我当时写的就是把HEAP顶端一个一个POP出来,直到顶端的COUNT比上一个POP出来的小,然后RETURN所有的值,然后把这些都塞回去。然后那个大哥觉得做得不好,让我优化这一部分,然后我就想到用两个MAP
第一个MAP,存KEY和COUNT,第二个MAP存COUNT和HEAP NODE, HEAP NODE包括一个COUNT和所有这个COUNT的KEY的一个HASHSET,每次新来一个KEY或者REMOVE一次KEY,更新COUNT,然后把他从第二个MAP中旧的COUNT他的SET里拿出来,放入更高的或者更低的COUNT的SET里,如果更高的COUNT的SET没有,就新建一个,如果这个KEY是这个COUNT的最后一个KEY,就REMOVE掉这个ENTRY,HEAP还是根据COUNT排序,这样最顶上的那个HEAP NODE里就会有所有这个COUNT的所有的KEY的一个SET,RETURN那个SET就行
那个中国大哥不怎么说话,反应比较慢,最后也没有表情,不知道是认可还是不认可
回复 支持 反对

使用道具 举报

The8023 发表于 2016-9-17 04:46:25 | 显示全部楼层
My idea is: (zai gong si bu neng da zhong wen = =.)
2hashmap + 1 heap,      
One HashMap <Integer, Integer>    key, count
One HashMap<Integer, List<Integer>>    count,  list of keys with that count

One Heap <Integer>,  store count,

add(),  if no new count , O(1),  if there is a new count, you need to insert to Heap,  O(logn);
remove()  if no need to remove count from heap, O(1), otherwise, O(logn)
max(),  O(1) , countMap.get(heap.peek())

回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-17 05:18:13 | 显示全部楼层
求问楼主像R3这种系统设计应该怎么准备啊? 看了一下你的题目 一头雾水啊, 还涉及网络方面的?
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-9-17 05:58:46 | 显示全部楼层
R2基本思路是HashHeap。定义一个wrapper用来存,count,index(heap中的位置)和属于同一个count的keys。Heap里面存Wrapper,根据count来决定顺序。另外加一个HashMap<Integer, Wrapper> 方面根据key来索引。

class Wrapper {-google 1point3acres
    int count;
    int idx;
    HashSet<Integer> keys;
}
回复 支持 反对

使用道具 举报

cococecil 发表于 2016-9-17 06:01:43 | 显示全部楼层
heap要自己实现吗?
如果是自己实现的,可以不需要count那个hashmap,root是max,从root往下找,如果有任意child也是max就继续往下。
回复 支持 反对

使用道具 举报

dianek 发表于 2016-9-17 06:23:19 | 显示全部楼层
R3主要是考你FTP斷點續傳和對文件系統的了解。

已經提示網路帶寬很小,所以不能用很多TCP連接。TCP連接會斷,所以需要設計控制協議。一般用服務器上文件的filesize作為進度。
. 鍥磋鎴戜滑@1point 3 acres
FTP或HTTP單線程上傳,FTP用一個控制TCP一個數據TCP,HTTP用HTTP POST。。。連接中斷。。。重新連接,先發控制指令讀取服務器上文件的filesize,調整FTP文件上傳的offset,移動fp指針到offset,然後繼續上傳。HTTP可以使用Range header指明file range,HTTP response是206 Partial File,而不是200 OK

不需要把文件切成小份,因為網路慢,切成小份也沒用。而且小文件會佔用控制TCP連接的帶寬,客戶端需要切文件,服務器需要組裝,效率太低
TCP自帶checksum,誤碼率很低,不需要切文件後自己再寫checksum檢查
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-17 08:07:46 来自手机 | 显示全部楼层
楼主你面的new grad么
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-9-17 09:19:24 | 显示全部楼层
liurudahai 发表于 2016-9-14 23:39 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这题当时比较纠结,然后他提示我用HEAP做,然后就一个HASHMAP存KEY和(KEY, COUNT)的HEAP NODE,然后放 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你好,没有看懂没次操作你是如何更新heap的,能详细说说吗? heap怎么实现的? 感谢!
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-9-17 09:23:37 | 显示全部楼层
The8023 发表于 2016-9-17 04:46
.鐣欏璁哄潧-涓浜-涓夊垎鍦My idea is: (zai gong si bu neng da zhong wen = =.)
2hashmap + 1 heap,      . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
One HashMap     key,  ...

你好,没有看懂你的解。请问heap是如何更新的呢?
回复 支持 反对

使用道具 举报

Johannazzz 发表于 2016-9-18 02:32:20 | 显示全部楼层
cococecil 发表于 2016-9-17 06:01
heap要自己实现吗?
如果是自己实现的,可以不需要count那个hashmap,root是max,从root往下找,如果有任 ...
. From 1point 3acres bbs
同意自己实现heap要容易一些,加一个返回多个最大值的函数,这样一个heap,一个map<key, index>就可以了
回复 支持 反对

使用道具 举报

dydcfg 发表于 2016-9-18 03:29:16 | 显示全部楼层
第二题可以做到add/remove/max都是O(1)
list<pair<int,list<int>>> dataList;
unordered_map<int,pair<list<pair<int,list<int>>>::iterator,list<int>::iterator>> hashTable;

dataList是链表,表头的int存,count数后面的list跟具有这个count数的key.. 1point 3acres 璁哄潧
hashTable的key是题目里的key,value.first是指向key所在链表的表头,value.second指向key所在链表的元素位置.

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴add的时候通过hashTable删除链表里的位置,然后加入到后一个表头的链表里,remove差不多.max返回最后一个非空链表就可以.几个操作都是O(1)
回复 支持 反对

使用道具 举报

Johannazzz 发表于 2016-9-18 04:38:11 | 显示全部楼层
第二题经楼上启发,写了一个更易读的版本,ordered double linked list + hashmap, add/remove/max都是O(1)
class Node {
       int count;
       unordered_set<int> keys;
};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
list<Node> nodes;
unordered_map<int, list<Node>::iterator> mp;
如果按count从大到小排,max返回头节点里的keys,插入把key移到上一个node里或新建一个node,删除类似
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-9-20 00:58:26 | 显示全部楼层
yangmyfly 发表于 2016-9-17 08:07 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主你面的new grad么

不是,我是在职跳槽,不过在uber和他们聊天的时候,他们都在兴致勃勃的说怎么加班,怎么私下做了很多PROJECT,感觉WORK LIFE BALACNE不太适合我
回复 支持 反对

使用道具 举报

apepkuss 发表于 2016-9-20 01:42:48 | 显示全部楼层
两周前面Snapchat的Test Platform职位的时候,有遇到和你第二题类似的题目。题目是implement get(key), put(key, value) and max() functions of a hash map using BST. 我遇到的这个题目倒是不难,相信楼主也是可以搞定的。
回复 支持 反对

使用道具 举报

mymulife 发表于 2016-9-21 06:22:23 | 显示全部楼层
请问楼主面完多长时间收到结果的?
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-9-21 12:08:01 | 显示全部楼层
mymulife 发表于 2016-9-21 06:22
请问楼主面完多长时间收到结果的?

一天吧,一般第二天开会讨论要不要你
回复 支持 反对

使用道具 举报

whdawn 发表于 2016-9-27 07:20:38 | 显示全部楼层
dianek 发表于 2016-9-16 17:23. visit 1point3acres.com for more.
R3主要是考你FTP斷點續傳和對文件系統的了解。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
已經提示網路帶寬很小,所以不能用很多TCP連接。TCP連接 ...

我感觉更像是在考block和chunk的问题,然后这两个怎么拆分,每个大概多大,然后大文件的chunk和block在server上面怎么存吧
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-10-2 01:26:26 | 显示全部楼层
第二题感觉像 https://leetcode.com/problems/insert-delete-getrandom-o1/
可在每次删除最大的时候update以下max,O(n),但如果不是经常删最大的话期望应该是O(1)吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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