一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3415|回复: 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
for example
123,6 -> 1+2+3. 1point3acres.com/bbs
12345, 27-> 1+2*3+4*5.1point3acres缃

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

最开始就想到了类似leetcode basic calculator,后来又想到了用backtracking,但是backtracking不是很熟,写了半天也没写对,时间到了就问了几个问题就thank you了
. more info on 1point3acres.com
妥妥了跪了,来问问有没有大神能说下解法? 有java解法最好了,C++看不懂==. From 1point 3acres bbs


补充内容 (2015-9-25 11:08):
没想到面试完两天之后leetcode就加了这道题,这人品。。。. from: 1point3acres.com/bbs
. From 1point 3acres bbs
补充内容 (2015-9-25 11:09):. more info on 1point3acres.com
电面已过,onsite去了

评分

6

查看全部评分

本帖被以下淘专辑推荐:

Linzertorte 发表于 2015-9-12 13:30:45 | 显示全部楼层
  1. def get_next(xs):
  2.   if xs=='':
  3.     yield ''
  4.     return. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.   for x in get_next(xs[1:]):
  6.     for h in ['','+','*','-','/']:. more info on 1point3acres.com
  7.       yield h+xs[:1]+x

  8. def f(xs,val):
  9.   for x in get_next(xs[1:]):.1point3acres缃
  10.     if eval(xs[:1]+x)==val:
  11.        return xs[:1]+x
  12.   return "no solution"

  13. print '123->6,',f('123',6)
  14. print '12345->27, ', f('12345',27)
复制代码
回复 支持 1 反对 0

使用道具 举报

purplesky85 发表于 2015-9-12 20:32:26 | 显示全部楼层
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. .1point3acres缃
  8.   }

  9.   private String dfsHelper(StringBuilder ans, int pos, int tar) {
  10.     if (pos >= ans.length()) {
  11.       if (calculate(ans.toString()) == tar) {
  12.         return ans.toString();. visit 1point3acres.com for more.
  13.       }
  14.       return null;
  15.     }. visit 1point3acres.com for more.

  16.     char[] operator = {'+', '-', '*', '/'};
  17. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.     for (int i = 0; pos + i < ans.length(); i++) {
  19.       for (int j = 0; j < 4; j++) {
  20.         ans.insert(pos + i, operator[j]);
  21.         String temp = dfsHelper(ans, pos + i + 2, tar);
  22.         if (temp != null) {
  23.           return temp;
  24.         }
  25.         ans.deleteCharAt(pos + i);. more info on 1point3acres.com
  26.       }
  27.     }

  28.     return null;
  29.   }

  30.   private long calculate(String e) {
  31.     Stack<Character> operator = new Stack<>();
  32.     Stack<Long> operands = new Stack<>();

  33.     int[] pri = new int[128];. visit 1point3acres.com for more.
  34.     pri['+'] = 1;
  35.     pri['-'] = 1;. 鍥磋鎴戜滑@1point 3 acres
  36.     pri['*'] = 2;
  37.     pri['/'] = 2;

  38.     for (int i = 0; i < e.length(); i++) {
  39.       char c = e.charAt(i);. more info on 1point3acres.com
  40.       if (Character.isDigit(c)) {
  41.         int right = i + 1;
  42.         while (right < e.length() && Character.isDigit(e.charAt(right))) {
  43.           right++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.         }. visit 1point3acres.com for more.
  45.         operands.push(Long.parseLong(e.substring(i, right)));
  46.         i = right - 1;
  47.       } else {
  48.         if (!operator.isEmpty() && ((pri[c] < pri[operator.peek()]) || (pri[c] == pri[operator
  49.             .peek()] && pri[c] == 2))) {
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.           operands.push(op(operands.pop(), operands.pop(), operator.pop()));
  51.         }

  52.         operator.push(c);
  53.       }
  54.     }

  55.     while (!operator.isEmpty()) {
  56.       operands.push(op(operands.pop(), operands.pop(), operator.pop()));
  57.     }
  58. . 1point 3acres 璁哄潧
  59.     return operands.pop();
  60.   }. 1point3acres.com/bbs

  61.   private long op(long a, long b, Character operator) {
  62.     long result = 0L;
  63.     if (operator == '+') {
  64.       result =  b + a;
  65.     } else if (operator == '-') {. 1point3acres.com/bbs
  66.       result =  b - a;
  67.     } else if (operator == '*') {
  68.       result =  b * a;
  69.     } else if (operator == '/') {
  70.       if (a == 0) {
  71.         result =  Long.MAX_VALUE;
  72.       }
  73.       result =  b / a;
  74.     }
  75.     result = result > Integer.MAX_VALUE? Integer.MAX_VALUE + 1: result;. more info on 1point3acres.com
  76.     result = result < Integer.MIN_VALUE? Integer.MIN_VALUE - 1: result;
  77.     return result;
  78.   }
