《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1834|回复: 10
收起左侧

pocket gems一面

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

2015(10-12月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
basic calculator,有+,-,*,/,(,)。。。很费时,但面试官还和我一起走例子。。。
已跪了好几家了,心累。。。攒人品攒运气!希望大家找工作顺利!. 1point 3acres 璁哄潧

评分

1

查看全部评分

jzc007 发表于 2015-11-13 06:55:50 | 显示全部楼层
patpat 他家竟然换题了
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-11-13 07:16:57 | 显示全部楼层
LZ写出来了吗?这个临时写挺难的啊。。
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-13 07:23:36 | 显示全部楼层
lzyfriday 发表于 2015-11-13 07:16
LZ写出来了吗?这个临时写挺难的啊。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
写出来了,不过超时了。。coding之前聊了一刻钟,结束的时候发现面了一小时。。这个题走例子也费时间,我写完后自己主动走了一个例子,fix了一个bug,然后面试官给了一个更长的例子,又fix了一个bug。。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-11-13 07:28:29 | 显示全部楼层
moyier 发表于 2015-11-13 07:23
写出来了,不过超时了。。coding之前聊了一刻钟,结束的时候发现面了一小时。。这个题走例子也费时间,我 ...

用两个stack做的吗?
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-13 07:56:07 | 显示全部楼层
水逼一枚 发表于 2015-11-13 07:28
用两个stack做的吗?
. more info on 1point3acres.com
我就用了一个stack,遍历string的时候碰到数字、(就直接push;碰到+、-就处理前一个运算直到stack空或者stack top是(,然后push结果和运算符;碰到*、/要检查前一个运算,如果是+、-就不处理,如果是*、/就处理,push结果和运算符;碰到)就处理前一个运算,但是push结果之前要pop掉(

因为每次一边push一边在运算,所以保证了stack括号之间只有一个运算或只是一个数字,最后return之前也是。

已经被自己搞晕了。。
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-11-13 08:13:31 | 显示全部楼层
  1. public class BasicCalculator {
  2. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.         public static void main(String[] args) {
  4.                 // TODO Auto-generated method stub
  5.                 BasicCalculator solution = new BasicCalculator();.1point3acres缃
  6.                 System.out.println(solution.calculate("( 1 + 8 ) - ( ( 3 * 4 ) / 2 )"));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.         }
  8.        
  9.         /**
  10.          * first transfer to RPN and then calculate the RPN
  11.          * @param form
  12.          * @return
  13.          */
  14.         public int calculate(String form){. visit 1point3acres.com for more.
  15.                 ArrayList<String> polish = convertToRPN(form);
  16.                 Stack<Integer> stack = new Stack<Integer>();
    -google 1point3acres
  17.                 for(String token : polish){
  18.                         switch(token){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.                                 case "+":{
  20.                                         stack.push(stack.pop() + stack.pop());. From 1point 3acres bbs
  21.                                         break;
  22.                                 }
  23.                                 case "-":{
  24.                                         int a = stack.pop();
  25.                                         int b = stack.pop();
  26.                                         stack.push(b - a);
  27.                                         break;
  28.                                 }
  29.                                 case "*":{
  30.                                         stack.push(stack.pop() * stack.pop());
  31.                                         break;
  32.                                 }
  33.                                 case "/":{
  34.                                         int a = stack.pop();
  35.                                         int b = stack.pop();. 1point 3acres 璁哄潧
  36.                                         stack.push(b / a);
  37.                                         break;. visit 1point3acres.com for more.
  38.                                 }
  39.                                 default:{
  40.                                         stack.push(Integer.parseInt(token));
  41.                                 }
  42.                         }
  43.                 }
  44.                 return stack.peek();
  45.         }
  46.         -google 1point3acres
  47.         /**
  48.          * transfer the form to Reverse Polish Notation
  49.          * @param form-google 1point3acres
  50.          * @return
  51.          */
  52.         public ArrayList<String> convertToRPN(String form){
  53.                 String[] tokens = form.split("\\s+");
  54.                
  55.                 ArrayList<String> out = new ArrayList<String>();
  56.                 Stack<String> stack = new Stack();
  57.                
  58.                 for(String token : tokens){
  59.                        
  60.                         //add numbers to out stream direclty
  61.                         if(!isOperator(token)){
  62.                                 out.add(token);
  63.                         }else{
  64.                                 //if the token is ")", pop stack to out until meet "("
  65.                                 //otherwise push the operator into stack 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66.                                 if(!token.equals(")")){
  67.                                         stack.push(token);
  68.                                 }else{
  69.                                         while(!stack.peek().equals("(")){
  70.                                                 out.add(stack.pop());
  71.                                         }
  72.                                         stack.pop();
  73.                                 }
  74.                         }
  75.                 }. from: 1point3acres.com/bbs
  76.                 while(!stack.isEmpty()){
  77.                         out.add(stack.pop());
  78.                 }
  79.                
  80.                 return out;
  81.         }
  82.         private boolean isOperator(String s){
  83.                 return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")");
  84.         }

  85. }
复制代码


先把式子转化成reverse polish notation, 然后解RPN
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-11-13 08:26:59 | 显示全部楼层
lzyfriday 发表于 2015-11-13 08:13
先把式子转化成reverse polish notation, 然后解RPN

中缀表达式转后缀表达式,之前没写过的话现场很难写出来吧,几个rules还是得强行记忆一下。
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-18 12:13:13 | 显示全部楼层
你好,请问下考不考虑负数的情况?
比如3 * -2 ?
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-18 14:29:05 | 显示全部楼层
我也贴一下我的代码。感觉这题非常难写对啊。不知道面起来怎么办。
  1.         public static int calculate(String s) {. visit 1point3acres.com for more.
  2.             if (s == null || s.length() == 0) return 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.             Deque<Integer> stk = new LinkedList<Integer>();
  4.             Deque<Character> chstk = new LinkedList<Character>();
  5.             int num = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.             char sign = '+';. 1point3acres.com/bbs
  7.             int re = 0;
  8.             for (int i = 0; i < s.length(); i++) {. 鍥磋鎴戜滑@1point 3 acres
  9.                     char ch = s.charAt(i);
  10.                     if (Character.isDigit(ch)) {
  11.                             num = num * 10 + ch - '0';
  12.                     }
  13.                     if (ch == '*' || ch == '/') {
  14.                             if (sign == '*') re *= num;
  15.                             if (sign == '/') re /= num;
  16.                             if (sign == '+' || sign == '-') { // push. Waral 鍗氬鏈夋洿澶氭枃绔,
  17.                                     stk.push(re);
  18.                                     chstk.push(sign);
  19.                                     re = num;
  20.                             }
  21.                             sign = ch;
  22.                             num = 0;
  23.                     }
  24.                     if (ch == '+' || ch =='-') {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                             if (sign == '+') re += num;
  26.                             if (sign == '-') re -= num;
  27.                             if (sign == '*' || sign == '/') { // pop. 1point3acres.com/bbs
  28.                                     if (sign == '*') re *= num;. 1point 3acres 璁哄潧
  29.                                     if (sign == '/') re /= num;
  30.                                     char sg = chstk.pop();
  31.                                     if (sg == '+') re = stk.pop() + re;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.                                     if (sg == '-') re = stk.pop() - re;
  33.                             }
  34.                             sign = ch; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.                             num = 0;
  36.                     }
  37.                     if (ch == '(') { // push
  38.                             stk.push(re);
  39.                             chstk.push(sign);
  40.                             num = 0;
  41.                             sign = '+';
  42.                             re = 0;
  43.                     }
  44.                     if (ch == ')') { // pop
  45.                             if (sign == '+') re += num;
  46.                             if (sign == '-') re -= num;
  47.                             if (sign == '*' || sign == '/') { // pop
  48.                                     if (sign == '*') re *= num;
  49.                                     if (sign == '/') re /= num;
  50.                                     char sg = chstk.pop();. 鍥磋鎴戜滑@1point 3 acres
  51.                                     if (sg == '+') re = stk.pop() + re;
  52.                                     if (sg == '-') re = stk.pop() - re;
  53.                             }
  54.                             num = re;
  55.                             sign = chstk.pop();
  56.                             re = stk.pop();
  57.                     }
  58.             }
  59.             if (stk.size() > 0) {
  60.                     if (sign == '*') re *= num;
  61.                     if (sign == '/') re /= num;
  62.                     num = re;
  63.                     sign = chstk.pop();
  64.                     re = stk.pop();
  65.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66.             if (num != 0) {
  67.                     if (sign == '+') re += num;. 1point3acres.com/bbs
  68.                     if (sign == '-') re -= num; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  69.                     if (sign == '*') re *= num;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  70.                     if (sign == '/') re /= num;
  71.             }
  72.             return re;
  73.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-19 07:57:55 | 显示全部楼层
甯甯 发表于 2015-11-18 14:29
我也贴一下我的代码。感觉这题非常难写对啊。不知道面起来怎么办。

已跪估计有些地方考虑得不够周全,当时一听题目就有不好的感觉了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 19:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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