a*****h
发帖数: 36 | 1 1. Integral image
2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
情况，求出多少雨滴可以把线段覆盖完全
3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
。把那些从没成为过最高优先度的alarm删除。
4. rotate array by k steps（leetcode），要最优解：reverse不能用
5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
二维的点，判断此图是否对程
继续坚持！ |
e********2
发帖数: 495 | 2 1.什么意思？
2. P(x not overed by first n droplets) = ((L-D)/L)^n
To ensure p=99.999% points are covered, n = lg(1-p)/lg((L-D)/L)
3. Leetcode
4. leetcode
5. (1) dfs (2) check row by row.
【在 a*****h 的大作中提到】
: 1. Integral image
: 2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
: 情况，求出多少雨滴可以把线段覆盖完全
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 4. rotate array by k steps（leetcode），要最优解：reverse不能用
: 5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
: 二维的点，判断此图是否对程
: 继续坚持！
|
s*******7
发帖数: 23 | 3 看了你的题目， 我在考虑要不要专心写我自己的app，
不想这事了 。。。
看了下， 就会做 5（2）
我面的话， 明显就是K了一天， 临了， 给个安慰的节奏 。。。 |
j*****8
发帖数: 3635 | 4 +1
【在 s*******7 的大作中提到】
: 看了你的题目， 我在考虑要不要专心写我自己的app，
: 不想这事了 。。。
: 看了下， 就会做 5（2）
: 我面的话， 明显就是K了一天， 临了， 给个安慰的节奏 。。。
|
d********i
发帖数: 582 | 5 +1
【在 s*******7 的大作中提到】
: 看了你的题目， 我在考虑要不要专心写我自己的app，
: 不想这事了 。。。
: 看了下， 就会做 5（2）
: 我面的话， 明显就是K了一天， 临了， 给个安慰的节奏 。。。
|
f********y
发帖数: 156 | |
t***t
发帖数: 6066 | |
q***a
发帖数: 26 | 8 同问1详情。2 是不是要求写蒙特卡罗模拟？ 5（2）除了左右对称，是不是要包括各个
方向的中心对称和轴对称？
【在 a*****h 的大作中提到】
: 1. Integral image
: 2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
: 情况，求出多少雨滴可以把线段覆盖完全
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 4. rotate array by k steps（leetcode），要最优解：reverse不能用
: 5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
: 二维的点，判断此图是否对程
: 继续坚持！
|
f*******r
发帖数: 976 | 9 Move on!
【在 a*****h 的大作中提到】
: 1. Integral image
: 2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
: 情况，求出多少雨滴可以把线段覆盖完全
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 4. rotate array by k steps（leetcode），要最优解：reverse不能用
: 5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
: 二维的点，判断此图是否对程
: 继续坚持！
|
b******7
发帖数: 123 | 10 2）应该模拟随机数，然后判断什么时候全部覆盖吧。
3好像和2类似，也是带权重的覆盖问题。 |
|
|
r*******g
发帖数: 1335 | 11 这位大侠，第三题哪里是leetcode的？怎么一点印象都没有。
第四题，题目说了不能reverse，不知道楼主什么意思。
【在 e********2 的大作中提到】
: 1.什么意思？
: 2. P(x not overed by first n droplets) = ((L-D)/L)^n
: To ensure p=99.999% points are covered, n = lg(1-p)/lg((L-D)/L)
: 3. Leetcode
: 4. leetcode
: 5. (1) dfs (2) check row by row.
|
s*******o
发帖数: 1 | |
o*******y
发帖数: 362 | 13 艾玛我可以直接告诉recruiter取消面试了
【在 a*****h 的大作中提到】
: 1. Integral image
: 2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
: 情况，求出多少雨滴可以把线段覆盖完全
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 4. rotate array by k steps（leetcode），要最优解：reverse不能用
: 5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
: 二维的点，判断此图是否对程
: 继续坚持！
|
f*******o
发帖数: 14 | |
a*****h
发帖数: 36 | 15 楼主统一回答一下：
各位同僚可以google一下Integral Image，其实就是生成一个2D矩阵，里面的每一个点
(i,j)都记录了从这个点到(0,0)所形成的矩形的元素之和。这道题其实是最简单的。
雨滴那道题是让你写个程序模拟一下这个场景，不是直接给出数学公式。
对称那道题要考虑很多corner case，比如说所有点在一直线上，那么也是对称的，因
为每个点和自己对称。中心对称不考虑。
在Mountain View面的试。
各位加油！ |
c*****m
发帖数: 271 | 16 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
。把那些从没成为过最高优先度的alarm删除。
这个能仔细描述下要求是啥？是不是就是leetcode merge intervals的变种？另外在
file中是指最终的删除是在file中进行？ |
a*****h
发帖数: 36 | 17 不好意思，具体要求我也忘了。当时就写了一个最基本的，花了很多时间。
【在 c*****m 的大作中提到】
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 这个能仔细描述下要求是啥？是不是就是leetcode merge intervals的变种？另外在
: file中是指最终的删除是在file中进行？
|
d**********2
发帖数: 553 | |
l*******e
发帖数: 127 | 19 写了一下第三题，基本思路是类似于sweep-line算法，用一个max heap保持当前权重最
高的alarm，按照时间顺序扫描， 碰到alarm start event, add alarm to the heap,
for alarm end event,
remove the alarm from the heap. keep track the top of the heap, which
should be kept.
public class WeightedInterval {
public List removeAlarms(List alarms)
{
SortedMap> times = new TreeMap<>();
for(Alarm alarm : alarms)
{
if(!times.containsKey(alarm.start)) times.put(alarm.start, new
ArrayList<>());
times.get(alarm.start).add(alarm);
if(!times.containsKey(alarm.end)) times.put(alarm.end, new
ArrayList<>());
times.get(alarm.end).add(alarm);
}
List ret = new ArrayList<>();
PriorityQueue pq = new PriorityQueue<>((a, b) -> {
if (a.weight == b.weight)
{
return Integer.compare(a.start, b.start);
}
return Integer.compare(b.weight, a.weight);
});
for(Map.Entry> time : times.entrySet())
{
for(Alarm alarm : time.getValue())
{
if(alarm.start == time.getKey())
{
pq.add(alarm);
}
else
{
pq.remove(alarm);
}
}
if(!pq.isEmpty()) pq.peek().remove = false;
}
ret.addAll(alarms.stream().filter(alarm -> alarm.remove).collect(
Collectors.toList()));
return ret;
}
public static class Alarm {
final int start;
final int end;
final int weight;
boolean remove;
public Alarm(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
remove = true;
}
}
} |
o********a
发帖数: 1 | |
|
|
b********r
发帖数: 620 | 21 不知道用stack或者类似是不是更好些。
,
【在 l*******e 的大作中提到】
: 写了一下第三题，基本思路是类似于sweep-line算法，用一个max heap保持当前权重最
: 高的alarm，按照时间顺序扫描， 碰到alarm start event, add alarm to the heap,
: for alarm end event,
: remove the alarm from the heap. keep track the top of the heap, which
: should be kept.
: public class WeightedInterval {
: public List removeAlarms(List alarms)
: {
: SortedMap> times = new TreeMap<>();
: for(Alarm alarm : alarms)
|
S**n
发帖数: 403 | 22 这是leetcode城市高楼skyline那个题目的变形
【在 c*****m 的大作中提到】
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 这个能仔细描述下要求是啥？是不是就是leetcode merge intervals的变种？另外在
: file中是指最终的删除是在file中进行？
|
j******i
发帖数: 244 | 23 雨滴那题是coupon collector's problem
https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
【在 a*****h 的大作中提到】
: 1. Integral image
: 2. 一条线段长度L，雨滴直径D，雨滴从不同位置等概率下降到线段上，模拟一下这个
: 情况，求出多少雨滴可以把线段覆盖完全
: 3. 一个file里面有很多alarm，每个alarm有三个数值：起始时间、终止时间、优先度
: 。把那些从没成为过最高优先度的alarm删除。
: 4. rotate array by k steps（leetcode），要最优解：reverse不能用
: 5. （1）俄罗斯方块，求出正在下落的物体和底部的最短距离。 （2）一幅图有一系列
: 二维的点，判断此图是否对程
: 继续坚持！
|
w****e
发帖数: 3827 | 24 RE
太高端
【在 j******i 的大作中提到】
: 雨滴那题是coupon collector's problem
: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
|
g******d
发帖数: 152 | 25 aleram那道题：
比如有这些alarm
[0, 2], [1, 5], [6, 7]
合并后成为：
[0, 1] [1, 2] [2, 5], [5, 6 无alarm] [6, 7]
这个数组只记录优先级组好的
剩下的都可以删掉 |
w****5
发帖数: 46 | 26 第三题用interval tree,对每个优先级建立一棵interval tree，对任意一个alarm，在
所有比它优先级高的interval tree中搜索，看有没有起始时间小于等于它，结束时间
大于等于它的alarm，如有，则该alarm在其生存期中从未成为过最高alarm，如无，则
该alarm当过最高alarm。但复杂度的精确值分析起来比较麻烦，用拉格朗日乘子法列出
来的对数方程组很不好解。一个非常rough的upper bound是O(k*k*n*lgn),k是优先级的
数量，n是alarm数量 |
w****5
发帖数: 46 | 27
似乎跟coupon不一样呢。coupon那个是个样本是可列的，雨滴滴落的位置是个连续随机
变量，不可列啊
【在 j******i 的大作中提到】
: 雨滴那题是coupon collector's problem
: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
|