复制代码
回复 支持 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. Waral 鍗氬鏈夋洿澶氭枃绔,
应该就是back tracking + stack吧

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

使用道具 举报

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

使用道具 举报

Linzertorte 发表于 2015-9-12 13:24:14 | 显示全部楼层
写个枚兴趣完符号求值的部分,大家感受一下。. from: 1point3acres.com/bbs
这种简单的表达式求值,能用的方法是dijkstra双栈扫描(中缀转后缀),或者编译原理中的recursive descent.
  1. #include<iostream>. From 1point 3acres bbs
  2. #include<string.h>
  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;. from: 1point3acres.com/bbs
  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: 1point3acres.com/bbs
  14.     if(p>=s) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
  16.         if(*p=='*') return lhs*rhs;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.         if(*p=='/') return lhs/rhs;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.     }
  19.     int x = 0;. 1point 3acres 璁哄潧
  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);. more info on 1point3acres.com
  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;
  30.     cout<<eval("1*2/2+3-2*3")<<endl;
  31. }
复制代码
回复 支持 反对

使用道具 举报

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满足条件吗?
. visit 1point3acres.com for more.
满足啊   只要相等就行
回复 支持 反对

使用道具 举报

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了代码
.1point3acres缃
谢谢!我去看一下
回复 支持 反对

使用道具 举报

 楼主| 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,但是其实如果极端 ...

我也是类似的方法  看了你的代码 感觉我在helper那一块写的有问题  多谢分享
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-12 23:24:38 | 显示全部楼层
写了一个比较简单的dfs算法,思路是可以把前面的按照最后一个'+'或'-'的位置分成两部分,然后分别讨论在当前位置插入'+','-','*','/'的情况. 1point 3acres 璁哄潧
感觉电面问这个好难,当场估计写不出来
public static String addOperation(String s,int target){.1point3acres缃
                if(s == null || s.length() == 0){
                        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]);. from: 1point3acres.com/bbs
                boolean flag = dfsHelper(nums,0,nums[0],1,target,sb,true);.1point3acres缃
                if(flag){
. From 1point 3acres bbs                        return sb.toString();
                }
                return "";
        }
        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;
                }
                /*****************************当前插入符号‘+’*****************************/
                sb.append('+');
                sb.append(nums[pos]);
                if(isPlus){
                        if(dfsHelper(nums,first+second,nums[pos],pos+1,target,sb,true)){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                return true;
                        }
                }. from: 1point3acres.com/bbs
                else{
                        if(dfsHelper(nums,first-second,nums[pos],pos+1,target,sb,true)){
                                return true;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }
                }
                sb.deleteCharAt(sb.length()-1);. more info on 1point3acres.com
                sb.deleteCharAt(sb.length()-1);
                /************************************************************************/
                /*****************************当前插入符号‘-’*****************************/ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                sb.append('-');
                sb.append(nums[pos]);
                if(isPlus){. 1point3acres.com/bbs
                        if(dfsHelper(nums,first+second,nums[pos],pos+1,target,sb,false)){
                                return true;
                        }
                }
                else{.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if(dfsHelper(nums,first-second,nums[pos],pos+1,target,sb,false)){
                                return true;
                        }. visit 1point3acres.com for more.
                }.1point3acres缃
                sb.deleteCharAt(sb.length()-1);
                sb.deleteCharAt(sb.length()-1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                /************************************************************************/. Waral 鍗氬鏈夋洿澶氭枃绔,
                /*****************************当前插入符号‘*’*****************************/
                sb.append('*');
                sb.append(nums[pos]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                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);
                /************************************************************************/
                /*****************************当前插入符号‘/’*****************************/. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if(nums[pos] != 0){                         //如果当前的数是0,则不能当做除数
                        sb.append('/');
                        sb.append(nums[pos]);
                        if(dfsHelper(nums,first,second/nums[pos],pos+1,target,sb,isPlus)){
                                return true;
                        }
                        sb.deleteCharAt(sb.length()-1);
                        sb.deleteCharAt(sb.length()-1);
                }
                /*****************************当前插入符号‘+’*****************************/
                return false;
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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