一亩三分地论坛

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

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

第一次发面经,Uber电面

[复制链接] |试试Instant~ |关注本帖
bluezebra 发表于 2015-9-16 06:27:58 | 显示全部楼层 |阅读模式

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

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

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

x
同学内推的,hr反馈很快,大概一天。华裔小哥面的,人很nice,regular的面试过程:project,coding,Q&A
上来先问了十分钟project,然后开始coding。
Implement TimeTravelingHashTable的get和insert方法
* TimeTravelingHashTable.鐣欏璁哄潧-涓浜-涓夊垎鍦
* insert(key, value, timestamp)
* get(key, timestamp)
* get(key) // returns value associated with key at latest time

答的一般吧,写出来了但是最后有两个testcase没过,而且不是最优解。
. 1point 3acres 璁哄潧
要是我自己是面试官,应该不会给onsite的机会。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
无所谓啦,心态要好

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴




补充内容 (2015-9-16 07:40):
* insert("k1", "v1", 10)
* get("k1") // returns "v1"
* get("k1", 11) // returns "v1"
* insert("k1", "v2", 20)
* get("k1", 15) // returns "v1"
* get("k1", 11) // returns "v1"
* get("k1", 21)...

评分

1

查看全部评分

本帖被以下淘专辑推荐:

woaibai 发表于 2015-10-12 03:08:14 | 显示全部楼层
用treemap作value:
class keyToBSTMap<K, V>{
        Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();

        public V get(K k, Float time){
                if(keyToBSTMap.containsKey(k) == false) return null;
                if(keyToBSTMap.get(k).containsKey(time))
                        return  keyToBSTMap.get(k).get(time);
                else
                        return  keyToBSTMap.get(k).lowerEntry(time).getValue();
        }

        public void put(K k , Float time, V value){
                if(keyToBSTMap.containsKey(k)) keyToBSTMap.get(k).put(time, value);
                else{
                        TreeMap<Float, V> t = new TreeMap<>();
                        t.put(time, value);
                        keyToBSTMap.put(k, t);
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

                }
                keyToBSTMap.get(k).put(time, value);
        }


}
.鏈枃鍘熷垱鑷1point3acres璁哄潧

回复 支持 6 反对 0

使用道具 举报

f1371342385 发表于 2015-9-16 07:49:11 | 显示全部楼层
LZ,我的想法是开一个hashmap<String, List<Node>> map, node 包括 "v1" "时间"。调用get函数的时候,会有一个list,然后调用这个list的二分查找。这样比暴力的要快点?LZ,你看这个办法怎么样?

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wenqiang88 发表于 2015-9-16 06:35:23 | 显示全部楼层
请问LZ是怎么答的啊?我的想法是用hashmap, 这个map的key就是key, value是另一个hashmap+latest time+value。然后value的hashmap里key是timestamp, value是最终的value.
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 06:37:14 | 显示全部楼层
wenqiang88 发表于 2015-9-16 06:35
请问LZ是怎么答的啊?我的想法是用hashmap, 这个map的key就是key, value是另一个hashmap+latest time+value ...

握手握手,一模一样. 1point 3acres 璁哄潧

补充内容 (2015-9-16 06:38):
不过我觉得这个基本就是brute force了,小哥不是特别满意。坐等楼下大神们给更优解
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-16 06:42:39 | 显示全部楼层
bluezebra 发表于 2015-9-16 06:37
握手握手,一模一样

补充内容 (2015-9-16 06:38):

这样为啥会有2个case不过呢?
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-9-16 06:58:21 | 显示全部楼层
LZ 请问timestamp是什么数据类型?没有理解LZ的题意啊
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:36:22 | 显示全部楼层
wenqiang88 发表于 2015-9-16 06:42
这样为啥会有2个case不过呢?

最后时间不太够了也没有给我时间让我根据不过的case debug。。。
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:39:31 | 显示全部楼层
f1371342385 发表于 2015-9-16 06:58
LZ 请问timestamp是什么数据类型?没有理解LZ的题意啊

