- moving avg
- moving median
- moving max
https://github.com/interviewdiscussion/files/blob/master/Indeed Onsite记录/Moving Average.java
timer https://www.cnblogs.com/51kata/p/5128745.html
use a queue to store the coming data
Event{val, time}
addVal(val) : 1. q.offer(event) 2. total +=val;
getAvg() : total/q.size()
cleanExpired() : poll() until all element in the queue are not expired/ total -= val
if we have storage limit
compress the data, if the interval between the arrival of two data are less than 1s, combine together
Event{sum, time, size}
addVal(val) : 1. if > 1s q.offer(event), total +=val; 2. modify event(sum, size)
getAvg() : sum/total size
cleanExpired() : poll() until all element in the queue are not expired/ sum -= val
add O(k) avg(1+ k) k #of element needs clean
import java.io.*;
import java.util.*;
class Solution {
public static void main(String[] args) throws InterruptedException {
Solution s = new Solution();
s.add(3);
Thread.sleep(100*3);
System.out.println(s.avg());
s.add(4);
Thread.sleep(10);
System.out.println(s.avg());
s.add(5);
System.out.println(s.avg());
Thread.sleep(100*2);
s.add(6);
System.out.println(s.avg());
}
double time;
Event last;
public long getTime() {
return System.currentTimeMillis();
}
static class Event {
double val;
int size;
long time;
Event(double val, long time) {
this.val = val;
this.time = time;
size = 1;
}
}
Queue < Event > q = new LinkedList < > ();
double sumAll = 0;
int sizeAll = 0;
public void add(double val) {
long curTime = getTime();
if (last == null || curTime - last.time >= 100) {
Event evt = new Event(val, curTime);
q.offer(evt);
last = evt;
} else {
last.val += val;
last.size += 1;
}
sumAll += val;
sizeAll += 1;
cleanExpired();
}
public double avg() {
if (q.isEmpty()) return 0;
cleanExpired();
return sumAll / sizeAll;
}
public void cleanExpired() {
while (!q.isEmpty() && System.currentTimeMillis() - q.peek().time >= 500) {
sumAll -= q.peek().val;
sizeAll -= q.poll().size;
}
}
}
import java.io.*;
import java.util.*;
import java.text.SimpleDateFormat;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) throws InterruptedException {
System.out.println("main start:"+getCurrentTime());
Timer timer = startTimer();
Thread.sleep(1000*20); //休眠5秒
System.out.println("main end:"+getCurrentTime());
timer.cancel();
}
public static Date getCurrentTime() {
Date date = new Date();
//SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//return sdf.format(date);
return date;
}
public static Timer startTimer(){
TimerTask task = new TimerTask() {
Solution s = new Solution();
int i = 0;
@Override
public void run() {
i++;
s.add(i);
//System.out.println("add time"+getCurrentTime());
System.out.println(s.avg());
}
};
Timer timer = new Timer();
timer.schedule(task, 0,1000*1);
return timer;
}
static class Event {
double val;
Date date;
Event(double val, Date date) {
this.val = val;
this.date = date;
}
}
public Date getTime(){
return getCurrentTime();
}
Queue<Event> q = new LinkedList<>();
double sum = 0;
public void add(double val){
Event evt = new Event(val, getTime());
q.offer(evt);
sum += val;
cleanExpired();
}
public double avg(){
cleanExpired();
if (q.isEmpty()) return 0;
return sum/q.size();
}
public void cleanExpired(){
System.out.println(getTime());
long cur = getTime().getTime();
System.out.println("poll:"+q.peek().date);
while (cur - q.peek().date.getTime() >= 2000) {
sum -= q.poll().val;
}
}
}
- get Max
double time;
Event last;
public long getTime() {
return System.currentTimeMillis();
}
static class Event {
double val;
long time;
Event(double val, long time) {
this.val = val;
this.time = time;
}
}
Deque < Event > deque = new ArrayDeque < > ();
public void add(double val) {
long curTime = getTime();
if (last == null || curTime - deque.peek().time >= 100) {
while (!deque.isEmpty() && deque.peek().val <= val) {
deque.pop();
}
Event evt = new Event(val, curTime);
deque.push(evt);
} else {
deque.peek().val = Math.max(deque.peek().val,val);
}
cleanExpired();
}
public double max() {
cleanExpired();
if (deque.isEmpty()) return 0;
return deque.peekLast().val;
}
public void cleanExpired() {
while (!deque.isEmpty() && System.currentTimeMillis() - deque.peekLast().time >= 500) {
deque.removeLast();
}
}
- get median
class Solution {
public static void main(String[] args) throws InterruptedException {
Solution s = new Solution();
s.array = new int[] {1,2,5,4,3,8,9};
System.out.println(s.median());
}
int[] array;
public double median() {
if (array.length % 2 == 0) {
return (findK(0, array.length - 1, array.length/2 - 1) + findK( 0, array.length - 1, array.length/2))/2.0;
}
return findK(0, array.length - 1, array.length/2);
}
private int findK(int s, int e, int k) {
int p = array[s];
int l = s;
int r = e;
while (l < r) {
while (array[r] > p && l < r) {
r--;
}
while (array[l] <= p && l < r) {
l++;
}
swap(l,r);
}
swap(s,r);
if (r == k) {
return array[r];
}
if (r < k) return findK(r + 1, e, k);
return findK(s, r - 1, k);
}
private void swap(int i , int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
map.put(), map.getAverage() with expiration，求过去一小时的平均数，
要求constant spacecomplexity andconstant time complexityfor both operation。
地里的 add(sample), get_average(), 求过去一小时里的 average 是多少
max of latest k numbers in stream
腦子打結，分析老半天heap跟list的complexity
follow up 問median
不间断的会有stock price input，但是incoming rate是不确定的。 然后有一个function，让你返回当前没过期的最大stock price。initialize的时候会给一个input k代表存在data structure里的stock price多久会过期。我写了一个deque，不断更新最大值，但如果进来的比最大值小，还是放在deque里因为可能它会成为之后的最大值。如果有thread清理的话getPrice会是O(1). 设计了test case， 跑了几个test，然后结束了。
data stream average with expiration
。。说了普通做法以后让优化空间。。不会，大哥提示了一下牺牲精确度用等周期采样做。。最后稀里糊涂被带着写了个也不知道是啥的东西
Max of data stream with expiration经提示用list写的
Follow up: medianof data stream with expiration
想出来的办法是写一个find median in sliding window,用quickselect