一亩三分地论坛

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

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

Uber 两轮电面

[复制链接] |试试Instant~ |关注本帖
dananger 发表于 2015-2-7 02:50:30 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Uber - 网上海投 - 技术电面 |Pass

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

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

x
其实我已经面完onsite了,另开一个帖子发onsite面经吧。

1月3号网投,小米效率超级高,第二天就收到面试通知,而且我记得还是周日。. more info on 1point3acres.com
电面45mins,大概15分钟过一下简历然后做题。-google 1point3acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一轮电面. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

开始前4个小时左右面试官把做题链接发来了。我发现给的langguage是python,我问面试官能不能换成java。他说他是写python的(大概不怎么写java),而且我最近的实习写的是python,最好不要改。所以只能硬着头皮上了。。。
. 1point 3acres 璁哄潧
问题是这样的: 给一个不断更新的log文件,每一行是一条网页的访问记录,域名+时间+几个IP地址,IP地址中有些是无效的。例如:
www.1point3acres.com 02/06/2015 10.204.12.3 1.299.3.0 #第二个IP是无效的

. 1point 3acres 璁哄潧
要求把所有的有效的IP扒下来。用正则表达式写了。
然后问了两个follow up:
1. 怎么把这个log tail出来(因为是实时更新的)。
2. 现在给定一个DNS Server,要求把有效的IP对应的域名query出来。. From 1point 3acres bbs
我用的python的pipe,shell命令实现的,其实就是调一下tai和nslookup。面试官说这样总调用shell太慢了,要求用纯python写。只好答不会。。。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

面完感觉是跪了,没想到过几天收到小米回复,内容大意是觉得面的还可以,但是和面试官的组不match,要再来一轮电面。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二轮电面.鐣欏璁哄潧-涓浜-涓夊垎鍦
这回换成了一个写Java的面试官,面试形式和第一轮一样。
-google 1point3acres
问题是统计backtraces。
给一个1000行的文件。每一行是一个String数组,表示一个backtrace,例如
["main", "fun1", "fun2"]
["main"," "fun1", "fun3","fun4"]
["main","fun5"]
["main"]
["main","fun5","fun6"]
第一行表示一个函数调用关系main->fun1->fun2,其他类似。显然每一行的第0个元素必然是main。最后统计出每一个function的调用次数和调用关系,例如这个例子的输出是:
main 5
    fun1 2. visit 1point3acres.com for more.
        fun2 1
        fun3 1
            fun4 1
    fun5 2. 鍥磋鎴戜滑@1point 3 acres
        fun6 1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
调用关系用indent表示出来,每多调用一层就多一个tab。
实现就是写一个树的节点类,每一个点表示一个函数,储存它的函数名和调用次数的count,孩子存在一个HashMap里,Key是孩子的函数名。

public Class Node{. more info on 1point3acres.com
    public Stirng name;
    public int count;
    public HashMap<String, Node> children;
}

树根是main,建树的时候每读取一行就从main开始更新一条path,比如例子读到第二行的时候,从main更新main.count,从main.children里找到fun1,更新fun1的count,这时候发现fun1的children里没有fun2,就创建一个fun2节点加到fun1的children里,同理fun3。

因为这个题描述有点绕,花了些时间和面试官讨论题目,最后打印的部分没时间写了,就口头讲了一下打印的顺序,从main开始,每多一层递归就多打一个tab,讲着讲着发现其实就是dfs,面试官说OK,dfs能work。因为没写完也没跑test case。
.1point3acres缃
一周以后收到on site。-google 1point3acres

总结:
1.最近Uber在扩招,很多engineer都是入职半年左右。
2.Uber家只用Python和Node.JS。如果prefer其他语言最好提前跟小米讲一下。
3.电面题出的五花八门,不过bar不高,每次都感觉肯定挂了没想到还能进下一轮。.1point3acres缃

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · uber|主题: 19, 订阅: 16
ekco 发表于 2015-2-8 13:58:54 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感谢分享,总体感觉还是挺难的,特别是第二题,建树然后dfs打印的想法很赞。我想的方法是每个函数对应一个hashtable,key是函数名,value是频率和hashtable的pair,第二个hashtable是子函数和对应的频率。然后递归打印。

期待onsite面经!
回复 支持 反对

使用道具 举报

wendy33 发表于 2015-2-17 09:46:03 | 显示全部楼层
关注一亩三分地微博:
Warald
请问LZ,可能出现某个func同时出现在不同的层次吗?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-3-3 01:53:50 | 显示全部楼层
第二题有大牛写写代码么。。
回复 支持 反对

使用道具 举报

echo33 发表于 2015-3-4 04:31:30 | 显示全部楼层
这题目略难啊
回复 支持 反对

使用道具 举报

stleger 发表于 2015-6-22 13:49:31 | 显示全部楼层
第二题 不就是个拓扑排序吗
回复 支持 反对

使用道具 举报

sjtuzyt 发表于 2015-6-25 02:41:20 | 显示全部楼层
最近要电面,刚刚写了一下,调完花了半个小时,第一次在coderpad上写
  1. #include <iostream>. From 1point 3acres bbs
  2. #include <vector>
  3. #include <map>. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. using namespace std;.1point3acres缃
  5. . Waral 鍗氬鏈夋洿澶氭枃绔,
  6. // To execute C++, please define "int main()"
  7. struct TreeNode {
  8.   int count;
  9.   string val;
  10.   map<string, TreeNode*> str_map;
  11.   TreeNode(string v) {
  12.     count = 1;
  13.     val = v;
  14.   }. more info on 1point3acres.com
  15. };. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  16. void preorder(TreeNode* root, string prefix) {
  17.   if(root == NULL) return;. 鍥磋鎴戜滑@1point 3 acres
  18.   cout<<prefix<<root->val<<" "<<root->count<<endl;
  19.   map<string, TreeNode*>::iterator it;
  20.   for(it = root->str_map.begin(); it != root->str_map.end(); ++it).鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.     preorder(it->second, prefix + "  ");
  22. }
  23. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  24. void printBckTraces(vector<vector<string>>& record) {
  25.   TreeNode* root = new TreeNode("main");
  26.   root->count = 0;
  27.   TreeNode* cur_node;
  28.   . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.   int m = record.size();//n = record[0].size();
  30.   //build the tree
  31.   for (int i = 0; i < m; ++i) {
  32.     cur_node = root;
  33.     int n = record[i].size();
  34.     for (int j = 0; j < n; ++j) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.       if(j == 0) {
  36.         cur_node->count += 1;.1point3acres缃
  37.         continue;
  38.       }
  39.       if(cur_node->str_map.find(record[i][j]) == cur_node->str_map.end()) {
  40.         TreeNode* tmp_node = new TreeNode(record[i][j]);
  41.         cur_node->str_map[record[i][j]] = tmp_node;
  42.         cur_node = tmp_node;
  43.       }. more info on 1point3acres.com
  44.       else {
  45.         cur_node->str_map[record[i][j]]->count += 1;. 1point3acres.com/bbs
  46.         cur_node = cur_node->str_map[record[i][j]];
  47.       }
  48.     }
  49.   }
  50.   //print the stuffs
  51.   preorder(root, "");. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.   
  53. }

  54. int main() {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  55.   vector<vector<string>> test = {
  56.     {"main", "fun1", "fun2"},
  57.     {"main","fun1", "fun3","fun4"},
  58.     {"main","fun5"},
  59.     {"main"},
  60.     {"main", "fun5", "fun6"}
  61.   };
  62.   printBckTraces(test);
  63.   return 0;
  64. }
