<
回复: 9
收起左侧

snowflake一道题没做出来 求答案

匿名用户-1MKAQ  2024-4-23 12:50:44
本楼:   👍  1
100%
0%
0   👎

2023(1-3月) 码农类General 硕士 实习@snowflake - 校园招聘会 - Onsite  | 🙁 Negative 😫 HardestFail | 应届毕业生
好了 三个题一个没做出来
两个动态规划一个贪心
佬们会做
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
也造福一下后人

本帖子中包含更多资源

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

x

评分

参与人数 4大米 +10 收起 理由
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!
zaileon + 2 欢迎分享你知道的情况,会给更多积分奖励!
希望能留美的猫 + 1 赞一个
linlaw + 2 给你点个赞!

查看全部评分


上一篇:rippling 店面
下一篇:Uber, PhD Software Engineer Intern
地里匿名用户
匿名用户-JHXFF  2024-4-23 14:43:14
本楼:   👍  1
100%
0%
0   👎
hmm 感觉90分钟做三道好难

1.第一题的话感觉可以对每一个word维护一个num[i][j][char]
代表第 i 个word的第 j 位和之后的下一个char 的index
对每一个word前面加一个符号,比如 "#"
比如 aab -> #aab -> num[0][0][a] = 1, num[0][0][b] = 3, num[0][1][a] = 2, num[0][1][b] = 3, num[0][2][a] = sys.maxsize, num[0][2][b] = 3, num[0][3][b] = sys.maxsize
有点像 https://www.bilibili.com/video/BV18w411o7NA/
然后用dfs, 大概这样?不知道对不对
  1.     def dfs(target_idx, word_idx) -> int:
  2.         if target_idx == len(target):
  3.             return 1
  4.         if word_idx > len(word):
  5.             return 0
  6.         
  7.         cnt = 0
  8.         # the char we want to pick
  9.         c = target[target_idx]
  10.         for i in range(len(words)):
  11.             j = word_idx
  12.             while j < len(word):
  13.                 # jump to next c idx in word[i] after j
  14.                 j = num[i][j][c]
  15.                 cnt += dfs(target_idx + 1, j + 1)
  16.         return cnt % mod
复制代码
2. 第二题写个helper 对于每个server单独求解,因为要求是尽量多升级host, 所以要找到一个平衡点,尽量剩的host多和尽量升级的host多
手里的钱可以用来升级host的count = (num_sell * sell + money) // upgrade
剩余的host 的count = num - num_sell
找上面两个的平衡
  1.     def helper(num, money, sell, upgrade):
  2.         num_sell  = 0
  3.         while money // upgrade < (n - num_sell):
  4.             money += sell
  5.             num_sell += 1

  6.         return min(money // upgrade, (n - to_sell))
复制代码
3. 第三题也可以用dfs来生成pattern吧
idx代表当前生成到的第几位
prev代表前面连续的vowels
cur代表当前pattern 前面的组合数
大概这样
  1.     def dfs(prev, idx, cur):
  2.         if idx == wordLen:
  3.             rs += cur
  4.         # prev is number of contigous v
  5.         if prev + 1 < maxVowels:
  6.             # choose V
  7.             def dfs(prev + 1, idx + 1, cur * 5)
  8.         # choose C
  9.         def dfs(0, idx + 1, cur * 21)

  10.     dfs(0, 0, 1)
复制代码
加油!
回复

使用道具 举报

地里匿名用户
匿名用户-T3BWD  2024-4-23 13:05:24
本楼:   👍  0
0%
0%
0   👎
没投上,好可惜
回复

使用道具 举报

地里匿名用户
匿名用户-RU8JV  2024-4-23 18:59:21
本楼:   👍  0
0%
0%
0   👎
这是啥oa
回复

使用道具 举报

EbyccoCheng 2024-4-24 03:58:06 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   489
93%
7%
39
颈椎病又要复发了
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
请问 楼主 这不是实习的oa吧?
回复

使用道具 举报

vincent_great 2024-4-24 10:41:26 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   322
97%
3%
11
两道string题都是常规dp题。。。
中间那个server题直接模拟就行。。
1.5小时完成需要一定的刷题基础才行
回复

使用道具 举报

地里匿名用户
匿名用户-FBEOI  2024-4-24 13:01:19 来自APP
本楼:   👍  0
0%
0%
0   👎
第一题:dp[i][j]表示n个string已经match到了第i个字符,target string已经match到了第j个字符的方案数。枚举第j-1个的位置即可。可以用prefix sum进行优化。

第二题:模拟,一个求函数极值的问题。

第三题:dp[i][j]表示长度为i的string,最后连着j个vowels的方案数。递推就可以。
回复

使用道具 举报

地里匿名用户
匿名用户-1MKAQ  2024-4-27 13:36:40 来自APP
本楼:   👍  0
0%
0%
0   👎
vincent_great 发表于 2024-04-23 19:41:26
两道string题都是常规dp题。。。
中间那个server题直接模拟就行。。
1.5小时完成需要一定的刷题基础才行
这么容易的话把代码写出来给大家参考一下🌽
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
第二题是二分吧
回复

使用道具 举报

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

本版积分规则

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