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


一亩三分地论坛

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

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

第一次发面经,Uber电面

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

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

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

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

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没过,而且不是最优解。

要是我自己是面试官,应该不会给onsite的机会。。
无所谓啦,心态要好


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


补充内容 (2015-9-16 07:40):
* insert("k1", "v1", 10)
* get("k1") // returns "v1".鏈枃鍘熷垱鑷1point3acres璁哄潧
* 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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
用treemap作value:
class keyToBSTMap<K, V>{
        Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();
.1point3acres缃
        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);
        }


}


回复 支持 6 反对 0

使用道具 举报

yavinci 发表于 2015-12-3 06:16:59 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. import java.util.*;
  2. class TimeTravelingHashTable {

  3.         // <key : <timestamp : value>> = <key: sorted values on timestamp> = <key : treemap>
  4.         HashMap<String, TreeMap<Integer, String>> map = new HashMap<>();
  5.        
  6.         // insert <timestamp, value> into hashmap
  7.         public void insert(String key, String value, int timestamp) {
  8.                 if(map.containsKey(key)) {. visit 1point3acres.com for more.
  9.                         Map<Integer, String> values = map.get(key);
  10.                         values.put(timestamp, value);
  11.                 } else {
  12.                         TreeMap<Integer, String> values = new TreeMap<>();
  13.                         values.put(timestamp, value);
  14.                         map.put(key, values);
  15.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.         }

  17.         // get the floor value on timestamp
  18.         public String get(String key, int timestamp) {
  19.                 if(!map.containsKey(key)) return null;
  20.                 return map.get(key).floorEntry(timestamp).getValue();         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         }
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  22.         // Return the latest value on timestamp
  23.         public String get(String key) {
  24.                 return map.get(key).lastEntry().getValue();
  25.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26. .1point3acres缃
  27.         public static void main(String[] args) {
  28.                 TimeTravelingHashTable hashtable = new TimeTravelingHashTable();
  29.                 hashtable.insert("k1", "v1", 10);
  30.                 hashtable.insert("k1", "v2", 20);
  31.                 hashtable.insert("k2", "v1", 5);
  32.                 hashtable.insert("k2", "v2", 15);
  33.                 System.out.println(hashtable.get("k1"));     //  "v1"
  34.                 System.out.println(hashtable.get("k1", 11)); //  "v1". 鍥磋鎴戜滑@1point 3 acres
  35.                 System.out.println(hashtable.get("k1", 15)); //  "v1"
  36.                 System.out.println(hashtable.get("k1", 11)); //  "v1"
  37.                 System.out.println(hashtable.get("k1", 21)); //  "v2".1point3acres缃
  38.                 System.out.println(hashtable.get("k2", 10)); //  "v1"
  39.                 System.out.println(hashtable.get("k2", 20)); //  "v2"
  40.         }
  41. }
复制代码
回复 支持 1 反对 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 ...

握手握手,一模一样
. more info on 1point3acres.com
补充内容 (2015-9-16 06:38):. 1point 3acres 璁哄潧
不过我觉得这个基本就是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。. visit 1point3acres.com for more.
insert应该比较好理解吧就是直接插入。
get的话如果给明确的timestamp了,就返回比给定的timestamp小并且latest timestamp对应的value
如果没给timestamp就是返回key+latest timestamp的value
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:41:38 | 显示全部楼层
bluezebra 发表于 2015-9-16 07:39. 1point 3acres 璁哄潧
timestamp是int。
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 {-google 1point3acres
  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];
  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:. visit 1point3acres.com for more.
  15.     unordered_map<string, map<int, string, std::greater<int>>> hashmap;
  16. };
复制代码
用bst存timestamps,查找的时候可以log
. 1point 3acres 璁哄潧
补充内容 (2015-9-16 08:17):. visit 1point3acres.com for more.
第二个get应该是begin而不是rbegin
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 08:32:14 | 显示全部楼层
f1371342385 发表于 2015-9-16 07:49
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) . from: 1point3acres.com/bbs
get为什么还要time? key不是可以唯一确定value嘛?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
同一个key可能对应多个不同的timestamp
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-16 09:47:12 | 显示全部楼层
bluezebra 发表于 2015-9-16 09:38. 1point 3acres 璁哄潧
同一个key可能对应多个不同的timestamp

噢没看清题目。那用一个哈希表,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。
insert应该比较好理解吧就是直接插入。
get的话如果给明确的timestamp了,就返回比给 ...
. From 1point 3acres bbs
刚看到这个回复,不好意思啦!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-27 10:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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