查看: 2027|回复: 11
收起左侧

狗家VO挂经

|只看干货
匿名用户-1CE  发表于 2022-5-21 05:20:41 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎

2022(4-6月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | 😐 Neutral 😣 HardFail | 在职跳槽

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

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

x
被HR通知挂了,一周前狗家L5VO

第一题:
这一轮回看感觉挺难的,是做题网10的魔改,OOD,给了一个list,里面有一堆String,例如{carandcar,carand,plane,trainorcar},用这些构建pattern,写一个构建pattern函数。再写一个是否match的函数,是否在pattern中有match的string,函数输入是一个string,但是这个string有个特点,可能含有*,*可以match 0-n个字母,例如match(carandcar)-->True, match(plan)-->false, match(cara*d)-->True, match(trainor*)-->True

感觉是用trie构建pattern,然后用做题网10的方案做match?但是40分钟仍然没完
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式


第四轮:
BQ,回馈很好

第五轮:
SD,这轮的面试官做Key Value高性能操作的,所以出了一个Key Value高性能操作的题,而且挖的很深。反馈是不够好



评分

参与人数 3大米 +7 收起 理由
清道神君 + 5
姜姜 + 1 谢谢分享!
Falldawn + 1 给你点个赞!

查看全部评分


上一篇:数据砖 滇缅
下一篇:Indeed New grad 第一轮面经
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   74% (144)
 
 
25% (49)    👎
匿名者 发表于 2022-5-21 21:36
第二题是有可以比O(n)好的解法吗,好难想

binary search的变种, 时间复杂度大概k*logn(k是有多少个不同的字母):

boolean result = false;
boolean checkFrequency(int[] list){
  find(list,0,list.length);
  return result;
}
void find(int[] list, int start, int end){
  if (start>=end) return;
  int mid = (start+end)/2;
  char c = list[mid];
  int left = binarySearchLeft(list, start, mid, c); // find index of leftmost c
  int right = binarySearchRight(list, mid+1, end, c);  // find index of rightmost c
  if ((right-left+1)/list.length>=0.15) {
    result=true;
  } else {
    find(list, start, left-1);
    find(list, right+1, end);
  }
}

补充内容 (2022-05-24 04:52 +8:00):
输出应该是找到的character,剩下不变
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (257)
 
 
10% (30)    👎
匿名者 发表于 2022-5-21 13:36
第二题是有可以比O(n)好的解法吗,好难想

能不能每7个index 检查一下,得到 index=0,7,14,21,28 。。。位置的字母 a0, a7, a14, a21, a28...
如果有三个相邻的字母一样,比如a0=a7=a14,那就找到了
如果有两个相邻的字母一样,比如a7=a14,那就向a7和a14左右拓展,直到字母不一样,然后统计是否超过15%
如果没有两个相邻的字母一样,则没有字母超过15%

但这样划片寻找的复杂度依然是o(n),并没有本质区别。。
回复

使用道具 举报

地里的匿名用户
匿名用户-CBA  发表于 2022-5-25 05:49:36
本楼: 👍   0% (0)
 
 
0% (0)   👎
匿名者 发表于 2022-5-23 14:19
可是如果K比较大,那么K* logn比n还大, 那么最坏时间复杂度更糟。

K怎么会比较大呢
如果可以assume都是lower case letters K不会超过26
就算有大写或其他的符号存在也不会explode
当然如果不可以assume K的范围 只有O(n)的解法
如果是unsorted 用K个pointer可以把所有相同的letter移动到一起 O(n)解决
如果是sorted 用binary search 时间可以保证在O(logn) K 是constant
回复

使用道具 举报

地里的匿名用户
匿名用户-A14  发表于 2022-5-22 04:36:12
本楼: 👍   0% (0)
 
 
0% (0)   👎
第二题是有可以比O(n)好的解法吗,好难想
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (1007)
 
 
0% (4)    👎
请问你的hr会告诉你每轮的反馈吗?
我还以为不可以说,只能说overall positive/negative
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
请问楼主面完多久收到feedback的?
回复

使用道具 举报

地里的匿名用户
匿名用户-1CE  发表于 2022-5-24 05:13:52
本楼: 👍   0% (0)
 
 
0% (0)   👎
rocketdive 发表于 2022-5-21 17:45
能不能每7个index 检查一下,得到 index=0,7,14,21,28 。。。位置的字母 a0, a7, a14, a21, a28...
...

我最后用的是类似这个方法,就是跳着查,所以最坏时间复杂度也是n,但是这轮给的反馈中等,所以不知道最优解是什么。

回复

使用道具 举报

地里的匿名用户
匿名用户-1CE  发表于 2022-5-24 05:14:51
本楼: 👍   0% (0)
 
 
0% (0)   👎
冉冉檀香透过窗 发表于 2022-5-22 23:56
请问楼主面完多久收到feedback的?

一周后收到的回复
回复

使用道具 举报

地里的匿名用户
匿名用户-1CE  发表于 2022-5-24 05:16:23
本楼: 👍   0% (0)
 
 
0% (0)   👎
吃饱撑的胖猫 发表于 2022-5-21 20:15
请问你的hr会告诉你每轮的反馈吗?
我还以为不可以说,只能说overall positive/negative

这个要分HR,有些HR愿意多说,有些不愿意。
回复

使用道具 举报

地里的匿名用户
匿名用户-1CE  发表于 2022-5-24 05:19:40
本楼: 👍   0% (0)
 
 
0% (0)   👎
sshic 发表于 2022-5-23 13:50
binary search的变种, 时间复杂度大概k*logn(k是有多少个不同的字母):

boolean result = false;

可是如果K比较大,那么K* logn比n还大, 那么最坏时间复杂度更糟。
回复

使用道具 举报

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

本版积分规则

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