Walmart Labs Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

A Deque.

- Anonymous July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Deque +1

- Anonymous July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain how dequeu would help in getting min and max elements for the last k days ?

- learner February 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anonymous October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the bubbling process of step4, whenever there is a swap the positionArray values are no longer valid.

- kgp_coder November 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Stack is enough!!

- cobra July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- stalin July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

number of integers keep on increasing each day... and number of integer values each day = 1

- cobra July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Map will be help full Map <Date , Value> , as integer is coming only 1 per day so we can assume it will be unique

- Kala Swami July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but doesn map will take more space as compared to stack? which would be better ?

- deepika July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap<Date, BinaryTree> or HashMap<Date, SortedArrayOfInt> ...

- Hayato July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you elaborate?

- cobra July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we should not use a hash map that does not keep the order of elements and keeping the key as date .. overall will increase the space complexity

- deepika July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Take a circular array of size k.
2. insertion should be like arr[++i%k]=element.{i starts from 0}
3. At any time, to output min & max, we need {3*k/2 - 2} number of comparisons in the worst case.

Can we do better?

- Aashish July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

stack must be used..

- deepika July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heap. Easy to traverse and find the min and max elements and also to add a new element.

- ramblersm July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- alok September 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

- yh October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous - Guy October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Treeset will be fine as it stores the elements in the sorted order. To retrieve last k days get the subset of last k days from the set get the upper and lower bounds (max and min)

- Venkata Pavan Kumar January 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Geek January 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its modified version of Sliding window problem .
Hint: Use 2 deque
Leetcode -> sliding-window-maximum.html

- Anonymous May 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- devdev February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. you are destroying queue when u call process. Use getLast of linkedlist
2. You only need current > max and current < min. Those two are useless assignment.
3. This solution is not scalable. How about list of size 200 million.

- curious November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Nilesh July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

we need to find min and max in the last k days man.. not kth min and max..

- cobra July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simple data structure like circular array should be good enough because we don't care about older data here. Finding out minimum and maximum is O(k).

- Sumit September 15, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More