一亩三分地论坛

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

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

Uber 电面

[复制链接] |试试Instant~ |关注本帖
yyy884849 发表于 2015-11-24 06:34:14 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
uber两次电面面经一面:上上周好像是。Pig Latin. https://en.wikipedia.org/wiki/Pig_Latin
规则没有那么多,分了好几问update的问的,当时没有搞得特别清楚,代码写的惨不忍睹,幸好还有二面。

二面:刚刚
1. find occurence_time,就是一个排序好的int array里,让你找某个int出现的个数。比如[1 1 1 2 2 3 3], search 1, return 3. 我说binary search找到以后然后linear扫,worst case O(n). 他问有没有更快的,lgn的,想了半天没想出来,然后我说,让我先把这个东西码出来吧,然后码完他也没再问。
2. 设计Cache。扯完cache最基本的设计,写完hashmap以后,面试官问怎么expire cache。想演一演在往LRU上靠,结果。。。渣一般的演技。。。演了三分钟实在演不下去了,跟他说,我们用doubly linked list吧。面试官说好。然后开始码。码了一半吧,木有码完。

跪求onsite。。。


补充内容 (2015-11-23 19:36):
多谢woaibai.1point3acres缃
http://www.geeksforgeeks.org/cou ... -in-a-sorted-array/

评分

2

查看全部评分

qjunchen 发表于 2015-11-24 06:40:23 | 显示全部楼层
lz加油,祝拿到onsite~
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-24 07:56:02 | 显示全部楼层
find occurence_time 这个,可以binary search两次,第一次找number首先出现的位置i,第二次找最后一次出现的位置j, j-i+1就是次数. more info on 1point3acres.com
http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/
回复 支持 反对

使用道具 举报

 楼主| yyy884849 发表于 2015-11-24 08:33:06 | 显示全部楼层
woaibai 发表于 2015-11-23 18:56
find occurence_time 这个,可以binary search两次,第一次找number首先出现的位置i,第二次找最后一次出现 ...

哦,是哦
之前做这种问题的时候都是从中间直接往两边开撸的,没多想
受教了
回复 支持 反对

使用道具 举报

 楼主| yyy884849 发表于 2015-11-24 08:35:50 | 显示全部楼层
多谢woaibai
回复 支持 反对

使用道具 举报

 楼主| yyy884849 发表于 2015-11-24 08:35:58 | 显示全部楼层
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2015-11-24 14:44:20 | 显示全部楼层
二面的 expire cache 是google的面经题目 需要用到multithread 会涉及一些concurrency的东西
程序里面开一个静态块  用一个新的thread不断的扫 list 把expire的去掉就好了
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2015-11-24 14:47:27 | 显示全部楼层
哦 补充一下 我说的是 time expired cache 不是 Leetcode 的 LRU cache
回复 支持 反对

使用道具 举报

 楼主| yyy884849 发表于 2015-11-25 05:19:34 | 显示全部楼层
aiwojiujiu 发表于 2015-11-24 01:47
哦 补充一下 我说的是 time expired cache 不是 Leetcode 的 LRU cache

恩恩。一开始我也是这么说的,说多用一个hashmap存时间,然后用一个daemon来扫hashmap。但是后来觉得写起来还是LRU好写一点。
应该clarify一下面试官究竟想问什么来着。。。
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2015-11-25 05:21:25 | 显示全部楼层
yyy884849 发表于 2015-11-25 05:19
恩恩。一开始我也是这么说的,说多用一个hashmap存时间,然后用一个daemon来扫hashmap。但是后来觉得写起 ...

嗯 这个应该没关系啦 楼主面的是那个组?
回复 支持 反对

使用道具 举报

 楼主| yyy884849 发表于 2015-11-25 10:20:10 | 显示全部楼层
aiwojiujiu 发表于 2015-11-24 16:21
嗯 这个应该没关系啦 楼主面的是那个组?
. from: 1point3acres.com/bbs
没说大组,只是说是做driver experience的
回复 支持 反对

使用道具 举报

jygan 发表于 2015-12-31 12:59:04 | 显示全部楼层
cache设计那题还要写代码?如果是用multithread的话,面试官是否就会满意
回复 支持 反对

使用道具 举报

jygan 发表于 2016-1-5 06:17:58 | 显示全部楼层
expire  cache, 能否这样设计:
回复 支持 反对

使用道具 举报

jygan 发表于 2016-1-5 06:19:43 | 显示全部楼层
expire  cache, 能否这样设计:.鐣欏璁哄潧-涓浜-涓夊垎鍦
class CacheNode
{
public:
        int key;
        int val;
. 鍥磋鎴戜滑@1point 3 acres        long long timestamp;
        CacheNode()
        {
. 1point3acres.com/bbs
        }
        CacheNode(int _key, int _val, long long _time) :key(_key), val(_val),timestamp(_time)
        {.1point3acres缃

        }
        CacheNode(const CacheNode& node).鏈枃鍘熷垱鑷1point3acres璁哄潧
        {
                key = node.key;
                val = node.val;
                timestamp = node.timestamp;
        }
        CacheNode& operator=(const CacheNode& that)
        {. 1point3acres.com/bbs
                key = that.key;
                val = that.val;
                timestamp = that.timestamp;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
};.1point3acres缃
class ExpireCache. 鍥磋鎴戜滑@1point 3 acres
{
private:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        std::mutex m;
        int maxSize;
        int expiration; //in second
        list<CacheNode> cacheList;
        unordered_map<int, list<CacheNode>::iterator> cache;
public:
.....
};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
另有一个thread 从尾部 扫描 cacheList 把 expired 的删掉
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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