當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 10553|回复: 31
收起左侧

第一次发面经,Uber电面

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

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

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

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

x
同学内推的,hr反馈很快,大概一天。华裔小哥面的,人很nice,regular的面试过程:project,coding,Q&A
上来先问了十分钟project,然后开始coding。
Implement TimeTravelingHashTable的get和insert方法
* TimeTravelingHashTable
* insert(key, value, timestamp).本文原创自1point3acres论坛
* get(key, timestamp)
* get(key) // returns value associated with key at latest time

答的一般吧,写出来了但是最后有两个testcase没过,而且不是最优解。

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





. 1point 3acres 论坛
补充内容 (2015-9-16 07:40):. 1point3acres
* 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);
        }

.留学论坛-一亩-三分地
}
. 一亩-三分-地,独家发布

回复 支持 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>
  4.         HashMap<String, TreeMap<Integer, String>> map = new HashMap<>();
  5.        
  6.         // insert <timestamp, value> into hashmap. visit 1point3acres for more.
  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);
  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.         public static void main(String[] args) {
  27.                 TimeTravelingHashTable hashtable = new TimeTravelingHashTable();
  28.                 hashtable.insert("k1", "v1", 10);
  29.                 hashtable.insert("k1", "v2", 20);
  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" . from: 1point3acres
  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.         }. 1point 3acres 论坛
  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 ...

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

使用道具 举报

wenqiang88 发表于 2015-9-16 06:42:39 | 显示全部楼层
bluezebra 发表于 2015-9-16 06:37. Waral 博客有更多文章,
握手握手,一模一样

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

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

使用道具 举报

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

使用道具 举报

 楼主| 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. 1point 3acres 论坛
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
timestamp是int。
insert应该比较好理解吧就是直接插入。
get的话如果给明确的timestamp了,就返回比给 ...
. 一亩-三分-地,独家发布
可能我描述的不是太清楚,补充了一下原帖。. 围观我们@1point 3 acres
最后一个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. 来源一亩.三分地论坛.
  2. class TimeTravelingHashTable {. from: 1point3acres
  3. public:. 1point3acres
  4.     void insert(const string& key, const string& value, int timestamp) {
  5.         hashmap[key][timestamp] = value;
    . from: 1point3acres
  6.     }
  7.     string get(const string& key, int timestamp) {
  8.         auto& times = hashmap[key];. 1point 3acres 论坛
  9.         auto it = times.upper_bound(timestamp);
  10.         return it->second;
  11.     }
  12.     string get(const string& key) {
  13.         return hashmap[key].rbegin()->second;
  14.     }
  15. private:
  16.     unordered_map<string, map<int, string, std::greater<int>>> hashmap;. from: 1point3acres
  17. };
复制代码
用bst存timestamps,查找的时候可以log

补充内容 (2015-9-16 08:17):.本文原创自1point3acres论坛
第二个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)
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了,就返回比给 ...

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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