一亩三分地论坛

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

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

google电面

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

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

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

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

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


expr := number | '(' operator expr+ ')'
operator := '+' | '*'

. 鍥磋鎴戜滑@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.com
另外求点大米,谢谢大家!

本帖被以下淘专辑推荐:

wenqiang88 发表于 2015-9-30 12:50:49 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
(+123(*123))里面1,2,3之间有空格吗?
回复 支持 反对

使用道具 举报

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

没有空格。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 02:41:44 | 显示全部楼层
. visit 1point3acres.com for more.
所以说计算里没有大于等于10的数?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

wenqiang88 发表于 2015-10-1 03:25:11 | 显示全部楼层
qlan2 发表于 2015-10-1 02:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
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

的确,他给的条件很少,就只有例子,然后我不断的思考不断的问,然后他才慢慢回答,中间还误解了一个重要条件,猜题花了我不少时间,最后就只能边写边讲思路,如果一开始能弄懂题目应该能写完,我还特意留了十分钟跟考官聊聊天,onsite看人品了,祝你早日斩获google offer。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 10:32:28 | 显示全部楼层
qlan2 发表于 2015-10-1 09:59
的确,他给的条件很少,就只有例子,然后我不断的思考不断的问,然后他才慢慢回答,中间还误解了一个重要 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
LZ加油!祝早日进Google!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

需要考虑有的string不是valid的情况吗..
. visit 1point3acres.com for more.
应该不用,假设输入的都是合法的吧。
回复 支持 反对

使用道具 举报

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.com/bbs
  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.                                 }. From 1point 3acres bbs
  22.                                 . 1point 3acres 璁哄潧
  23.                         }. 1point 3acres 璁哄潧
  24.                                
  25.                 }
  26.                
  27.                 return _cal(map, countLeft);
  28.         }
  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()){. visit 1point3acres.com for more.
  35.                                 stack.push(eval(exp, stack.pop()));
  36.                                
  37.                         } else{
  38.                                 stack.push(eval(exp, 0));
  39.                         }. visit 1point3acres.com for more.
  40.                         max--;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  41.                 }-google 1point3acres
  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';
  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');
  59.                                

  60.                         }. from: 1point3acres.com/bbs
  61.                         if(d != 0) res *= d;
  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). Waral 鍗氬鏈夋洿澶氭枃绔,
  12.                 stack.pop() # pop '('
  13.                 stack.append(temp)
  14.             else:
  15.                 stack.append(express[i])
  16.         return int(stack[0])

  17.     def calculate(self, op, nums):
  18.         if op == '+':.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.             res = 0
  20.             for n in nums:
  21.                 res += int(n)
  22.         else:
  23.             res = 1
  24.             for n in nums:
  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;
  4.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.         return helper(s, 0, s.length() - 1);. from: 1point3acres.com/bbs
  6. }
  7. . From 1point 3acres bbs
  8. private static int helper(String s, int lo, int hi) {
  9.         int innerLo = -1;                                // if there is inner parentheses
  10.         char oper = s.charAt(lo + 1);        // the operator: '+' or '*'
  11. . 1point3acres.com/bbs
  12.         int res = 1;                                        // result of string  from lo ~ hi. visit 1point3acres.com for more.
  13.         for (int i = lo + 2; i < hi; i++) {
  14.                 char ch = s.charAt(i);

  15.                 if (ch == '(') {
  16.                         innerLo = i;                        // calculate the right part in recursion. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.                         break;
  18.                 }
  19. . 1point 3acres 璁哄潧
  20.                 if (oper == '+') {
  21.                         res += ch - '0';
  22.                 } else if (oper == '*') {
  23.                         res *= ch - '0';
  24.                 }
  25.         }

  26.         if (oper == '+') {
  27.                         return res - 1 + (innerLo < 0 ? 0
  28.                         : helper(s, innerLo, hi - 1));
  29.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  30.         return res * (innerLo < 0 ? 1 : helper(s, innerLo, hi - 1));
  31. }
复制代码
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-5 04:35:41 | 显示全部楼层
romanchelsea 发表于 2015-10-4 15:16
如果这道题的string是正确的,如果string的形式是像lz列出来一样,每个括号内如果还有括号,内部的括号都靠 ...

"(+(+1(+11))1)"~=
回复 支持 反对

使用道具 举报

romanchelsea 发表于 2015-10-5 05:03:53 | 显示全部楼层
额,我假设的是字符串末尾是连续的‘)’. visit 1point3acres.com for more.
像你给的这这个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<>();. From 1point 3acres bbs
  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') {. visit 1point3acres.com for more.
  12.                                 sum = cal(sum, c - '0', op, isFirst);. 鍥磋鎴戜滑@1point 3 acres
  13.                                 isFirst = false;
  14.                         }else if (c == '+' || c == '*') {
  15.                                 op = c;. 1point3acres.com/bbs
  16.                         }else if (c == '(') {
  17.                                 numStack.push(sum);. From 1point 3acres bbs
  18.                                 sum = 0;. 1point3acres.com/bbs
  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.         }
  28.        
  29.         private static int cal(int sum, int num, char op, boolean isFirst) {
  30.                 if (isFirst)
  31.                         return num;
  32.                 else
  33.                         return (op == '+' ? sum + num : sum * num);
  34.         }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-30 03:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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