o******s
发帖数: 416 | 1 一个公司的screening programming problem:
概括来说就是给一些时间点，然后一个固定的窗口大小，问窗口下能罩住最多，最少个
时间点。如果所给的时间点最大和最小值差距小于窗口大小，则getmax(), getmin()都
返回－1。
假设，时间点是按照递增的顺序给出的，如：
> cat stat.inp //input source file contains timestamps
1.0
1.0
1.0
1.2
1.3
1.5
1.6
1.8
2.0
3.0
3.0
3.0
3.0
4.1
7.0
> cat stat.inp |./StatisticsTracker (window size=2)
now: 1 max: -1 min: -1
now: 1 max: -1 min: -1
now: 1 max: -1 min: -1
now: 1.2 max: -1 min: -1
now: 1.3 max: -1 min: -1
now: 1.5 max: -1 min: -1
now: 1.6 max: -1 min: -1
now: 1.8 max: |
c******n
发帖数: 4965 | 2 just linearly go down the list of points
first sort them
【在 o******s 的大作中提到】
: 一个公司的screening programming problem:
: 概括来说就是给一些时间点，然后一个固定的窗口大小，问窗口下能罩住最多，最少个
: 时间点。如果所给的时间点最大和最小值差距小于窗口大小，则getmax(), getmin()都
: 返回－1。
: 假设，时间点是按照递增的顺序给出的，如：
: > cat stat.inp //input source file contains timestamps
: 1.0
: 1.0
: 1.0
: 1.2
|
o******s
发帖数: 416 | 3 这些点就是按照从小到大的顺序出现的。主要是，在新增一个点以后，需要检查是否需
要挪动窗口，并且计算最多能覆盖住多少个点儿，最少能覆盖住多少个点。
看着像动态规划类的问题。
【在 c******n 的大作中提到】
: just linearly go down the list of points
: first sort them
|
g******d
发帖数: 511 | 4 怎么是出来的
//window with max [1,3) window with min (1,3]
window with min [2.1,4.1)
2.1是怎么出来的?
听起来好像就是move pointers,同时maintain counters. |
