回复: 19
收起左侧

阅后即焚 店面

匿名用户-LNAXE  2021-4-6 10:17:26
本楼:   👍  0
0%
0%
0   👎

2021(1-3月) 码农类General 硕士 全职@snapchat - 网上海投 - 技术电面  | Fail | 在职跳槽

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

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

x
本帖最后由 匿名 于 2021-4-6 10:37 编辑

上周约的店面,上来先介绍然后BQ: 1. challenge
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
来了个offer太激动了,就没做好
暴力解法做的估计是挂了


求问更好的解法

评分

参与人数 8大米 +13 收起 理由
avalon516 + 1 给你点个赞!
kkkkky + 1 给你点个赞!
noi10 + 2 很有用的信息!
ggtnht77 + 2 很有用的信息!
请叫我热情老八 + 2 很有用的信息!

查看全部评分


上一篇:脸店面对的对的
下一篇:DoorDash 电面
shouhm 2021-4-6 11:12:39 | 显示全部楼层
本楼:   👍  8
100%
0%
0   👎
全局:   1629
83%
17%
326
将区间表示为事件(left, +1)和(right, -1) 然后按顺序扫描这些事件

评分

参与人数 3大米 +4 收起 理由
kevinguo09 + 1 赞一个
thunder + 2 给你点个赞!
xiao90537 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

xiao90537 2021-4-6 10:26:36 | 显示全部楼层
本楼:   👍  3
100%
0%
0   👎
全局:   752
98%
2%
14
來offer太激動好好笑 給你加米

评分

参与人数 1大米 +2 收起 理由
kevinguo09 + 2 给力

查看全部评分

回复

使用道具 举报

funmastermike 2021-4-7 04:59:46 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   1525
92%
8%
129
Blazer 发表于 2021-4-6 11:03
public int[] findInterval(int[][] arr){
        int maxInteval = 0;
        for (int[] a: arr) ...

感觉有点小bug啊这里

按你这个输出的 【4, 4】

感觉可以设一个flag,以count第一次减少的时候去reset maxEnd的值
回复

使用道具 举报

thunder 2021-4-6 12:07:55 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   449
97%
3%
15
这题有什么小于n^2的做法么?
回复

使用道具 举报

donald27 2021-4-6 12:30:45 来自APP | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   612
95%
5%
29
要问清楚edge case,有没有多个频率都是一样最大的情况,前大后小区间怎么算的情况,输入集合为空的情况。
过一遍,计算区间,使用hashtable/hashmap记录区间:频次,如果只有唯一最大值就用一对变量记录最大频次和区间长度,如果有多个最大值就麻烦一点还要有另一个hashmap记录频次和区间的关系。
过一遍时间O (n),hashtable查区间:频次关系O (lg
k ),k约等于lg n,总时间复杂度O (n * lg k),最坏情况O (n * lg n)。空间复杂度O (k)。
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   823
95%
5%
40
谢谢楼主分享,已加米~

另外想请问下,阅后即焚有没有说电面是一定只做一题或者 2 题 的说法?
回复

使用道具 举报

Blazer 2021-4-7 03:03:23 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   21
100%
0%
0
    public int[] findInterval(int[][] arr){
        int maxInteval = 0;
        for (int[] a: arr){
            maxInteval = Math.max(a[1], maxInteval);
        }
        // assume all num >= 0
        int[] cache = new int[maxInteval];
        for (int[] a: arr){
            cache[a[0]]++;
            cache[a[1]]--;
        }
        int maxCount = 0, maxStart = 0, maxEnd = 0, count = 0;
        for (int i = 0; i < cache.length; i++){
            count += cache[i];
            if (count == maxCount){
                maxEnd = i;
            } else if (count > maxCount){
                maxCount = count;
                maxStart = i;
                maxEnd = i;
            }
        }
        return new int[]{maxStart, maxEnd};
    }
max number k, number of intervals N
如果interval的max很大,就用TreeMap,空间减少,时间增加. 空间O(N),时间O(NlgN)
如果overlap比较多,max比较小,用这个,空间O(k),时间O(max(N,k))

评分

参与人数 2大米 +3 收起 理由
guanhoo + 2 给你点个赞!
kevinguo09 + 1 赞一个

查看全部评分

回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   1776
97%
3%
62
请叫我热情老八 发表于 2021-04-06 09:42:28
谢谢楼主分享,已加米~

另外想请问下,阅后即焚有没有说电面是一定只做一题或者 2 题 的说法?
我这个花了很久就写了一道题,所以不太清楚是否1-2题。 但是我觉得面试的人还有后面的题,时间不够了,就直接跳到问题了!
回复

使用道具 举报

dwt585 2021-4-7 05:17:42 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   263
98%
2%
5
meeting room套了个马甲
回复

使用道具 举报

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

本版积分规则

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