一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1794|回复: 34
收起左侧

Snapchat 面经请教

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-10-18 11:48:12 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
面经的高频题calculator加括号,但是看到一个follow up是只加一个括号,求最大值,请问这个怎么做呢?

多谢各位大神。
小A要当码农 发表于 2016-10-26 00:45:24 | 显示全部楼层

没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个dp[j] 然后遍历所有的加括号组合, 从dp矩阵中得到括号内的evaluation的值和括号左右两边的evaluation的值。。 同时还要记录每一部分值的lastAdd, 感觉有点麻烦。。。
回复 支持 0 反对 1

使用道具 举报

linweihua0 发表于 2016-10-19 03:14:00 | 显示全部楼层
是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-10-19 03:20:42 | 显示全部楼层
linweihua0 发表于 2016-10-19 03:14
是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗

原输入没有括号~
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-19 03:22:18 来自手机 | 显示全部楼层
那就二维dp 然后遍历一次所以可以加括号的地方 n^2
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-10-19 03:57:41 | 显示全部楼层
linweihua0 发表于 2016-10-19 03:22. visit 1point3acres.com for more.
那就二维dp 然后遍历一次所以可以加括号的地方 n^2
. 鍥磋鎴戜滑@1point 3 acres
转移方程怎么写?比如5+6/5*5,dp[j]表示括号加在index i 和 j这样两个地方?
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-19 05:23:28 | 显示全部楼层
如果有 * / + -的话 我觉得存两个状态 因为没有括号的情况最多是两层stack 所以左右两端各要存这两层stack
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-10-25 22:23:36 | 显示全部楼层
brute force...

  1. public class Solution {
  2.     public static void main(String[] args) {
  3.         Solution s = new Solution();. 鍥磋鎴戜滑@1point 3 acres
  4.         String str = "9+3*2+3";
  5.         System.out.println(str);
  6.         System.out.println(s.getExpMax(str));
  7.     }


  8.     public int getExpMax(String s) {
  9.         int n = s.length();
  10.         int ind = 0;

  11.         int max = 0;
  12.         List<Integer> finalLast = new ArrayList<>();
  13.         List<Integer> finalRes = new ArrayList<>();
  14.         List<Integer> openLast = new ArrayList<>();
  15.         List<Integer> openRes = new ArrayList<>();
  16.         List<Integer> openPrev = new ArrayList<>();
  17.         List<Integer> openPrevLast = new ArrayList<>();.1point3acres缃
  18.         List<Character> openOp = new ArrayList<>();
  19.         //note the first element in the final list is the version without brackets
  20.         finalLast.add(0);
  21.         finalRes.add(0);

  22.         int curVal = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.         char op = '+';
  24.         while (ind < n) {
  25.             if (s.charAt(ind) >= '0' && s.charAt(ind) <= '9') {
  26.                 while (ind < n && Character.isDigit(s.charAt(ind))) {
  27.                     curVal = curVal * 10 + s.charAt(ind) - '0';. From 1point 3acres bbs
  28.                     ind++;
  29.                 }. from: 1point3acres.com/bbs
  30.                 //after reading a value we should do calculation
  31.                 //do final calculation first
  32.                 int prevRes = finalRes.get(0);
  33.                 int prevResLast = finalLast.get(0);
  34.                 calculateList(finalLast, finalRes, curVal, op);
  35.                 calculateList(openLast, openRes, curVal, op);
  36.                 //now we can close the brackets and add it to final
  37.                 for (int i = 0; i < openRes.size(); i++) {
  38.                     int prevResult = openPrev.get(i);
  39.                     char prevOp = openOp.get(i);. 1point3acres.com/bbs
  40.                     int closeVal = openRes.get(i);
  41.                     int prevResultLast = openPrevLast.get(i);
  42.                     if (prevOp == '+') {
  43.                         finalRes.add(prevResult + closeVal);
  44.                         finalLast.add(closeVal);
  45.                     } else if (prevOp == '-') {
  46.                         finalRes.add(prevResult - closeVal);
  47.                         finalLast.add(-closeVal);
  48.                     } else if (prevOp == '*') {
  49.                         finalRes.add(prevResult - prevResultLast + prevResultLast * closeVal);
  50.                         finalLast.add(prevResultLast * closeVal);
  51.                     } else {
  52.                         finalRes.add(prevResult - prevResultLast + prevResultLast/closeVal);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  53.                         finalLast.add(prevResultLast/closeVal);
  54.                     }. From 1point 3acres bbs
  55.                 }
  56. . 1point 3acres 璁哄潧

  57.                 //add to open, means this element is the starting of the bracket 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58.                 openLast.add(curVal);
  59.                 openRes.add(curVal);
  60.                 openOp.add(op);
  61.                 openPrev.add(prevRes);
  62.                 openPrevLast.add(prevResLast);
  63.                 curVal = 0;
  64. . 鍥磋鎴戜滑@1point 3 acres

  65.             } else if (s.charAt(ind) == ' ') ind++;
  66.             else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  67.                 //operators
  68.                 op = s.charAt(ind);
  69.                 ind++;

  70.             }
  71.         }
  72.         System.out.println("list of results");
  73.         for (int r : finalRes) {
  74.             System.out.println(r);
  75.         }. 1point 3acres 璁哄潧
  76.         max = Collections.max(finalRes);
  77.         return max;

  78.     }



  79.     public void calculateList(List<Integer> finalLast, List<Integer> finalRes, int curVal, char op) {
  80.         for (int i = 0; i < finalLast.size(); i++) {
  81.             int last = finalLast.get(i);
  82.             int left = finalRes.get(i);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  83.             if (op == '+') {
  84.                 finalRes.set(i, left+curVal);
  85.                 finalLast.set(i, curVal);
  86.             } else if (op == '-') {. visit 1point3acres.com for more.
  87.                 finalRes.set(i, left-curVal);
  88.                 finalLast.set(i, -curVal);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  89.             } else if (op == '*') {
  90.                 finalRes.set(i, left-last+last*curVal);
  91.                 finalLast.set(i, last*curVal);
  92.             } else {
  93.                 finalRes.set(i, left-last+last/curVal);
  94.                 finalLast.set(i, last/curVal);
  95.             }
  96.         }
  97.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  98. }

  99. /*

  100. 9+3*2+3
  101. list of results . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  102. 18
  103. 27 . 1point3acres.com/bbs
  104. 18
  105. 18
  106. 18
  107. 18
  108. 24


  109. */