timestamp是int。
insert应该比较好理解吧就是直接插入。
. From 1point 3acres bbsget的话如果给明确的timestamp了,就返回比给定的timestamp小并且latest timestamp对应的value
如果没给timestamp就是返回key+latest timestamp的value
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:41:38 | 显示全部楼层
bluezebra 发表于 2015-9-16 07:39
timestamp是int。. visit 1point3acres.com for more.
insert应该比较好理解吧就是直接插入。
get的话如果给明确的timestamp了,就返回比给 ...

可能我描述的不是太清楚,补充了一下原帖。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最后一个example应该return “v2"
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-9-16 07:45:48 | 显示全部楼层
get("k1", 21) 这个应该返回v2吧
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:48:20 | 显示全部楼层
f1371342385 发表于 2015-9-16 07:45
get("k1", 21) 这个应该返回v2吧

恩对的,不好意思原帖没补充上
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-16 08:16:00 | 显示全部楼层

  1. class TimeTravelingHashTable {
  2. public:
  3.     void insert(const string& key, const string& value, int timestamp) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         hashmap[key][timestamp] = value;
  5.     }
  6.     string get(const string& key, int timestamp) {
  7.         auto& times = hashmap[key];. 鍥磋鎴戜滑@1point 3 acres
  8.         auto it = times.upper_bound(timestamp);
  9.         return it->second;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.     }
  11.     string get(const string& key) {
  12.         return hashmap[key].rbegin()->second;
  13.     }
  14. private:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.     unordered_map<string, map<int, string, std::greater<int>>> hashmap;
  16. };
复制代码
用bst存timestamps,查找的时候可以log

补充内容 (2015-9-16 08:17):
第二个get应该是begin而不是rbegin
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 08:32:14 | 显示全部楼层
f1371342385 发表于 2015-9-16 07:49. visit 1point3acres.com for more.
LZ,我的想法是开一个hashmap map, node 包括 "v1" "时间"。调用get函数的时候,会有一个list,然后调用这 ...

我也不是很清楚最优的解法是什么,小哥也并没有说,就直接让我按照我的想法写了。
二分查找肯定比暴搜要省时,不过我一直在想有没有可能在insert的时候直接就用某种构造好一个有序且搜索时满足较低时间复杂度的数据结构。。
我想的是,对于某一个特定数据,一般insert可能就一次,但是get可能会被call很多次。所以我觉得最好的想法是从insert入手,在这里增加一些复杂度,相应的查找的时候可能就会简单一些?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-16 09:30:20 | 显示全部楼层
get(key, timestamp)
get为什么还要time? key不是可以唯一确定value嘛?
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 09:38:58 | 显示全部楼层
hj867955629 发表于 2015-9-16 09:30
get(key, timestamp)
get为什么还要time? key不是可以唯一确定value嘛?

同一个key可能对应多个不同的timestamp
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-16 09:47:12 | 显示全部楼层
bluezebra 发表于 2015-9-16 09:38
同一个key可能对应多个不同的timestamp
. 1point3acres.com/bbs
噢没看清题目。那用一个哈希表,key就是key,value是一个treeset, treeset节点是time和value,这样按照查找time就是o(logn)吧,哈希表得遍历。。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-9-16 10:27:57 | 显示全部楼层
hj867955629 发表于 2015-9-16 09:47
噢没看清题目。那用一个哈希表,key就是key,value是一个treeset, treeset节点是time和value,这样按照查 ...

那么查找的最好时间是O(lgn),除非有更好的办法,但是我暂时没想到有什么更好的办法了来实现O(1)了
回复 支持 反对

使用道具 举报

airwindow 发表于 2015-10-10 22:06:04 | 显示全部楼层
请问lz,为什么get("k)
回复 支持 反对

使用道具 举报

airwindow 发表于 2015-10-10 22:11:04 | 显示全部楼层
请问lz,为什么 get("k1", 11) // returns "v1" 呢? 所以get 这里是返回的是 k1下values中 最后一个value的timestamp满足 "a.timestamp < input.timestamp"么?
回复 支持 反对

使用道具 举报

airwindow 发表于 2015-10-10 22:11:50 | 显示全部楼层
bluezebra 发表于 2015-9-16 07:39
timestamp是int。. 1point 3acres 璁哄潧
insert应该比较好理解吧就是直接插入。.1point3acres缃
get的话如果给明确的timestamp了,就返回比给 ...

刚看到这个回复,不好意思啦!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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