[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

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

google电面

[复制链接] |试试Instant~ |关注本帖
qlan2 发表于 2015-9-30 12:34:45 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚参加google电面,之前仔细看过本版电面题目,非常感谢各位分享。面试的应该是个白人小哥,说话很快很有磁性,今天阴天信号本来就不太好,这样一来很难听清细节。. 1point 3acres 论坛
小哥迟到8分钟,就问一个题,上来就让我写parser,leetcode有个类似的题。
题目是给一个string "( + 1 2 ( * 3 4 ) )" 返回15.本文原创自1point3acres论坛
(+123(*123)) 返回12

. Waral 博客有更多文章,
expr := number | '(' operator expr+ ')'
operator := '+' | '*'. more info on 1point3acres
. 围观我们@1point 3 acres

[size=13.3333px]以上都是小哥给的条件,刚刚开始有点误解,后来我说用stack或者recursive写,我跟小哥聊了聊思路,没写完,然后聊聊他的project,
[size=13.3333px]然后欢乐的挂了电话,坐等据信。
[size=13.3333px].留学论坛-一亩-三分地

[size=13.3333px]另外,之前面过IBM,第一轮出了两个leetcode原题,Lowest Common Ancestor Of a Binary Search Tre 和 Maximam subarray,瞬间写完. 面的是大数据组,第二轮是一个白人大哥,
就聊聊project和culture fit,跟他聊天非常有意思。但是貌似他们招人比较缺钱,一直说他们打算先面local candidate,各种暗示我自己飞过去onsite,我表示自己是穷学生,掏不起机票钱,然后就没有然后了。
祝大家各种offer!. more info on 1point3acres
. 一亩-三分-地,独家发布
另外求点大米,谢谢大家!. 一亩-三分-地,独家发布

本帖被以下淘专辑推荐:

wenqiang88 发表于 2015-9-30 12:50:49 | 显示全部楼层
(+123(*123))里面1,2,3之间有空格吗?
回复 支持 反对

使用道具 举报

 楼主| qlan2 发表于 2015-10-1 02:33:40 | 显示全部楼层
wenqiang88 发表于 2015-9-30 12:50
(+123(*123))里面1,2,3之间有空格吗?

. from: 1point3acres 没有空格。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 02:41:44 | 显示全部楼层
qlan2 发表于 2015-10-1 02:33. 一亩-三分-地,独家发布
没有空格。

所以说计算里没有大于等于10的数?
回复 支持 反对

使用道具 举报

 楼主| qlan2 发表于 2015-10-1 02:50:50 | 显示全部楼层
wenqiang88 发表于 2015-10-1 02:41. from: 1point3acres
所以说计算里没有大于等于10的数?

str都是独立的digit,但是括号里面可能会计算出来大于9的数字。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 03:25:11 | 显示全部楼层
qlan2 发表于 2015-10-1 02:50
str都是独立的digit,但是括号里面可能会计算出来大于9的数字。

好的,明白了。但是面试官给的这个语法有点confusing, 按道理来说number应该是123 而不是 1 2 3
回复 支持 反对

使用道具 举报

 楼主| qlan2 发表于 2015-10-1 09:59:22 | 显示全部楼层
wenqiang88 发表于 2015-10-1 03:25
好的,明白了。但是面试官给的这个语法有点confusing, 按道理来说number应该是123 而不是 1 2 3
-google 1point3acres
的确,他给的条件很少,就只有例子,然后我不断的思考不断的问,然后他才慢慢回答,中间还误解了一个重要条件,猜题花了我不少时间,最后就只能边写边讲思路,如果一开始能弄懂题目应该能写完,我还特意留了十分钟跟考官聊聊天,onsite看人品了,祝你早日斩获google offer。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 10:32:28 | 显示全部楼层
qlan2 发表于 2015-10-1 09:59. 牛人云集,一亩三分地
的确,他给的条件很少,就只有例子,然后我不断的思考不断的问,然后他才慢慢回答,中间还误解了一个重要 ...

LZ加油!祝早日进Google!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

romanchelsea 发表于 2015-10-1 12:07:30 | 显示全部楼层
(+123(*123)) 的意思是不是 1 + 2 + 3 + (1 * 2 * 3)?

需要考虑有的string不是valid的情况吗... 1point3acres
比如(+-123(*/123))这种。
回复 支持 反对

使用道具 举报

 楼主| qlan2 发表于 2015-10-1 21:24:33 | 显示全部楼层
romanchelsea 发表于 2015-10-1 12:07. visit 1point3acres for more.
(+123(*123)) 的意思是不是 1 + 2 + 3 + (1 * 2 * 3)?. 围观我们@1point 3 acres

需要考虑有的string不是valid的情况吗..

应该不用,假设输入的都是合法的吧。
回复 支持 反对

使用道具 举报

0011999 发表于 2015-10-2 03:36:01 | 显示全部楼层
thanks for sharing
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-2 05:41:51 | 显示全部楼层
感觉第一题用hashmap 做比较好
  1. public static int cal(String input){
  2.                 int countLeft = 0;
  3.                 int countRight = 0;.本文原创自1point3acres论坛
  4.                 HashMap<Integer, String> map = new HashMap<Integer, String>();
  5.                 int prevLeft = 0;
  6.                 for(int i = 0; i < input.length(); i++){
  7.                         if(input.charAt(i) == '('){
  8.                                
  9.                                 if(i > prevLeft){
  10.                                         String exp = input.substring(prevLeft+1, i);
  11.                                         map.put(countLeft, exp);
  12.                                 }
  13.                                 countLeft++;
  14.                                 prevLeft = i;
  15.                                
  16.                         } else if(input.charAt(i) == ')'){
  17.                                 if(countRight == 0){
  18.                                         String exp = input.substring(prevLeft + 1, i);. 牛人云集,一亩三分地
  19.                                         map.put(countLeft, exp);
  20.                                         countRight++;
  21.                                 }
  22.                                
  23.                         }
  24.                                
  25.                 }
  26.                
  27.                 return _cal(map, countLeft);. visit 1point3acres for more.
  28.         }. 1point3acres
  29.        
  30.         private static int _cal(HashMap<Integer, String> map, int max){
  31.                 Stack<Integer> stack = new Stack<Integer>();
  32.                 while(max >= 1){
  33.                         String exp = map.get(max);
  34.                         if(!stack.isEmpty()){
  35.                                 stack.push(eval(exp, stack.pop()));
  36.                                
  37.                         } else{
  38.                                 stack.push(eval(exp, 0));
  39.                         }
  40.                         max--;
  41.                 }
  42.                 return stack.pop();
  43.         }
  44.        
  45.         private static int eval(String exp, int d){
  46.                 char op = exp.charAt(0);
  47.                
  48.                 int res = 0;
  49.                 if(op == '+'){
  50.                         for(int i = 1; i < exp.length(); i++){
  51.                                 res += exp.charAt(i) - '0';. 围观我们@1point 3 acres
  52.                         }. 一亩-三分-地,独家发布
  53.                         return res + d;
  54.        
  55.                 }else{
  56.                         res = 1;
  57.                         for(int i = 1; i < exp.length(); i++){
  58.                                 res *= (exp.charAt(i) - '0');. From 1point 3acres bbs
  59.                                

  60.                         }
  61.                         if(d != 0) res *= d;. 围观我们@1point 3 acres
  62.                         return res;
  63.                 }
  64.                                                
  65.         }
  66.        
复制代码

补充内容 (2015-10-2 05:42):. 一亩-三分-地,独家发布
调了半天, 才弄好。 大家看看, 有没有更好的solution
回复 支持 反对

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-10-2 07:56:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-10-2 08:14:47 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-2 09:23:58 | 显示全部楼层
感觉如果不考虑表达式可能不正确以及digit都是一位不超过10的话好像用stack挺简单的
用Python写了下不知道如何
  1. class Solution:
  2.     def expressParser(self, express):
  3.         if not express: return 0
  4.         stack = []
  5.         for i in range(len(express)):
  6.             if express[i] == ')':
  7.                 nums = []
  8.                 while stack[-1] not in '+*':
  9.                     nums.append(stack.pop())
  10.                 op = stack.pop()
  11.                 temp = self.calculate(op, nums)
  12.                 stack.pop() # pop '('.本文原创自1point3acres论坛
  13.                 stack.append(temp). From 1point 3acres bbs
  14.             else:. From 1point 3acres bbs
  15.                 stack.append(express[i])
  16.         return int(stack[0])

  17.     def calculate(self, op, nums):
  18.         if op == '+':
  19.             res = 0
  20.             for n in nums:
  21.                 res += int(n). visit 1point3acres for more.
  22.         else:. more info on 1point3acres
  23.             res = 1
  24.             for n in nums:.本文原创自1point3acres论坛
  25.                 res *= int(n)
  26.         return str(res)
复制代码
回复 支持 反对

使用道具 举报

romanchelsea 发表于 2015-10-4 15:16:46 | 显示全部楼层
如果这道题的string是正确的,如果string的形式是像lz列出来一样,每个括号内如果还有括号,内部的括号都靠右的话(即所有的右括号')'都在string的最右端),可以用recursion。
如果右括号不全是在string最右边,也可以recursion,只不过要记住内部左右括号的位置。
  1. public static int parse(String s) {
  2.         if (s == null || s.length() == 0) {
  3.                 return 0;. Waral 博客有更多文章,
  4.         }
  5.         return helper(s, 0, s.length() - 1);
  6. }. 一亩-三分-地,独家发布
  7. 来源一亩.三分地论坛.
  8. private static int helper(String s, int lo, int hi) {
    . 围观我们@1point 3 acres
  9.         int innerLo = -1;                                // if there is inner parentheses.本文原创自1point3acres论坛
  10.         char oper = s.charAt(lo + 1);        // the operator: '+' or '*'

  11.         int res = 1;                                        // result of string  from lo ~ hi
  12.         for (int i = lo + 2; i < hi; i++) {. Waral 博客有更多文章,
  13.                 char ch = s.charAt(i);

  14.                 if (ch == '(') {
  15.                         innerLo = i;                        // calculate the right part in recursion. 围观我们@1point 3 acres
  16.                         break; 来源一亩.三分地论坛.
  17.                 }

  18.                 if (oper == '+') {
  19.                         res += ch - '0';
  20.                 } else if (oper == '*') {
  21.                         res *= ch - '0';
  22.                 }
  23.         }. 牛人云集,一亩三分地

  24.         if (oper == '+') {. visit 1point3acres for more.
  25.                         return res - 1 + (innerLo < 0 ? 0.留学论坛-一亩-三分地
  26.                         : helper(s, innerLo, hi - 1));. from: 1point3acres
  27.         }
  28. . 牛人云集,一亩三分地
  29.         return res * (innerLo < 0 ? 1 : helper(s, innerLo, hi - 1));
  30. }
复制代码
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-5 04:35:41 | 显示全部楼层
romanchelsea 发表于 2015-10-4 15:16
如果这道题的string是正确的,如果string的形式是像lz列出来一样,每个括号内如果还有括号,内部的括号都靠 ...
. visit 1point3acres for more.
"(+(+1(+11))1)"~=
回复 支持 反对

使用道具 举报

romanchelsea 发表于 2015-10-5 05:03:53 | 显示全部楼层
额,我假设的是字符串末尾是连续的‘)’.本文原创自1point3acres论坛
像你给的这这个string,确定当前部分内部还有括号的话,再从右往左找第二个‘)’..
回复 支持 反对