复制代码
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-26 00:01:30 | 显示全部楼层
帮顶,同求问follow up,地里有大神会么?
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-10-26 00:35:42 | 显示全部楼层
小A要当码农 发表于 2016-10-26 00:01
帮顶,同求问follow up,地里有大神会么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
as above
回复 支持 反对

使用道具 举报

Liuology 发表于 2016-10-26 01:01:17 | 显示全部楼层
小A要当码农 发表于 2016-10-26 00:45. 鍥磋鎴戜滑@1point 3 acres
没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个 ...
. more info on 1point3acres.com
idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结果
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-26 02:34:43 | 显示全部楼层
Liuology 发表于 2016-10-26 01:01
idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结 ...

好的 多谢 我研究一下。。
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-3 10:29:41 | 显示全部楼层
这样行不行 比如   2+3/3-4 咱就用最笨的方法,对于每一个部分式 咱都求个值,因为evaluate  只是o(n) 所以这一步是o(n^2),思路就是区间DP
. From 1point 3acres bbs
for(int len=3;len<=s.length();len++)
for(int left=1;left+len-1<s.length();left++). From 1point 3acres bbs
{. 1point 3acres 璁哄潧
    int right = left+len-1;
    for(int mid=left+1;mid<right;mid+=2)
       {
            先做一次这个len范围内的值,可以用dp记一下,然后把这个值tostring,加上后面的式子,再做一次evaluate
       }
}

总时间应该是o(n^4),虽然慢了点。。但是能出结果,,,接下来就是拼人品了,,再慢慢优化吧
. From 1point 3acres bbs
补充内容 (2016-11-3 10:30):
left += 2
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-11-3 10:36:51 | 显示全部楼层
clxy2008 发表于 2016-11-3 10:29
这样行不行 比如   2+3/3-4 咱就用最笨的方法,对于每一个部分式 咱都求个值,因为evaluate  只是o(n) 所 ...

怎么O(n ^ 4)了呢,brute force也才n ^ 3呀
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-3 10:44:56 | 显示全部楼层
噢。。我傻了,区间dp不用最外面那一层。。是o(n^3)
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-3 10:45:59 | 显示全部楼层
就是brute force 既然不是指数级,dp也没意义了 直接bf恁
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-11-3 10:47:38 | 显示全部楼层
clxy2008 发表于 2016-11-3 10:45
就是brute force 既然不是指数级,dp也没意义了 直接bf恁

我也觉得,这种情况,感觉最好先写出来能run了就好
回复 支持 反对

使用道具 举报

kradnangel 发表于 2016-11-5 04:11:03 | 显示全部楼层
楼主你好,calculator加括号原题是给一组数,随便加 + * () 吧。所以follow up意思是随便加+*,然后只能加一个()吧?所以也不知道哪里该加+*,是这样吗?这样解法和“+*符号确定,找个位置加一组()”会不一样嗯
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-11-5 04:12:52 | 显示全部楼层
kradnangel 发表于 2016-11-5 04:11
楼主你好,calculator加括号原题是给一组数,随便加 + * () 吧。所以follow up意思是随便加+*,然后 ...

不是这个,这个只加了括号求值,然后follow up是给你一个string, 加减乘除都有了,只加一个括号,求最大值
回复 支持 反对

使用道具 举报

kradnangel 发表于 2016-11-5 04:25:04 | 显示全部楼层
神罗天征 发表于 2016-11-5 04:12. 1point 3acres 璁哄潧
不是这个,这个只加了括号求值,然后follow up是给你一个string, 加减乘除都有了,只加一个括号,求最大 ...

楼主回复好快! 但还是没太明白原题,是给string,随便加(),求max吗?。。。follow up懂了。暴力解的确就是,for 枚举(位置,for枚举)位置,计算整个式子值。O(N^3)。好一点的解法,我的想法是,先处理字符串,取出numbers list 和 operations list,然后预处理计算 任意两个数字位置之间的计算结果(O(N^2)),然后DP,其实就是分别枚举(和)位置,但是计算整个式子的值会变成O(1)(因为预处理)。然后整个时间复杂度应该可以降到O(N^2)。我想,预处理和计算值的关键应该是还要记录一下+-的位置。  没实现过,先讲讲想法,欢迎讨论!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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