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

脸家店面

🔗
匿名用户-ERRU5  2021-3-2 12:36:04 |倒序浏览

2021(1-3月) 码农类General 硕士 全职@meta - 猎头 - 技术电面  | | Pass | 在职跳槽

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

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

x
第一题  肆似散 简化版,输入是字符串,输出是压缩以后的字符串。只有一个字符的情况不用特别处理。
第二题  给两个数组,两个数组中的元素都是p
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
,1), (1,1), (9,1), (6,4)]
要求不能展开A和B以后做乘法再压缩。

评分

参与人数 13大米 +24 收起 理由
wantyoulee + 2 很有用的信息!
umd2011 + 2 给你点个赞!
亚特兰蒂斯 + 2 很有用的信息!
StupidCorn + 1 给你点个赞!
hgon23 + 3 很有用的信息!

查看全部评分


上一篇:Cruise 电面+onsite
下一篇:字节两轮
推荐
glitterk 2021-3-15 07:57:58 | 只看该作者
全局:
第二题 Java version

  1. import java.util.*;

  2. public class LocalRun2 {
  3. //    A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
  4. //    B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
  5. //    求A点乘B的结果,以压缩形式的返回。以上面的A,B为例,结果是[(5,1), (1,1), (9,1), (6,4)]

  6.     public static void main(String[] args) {
  7.         int[][] a = new int[][] {{1,2}, {3,1}, {2,3}, {3, 1}};
  8.         int[][] b = new int[][] {{5,1}, {1,1}, {3,4}, {2, 1}};
  9.         int[][] result = solution(a, b);
  10.         for (int[] i : result) {
  11.             System.out.println(Arrays.toString(i));
  12.         }
  13.     }

  14.     public static int[][] solution(int[][] a, int[][] b) {
  15.         int i = 0;
  16.         int j = 0;

  17.         List<int[]> list = new ArrayList<int[]>();
  18.         while (i < a.length && j < b.length) {
  19.             int[] currentA = a[i];
  20.             int[] currentB = b[j];
  21.             if (currentA[1] == 0) {
  22.                 i++;
  23.                 continue;
  24.             }
  25.             if (currentB[1] == 0) {
  26.                 j++;
  27.                 continue;
  28.             }
  29.             int min = Math.min(currentA[1], currentB[1]);
  30.             currentA[1] -= min;
  31.             currentB[1] -= min;
  32.             int current = currentA[0] * currentB[0];
  33.             if (list.isEmpty()) {
  34.                 list.add(new int[] {current, min});
  35.             } else {
  36.                 int[] prev = list.get(list.size() - 1);
  37.                 if (prev[0] == current) {
  38.                     prev[1] = prev[1] + min;
  39.                 } else {
  40.                     list.add(new int[] {current, min});
  41.                 }
  42.             }
  43.         }
  44.         return list.toArray(new int[list.size()][]);
  45.     }
  46. }

复制代码
回复

使用道具 举报

推荐
whiteboard 2021-3-2 23:43:11 | 只看该作者
全局:
第二题
  1. /*
  2. A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
  3. B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
  4. 求A点乘B的结果,以压缩形式的返回。以上面的A,B为例,结果是[(5,1), (1,1), (9,1), (6,4)]
  5. */

  6. vector<pair<int,int>> dot_product(vector<pair<int,int>> &A, vector<pair<int,int>> &B) {
  7.     int i = 0, j = 0;
  8.     vector<pair<int,int>> ans;

  9.     while (i < (int)A.size() && j < (int)B.size()) {
  10.         auto &a = A[i];
  11.         auto &b = B[j];

  12.         int product = a.first * b.first;
  13.         int len = min(a.second, b.second);

  14.         if ((int)ans.size() > 0 && product == ans.back().first)
  15.             ans.back().second += len;
  16.         else
  17.             ans.push_back({product, len});

  18.         a.second -= len;
  19.         if (a.second == 0) i++;
  20.         b.second -= len;
  21.         if (b.second == 0) j++;
  22.     }   

  23.     return ans;
  24. }

  25. int main()
  26. {
  27.     vector<pair<int,int>> A = {{1,2},{3,1},{2,3},{3,1}};
  28.     vector<pair<int,int>> B = {{5,1},{1,1},{3,4},{2,1}};
  29.     vector<pair<int,int>> C = dot_product(A, B);
  30.     for (auto &p : C)
  31.         cout << p.first << ", " << p.second << endl;
  32.     return 0;
  33. }
复制代码

评分

参与人数 1大米 +2 收起 理由
crayia + 2 good

查看全部评分

回复

使用道具 举报

推荐
Gina29 2021-3-22 05:02:13 | 只看该作者
全局:
本帖最后由 Gina29 于 2021-3-22 05:07 编辑

发一个我写的python版本,欢迎指正

  1. '''
  2. A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
  3. B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
  4. 求A点乘B的结果,以压缩形式的返回。以上面的A,B为例,结果是[(5,1), (1,1), (9,1), (6,4)]
  5. '''

  6. def product(A, B):
  7.     m, n = len(A), len(B)
  8.     i = j = 0
  9.     ans = []
  10.     p = 0
  11.     len_a = len_b = 0
  12.     while i < m and j < n:
  13.         a, b = A[i][0], B[j][0]
  14.         if len_a == 0:
  15.             len_a = A[i][1]
  16.         if len_b == 0:
  17.             len_b = B[j][1]
  18.         p = a * b
  19.         if len_a == len_b:
  20.             i += 1
  21.             j += 1
  22.         elif len_a < len_b:
  23.             i += 1
  24.         else:
  25.             j += 1
  26.         count = min(len_a, len_b)
  27.         len_a -= count
  28.         len_b -= count
  29.         if not ans or ans[-1][0] != p:
  30.             ans.append((p, count))
  31.         else:
  32.             ans.append((p, ans.pop()[1]+count))
  33.     return ans
  34. A = [(1, 2), (3,1), (2,3), (3, 1)]
  35. B = [(5, 1), (1,1), (3,4), (2, 1)]
  36. ret = product(A, B)
  37. print(ret)
复制代码

回复

使用道具 举报

🔗
glad2mu 2021-3-2 13:36:25 | 只看该作者
全局:
第二题求思路。。。 谢谢
回复

使用道具 举报

🔗
jy_121 2021-3-2 14:11:57 | 只看该作者
全局:
glad2mu 发表于 2021-3-2 13:36
第二题求思路。。。 谢谢

双指针应该就可以了吧
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-ERRU5  2021-3-3 02:22:33
glad2mu 发表于 2021-3-1 21:36
第二题求思路。。。 谢谢

比较A,B中element的range,重合部分做乘法,on-fly build pair<int, int>,加到结果中类似于find interval overlap。注意边界条件和指针移动。
回复

使用道具 举报

🔗
candy404 2021-3-5 08:42:10 | 只看该作者
全局:
积分不够 看不到题 TAT
回复

使用道具 举报

🔗
sherryhw 2021-3-22 03:50:58 | 只看该作者
全局:
求教 请问什么叫“数组表示压缩后的一串数字”? 谢谢
回复

使用道具 举报

🔗
Gina29 2021-3-22 04:37:27 | 只看该作者
全局:
本帖最后由 Gina29 于 2021-3-22 04:39 编辑
sherryhw 发表于 2021-3-22 03:50
求教 请问什么叫“数组表示压缩后的一串数字”? 谢谢

pair第一个表示数字,第二个表示该数字连续出现的个数。
回复

使用道具 举报

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

本版积分规则

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