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

G到场表演

🔗
匿名用户-XV0HV  2020-1-28 13:05:27 |倒序浏览

2020(1-3月) 码农类General 硕士 全职@google - 内推 - Onsite  | | Other | 在职跳槽

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

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

x
本帖最后由 匿名 于 2020-1-28 13:39 编辑

总的来说都比较常规,是大家平时刷题能解决的类型,一道2维DP,一道String操作有不少corner case,一道API design。大家平时好好刷题没问题的。
我这里想
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
之后我会贴这个interviewer给我的hint。


补充内容 (2020-1-28 14:20):
他并没有要求我对时间复杂度进行优化。。

评分

参与人数 4大米 +15 收起 理由
AnnaY + 1 很有用的信息!
spirit_room + 2 欢迎来一亩三分地论坛!
yywwd + 2 很有用的信息!
匿名用户-GLIRZ + 10

查看全部评分


上一篇:亚麻昂赛挂经
下一篇:脸家oculus面经

本帖被以下淘专辑推荐:

  • · google|主题: 24, 订阅: 4
全局:
应该就是slinding window吧。把words想象成一个个不同的字母,就是求正好包含所有的字母的字串。这题能用sliding window是因为所有的word都是定长的,如果不定长就该用DP了。
回复

使用道具 举报

推荐
Siil 2020-1-28 17:20:00 来自APP | 只看该作者
全局:
可以考虑将每个字符串哈希成一个数字。
然后维护一个长度为l的滑窗,和窗口的哈希值,划过去时,每次增加与删除处理一下,复杂度是
预处理O(m*l) list长度为m,滑窗O(n)
回复

使用道具 举报

推荐
gwy 2020-1-28 14:52:39 来自APP | 只看该作者
全局:
伞石吗 但是那道题我也用了O(L) space 做的

评分

参与人数 1大米 +1 收起 理由
spirit_room + 1 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

🔗
eclipseshadow 2020-1-28 13:41:43 | 只看该作者
全局:
从这个index开始的substring 是什么意思?从index到最后吗?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-XV0HV  2020-1-28 13:51:36
eclipseshadow 发表于 2020-1-28 13:41
从这个index开始的substring 是什么意思?从index到最后吗?

就是从这个index开始,到index + W, W是words加起来的长度
回复

使用道具 举报

🔗
gwy 2020-1-28 14:16:57 来自APP | 只看该作者
全局:
减少空间复杂度的情况下要保持时间复杂度不变吗?可以sort words吗
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-XV0HV  2020-1-28 14:24:29
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
gwy 2020-1-28 14:41:04 来自APP | 只看该作者
全局:
论坛匿名账号 发表于 2020/01/28 14:24:29

他是在我的那个solution的基础上提出如何优化空间,我感觉prefer时间复杂度不变。
你sort words...
也对。。那应该怎么做😂 bit manipulation吗
回复

使用道具 举报

🔗
gwy 2020-1-28 14:42:00 来自APP | 只看该作者
全局:
论坛匿名账号 发表于 2020/01/28 14:24:29

他是在我的那个solution的基础上提出如何优化空间,我感觉prefer时间复杂度不变。
你sort words...
我刚开始是想sort了可以二分法找单词 但感觉时间复杂度太高了
回复

使用道具 举报

🔗
fatalme 2020-1-28 14:42:07 | 只看该作者
全局:
本帖最后由 fatalme 于 2020-1-28 15:25 编辑

好像leetcode有。
觉得就是一个kmp

  1. for(string& w : words) {
  2.       find all positions of w in A;
  3.       record the last w appearing position;
  4.       if current w postion - last w position <  within L, then  don't mark it.
  5. }

  6. int count = 0;
  7. for(int i = 0; i < A.size(); i++) {
  8.          if(A[i], A[i+w],....A[i + L/w]) is marked, count ++;
  9. }

  10. return count;

复制代码


回复

使用道具 举报

地里匿名用户
🔗
匿名用户-XV0HV  2020-1-28 15:36:21
interviewer的hint是用regular expression
回复

使用道具 举报

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

本版积分规则

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