近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3776|回复: 13
收起左侧

Uber 电面

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

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

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

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

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

二面:刚刚. from: 1point3acres.com/bbs
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的,想了半天没想出来,然后我说,让我先把这个东西码出来吧,然后码完他也没再问。. 鍥磋鎴戜滑@1point 3 acres
2. 设计Cache。扯完cache最基本的设计,写完hashmap以后,面试官问怎么expire cache。想演一演在往LRU上靠,结果。。。渣一般的演技。。。演了三分钟实在演不下去了,跟他说,我们用doubly linked list吧。面试官说好。然后开始码。码了一半吧,木有码完。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
跪求onsite。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-11-23 19:36):
多谢woaibai
http://www.geeksforgeeks.org/cou ... -in-a-sorted-array/

评分

2

查看全部评分

qjunchen 发表于 2015-11-24 06:40:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
lz加油,祝拿到onsite~
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-24 07:56:02 | 显示全部楼层
关注一亩三分地微博:
Warald
find occurence_time 这个,可以binary search两次,第一次找number首先出现的位置i,第二次找最后一次出现的位置j, j-i+1就是次数. 1point 3acres 璁哄潧
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. 鍥磋鎴戜滑@1point 3 acres
嗯 这个应该没关系啦 楼主面的是那个组?

没说大组,只是说是做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. From 1point 3acres bbs
{
public:
        int key;
        int val;
        long long timestamp;
        CacheNode()
        {

        }
        CacheNode(int _key, int _val, long long _time) :key(_key), val(_val),timestamp(_time). visit 1point3acres.com for more.
        {

        }
        CacheNode(const CacheNode& node)
        {
                key = node.key;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                val = node.val;
                timestamp = node.timestamp;
        }
        CacheNode& operator=(const CacheNode& that)
        {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                key = that.key;
                val = that.val;
                timestamp = that.timestamp;
        }
};
class ExpireCache
{
private:
        std::mutex m;
        int maxSize;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        int expiration; //in second
        list<CacheNode> cacheList;
        unordered_map<int, list<CacheNode>::iterator> cache;
public:
.....
};. more info on 1point3acres.com
另有一个thread 从尾部 扫描 cacheList 把 expired 的删掉
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-27 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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