推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

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

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

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

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

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

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
12345, 27-> 1+2*3+4*5

然后我问了数字顺序能不能变,答说不能;问了要不要括号,答说不能用括号。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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

妥妥了跪了,来问问有没有大神能说下解法? 有java解法最好了,C++看不懂==
. Waral 鍗氬鏈夋洿澶氭枃绔,.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-9-25 11:08):. From 1point 3acres bbs
没想到面试完两天之后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:]):
  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 | 显示全部楼层
关注一亩三分地微博:
Warald
backtracking+stack计算的,计算的时候因为是字符串转换的数字,可能会溢出,用了long,但是其实如果极端长还是会溢出,后来想到其实可以先从个位开始一位一位的运算并和target比较,这样就不会有特别长的数溢出的问题了,不过实现起来稍微麻烦点。
  1.   public String calculateToSum(String str, int tar) {
  2.     if (str == null || str.length() == 0) {
  3.       return ""; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.     }
  5. . more info on 1point3acres.com
  6.     StringBuilder ans = new StringBuilder(str);
  7.     return dfsHelper(ans, 1, tar);
  8. . 1point3acres.com/bbs
  9.   }

  10.   private String dfsHelper(StringBuilder ans, int pos, int tar) {
  11.     if (pos >= ans.length()) {
  12.       if (calculate(ans.toString()) == tar) {
  13.         return ans.toString();
  14.       }
  15.       return null;
  16.     }

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

  18.     for (int i = 0; pos + i < ans.length(); i++) {
  19.       for (int j = 0; j < 4; j++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.         ans.insert(pos + i, operator[j]);
  21.         String temp = dfsHelper(ans, pos + i + 2, tar);
  22.         if (temp != null) {
  23.           return temp;.1point3acres缃
  24.         }
  25.         ans.deleteCharAt(pos + i);
  26.       }. 1point 3acres 璁哄潧
  27.     }
  28. . visit 1point3acres.com for more.
  29.     return null;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.   }

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

  34.     int[] pri = new int[128];
  35.     pri['+'] = 1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.     pri['-'] = 1;
  37.     pri['*'] = 2;
    -google 1point3acres
  38.     pri['/'] = 2;

  39.     for (int i = 0; i < e.length(); i++) {
  40.       char c = e.charAt(i);. visit 1point3acres.com for more.
  41.       if (Character.isDigit(c)) {
  42.         int right = i + 1;
  43.         while (right < e.length() && Character.isDigit(e.charAt(right))) {
  44.           right++;
  45.         }. 1point 3acres 璁哄潧
  46.         operands.push(Long.parseLong(e.substring(i, right)));
  47.         i = right - 1;
  48.       } else {-google 1point3acres
  49.         if (!operator.isEmpty() && ((pri[c] < pri[operator.peek()]) || (pri[c] == pri[operator
  50.             .peek()] && pri[c] == 2))) {
  51.           operands.push(op(operands.pop(), operands.pop(), operator.pop()));
  52.         }. from: 1point3acres.com/bbs
  53. . from: 1point3acres.com/bbs
  54.         operator.push(c);
  55.       }
  56.     }. from: 1point3acres.com/bbs

  57.     while (!operator.isEmpty()) {
  58.       operands.push(op(operands.pop(), operands.pop(), operator.pop()));
  59.     }

  60.     return operands.pop();
  61.   }
  62. . 鍥磋鎴戜滑@1point 3 acres
  63.   private long op(long a, long b, Character operator) {
  64.     long result = 0L;
  65.     if (operator == '+') {
  66.       result =  b + a;. Waral 鍗氬鏈夋洿澶氭枃绔,
  67.     } else if (operator == '-') {
  68.       result =  b - a;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  69.     } else if (operator == '*') {
  70.       result =  b * a;
  71.     } else if (operator == '/') {. from: 1point3acres.com/bbs
  72.       if (a == 0) {
  73.         result =  Long.MAX_VALUE;
  74.       }.1point3acres缃
  75.       result =  b / a;
  76.     }
  77.     result = result > Integer.MAX_VALUE? Integer.MAX_VALUE + 1: result;
  78.     result = result < Integer.MIN_VALUE? Integer.MIN_VALUE - 1: result;
  79.     return result;
  80.   }
复制代码
回复 支持 1 反对 0

使用道具 举报

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

话说语言本身很多相通的,尤其是这些算法题并没有用到复杂的语言本身的机制,应该不存在看不懂的问题,我只会写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
应该就是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>
  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;
  14.     if(p>=s) {. 1point 3acres 璁哄潧
  15.         lhs = eval_sub(s,p), rhs = eval_sub(p+1,t);
  16.         if(*p=='*') return lhs*rhs;
  17.         if(*p=='/') return lhs/rhs;
  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);. more info on 1point3acres.com
  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;
  30.     cout<<eval("1*2/2+3-2*3")<<endl;
  31. }-google 1point3acres
复制代码
回复 支持 反对

使用道具 举报

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满足条件吗?

满足啊   只要相等就行
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

. from: 1point3acres.com/bbs 补充内容 (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 不同的问题呢?
. from: 1point3acres.com/bbs
跟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吧,如果可以这样,那可能的情况就太多了,例子里也是每个数 ...
. From 1point 3acres bbs
可以的  有多种答案只要输出一种就好 没有就返回 “No answer"
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:11:13 | 显示全部楼层
Linzertorte 发表于 2015-9-12 13:24. 鍥磋鎴戜滑@1point 3 acres
写个枚兴趣完符号求值的部分,大家感受一下。.1point3acres缃
这种简单的表达式求值,能用的方法是dijkstra双栈扫描(中缀 ...
. from: 1point3acres.com/bbs
大神啊。。方法名字我都看不懂了==
回复 支持 反对

使用道具 举报

 楼主| newyorker89 发表于 2015-9-12 23:16:43 | 显示全部楼层
purplesky85 发表于 2015-9-12 20:32
backtracking+stack计算的,计算的时候因为是字符串转换的数字,可能会溢出,用了long,但是其实如果极端 ...

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 05:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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