一亩三分地论坛

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

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

妥妥跪了的Google电面,代码没写完==求大牛讲解

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

2015(7-9月) 码农类 本科 全职@Google - 网上海投 - HR筛选 |Otherfresh grad应届毕业生

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

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

x
一个白人小哥,上来直接在google docs上粘贴了题目
write a fuction to add operator(+-*/) to a string so it equals to a target value. 1point3acres.com/bbs
for example
123,6 -> 1+2+3
12345, 27-> 1+2*3+4*5

然后我问了数字顺序能不能变,答说不能;问了要不要括号,答说不能用括号。

最开始就想到了类似leetcode basic calculator,后来又想到了用backtracking,但是backtracking不是很熟,写了半天也没写对,时间到了就问了几个问题就thank you了

妥妥了跪了,来问问有没有大神能说下解法? 有java解法最好了,C++看不懂==
. visit 1point3acres.com for more.

补充内容 (2015-9-25 11:08):
.1point3acres缃没想到面试完两天之后leetcode就加了这道题,这人品。。。

补充内容 (2015-9-25 11:09):
电面已过,onsite去了

评分

6

查看全部评分

本帖被以下淘专辑推荐:

Linzertorte 发表于 2015-9-12 13:30:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  1. def get_next(xs):
  2.   if xs=='':
  3.     yield ''
  4.     return
  5.   for x in get_next(xs[1:]):
  6.     for h in ['','+','*','-','/']:
  7.       yield h+xs[:1]+x

  8. def f(xs,val):
  9.   for x in get_next(xs[1:]):. from: 1point3acres.com/bbs
  10.     if eval(xs[:1]+x)==val:
  11.        return xs[:1]+x
  12.   return "no solution"
  13. . Waral 鍗氬鏈夋洿澶氭枃绔,
  14. print '123->6,',f('123',6). Waral 鍗氬鏈夋洿澶氭枃绔,
  15. print '12345->27, ', f('12345',27)
复制代码
回复 支持 1 反对 0

使用道具 举报

purplesky85 发表于 2015-9-12 20:32:26 | 显示全部楼层
关注一亩三分地微博:
Warald
backtracking+stack计算的,计算的时候因为是字符串转换的数字,可能会溢出,用了long,但是其实如果极端长还是会溢出,后来想到其实可以先从个位开始一位一位的运算并和target比较,这样就不会有特别长的数溢出的问题了,不过实现起来稍微麻烦点。
  1.   public String calculateToSum(String str, int tar) {
  2.     if (str == null || str.length() == 0) {
  3.       return "";
  4.     }

  5.     StringBuilder ans = new StringBuilder(str);
  6.     return dfsHelper(ans, 1, tar);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  7.   }

  8.   private String dfsHelper(StringBuilder ans, int pos, int tar) {
  9.     if (pos >= ans.length()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.       if (calculate(ans.toString()) == tar) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.         return ans.toString();-google 1point3acres
  12.       }
  13.       return null;
  14.     }

  15.     char[] operator = {'+', '-', '*', '/'};

  16.     for (int i = 0; pos + i < ans.length(); i++) {
  17.       for (int j = 0; j < 4; j++) {. visit 1point3acres.com for more.
  18.         ans.insert(pos + i, operator[j]);
  19.         String temp = dfsHelper(ans, pos + i + 2, tar);
  20.         if (temp != null) {
  21.           return temp;
  22.         }
  23.         ans.deleteCharAt(pos + i);
  24.       }
  25.     }

  26.     return null;
  27.   }
  28. . 1point3acres.com/bbs
  29.   private long calculate(String e) {
  30.     Stack<Character> operator = new Stack<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  31.     Stack<Long> operands = new Stack<>();

  32.     int[] pri = new int[128];
  33.     pri['+'] = 1;
  34.     pri['-'] = 1;. from: 1point3acres.com/bbs
  35.     pri['*'] = 2;
  36.     pri['/'] = 2;

  37.     for (int i = 0; i < e.length(); i++) {
  38.       char c = e.charAt(i);
  39.       if (Character.isDigit(c)) {
  40.         int right = i + 1;
  41.         while (right < e.length() && Character.isDigit(e.charAt(right))) {
  42.           right++;
  43.         }. 1point 3acres 璁哄潧
  44.         operands.push(Long.parseLong(e.substring(i, right)));
  45.         i = right - 1;
  46.       } else {
  47.         if (!operator.isEmpty() && ((pri[c] < pri[operator.peek()]) || (pri[c] == pri[operator.1point3acres缃
  48.             .peek()] && pri[c] == 2))) {
  49.           operands.push(op(operands.pop(), operands.pop(), operator.pop()));
  50.         }

  51.         operator.push(c);
  52.       }. 1point 3acres 璁哄潧
  53.     }

  54.     while (!operator.isEmpty()) {
  55.       operands.push(op(operands.pop(), operands.pop(), operator.pop()));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  56.     }

  57.     return operands.pop();
  58.   }

  59.   private long op(long a, long b, Character operator) {
  60.     long result = 0L;
  61.     if (operator == '+') {
  62.       result =  b + a;
  63.     } else if (operator == '-') {
  64.       result =  b - a;
  65.     } else if (operator == '*') {
  66.       result =  b * a;
  67.     } else if (operator == '/') { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  68.       if (a == 0) {
  69.         result =  Long.MAX_VALUE;
  70.       }
  71.       result =  b / a;
  72.     }
  73.     result = result > Integer.MAX_VALUE? Integer.MAX_VALUE + 1: result;
  74.     result = result < Integer.MIN_VALUE? Integer.MIN_VALUE - 1: result;
  75.     return result;
  76.   }
