回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

Meta 电面面经

🔗
匿名用户-LYFLR  2022-2-15 03:49:42 |倒序浏览

2022(1-3月) 码农类General 博士 全职@meta - 内推 - 技术电面  | 😐 Neutral 😐 Average | Other | 在职跳槽

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

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

x
今天新鲜面经.
Coderpad execution disabled, 我的界面只有highlighting, 没有自动indent和括号补全, 写起来好蛋疼..

第一题斯吆舞变种, 两个数含有小数点, 处理小数点花了很多时间.  我的处理方法是把小数点后位数多的string多余的位数截掉, 加两个rightmost digit ali
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
ip = left.maxLeftBranch + right.maxRightBranch - 1, 然后更新global lipMax. 时间复杂度是 O(N).

求问这题有O(logN)的算法吗?


评分

参与人数 3大米 +7 收起 理由
sccnju + 1 给你点个赞!
匿名用户-QNXOH + 5
yyyooohhhooo + 1 很有用的信息!

查看全部评分


上一篇:硬币基地 虚拟现场面经
下一篇:買它VO
地里匿名用户
推荐
匿名用户-TMM46  2022-2-15 06:30:29 来自APP
第二个题,应该没有OlogN的解法吧?说到底他是要求每个子结点的高度,那怎么着都要全走一遍吧。这样就是ON了
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-LYFLR  2022-2-15 06:37:29 来自APP
匿名用户 发表于 2022-02-14 14:30:29
第二个题,应该没有OlogN的解法吧?说到底他是要求每个子结点的高度,那怎么着都要全走一遍吧。这样就是ON了
呵呵,就是担心有啥奇技淫巧没想到。面试官上来说第二题是关于binary search的,所以我耿耿于怀没有用上binary search
回复

使用道具 举报

🔗
ppscyye 2022-2-15 10:10:07 | 只看该作者
全局:
第一题3.14 + 0.9装成3.14 + 0.90 然后 314 + 90是不是要好写一些。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-LYFLR  2022-2-15 10:25:57
ppscyye 发表于 2022-2-14 20:10
第一题3.14 + 0.9装成3.14 + 0.90 然后 314 + 90是不是要好写一些。

可能差不多吧, 代码不复杂, 我当时处理小数点想复杂了, 其实直接往栈里推就可以了.

改了之后其实不难写
  1. public String add(String a, String b) {
  2.         if (a == null || a.isEmpty()) {
  3.             return b;
  4.         }
  5.         if (b == null || b.isEmpty()) {
  6.             return a;
  7.         }

  8.         // find string with more digits after ., and split extra digits out
  9.         int digitsAfterDotA = a.length() - a.indexOf('.') - 1;
  10.         int digitsAfterDotB = b.length() - b.indexOf('.') - 1;
  11.         int delta = Math.abs(digitsAfterDotA - digitsAfterDotB);

  12.         String longer = digitsAfterDotA >= digitsAfterDotB ? a : b;
  13.         String shorter = longer == a ? b : a;

  14.         // Push extra digits after . in longer string
  15.         Deque<Character> stack = new ArrayDeque<>();
  16.         int i = longer.length() - 1;
  17.         int j = shorter.length() - 1;
  18.         while (delta-- > 0) {
  19.             stack.push(longer.charAt(i--));
  20.         }

  21.         // Add remaining digits
  22.         int carry = 0;
  23.         for (; i >= 0 || j >= 0; i--, j--) {
  24.             if (i >= 0 && longer.charAt(i) == '.') {
  25.                 stack.push('.');
  26.                 continue;
  27.             }
  28.             int num1 = i >= 0 ? longer.charAt(i) - '0' : 0;
  29.             int num2 = j >= 0 ? shorter.charAt(j) - '0' : 0;
  30.             int sum = num1 + num2 + carry;
  31.             stack.push((char) ('0' + sum % 10));
  32.             carry = sum / 10;
  33.         }
  34.         StringBuilder sb = new StringBuilder();
  35.         while (!stack.isEmpty()) {
  36.             sb.append(stack.pop());
  37.         }
  38.         return sb.toString();
  39.     }
复制代码
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-SIK8S  2022-2-15 13:35:44
谢谢楼主分享,感谢
回复

使用道具 举报

🔗
sccnju 2022-2-18 10:49:40 | 只看该作者
全局:
能不能求楼主写下第二题的解法,自己写了半天都不是特别clear。多谢啦
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-K1TLG  2022-2-18 11:06:04
楼主能看下这个写法对不吗?
  1. def lit_bst(root):
  2.         res = 0
  3.         def dfs(node):
  4.                 nonlocal res
  5.                 if not node:
  6.                         return 0, 0
  7.                 if not node.left and not node.right:
  8.                         return 1, 1

  9.                 left = dfs(node.left)
  10.                 right = dfs(node.right)

  11.                 decrese,increase  = 1 ,1

  12.                 decrese = max(decrese, 1 + left[0])
  13.                 increase max(increase, 1 + right[1])
  14.                 res = max(res, increase + decrese - 1)

  15.                 return decrese, increase

  16.         dfs(root)
  17.         return res
复制代码
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-LYFLR  2022-2-18 11:42:47
sccnju 发表于 2022-2-17 20:49
能不能求楼主写下第二题的解法,自己写了半天都不是特别clear。多谢啦

和楼下Python的写法一样的, 我的是java
  1. class Node {
  2.   int val;
  3.   Node left;
  4.   Node right;
  5.   pubic Node(int val) {
  6.     this.val = val;
  7.   }
  8. }

  9. public class Solution {
  10.   static class Result {
  11.     int maxLeftBranch;
  12.     int maxRightBranch;
  13.    
  14.     public Result(int l, int r) {
  15.       maxLeftBranch = l;
  16.       maxRightBranch = r;
  17.     }
  18.   }
  19.   
  20.   private int lip;

  21.   public int longestIncreasingPath(Node root) {
  22.     if (root == null) {
  23.       return 0;
  24.     }
  25.     lip = 0;
  26.     dfs(root);
  27.     return lip;
  28.   }
  29.   
  30.   // Traverse the tree, and return maxLeftBranch and maxRightBranch, update LIP on the fly
  31.   private Result dfs(Node root) {
  32.     if (root == null) {
  33.       return new Result(0, 0);
  34.     }
  35.    
  36.     Result left = dfs(root.left);
  37.     Result right = dfs(root.right);
  38.    
  39.     // update lip
  40.     int lipRootedHere = left.maxLeftBranch + right.maxRightBranch - 1; // since adding root twice
  41.     lip = Math.max(lip, lipRootedHere);
  42.    
  43.     // compute result
  44.     return new Result(left.maxLeftBranch + 1, right.maxRightBranch + 1);
  45.   }
  46.   
  47. }
复制代码
回复

使用道具 举报

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

本版积分规则

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