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

Airbnb 电面难题

全局:

2019(7-9月) 码农类General 硕士 全职@airbnb - 猎头 - HR筛选  | | Other | 在职跳槽

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

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

x
给n个长度是k的字符串,问其中是不是有两个字符串相差只有一个字符。

讨论了蛮久,一开始想到的方法是hashtable,把abc 变成 ab_, a
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
到O(nk),面试官也认可了。

求过求大米!看不见隐藏内容好痛苦。

评分

参与人数 13大米 +28 收起 理由
andy20160507 + 2 给你点个赞!
zhangli811811 + 2 给你点个赞!
破风 + 2 很有用的信息!
海绵宝宝 + 1 赞一个
fufjvnvnf + 1 欢迎分享你知道的情况,会给更多积分奖励!

查看全部评分


上一篇:DRW OA
下一篇:亚麻 2020 new grad oa2
全局:
N个字符串,每个字符串最多生成K个有且只有一个空格的字符串,总共难道不应该是NK个这样的字符串插入到hash map吗?然后扫一遍map看看有没有哪个key是map到多个原来的字符串来给出答案。我的理解不知道哪里有问题,因为我看不出来NKK, 而是NK
回复

使用道具 举报

推荐
 楼主| 匿名函数 2019-9-15 21:04:13 | 只看该作者
全局:
把长度是k的字符串放入hash table是O(k)不是O(1)
回复

使用道具 举报

全局:
这个直接扫一遍建一个trie,然后再扫一遍,用trie判断是不是满足有且仅有一个char match不上就好了吧,不需要俩trie吧
回复

使用道具 举报

🔗
douch 2019-9-15 14:18:08 | 只看该作者
全局:
mrno5zzz 发表于 2019-9-15 13:27
这个直接扫一遍建一个trie,然后再扫一遍,用trie判断是不是满足有且仅有一个char match不上就好了吧,不需 ...

那这种时间复杂度就是nkk了吧?
回复

使用道具 举报

🔗
5290 2019-9-16 06:05:17 | 只看该作者
全局:
已加米,不过没看懂nk怎么搞的OTZ..。求解 “然后两边连起来,中间隔着一个字符这样”什么意思
回复

使用道具 举报

🔗
 楼主| 匿名函数 2019-9-16 06:36:36 来自APP | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 3大米 +3 收起 理由
veryblues + 1 很有用的信息!
5290 + 1 很有用的信息!
zetianxiao + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
 楼主| 匿名函数 2019-9-16 06:42:59 来自APP | 只看该作者
全局:
mrno5zzz 发表于 2019/09/15 13:27:13
这个直接扫一遍建一个trie,然后再扫一遍,用trie判断是不是满足有且仅有一个char match不上就好了吧,不需要俩trie吧
你怎么判断?
回复

使用道具 举报

🔗
 楼主| 匿名函数 2019-9-16 08:47:00 来自APP | 只看该作者
全局:
匿名函数 发表于 2019/09/16 06:36:36

不好意思没说清楚。比如abcde,左trie的ab连右tire的de,a连cde,abc连e。如果连的时候发现已经连过了,说明有一个别的string只差一位。
这样建tire是nk,额外连的也只有nk个边。
回复

使用道具 举报

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

使用道具 举报

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

本版积分规则

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