一亩三分地论坛

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

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

Uber 两轮电面

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

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

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

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

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

1月3号网投,小米效率超级高,第二天就收到面试通知,而且我记得还是周日。
电面45mins,大概15分钟过一下简历然后做题。
. From 1point 3acres bbs
第一轮电面. Waral 鍗氬鏈夋洿澶氭枃绔,

开始前4个小时左右面试官把做题链接发来了。我发现给的langguage是python,我问面试官能不能换成java。他说他是写python的(大概不怎么写java),而且我最近的实习写的是python,最好不要改。所以只能硬着头皮上了。。。

问题是这样的: 给一个不断更新的log文件,每一行是一条网页的访问记录,域名+时间+几个IP地址,IP地址中有些是无效的。例如:
www.1point3acres.com 02/06/2015 10.204.12.3 1.299.3.0 #第二个IP是无效的


要求把所有的有效的IP扒下来。用正则表达式写了。
然后问了两个follow up:
1. 怎么把这个log tail出来(因为是实时更新的)。
2. 现在给定一个DNS Server,要求把有效的IP对应的域名query出来。
我用的python的pipe,shell命令实现的,其实就是调一下tai和nslookup。面试官说这样总调用shell太慢了,要求用纯python写。只好答不会。。。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
面完感觉是跪了,没想到过几天收到小米回复,内容大意是觉得面的还可以,但是和面试官的组不match,要再来一轮电面。

第二轮电面
这回换成了一个写Java的面试官,面试形式和第一轮一样。

问题是统计backtraces。
给一个1000行的文件。每一行是一个String数组,表示一个backtrace,例如
["main", "fun1", "fun2"]
["main"," "fun1", "fun3","fun4"]
["main","fun5"]
["main"]
["main","fun5","fun6"]. 1point 3acres 璁哄潧
第一行表示一个函数调用关系main->fun1->fun2,其他类似。显然每一行的第0个元素必然是main。最后统计出每一个function的调用次数和调用关系,例如这个例子的输出是:
main 5
    fun1 2
        fun2 1
        fun3 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            fun4 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    fun5 2. From 1point 3acres bbs
        fun6 1
调用关系用indent表示出来,每多调用一层就多一个tab。
实现就是写一个树的节点类,每一个点表示一个函数,储存它的函数名和调用次数的count,孩子存在一个HashMap里,Key是孩子的函数名。

public Class Node{
    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。

一周以后收到on site。

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

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

使用道具 举报

wendy33 发表于 2015-2-17 09:46:03 | 显示全部楼层
请问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>
  2. #include <vector>
  3. #include <map>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4. using namespace std;

  5. // To execute C++, please define "int main()"-google 1point3acres
  6. struct TreeNode {
  7.   int count;
  8.   string val;
  9.   map<string, TreeNode*> str_map;
  10.   TreeNode(string v) {
  11.     count = 1;
  12.     val = v;
  13.   }
  14. };

  15. void preorder(TreeNode* root, string prefix) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.   if(root == NULL) return;
  17.   cout<<prefix<<root->val<<" "<<root->count<<endl;
  18.   map<string, TreeNode*>::iterator it;
  19.   for(it = root->str_map.begin(); it != root->str_map.end(); ++it)
  20.     preorder(it->second, prefix + "  ");
  21. }

  22. void printBckTraces(vector<vector<string>>& record) {
  23.   TreeNode* root = new TreeNode("main");
  24.   root->count = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  25.   TreeNode* cur_node;
  26.   
  27.   int m = record.size();//n = record[0].size();
  28.   //build the tree
  29.   for (int i = 0; i < m; ++i) {
  30.     cur_node = root;
  31.     int n = record[i].size();
  32.     for (int j = 0; j < n; ++j) {
  33.       if(j == 0) {
  34.         cur_node->count += 1;
  35.         continue;.1point3acres缃
  36.       }.1point3acres缃
  37.       if(cur_node->str_map.find(record[i][j]) == cur_node->str_map.end()) {
  38.         TreeNode* tmp_node = new TreeNode(record[i][j]);
  39.         cur_node->str_map[record[i][j]] = tmp_node;
  40.         cur_node = tmp_node;
  41.       }. 鍥磋鎴戜滑@1point 3 acres
  42.       else {
  43.         cur_node->str_map[record[i][j]]->count += 1;-google 1point3acres
  44.         cur_node = cur_node->str_map[record[i][j]];
  45.       }
  46.     }
  47.   }
  48.   //print the stuffs-google 1point3acres
  49.   preorder(root, "");
  50.   
  51. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  52. int main() {
  53.   vector<vector<string>> test = {. 鍥磋鎴戜滑@1point 3 acres
  54.     {"main", "fun1", "fun2"},. more info on 1point3acres.com
  55.     {"main","fun1", "fun3","fun4"},
  56.     {"main","fun5"},
  57.     {"main"},
  58.     {"main", "fun5", "fun6"}
  59.   };
  60.   printBckTraces(test);
  61.   return 0;
  62. }
复制代码
回复 支持 反对

使用道具 举报

tonyjiang 发表于 2015-8-27 14:25:16 | 显示全部楼层
  1. bt = [
  2.     ["main", "fun1", "fun2"],
  3.     ["main", "fun1", "fun3", "fun4"],
  4.     ["main", "fun5"],
  5. #     ['main', 'fun1', 'fun3'],
  6.     ["main"],
  7.     ["main", "fun5", "fun6"]
  8. ]

  9. dic = {}

  10. for bck in bt:
  11.     tmp = dic
  12.     for fct in bck:
  13.         if fct not in tmp:
  14.             tmp[fct] = [1,{}]   # count 1 and add child node
  15.             tmp = tmp[fct][1]   # move to child node
  16.         else:
  17.             tmp[fct][0] += 1
  18.             tmp = tmp[fct][1]
  19.             
    .1point3acres缃
  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). from: 1point3acres.com/bbs
  26.         
  27. dfs(dic,0)
复制代码
来个Python
  1. main 5 . 鍥磋鎴戜滑@1point 3 acres
  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, 2016-12-11 10:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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