复制代码
回复 支持 1 反对 0

使用道具 举报

chenyy0527 发表于 2015-9-13 03:30:50 | 显示全部楼层
哇塞google的 title果然声势大好多! 这道题不难,我帖子里有人给出了非常简练的解法,我自己当时是OA,半小时不到写完的,还是偏慢了。楼主可以去看一下 http://www.1point3acres.com/bbs/thread-139727-1-1.html    都是C++就是了

话说语言本身很多相通的,尤其是这些算法题并没有用到复杂的语言本身的机制,应该不存在看不懂的问题,我只会写C++,但是读代码还是都能读的, 也可以轻松翻译,楼主如果看主流代码尚有困难可能还需一段时间的加强 0.0
回复 支持 1 反对 0

使用道具 举报

幕天 发表于 2015-9-12 11:23:38 | 显示全部楼层
如果是123,15->12+3满足条件吗?
回复 支持 反对

使用道具 举报

juslun 发表于 2015-9-12 11:36:51 | 显示全部楼层
暴力遍历。。  有人有更好的方法吗
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-12 12:29:36 | 显示全部楼层
应该就是back tracking + stack吧
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-12 12:39:42 | 显示全部楼层
wenqiang88 发表于 2015-9-12 12:29. more info on 1point3acres.com
应该就是back tracking + stack吧

怎么处理operator precedence 不同的问题呢?
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-9-12 13:00:32 | 显示全部楼层
backtracking.
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-12 13:24:14 | 显示全部楼层
写个枚兴趣完符号求值的部分,大家感受一下。
这种简单的表达式求值,能用的方法是dijkstra双栈扫描(中缀转后缀),或者编译原理中的recursive descent.
  1. #include<iostream>
  2. #include<string.h>.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3. using namespace std;
  4. int eval_sub(const char *s,const char *t){
  5.     const char *p;
  6.     int lhs,rhs;
  7.     for(p=t-1;p>=s;p--) if(*p=='+'||*p=='-') break;
  8.     if(p>=s) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
  10.         if(*p=='+') return lhs+rhs;
  11.         if(*p=='-') return lhs-rhs;
  12.     }
  13.     for(p=t-1;p>=s;p--) if(*p=='*'||*p=='/') break;. From 1point 3acres bbs
  14.     if(p>=s) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.         if(*p=='*') return lhs*rhs;
  17.         if(*p=='/') return lhs/rhs;. From 1point 3acres bbs
  18.     }
  19.     int x = 0;
  20.     for(p=s;p<t;p++) x = x*10 + (*p-'0');
  21.     return x;
  22. }
  23. int eval(const char *expr){
  24.     int n = strlen(expr);
  25.     return eval_sub(expr,expr+n);
  26. }
  27. int main(){
  28.     cout<<eval("3*4*56+2+3*7+490")<<endl;
  29.     cout<<eval("12*3+1+23*123*4")<<endl;. 鍥磋鎴戜滑@1point 3 acres
  30.     cout<<eval("1*2/2+3-2*3")<<endl;
  31. }. from: 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-12 13:24:39 | 显示全部楼层