复制代码
回复 支持 反对

使用道具 举报

tonyjiang 发表于 2015-8-27 14:25:16 | 显示全部楼层
  1. bt = [
  2.     ["main", "fun1", "fun2"],.1point3acres缃
  3.     ["main", "fun1", "fun3", "fun4"],
  4.     ["main", "fun5"],. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5. #     ['main', 'fun1', 'fun3'],
  6.     ["main"],
  7.     ["main", "fun5", "fun6"]
  8. ]. more info on 1point3acres.com

  9. dic = {}

  10. for bck in bt:
  11.     tmp = dic
  12.     for fct in bck:
  13.         if fct not in tmp:. 1point 3acres 璁哄潧
  14.             tmp[fct] = [1,{}]   # count 1 and add child node
  15.             tmp = tmp[fct][1]   # move to child node.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.         else:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.             tmp[fct][0] += 1
  18.             tmp = tmp[fct][1]
  19.             
  20. def dfs(dic, level):
  21.     if len(dic) == 0:
  22.         return. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.     for key in dic:
  24.         print "%s%s %d" % ('  '*level, key, dic[key][0])
  25.         dfs(dic[key][1], level+1)
  26.         
  27. dfs(dic,0)
复制代码
来个Python
  1. main 5
  2.   fun5 2
  3.     fun6 1 . From 1point 3acres bbs
  4.   fun1 2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     fun3 1
  6.       fun4 1
  7.     fun2 1
复制代码
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-8-27 16:52:03 | 显示全部楼层
请问 log 更新那题,

1. 怎么把这个log tail出来(因为是实时更新的)。.


这个怎么做啊,总不能是 tail -f 吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-27 22:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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