推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 9620|回复: 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)
. from: 1point3acres.com/bbs * get(key, timestamp)
* get(key) // returns value associated with key at latest time. From 1point 3acres bbs

答的一般吧,写出来了但是最后有两个testcase没过,而且不是最优解。
.1point3acres缃
要是我自己是面试官,应该不会给onsite的机会。。
无所谓啦,心态要好




. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
补充内容 (2015-9-16 07:40):
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴 * insert("k1", "v1", 10). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
* get("k1") // returns "v1"
* get("k1", 11) // returns "v1". Waral 鍗氬鏈夋洿澶氭枃绔,
* insert("k1", "v2", 20). 1point3acres.com/bbs
* 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);
        }


}


回复 支持 6 反对 0

使用道具 举报

yavinci 发表于 2015-12-3 06:16:59 | 显示全部楼层
  1. import java.util.*;
  2. class TimeTravelingHashTable {

  3.         // <key : <timestamp : value>> = <key: sorted values on timestamp> = <key : treemap>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.         HashMap<String, TreeMap<Integer, String>> map = new HashMap<>();
  5.         .1point3acres缃
  6.         // insert <timestamp, value> into hashmap
  7.         public void insert(String key, String value, int timestamp) {
  8.                 if(map.containsKey(key)) {
  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);. visit 1point3acres.com for more.
  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.         }. Waral 鍗氬鏈夋洿澶氭枃绔,

  22.         // Return the latest value on timestamp
  23.         public String get(String key) {
  24.                 return map.get(key).lastEntry().getValue();
  25.         }

  26.         public static void main(String[] args) {
  27.                 TimeTravelingHashTable hashtable = new TimeTravelingHashTable();
  28.                 hashtable.insert("k1", "v1", 10);
  29.                 hashtable.insert("k1", "v2", 20);. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.                 hashtable.insert("k2", "v1", 5);
  31.                 hashtable.insert("k2", "v2", 15);
  32.                 System.out.println(hashtable.get("k1"));     //  "v1"
  33.                 System.out.println(hashtable.get("k1", 11)); //  "v1"
  34.                 System.out.println(hashtable.get("k1", 15)); //  "v1"
  35.                 System.out.println(hashtable.get("k1", 11)); //  "v1"
  36.                 System.out.println(hashtable.get("k1", 21)); //  "v2"
  37.                 System.out.println(hashtable.get("k2", 10)); //  "v1".鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.                 System.out.println(hashtable.get("k2", 20)); //  "v2". 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.         }
  40. }
复制代码
回复 支持 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 ...

握手握手,一模一样

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

使用道具 举报

wenqiang88 发表于 2015-9-16 06:42:39 | 显示全部楼层
bluezebra 发表于 2015-9-16 06:37.1point3acres缃
握手握手,一模一样. visit 1point3acres.com for more.

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

. more info on 1point3acres.com这样为啥会有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. 鍥磋鎴戜滑@1point 3 acres
这样为啥会有2个case不过呢?
. visit 1point3acres.com for more.
最后时间不太够了也没有给我时间让我根据不过的case debug。。。
回复 支持 反对

使用道具 举报

 楼主| bluezebra 发表于 2015-9-16 07:39:31 | 显示全部楼层
f1371342385 发表于 2015-9-16 06:58
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴LZ 请问timestamp是什么数据类型?没有理解LZ的题意啊
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
timestamp是int。
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-google 1point3acres
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 {
  2. public:. from: 1point3acres.com/bbs
  3.     void insert(const string& key, const string& value, int timestamp) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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);. 1point3acres.com/bbs
  9.         return it->second;
  10.     }
  11.     string get(const string& key) {
  12.         return hashmap[key].rbegin()->second;
  13.     }
  14. private:
  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
LZ,我的想法是开一个hashmap map, node 包括 "v1" "时间"。调用get函数的时候,会有一个list,然后调用这 ...
. 1point3acres.com/bbs
我也不是很清楚最优的解法是什么,小哥也并没有说,就直接让我按照我的想法写了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
二分查找肯定比暴搜要省时,不过我一直在想有没有可能在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

噢没看清题目。那用一个哈希表,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了,就返回比给 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 09:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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