<
回复: 4
收起左侧

Applied Intuition面试题求解

匿名用户-PENDW  2023-12-4 16:19:35
本楼:   👍  0
0%
0%
0   👎

2023(10-12月) 码农类General 硕士 全职@applied-intuition - 校园招聘会 - 技术电面  | 😃 Positive 😐 AverageOther | 应届毕业生

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

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

x
求助这道题的解法,谢谢大家# Given a list of words, return a mapping from an encoded string to the word such that the encodings are unique, unambiguous, and of minimal length.
# The encoding algorithm is to take the first and last characters and count the number of characters in between.
# kubernetes -> k8s.--
# internationalization  -> i18n
# E.g apple -> a3e, amazon -> a4n, netflix -> n5x
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
encodes do not conflict.
# google -> g4e -> go3e -> goo2e
# goggle -> g4e -> go3e -> gog2e

评分

参与人数 1大米 +10 收起 理由
清道神君 + 10 欢迎分享你知道的情况,会给更多大米奖励!

查看全部评分


上一篇:买它电面两道题
下一篇:大超市挂经 + timeline
yugioh 2023-12-4 23:43:56 | 显示全部楼层
本楼:   👍  3
100%
0%
0   👎
全局:   34
100%
0%
0
这不是Leetcode 527原题吗?
回复

使用道具 举报

wizard19900509 2024-2-8 15:16:01 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   222
97%
3%
8
有两种思路
1. 维护一个ignored set 放所有不允许出现的缩写(初始为空) 然后iterate一边所有的word 每个word先encode到最小 看是不是在那个ignore set里 如果在就扩展 一直到不在那个set里 然后看现在的result map里有没有这个encoded key
- 如果key已经存在:那这样的key最多只有一个(现有的result map都已经unique)把这个拿出来 两个一起往下扩展 一直到不相同位置 然后放回result map里(记得把旧的key删掉)过程当中生成的key都要放进ignore set里
- 如果key不存在 那直接存入result map即可
这样搞完直接返回result map即可 这个是我面试时候想出来的解法

2. 面试官后面讨论的时候给出的他预期的解法
result map的value搞成一个list 这样key永远是最短压缩 里面list的value都是等长的words 处理完一般以后 对于每个key下面的list 选择合适的encoded即可 其实就是第一步把问题变成只比较等长的words 后面估计用个prefix map去搞到每个encode都unique就行(我感觉还是我自己的方法比较intuitive)
回复

使用道具 举报

地里匿名用户
匿名用户-B999W  2024-2-24 07:32:13
本楼:   👍  0
0%
0%
0   👎
我当时也面了这道题,很离谱的是面试官只贴了第一句话,连个例子都没有,要不是我刷过这个题,我连题都看不懂。当时我想用trie做,面试官不允许,然后就写了greedy,写代码的时候面试官态度超差,一直逼逼,还没写完就说这句话不该这样写,那句话不准那样写,都不知道到底谁写代码。他家面试官像没培训过就出来面试的,没法吐槽。
回复

使用道具 举报

kl_hrz 2024-4-4 01:40:46 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   33
97%
3%
1
匿名用户 发表于 2024-02-23 15:32:13
我当时也面了这道题,很离谱的是面试官只贴了第一句话,连个例子都没有,要不是我刷过这个题,我连题都看不懂。当时我想用trie做,面试官不允许,然后就写了greed
幸亏刷到这帖子,不然我本来想用trie
回复

使用道具 举报

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

本版积分规则

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