如何在Toastmaster锻炼领导力

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 3878|回复: 34
收起左侧

Snapchat 面经请教

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

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

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

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

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

多谢各位大神。

上一篇:亚马逊网上测评第一面刚做完但感觉有个问题存疑
下一篇: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% (525)
 
 
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

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-10-19 03:57:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (525)
 
 
2% (16)  踩
linweihua0 发表于 2016-10-19 03:22
那就二维dp 然后遍历一次所以可以加括号的地方 n^2
. visit 1point3acres for more.
转移方程怎么写?比如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. . 牛人云集,一亩三分地
  9.     public int getExpMax(String s) {
  10.         int n = s.length();
  11.         int ind = 0;

  12.         int max = 0;. more info on 1point3acres
  13.         List<Integer> finalLast = new ArrayList<>();. 牛人云集,一亩三分地
  14.         List<Integer> finalRes = new ArrayList<>();
  15.         List<Integer> openLast = new ArrayList<>();
  16.         List<Integer> openRes = new ArrayList<>();
  17.         List<Integer> openPrev = new ArrayList<>();. more info on 1point3acres
  18.         List<Integer> openPrevLast = new ArrayList<>();
  19.         List<Character> openOp = new ArrayList<>();
  20.         //note the first element in the final list is the version without brackets
  21.         finalLast.add(0);
  22.         finalRes.add(0);
  23. . 留学申请论坛-一亩三分地
  24.         int curVal = 0;
  25.         char op = '+';
  26.         while (ind < n) {
  27.             if (s.charAt(ind) >= '0' && s.charAt(ind) <= '9') {
  28.                 while (ind < n && Character.isDigit(s.charAt(ind))) {
  29.                     curVal = curVal * 10 + s.charAt(ind) - '0';
  30.                     ind++;
  31.                 }
  32.                 //after reading a value we should do calculation
  33.                 //do final calculation first.1point3acres网
  34.                 int prevRes = finalRes.get(0);. from: 1point3acres
  35.                 int prevResLast = finalLast.get(0);
  36.                 calculateList(finalLast, finalRes, curVal, op);
  37.                 calculateList(openLast, openRes, curVal, op);. 一亩-三分-地,独家发布
  38.                 //now we can close the brackets and add it to final
  39.                 for (int i = 0; i < openRes.size(); i++) {
  40.                     int prevResult = openPrev.get(i);
  41.                     char prevOp = openOp.get(i);
  42.                     int closeVal = openRes.get(i);
  43.                     int prevResultLast = openPrevLast.get(i);
  44.                     if (prevOp == '+') {
  45.                         finalRes.add(prevResult + closeVal);
  46.                         finalLast.add(closeVal);
  47.                     } else if (prevOp == '-') {
    . 1point 3acres 论坛
  48.                         finalRes.add(prevResult - closeVal);
  49.                         finalLast.add(-closeVal);
  50.                     } else if (prevOp == '*') {
  51.                         finalRes.add(prevResult - prevResultLast + prevResultLast * closeVal);
  52.                         finalLast.add(prevResultLast * closeVal);
  53.                     } else {
  54.                         finalRes.add(prevResult - prevResultLast + prevResultLast/closeVal);
  55.                         finalLast.add(prevResultLast/closeVal);. 一亩-三分-地,独家发布
  56.                     }
  57.                 }

  58. .1point3acres网
  59.                 //add to open, means this element is the starting of the bracket
  60.                 openLast.add(curVal);
  61.                 openRes.add(curVal);. visit 1point3acres for more.
  62.                 openOp.add(op);
  63.                 openPrev.add(prevRes); 来源一亩.三分地论坛.
  64.                 openPrevLast.add(prevResLast);
  65.                 curVal = 0;


  66.             } else if (s.charAt(ind) == ' ') ind++;
  67.             else {
  68.                 //operators
  69.                 op = s.charAt(ind);. 1point3acres
  70.                 ind++;

  71.             }
  72.         }
  73.         System.out.println("list of results");
  74.         for (int r : finalRes) {. 一亩-三分-地,独家发布
  75.             System.out.println(r);
  76.         }. Waral 博客有更多文章,
  77.         max = Collections.max(finalRes);. 围观我们@1point 3 acres
  78.         return max;

  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);. 1point3acres
  87.             } else if (op == '-') {
    . From 1point 3acres bbs
  88.                 finalRes.set(i, left-curVal);
  89.                 finalLast.set(i, -curVal);
  90.             } else if (op == '*') {
  91.                 finalRes.set(i, left-last+last*curVal);
  92.                 finalLast.set(i, last*curVal);
  93.             } else {
  94.                 finalRes.set(i, left-last+last/curVal);
  95.                 finalLast.set(i, last/curVal);
  96.             }
  97.         }
  98.     }.本文原创自1point3acres论坛
  99. }
  100. . 一亩-三分-地,独家发布
  101. /*

  102. 9+3*2+3 . 一亩-三分-地,独家发布
  103. list of results -google 1point3acres
  104. 18
  105. 27
  106. 18
  107. 18
  108. 18
  109. 18
  110. 24


  111. */
复制代码
回复

使用道具 举报

我的人缘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
没太看懂。。 能简要说一下你的idea么。。 我个人的想法是先计算一遍所有的sub evaluation(i, j)得到一个 ...

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

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘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% (53)
 
 
0% (0)  踩
这样行不行 比如   2+3/3-4 咱就用最笨的方法,对于每一个部分式 咱都求个值,因为evaluate  只是o(n) 所以这一步是o(n^2),思路就是区间DP. 1point 3acres 论坛

for(int len=3;len<=s.length();len++)
for(int left=1;left+len-1<s.length();left++)
{
    int right = left+len-1;
    for(int mid=left+1;mid<right;mid+=2)
       {. 围观我们@1point 3 acres
            先做一次这个len范围内的值,可以用dp记一下,然后把这个值tostring,加上后面的式子,再做一次evaluate
       }
}

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

补充内容 (2016-11-3 10:30):
left += 2
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-11-3 10:47:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (525)
 
 
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% (26)
 
 
0% (0)  踩
楼主你好,calculator加括号原题是给一组数,随便加 + * () 吧。所以follow up意思是随便加+*,然后只能加一个()吧?所以也不知道哪里该加+*,是这样吗?这样解法和“+*符号确定,找个位置加一组()”会不一样嗯
回复

使用道具 举报

我的人缘0
 楼主| 神罗天征 发表于 2016-11-5 04:12:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (525)
 
 
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% (26)
 
 
0% (0)  踩
神罗天征 发表于 2016-11-5 04:12-google 1point3acres
不是这个,这个只加了括号求值,然后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

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

GMT+8, 2018-9-20 07:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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