Walmart Labs Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Use in place heap. Let's say we just track the min of last k days.
let heapArray contain the last k values.
let positionArray contain the position of i-th day in the heapArray.
For example, positionArray[0] = 5 means the value of the first day in at 5th index of heapArray.
Now, when k+1 th value comes:
0. init old = 0;
1. get index = positionArray[old];
2. remove heapArray[index] O(log k).
3. insert new value 'v' in heapArray, O(log k)
4. in the bubling up process of step 3 remember the position 'pos' of v in heapArray
5. positionArray[old] = pos;
6. old = (old+1)%k;
7. for new value repeat from 1.
Does the set always contains same number of integers everyday? In that case we can retrieve max and min values by incrementing the pointer by (no. of integer values each day*(total_days-k))
number of integers keep on increasing each day... and number of integer values each day = 1
Map will be help full Map <Date , Value> , as integer is coming only 1 per day so we can assume it will be unique
store min max values of sqrt(k) size intervals
as such whenver a query is made we would have a maximum of k/sqrt(k) = sqrt(k) intervals + sqrt(k) values not in interval.
Here comparsions will be 2*sqrt(k)
example k=9
time stamps and intervals
time stamps: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
intervals: ------ ------ ------- ----------- ----------- ----------- -----------
A B C D E F G
if asked between say 8 to 16
we consider values of 8,9,16 and Min Max values of intervals D and E
total of sqrt(9) complexity
This n^2 array has O(1) access time, but require O(n^2) memory.
void append(int value){
array[size][size] = value;
if(size==0) {++size; return;}
// min filling
for(int i=size; i>0; --i){
array[size][i-1] = array[size][i]<array[size-1][i-1]?array[size][i]:array[size-1][i-1];
}
// max filling
for(int i=size; i>0; --i){
array[i-1][size] = array[i][size]>array[i-1][size-1]?array[i][size]:array[i-1][size-1];
}
++size;
}
int getMin(int day, int duration){
return array[day][day-duration];
}
int getMax(int day, int duration){
return array[day-duration][day];
}
A MinMaxQueue would be the most appropriate.
Just pop_front() at every kth day and push_back(). And do min-max query as required.
Below is the complexities.
insert() - O(1)
pop_front() - O(1)
push_back() - O(1)
min() - O(1)
max() - O(1)
Check out the implementation here : github[dot]com[slash]nikhilgarg28/Algorithm-Library/blob/master/MinMaxQ.cpp
Use , a queue a doubly linked list and a hash map , every thing will be O(1). Insert every new element in queue and
insert a new element to head of linked list if it is greater then the head. maintain pointer from queue to node of linked list so that you can delete an element from linked list when it gets popped from queue.
head of l;inked list will have maximum all the times ,.
you can maintain one more doubly linked list in similar fashion to tell you minimum./
Don't let the size of queue exceed k
What do you think?
import java.util.Queue;
import java.util.LinkedList;
public class minmax2{
static Queue<Integer> queue = new LinkedList<>();
public static void main(String[] args){
int a =9,b=1,c=11,d=12;
int k=77;
queue.add(a);
queue.add(b);
queue.add(c);
queue.add(d);
process(k);
}
public static void process(int days){
int min =0, max =0;
if(days > queue.size() || days <=0) throw new IllegalArgumentException("invalid k");
for(int i=0; i< days;i++){
int current = queue.remove();
if(i==0){
int temp = current;
min= temp;
max = temp;
continue;
}
if(current >= max){
max =current;
}else if(current <= min){
min=current;
}
}
System.out.println("max="+max+", min="+min);
}
}
I think a Ascending Priority Queue will be better. As it will be sorted. We can retrieve min and max values just by incrementing the pointer kth time
A Deque.
- Anonymous July 14, 2012