查看: 1401|回复: 4
收起左侧

狗家电面面经2022Jan,攒人品求米

|只看干货
匿名用户-FEE  发表于 2022-1-22 13:05:50 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2022(1-3月) 码农类General 硕士 全职@Google - 网上海投 - 技术电面  | 😃 Positive 😐 AverageOther | 在职跳槽

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

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

x
本帖最后由 匿名 于 2022-1-22 00:10 编辑

面试职位 SDE III

给一个string,求所有contiguous substrings的个数。
n * (n + 1) / 2

Follow up:
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式


总之,中规中矩的一个题目,题目本身并不复杂,但是时间和空间复杂度容易一不走神就会搞错了。祝大家好运,求大米!!!!!

评分

参与人数 4大米 +17 收起 理由
bryanjhy + 10 给你点个赞!
清道神君 + 5
z + 1 给你点个赞!
14417335 + 1 给你点个赞!

查看全部评分


上一篇:灵婴电面过经
下一篇:亚麻 OA1 2022新题及思路 附上近期整理

本帖被以下淘专辑推荐:

地里的匿名用户
匿名用户-EAB  发表于 2022-1-23 05:08:01
本楼: 👍   100% (1)
 
 
0% (0)   👎
谢谢分享!稍微有一个地方没明白,本身n * (n + 1) / 2求的不就是unique的吗,以每个char为首的所有substring加一起就可以。那follow up会有哪些重复的地方呢?非常感谢。
回复

使用道具 举报

z 2022-1-25 07:58:06 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (47)
 
 
0% (0)    👎
本帖最后由 z 于 2022-1-24 16:00 编辑

这个是O(n^2)的DP吗?

假如nums是input,定义:
dp(prefix, i, j) : 能和nums[i, j] match且它前的char为prex的个数
dp(surfix, i, j) : 能和nums[i, j] match且它后面的char为surfix的数

dp(prefix, i, j) = dp(nums, i+1, j) + dp(nums[j], i, j-1) if nums[i-1] == prefix else 0
surfix同理
然后prefix取自允许字符集,是个常数,i,j range from n。 复杂度n^2。
按照楼主的方式优化,改成dp(prefix, i, k), k是长度,空间复杂度为n
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
z 发表于 2022-1-24 18:58
这个是O(n^2)的DP吗?

假如nums是input,定义:

如果我理解没错的话,这题应该不复杂,就是求unique substring。楼主的做法挺好的,感觉没必要dp
回复

使用道具 举报

地里的匿名用户
匿名用户-5F3  发表于 2022-2-5 14:33:10
本楼: 👍   0% (0)
 
 
0% (0)   👎
请问follow up的时间为什么是O(N*3)?
遍历所有的substring应该两个for循环,O(N^2)就行了吧,空间复杂度存的是所有的substring的个数是O(N^2)如果算上字符串长度确实算是O(N^3)
回复

使用道具 举报

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

本版积分规则

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