狗家昂赛1.25

英国伦敦

1. 设计一个数据结构支持插入一系列interval [1,5], [6,10], [3, 4] .... 和查询某一个整数是否存在于某个 interval
   楼主设计了一个Interval 类，插入的时候直接往一个vector里面放Interval，插入完毕之后这个类再用一个finalize方法先对vector里面的所有Interval按照第一个数排序，然后遍历每个interval做merge. 检查某个数是否存在于任何一个interval区间时可以用upper_bound然后再对比前一个元素即可

2. 给定一系列字符到二进制字符串的唯一mapping: {'a' : '00', 'b': '0101', 'c': '0111', 'd': '0100', 'e': '01'}, 再给定一个encode好的二进制字符串例如"01010111010001", 求其decode的字符串，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

箱子。楼主用的DP，可是面试官说能不能再优化。因为DP难度是O(M*N)。听说有一个方案可以做到O(M+N), 可是楼主面到最后一轮大脑已经快烧坏了，所以只答到说可以把代表坑的数组维护成一个递减的状态(单调栈)例如{2,3,1} - > {2,2,1}。即遍历的时候记录一个当前最小值，如果当前遍历的值大于当前最小值，就赋值当前最小值。这样可能可以缩短判断时间，不过具体想不出来了。面试官也给这段代码拍照了，但是没有时间继续往后实现了。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

glc12125 发表于 2019-1-27 03:58
你好，箱子是必须按照顺序来的。最佳方案应该是双指针的方式，我最后解释了应该维护一个单调不递增的坑的 ...

请问推箱子这题，箱子高度是已经排序好的吗？要是没排序的话指向高度最小的箱子的指针该怎么移动

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

第五题需要按照顺序来推吗？难道是Greedy两根指针？

4,5,1,1
2,3,2,1

请问 5. 一个坑能多个箱子吗

第五题是不是可以greedy，箱子和坑都排好序，依次推，推满一个坑换下一个

阿满 发表于 2019-1-27 02:45
请问 5. 一个坑能多个箱子吗

你好，一个坑只能一个箱子

xiaozong 发表于 2019-1-27 03:06
第五题是不是可以greedy，箱子和坑都排好序，依次推，推满一个坑换下一个

不能greedy的吧？如果前一个箱子放不进去就卡住了，就得重新选择从哪一个箱子开始往坑里面放

stellari 发表于 2019-1-27 04:13
结合其他人的面经，再加上楼主follow up的思路。我觉得楼主说的“坑数组”可能代表的是“一个连续的水平 ...

恩，翻译非常正确！

glc12125 发表于 2019-1-27 04:24
恩，翻译非常正确！

多谢确认。这样的话，可能用“山洞”来描述更合适一些。“坑”通常会被理解成“竖直洞穴”，进而“坑数组”会被理解为“多个（互不相连）的竖直洞穴”。楼上几位谈到的greedy法，应该就是基于这种理解得到的。