Linzertorte 发表于 2015-9-12 13:24
写个枚兴趣完符号求值的部分,大家感受一下。
这种简单的表达式求值,能用的方法是dijkstra双栈扫描(中缀 ...

这里假设数字里没有0,而且除法是整数除法。
回复 支持 反对

使用道具 举报

stevenlordiam 发表于 2015-9-12 13:40:05 | 显示全部楼层
幕天 发表于 2015-9-12 11:23
如果是123,15->12+3满足条件吗?
. 1point 3acres 璁哄潧
满足啊   只要相等就行
回复 支持 反对

使用道具 举报

stevenlordiam 发表于 2015-9-12 13:41:35 | 显示全部楼层
这个题跟crysptic的OA很像啊   楼主可以看看地里相关的帖子 我记得有人po了代码
回复 支持 反对

使用道具 举报

wenhanz 发表于 2015-9-12 15:08:50 | 显示全部楼层
back tracking解妥妥的~

补充内容 (2015-9-12 15:09):
只会python,java基本上手生了...所以讲不来了...
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-12 15:23:50 | 显示全部楼层
楼上说的那种123,15的,应该不能用12+3 -> 15吧,如果可以这样,那可能的情况就太多了,例子里也是每个数字都分开的。

我感觉和basic calculator有点像,可以先把所有的可能都列出来,比如说12,就生成四个string,1+2, 1-2, 1*2, 1/2,然后调用basic calculator来算是否等于目标值。

这个方法比较笨,没想出更好的。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-12 20:34:44 | 显示全部楼层
say543 发表于 2015-9-12 12:39. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
怎么处理operator precedence 不同的问题呢?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
跟leetcode里的basic calculator II一样的做法
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:08:57 | 显示全部楼层
stevenlordiam 发表于 2015-9-12 13:41
这个题跟crysptic的OA很像啊   楼主可以看看地里相关的帖子 我记得有人po了代码

谢谢!我去看一下
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:10:01 | 显示全部楼层
edna 发表于 2015-9-12 15:23
楼上说的那种123,15的,应该不能用12+3 -> 15吧,如果可以这样,那可能的情况就太多了,例子里也是每个数 ...

可以的  有多种答案只要输出一种就好 没有就返回 “No answer"
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:11:13 | 显示全部楼层
Linzertorte 发表于 2015-9-12 13:24
写个枚兴趣完符号求值的部分,大家感受一下。
这种简单的表达式求值,能用的方法是dijkstra双栈扫描(中缀 ...

大神啊。。方法名字我都看不懂了==
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:16:43 | 显示全部楼层
purplesky85 发表于 2015-9-12 20:32
backtracking+stack计算的,计算的时候因为是字符串转换的数字,可能会溢出,用了long,但是其实如果极端 ...
. visit 1point3acres.com for more.
我也是类似的方法  看了你的代码 感觉我在helper那一块写的有问题  多谢分享
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-12 23:24:38 | 显示全部楼层
写了一个比较简单的dfs算法,思路是可以把前面的按照最后一个'+'或'-'的位置分成两部分,然后分别讨论在当前位置插入'+','-','*','/'的情况
感觉电面问这个好难,当场估计写不出来
public static String addOperation(String s,int target){-google 1point3acres
                if(s == null || s.length() == 0){. From 1point 3acres bbs
                        return "";
                }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int length = s.length();
                int[] nums = new int[length];
                for(int i=0;i<length;i++){
                        int cur = s.charAt(i) - '0';
                        nums[i] = cur;
                }
                StringBuilder sb = new StringBuilder();
                sb.append(nums[0]);
                boolean flag = dfsHelper(nums,0,nums[0],1,target,sb,true);
                if(flag){. visit 1point3acres.com for more.
                        return sb.toString();
                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                return "";. 1point 3acres 璁哄潧
        }
        public static boolean dfsHelper(int[] nums,long first,long second,int pos,int target,StringBuilder sb,boolean isPlus){
                if((isPlus &&first + second == target && pos == nums.length) || (!isPlus && first - second == target && pos == nums.length)){
                        return true;
                }
                if(pos == nums.length){
                        return false;
                }
                /*****************************当前插入符号‘+’*****************************/. 1point 3acres 璁哄潧
                sb.append('+');. 鍥磋鎴戜滑@1point 3 acres
                sb.append(nums[pos]);
                if(isPlus){
                        if(dfsHelper(nums,first+second,nums[pos],pos+1,target,sb,true)){. 1point 3acres 璁哄潧
                                return true;
                        }
                }
                else{
                        if(dfsHelper(nums,first-second,nums[pos],pos+1,target,sb,true)){
                                return true;
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                sb.deleteCharAt(sb.length()-1);
                sb.deleteCharAt(sb.length()-1);
                /************************************************************************/
                /*****************************当前插入符号‘-’*****************************/
                sb.append('-');. visit 1point3acres.com for more.
                sb.append(nums[pos]);
                if(isPlus){
                        if(dfsHelper(nums,first+second,nums[pos],pos+1,target,sb,false)){
                                return true;
                        }
                }
                else{
                        if(dfsHelper(nums,first-second,nums[pos],pos+1,target,sb,false)){
                                return true;. from: 1point3acres.com/bbs
                        }
                }
                sb.deleteCharAt(sb.length()-1);
                sb.deleteCharAt(sb.length()-1);
                /************************************************************************/
                /*****************************当前插入符号‘*’*****************************/
                sb.append('*');
                sb.append(nums[pos]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if(dfsHelper(nums,first,second*nums[pos],pos+1,target,sb,isPlus)){. visit 1point3acres.com for more.
                        return true;. 1point 3acres 璁哄潧
                }
                sb.deleteCharAt(sb.length()-1);
                sb.deleteCharAt(sb.length()-1);
                /************************************************************************/
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                /*****************************当前插入符号‘/’*****************************/.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if(nums[pos] != 0){                         //如果当前的数是0,则不能当做除数. 1point3acres.com/bbs
                        sb.append('/');
                        sb.append(nums[pos]);. From 1point 3acres bbs
                        if(dfsHelper(nums,first,second/nums[pos],pos+1,target,sb,isPlus)){.1point3acres缃
                                return true;
                        }
                        sb.deleteCharAt(sb.length()-1);
                        sb.deleteCharAt(sb.length()-1);. from: 1point3acres.com/bbs
                }
                /*****************************当前插入符号‘+’*****************************/. more info on 1point3acres.com
                return false;
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 16:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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