使用道具 举报

 楼主| qlan2 发表于 2015-10-6 01:28:56 | 显示全部楼层
楼主吧自己的代码贴出来方便大家准备google面试,祝大家面试成功!
  1. public static int parser(String str) {. 一亩-三分-地,独家发布
  2.                 int N = str.length(), sum = 0;
  3.                 boolean isFirst = true;
  4.                 char op = '+';
  5.                 Deque<Integer> numStack = new ArrayDeque<>();
  6.                 Deque<Character> opStack = new ArrayDeque<>();
  7.                
  8.                 for (int i = 0; i < N; i++) {
  9.                         char c = str.charAt(i);
  10.                        
  11.                         if (c >= '0' && c <= '9') {
  12.                                 sum = cal(sum, c - '0', op, isFirst);. 围观我们@1point 3 acres
  13.                                 isFirst = false;
  14.                         }else if (c == '+' || c == '*') {. from: 1point3acres
  15.                                 op = c;. Waral 博客有更多文章,
  16.                         }else if (c == '(') {
    . 留学申请论坛-一亩三分地
  17.                                 numStack.push(sum);
    .留学论坛-一亩-三分地
  18.                                 sum = 0;
  19.                                 isFirst = true;
  20.                                 opStack.push(op);
  21.                         }else if (c == ')') {
  22.                                 op = opStack.pop();
  23.                                 sum = cal(numStack.pop(), sum, op, isFirst);
  24.                         }
  25.                 }. 一亩-三分-地,独家发布
  26.                 return sum;
  27.         }. 1point3acres
  28.         . 留学申请论坛-一亩三分地
  29.         private static int cal(int sum, int num, char op, boolean isFirst) {
  30.                 if (isFirst) -google 1point3acres
  31.                         return num;
  32.                 else
  33.                         return (op == '+' ? sum + num : sum * num);
  34.         }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 01:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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