回复: 32
收起左侧

买它店面挂经

本楼:   👍  2
100%
0%
0   👎
全局:   157
99%
1%
1

2024(1-3月) 码农类General 硕士 全职@Meta - 猎头 - 技术电面  | 🙁 Negative 😣 HardFail | 在职跳槽

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

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

x

拜仁秃头扑克脸小哥 如果面试官全程冷漠 建议跟recruiter反馈


第一题 黎口 屋思霰 说了思路 码了code 准备写test case 写完发现没有跑代码的功能 小哥全程看我写testcase没有提醒我没有compiler 耽误时间了


重点来了


第二题  没有在之前面经里看到


give you a unsorted list of integers, same integers are grouped together. Find the list of integers who has leng
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
返回 4


我给了双指针的解法 时间On 空间O1 但是面试官让我优化时间 实在没想出来怎么优化 应该是挂在第二题了 地里的兄弟姐妹们有啥思路么



评分

参与人数 4大米 +8 收起 理由
NeildylandyNC + 1 欢迎分享你知道的情况,会给更多积分奖励!
Imtram + 1 赞一个
manyfun711 + 1 赞一个
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!

查看全部评分


上一篇:Tiktok 全套挂经
下一篇:Confluent VO 面试
桑梓 2025-1-17 04:50:21 | 显示全部楼层
本楼:   👍  4
100%
0%
0   👎
全局:   23
100%
0%
0
本帖最后由 桑梓 于 2025-1-16 12:55 编辑

有点像1287,那题是sorted可以用二分。楼主这个unsorted也可以枚举3个位置,n/4, n/2, 3*n/4,对枚举的每个数用二分查上下边界。比如对n/4位置的数x,去[0, n/4]查index下边界,可以当成0 1 数组找边界问题,非x的数都当成0

评分

参与人数 1大米 +1 收起 理由
匿名账號 + 1 赞一个

查看全部评分

回复

使用道具 举报

桑梓 2025-1-17 07:42:10 | 显示全部楼层
本楼:   👍  3
100%
0%
0   👎
全局:   23
100%
0%
0
Ayaneru 发表于 2025-1-16 15:23
同意,但是01本身不是有序,比如1中间加个0,如何确定1的subarray长度满足条件

题目里说了相同数字都在一起,只不过不是有序的。如果相同数字不集中在一起的话,这题应该无法低于O(n)的时间,怎么着都得全部遍历一遍,空间的话倒是可以用投票算法做到O(1)
回复

使用道具 举报

桑梓 2025-1-17 06:28:49 | 显示全部楼层
本楼:   👍  3
100%
0%
0   👎
全局:   23
100%
0%
0
breakthechain 发表于 2025-1-16 13:46
[2, 1, 1, 1, 4, 4, 3, 3]

N=8

n=8的话就枚举 index = 2, 4, 6 这三个位置的数。比如对于第一个位置2上的数是1,去[0,2]里用二分搜1的下边界,二分时当成01数组问题,因为1在这段区间内肯定都是集中在右侧的,所以mid不是1就收缩left指针,这样可以找到1的下边界index是1;然后再去[2,7]里找数字1的上边界,此时1肯定集中在区间的左侧,因此mid指向不是1时就收缩right指针,二分找到1的index上边界是3,就能算出1的数量是3满足要求。如果要求返回所有超过25%的数的话就继续枚举其他两个位置。总共枚举3个数,6次二分查找

评分

参与人数 3大米 +3 收起 理由
shawhull + 1 赞一个
gunduzi + 1 赞一个
breakthechain + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

tachy_9 2025-1-17 04:49:06 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   445
96%
4%
20
为什么第一个example返回1,4,3都行

题目不是要求返回list of int,所以是所有超过25%的int,就是[1, 4, 3] ?
回复

使用道具 举报

桑梓 2025-1-17 04:56:28 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   23
100%
0%
0
桑梓 发表于 2025-1-16 12:50
有点像1287,那题是sorted可以用二分。楼主这个unsorted也可以枚举3个位置,n/4, n/2, 3*n/4,对枚举的每个 ...

这样时间复杂度应该可以压到 logN

评分

参与人数 1大米 +1 收起 理由
匿名账號 + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| breakthechain 2025-1-17 05:01:36 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   157
99%
1%
1
tachy_9 发表于 2025-01-16 12:49:06
为什么第一个example返回1,4,3都行

题目不是要求返回list of int,所以是所有超过25%的int,就是 ?
不好意思没说清楚 返回那个integer就行
回复

使用道具 举报

地里匿名用户
匿名用户-J8IMX  2025-1-17 05:21:11 来自APP
本楼:   👍  0
0%
0%
0   👎
桑梓 发表于 2025-01-16 12:50:21
有点像1287,那题是sorted可以用二分。楼主这个unsorted也可以枚举3个位置,n/4, n/2, 3*n/4,对枚举的每个数用二分查上下边界。比如对
不错 思路很精彩 唯一我没想清楚的是当数组长度无法被4整除时 如果还是只看这三个位置可能不太够
回复

使用道具 举报

桑梓 2025-1-17 05:37:21 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   23
100%
0%
0
匿名用户 发表于 2025-1-16 13:21
不错 思路很精彩 唯一我没想清楚的是当数组长度无法被4整除时 如果还是只看这三个位置可能不太够

应该是够的,只要有数超过数组总长度的1/4而且是连续的,必然会至少占据这三个位置其中之一
回复

使用道具 举报

 楼主| breakthechain 2025-1-17 05:46:24 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   157
99%
1%
1
桑梓 发表于 2025-1-16 12:56
这样时间复杂度应该可以压到 logN

[2, 1, 1, 1, 4, 4, 3, 3]

N=8

这种情况应该怎么处理呢 只有1符合条件

但是  [0, n/4]落在了sublist [2, 1, 1]上, [n/4, n/2]落在了[1, 1, 4]上

这两个subproblem都没有找到符合条件的sublist
回复

使用道具 举报

whalejasmine 2025-1-17 06:23:47 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   159
94%
6%
11
请问楼主店面多久出的结果呀?谢谢!
回复

使用道具 举报

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

本版积分规则

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