地里同学要出来数数缺德舅的好吃的嘛

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3805|回复: 34
收起左侧

Snapchat 面经请教

[复制链接] |试试Instant~ |关注本帖
我的人缘0
神罗天征 发表于 2016-10-18 11:48:12 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (523)
 
 
2% (16)  踩

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

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

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

x
面经的高频题calculator加括号,但是看到一个follow up是只加一个括号,求最大值,请问这个怎么做呢?
. 1point3acres
多谢各位大神。

上一篇:亚马逊网上测评第一面刚做完但感觉有个问题存疑
下一篇:Amazon OA2
我的人缘0
小A要当码农 发表于 2016-10-26 00:45:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩

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

使用道具 举报

我的人缘0
linweihua0 发表于 2016-10-19 03:14:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗
回复

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-10-19 03:20:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (523)
 
 
2% (16)  踩
linweihua0 发表于 2016-10-19 03:14.留学论坛-一亩-三分地
是指输入一个 5+6/5*5的string 然后加括号吗 原输入有括号吗

原输入没有括号~
回复

使用道具 举报

我的人缘0
linweihua0 发表于 2016-10-19 03:22:18 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
那就二维dp 然后遍历一次所以可以加括号的地方 n^2
回复

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-10-19 03:57:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (523)
 
 
2% (16)  踩
linweihua0 发表于 2016-10-19 03:22
那就二维dp 然后遍历一次所以可以加括号的地方 n^2

转移方程怎么写?比如5+6/5*5,dp[j]表示括号加在index i 和 j这样两个地方?
回复

使用道具 举报

我的人缘0
linweihua0 发表于 2016-10-19 05:23:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
如果有 * / + -的话 我觉得存两个状态 因为没有括号的情况最多是两层stack 所以左右两端各要存这两层stack
回复

使用道具 举报

我的人缘0
Liuology 发表于 2016-10-25 22:23:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
brute force...

  1. public class Solution {
  2.     public static void main(String[] args) {
  3.         Solution s = new Solution();
  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<>();.本文原创自1point3acres论坛
  15.         List<Integer> openRes = new ArrayList<>();
  16.         List<Integer> openPrev = new ArrayList<>();
  17.         List<Integer> openPrevLast = new ArrayList<>();
  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))) {. 1point3acres
  27.                     curVal = curVal * 10 + s.charAt(ind) - '0';
  28.                     ind++;
  29.                 }
  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);.1point3acres网
  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);
  40.                     int closeVal = openRes.get(i);
  41.                     int prevResultLast = openPrevLast.get(i);. 1point3acres
  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);. 围观我们@1point 3 acres
  53.                         finalLast.add(prevResultLast/closeVal);.1point3acres网
  54.                     }
  55.                 }
  56. .留学论坛-一亩-三分地

  57.                 //add to open, means this element is the starting of the bracket. 1point 3acres 论坛
  58.                 openLast.add(curVal);
  59.                 openRes.add(curVal);
  60.                 openOp.add(op);
  61.                 openPrev.add(prevRes);
  62.                 openPrevLast.add(prevResLast);
  63.                 curVal = 0;


  64.             } else if (s.charAt(ind) == ' ') ind++;
  65.             else {
  66.                 //operators
  67.                 op = s.charAt(ind);
  68.                 ind++;
  69. . from: 1point3acres
  70.             }. 留学申请论坛-一亩三分地
  71.         }
  72.         System.out.println("list of results");
  73.         for (int r : finalRes) {
  74.             System.out.println(r);
  75.         }
  76.         max = Collections.max(finalRes);. more info on 1point3acres
  77.         return max;

  78.     }


  79. . 留学申请论坛-一亩三分地
  80.     public void calculateList(List<Integer> finalLast, List<Integer> finalRes, int curVal, char op) {
  81.         for (int i = 0; i < finalLast.size(); i++) {
  82.             int last = finalLast.get(i);
  83.             int left = finalRes.get(i);
  84.             if (op == '+') {
  85.                 finalRes.set(i, left+curVal);
  86.                 finalLast.set(i, curVal);. Waral 博客有更多文章,
  87.             } else if (op == '-') {
  88.                 finalRes.set(i, left-curVal);
  89.                 finalLast.set(i, -curVal);
  90.             } else if (op == '*') {
  91.                 finalRes.set(i, left-last+last*curVal);. visit 1point3acres for more.
  92.                 finalLast.set(i, last*curVal);
  93.             } else {
  94.                 finalRes.set(i, left-last+last/curVal);
    .留学论坛-一亩-三分地
  95.                 finalLast.set(i, last/curVal);
  96.             }. 1point 3acres 论坛
  97.         }
  98.     }
  99. }

  100. /*. Waral 博客有更多文章,

  101. 9+3*2+3
  102. list of results
  103. 18 . visit 1point3acres for more.
  104. 27 . 牛人云集,一亩三分地
  105. 18
  106. 18
  107. 18
  108. 18
  109. 24 . 一亩-三分-地,独家发布
  110. -google 1point3acres
  111. . 围观我们@1point 3 acres
  112. */
