📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 34
跳转到指定楼层
上一主题 下一主题
收起左侧

Snapchat 面经请教

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
面经的高频题calculator加括
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

多谢各位大神。

上一篇:亚马逊网上测评第一面刚做完但感觉有个问题存疑
下一篇:Amazon OA2
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
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();
  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<>();
  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';
  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);
  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);
  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.                     }
  55.                 }


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


  63.             } else if (s.charAt(ind) == ' ') ind++;
  64.             else {
  65.                 //operators
  66.                 op = s.charAt(ind);
  67.                 ind++;

  68.             }
  69.         }
  70.         System.out.println("list of results");
  71.         for (int r : finalRes) {
  72.             System.out.println(r);
  73.         }
  74.         max = Collections.max(finalRes);
  75.         return max;

  76.     }



  77.     public void calculateList(List<Integer> finalLast, List<Integer> finalRes, int curVal, char op) {
  78.         for (int i = 0; i < finalLast.size(); i++) {
  79.             int last = finalLast.get(i);
  80.             int left = finalRes.get(i);
  81.             if (op == '+') {
  82.                 finalRes.set(i, left+curVal);
  83.                 finalLast.set(i, curVal);
  84.             } else if (op == '-') {
  85.                 finalRes.set(i, left-curVal);
  86.                 finalLast.set(i, -curVal);
  87.             } else if (op == '*') {
  88.                 finalRes.set(i, left-last+last*curVal);
  89.                 finalLast.set(i, last*curVal);
  90.             } else {
  91.                 finalRes.set(i, left-last+last/curVal);
  92.                 finalLast.set(i, last/curVal);
  93.             }
  94.         }
  95.     }
  96. }

  97. /*

  98. 9+3*2+3
  99. list of results
  100. 18
  101. 27
  102. 18
  103. 18
  104. 18
  105. 18
  106. 24


  107. */
复制代码

评分

参与人数 1大米 +5 收起 理由
高渐离击筑高歌 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
geng77 2016-11-10 00:33:07 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
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
那就二维dp 然后遍历一次所以可以加括号的地方 n^2

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

使用道具 举报

🔗
linweihua0 2016-10-19 05:23:28 | 只看该作者
全局:
如果有 * / + -的话 我觉得存两个状态 因为没有括号的情况最多是两层stack 所以左右两端各要存这两层stack
回复

使用道具 举报

全局:
帮顶,同求问follow up,地里有大神会么?
回复

使用道具 举报

🔗
Liuology 2016-10-26 00:35:42 | 只看该作者
全局:
小A要当码农 发表于 2016-10-26 00:01
帮顶,同求问follow up,地里有大神会么?

as above
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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