复制代码
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-10-26 00:01:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
帮顶,同求问follow up,地里有大神会么?
回复

使用道具 举报

我的人缘0
Liuology 发表于 2016-10-26 00:35:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
小A要当码农 发表于 2016-10-26 00:01
帮顶,同求问follow up,地里有大神会么?

as above
回复

使用道具 举报

我的人缘0
Liuology 发表于 2016-10-26 01:01:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
小A要当码农 发表于 2016-10-26 00:45.1point3acres网
没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个 ...

idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结果
回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-10-26 02:34:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
Liuology 发表于 2016-10-26 01:01
idea就是每读完一个数字后开一个new bracket 加到list里面同时计算之前打开bracket的结果。。和最终的结 ...

好的 多谢 我研究一下。。
回复

使用道具 举报

我的人缘0
clxy2008 发表于 2016-11-3 10:29:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (50)
 
 
0% (0)  踩
这样行不行 比如   2+3/3-4 咱就用最笨的方法,对于每一个部分式 咱都求个值,因为evaluate  只是o(n) 所以这一步是o(n^2),思路就是区间DP

for(int len=3;len<=s.length();len++)
.1point3acres网for(int left=1;left+len-1<s.length();left++)
{
    int right = left+len-1;
    for(int mid=left+1;mid<right;mid+=2)
       {. 留学申请论坛-一亩三分地
            先做一次这个len范围内的值,可以用dp记一下,然后把这个值tostring,加上后面的式子,再做一次evaluate
       }
}

总时间应该是o(n^4),虽然慢了点。。但是能出结果,,,接下来就是拼人品了,,再慢慢优化吧

补充内容 (2016-11-3 10:30):.留学论坛-一亩-三分地
left += 2
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
clxy2008 发表于 2016-11-3 10:44:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (50)
 
 
0% (0)  踩
噢。。我傻了,区间dp不用最外面那一层。。是o(n^3)
回复

使用道具 举报

我的人缘0
clxy2008 发表于 2016-11-3 10:45:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (50)
 
 
0% (0)  踩
就是brute force 既然不是指数级,dp也没意义了 直接bf恁
回复

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-11-3 10:47:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (523)
 
 
2% (16)  踩
clxy2008 发表于 2016-11-3 10:45
就是brute force 既然不是指数级,dp也没意义了 直接bf恁

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-11-5 04:12:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (523)
 
 
2% (16)  踩
kradnangel 发表于 2016-11-5 04:11
楼主你好,calculator加括号原题是给一组数,随便加 + * () 吧。所以follow up意思是随便加+*,然后 ...

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

使用道具 举报

我的人缘0
kradnangel 发表于 2016-11-5 04:25:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
神罗天征 发表于 2016-11-5 04:12
不是这个,这个只加了括号求值,然后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)。我想,预处理和计算值的关键应该是还要记录一下+-的位置。  没实现过,先讲讲想法,欢迎讨论!
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-16 10:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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