Walmart Labs Interview Question
Senior Software Development EngineersTeam: R&D
Country: India
Interview Type: Written Test
By the way, I don't understand why the median method works, but I have not found a case where it doesn't. It requires some more thought to understand why it works.
Simple brute force algorithm will be as follows: -
1. count number of occupied seats S
2. sort the occupied seat by position in pos[]
2. try placing seats in row starting at ith position
3. minimum cost for starting at ith position is abs(i-pos[0]) + abs(i+1-pos[1])..
4. find minimum of all possible i's
@gudujarlson points out median is the fast way to go. I'll give a
proof here.
Let's start with two observations,
- Some persons move left, some persons move right. They should never
move cross each other, otherwise they can just take the new seat of
each others, reducing the total moves.
- For two persons move the same direction, there is no need for one
person to pass the other one. They can switch their new seats,
resulting the same number of move.
Hence, we can find an optimized solution, such that the order of seats
were kept. For a solution that l persons on the left move right, m
persons in the middle don't move, and r persons on the right move left.
- If l > m + r, we can improve the solution by shift left by one seat
- If l + m < r, we can improve the solution by shift right by one seat
- Otherwise ( |l - r| < m ), we reach a local minimal.
Then it is easy to show that a solution constructed by aligning the
median meet the requirement.
If you found the proof complex, you may want to compare it with a
classical question: If we want to move all the people to one seat,
which is the best seat?
The first part of your proof makes sense to me, but I'm not following the second part. You appear to be ignoring the distance each person has to move. I think the proof needs to prove that the minimum of this function occurs when i is the median.
cost(i) = sum { distance(i,j) - count(i,j) }
where
i = seat index that we move everyone towards
j = seat index of a particular person
distance(i,j) = abs(j-i)
count(i,j) = the number of people between seat i and j, not counting the person sitting at j.
When we shift a solution to the right by one seat, every person who moved right have to move one extra step, no matter how many steps one moved; and everyone who were moving left can save one step. All the persons who were not moving will move one extra step when we shift to the left or right by one step.
If the total saving is larger than the total cost, one can improve the solution by shift solution to the left or to the right. Otherwise, it is the optimized solution.
Let position of people be x[1], x[2], ..., x[n], and define S[i] = x[1]+x[2]+...+x[i]
Assume the central is y where x[i] <= y < x[i+1], i.e. x[1],x[2], ..., x[i] will move towards y and x[i+1], x[i+2], ..., x[n] will move towards y+1
then the cost m[j] = for x[j], 1 <= j <= i is
m[i] = y-x[i]
m[i-1] = (x[i]-x[i-1]-1) + m[i] = y-x[i-1]-1
m[i-2] = (x[i-1]-x[i-2]-1) + m[i-1] = y-x[i-2]-2
...
m[1] = (x[2]-x[1]-1) + m[2] = y-x[1]-(i-1)
total cost (left) is m[1]+...+m[i] = i*y-S[i]-(1+2+...+(i-1))
similarly the total cost (right) is S[n]-S[i] - (n-i)*y - (1+2+...+n-i)
total cost = S[n]-2*S[i] + (2*i-n)*y - i*(i-1)/2-(n-i+1)*(n-i)/2 for x[i] <= y < x[i+1]
Now it is easy to precompute S[i] and then find min total cost, O(n)
Everytime two groups of people need to be merged together, the group with lesser number of people should join the larger group so that hops are minimum. Below is the pseudo code using this approach
int findMinShifts(String input)
{
int sizePrev = 0;
int sizeNext = 0;
int countBetween = 0;
int numShifts = 0;
for (int i =0; i < input.length(); i ++)
{
if (input.charAt(i) == '.')
countBetween++;
else {
while (i < input.length() && input.charAt(i) == 'X')
sizeNext++;
if(sizeNext > sizePrev)
numShitfts += sizePrev*countBetween;
else
numShifts += sizeNext*countBetween;
sizePrev +=sizeNext;
countBetween = 0;
sizeNext = 0;
}
}
return MinShifts;
}
//Here is a brute force solution in javascript
//find the steps required to group all x's around each x
//whichever yields the min steps is the answer
function minStepsToGroup (input) {
var array = input.split('');
var totalJumps = [];
for (var i = 0; i < array.length; i++) {
if (containsElementAt(i, array)) {
totalJumps[i] = computeStepsForGroupingElementsAround(i, array);
}
}
var min = totalJumps.length;
for (var i = 0; i < totalJumps.length; i++) {
if (totalJumps[i]) {
if (totalJumps[i] < min) {
min = totalJumps[i]
}
}
}
return min;
}
function computeStepsForGroupingElementsAround(index, array) {
var start = index, end = index, steps = 0;
for (var i = index; i >= 0 ; i--) {
if (containsElementAt(i, array)) {
start = i;
} else {
break;
}
}
for (var i = index; i <= array.length - 1 ; i++) {
if (containsElementAt(i, array)) {
end = i;
} else {
break;
}
}
for (var i = 0; i < array.length; i++) {
if (containsElementAt(i, array)) {
if (i < start) {
steps += start - 1 - i;
start--;
}
if (i > end) {
steps += i - end - 1;
end++;
}
}
}
return steps;
}
function containsElementAt (index, array) {
return array[index] === 'X' || array[index] === 'x';
}
Here is a solution using median in javascript as explained by @gudujarlson
//Unlike brute force algorithm this one first finds the median element
//and groups everything around it
function findMinShifts (input) {
//find median
var array = input.split('');
var median = computeMedian(array);
//find number of steps to group elements around that
return computeStepsForGroupingElementsAround(median, array);
}
function computeMedian(array) {
var xIndices = [];
for (var index = 0; index < array.length; index++) {
if (containsElementAt(index, array)) {
xIndices.push(index);
}
}
if (xIndices.length === 0) {
return -1;
}
var medianIndex = -1;
if (xIndices.length % 2 === 0) {
medianIndex = xIndices.length / 2;
} else {
medianIndex = (xIndices + 1) / 2;
}
return xIndices[medianIndex];
}
function computeStepsForGroupingElementsAround(index, array) {
var start = index, end = index, steps = 0;
for (var i = index; i >= 0 ; i--) {
if (containsElementAt(i, array)) {
start = i;
} else {
break;
}
}
for (var i = index; i <= array.length - 1 ; i++) {
if (containsElementAt(i, array)) {
end = i;
} else {
break;
}
}
for (var i = 0; i < array.length; i++) {
if (containsElementAt(i, array)) {
if (i < start) {
steps += start - 1 - i;
start--;
}
if (i > end) {
steps += i - end - 1;
end++;
}
}
}
return steps;
}
function containsElementAt (index, array) {
return array[index] === 'X' || array[index] === 'x';
}
At each step either the left most set of continuous occupants (L) need to be moved to right or the right most set of continuous occupants(R) needs to be moved to left.
We can be greedy and chose the smaller group.
Reasoning:Eventually the gap needs to be bridged between L & R. assume L is the smaller group. If in optimal solution L is not moved right, (R+(Total - L -R) which is > R > L) need to be moved to left as a last step. Which is costlier than moving L to right. This means L moving right in last steps gives a better solution. This contradicts that L is not moved right in solution.
Solution: in each step move lower of L, R to right or left respectively. Add new next continuous merged block to L or R respectively. Continue till L meets R.
Python code:
#left is number of continuous occupants to left of rest of seats to be looked into
#right is number of continuous occupants to right of rest of seats to be looked into
#b is left index of seats yet to be looked into
#e is right index of seats yet to be looked into
def cost(left, right, b, e):
if (b == e):
return 0
nl = left+summary[b]
nr = right+summary[e];
if (nl <= nr):
return nl * summary[b+1] + cost(nl, right, b + 2, e)
else:
return nr * summary[e-1] + cost(left, nr, b, e-2)
seating = get_string_from_user("Enter seat occupancy string: ");
#seating = "...XXX..XX.XXXX...."
print seating
summary = [];
inplen = len(seating)
summary.append(0);
j = 0;
prev = 'X'
dpa={}
# build summary array that contains alternating counts of occupied sets and empty seats
# always starts with occupied seats and ends with occupied seats
for i in range (inplen):
if (seating[i] == prev):
summary[j] = summary[j] + 1
else:
prev = seating[i]
summary.append(1)
j = j+1
if(seating[inplen-1] == '.'):
j = j + 1
summary.append(0)
print summary
print cost(0, 0, 0, j)
This does not work in all cases. Take the example "xx.x.x....x". Your solution would result in the follow sequence of shifts:
xx.x.x....x
xxx..x....x
xxx.x.....x
xxxx......x
xxxx.....x.
xxxx....x..
xxxx...x...
xxxx..x....
xxxx.x.....
xxxxx......
And then output 9, however the correct answer is 8.
The correct answer is achieved by choosing the median person and then shifting everyone to the nearest empty seat. The correct sequence looks like this:
xx.x.x....x
x.xx.x....x
.xxx.x....x
.xxxx.....x
.xxxx....x.
.xxxx...x..
.xxxx..x...
.xxxx.x....
.xxxxx.....
The correct sequence according to my solution would be:
xx.x.x....x - right most count is least and cost = 1*4
xx.x.xx.... - now it may move either left or right cost = 2*1
.xxx.xx.... - right most count is least and cost = 2*1
.xxxxx..... - Total cost = 4+2+2 = 8
Total cost = 8
@gudujarlson, at each step we move either the right most or the left most occupants never the ones in between so your sequence displayed is incorrect.
Always shrink occupied seats to median
def count_moves(s):
lst = []
for i in range(len(s)):
if s[i] == 'X':
lst.append(i)
med = len(lst) / 2
left_count = 0
right_count = 0
for i in range(med - 1, -1, -1):
left_count += lst[med] - lst[i] - (med - i)
for i in range(med + 1, len(lst)):
right_count += lst[i] - lst[med] - (i - med)
return left_count + right_count
Take two point ( Left and Right) and take two counts(LeftCount and RightCount).
xx.x.x....x
Left=0 and Right=10, LeftCount=2 and RightCount=1
Move which count is less or if equal move any.
xx.x.xx.... Total Move=4
Left=0 and Right=7, LeftCount=2 and RightCount=2
xx.xxx..... Total Move=2
Left=0 and Right=6, LeftCount=2 and RightCount=3
.xxxxx..... Total Move=2
Grand Total Move=8
How about a very simple implementation using the median O(n) complexity and O(1) memory:
public static int countMoves(String str){
//find the median or median-like position
int leftIndex = -1;
int rightIndex = 15;
while(leftIndex < rightIndex){
leftIndex = findNext(1, str, leftIndex, 'x');
rightIndex = findNext(-1, str, rightIndex, 'x');
}
int total = 0;
//now move positions back towards the edges
//start with the left
//find first open position
int open = findNext(-1, str, leftIndex, '.');
//find first seated that needs to be moved
leftIndex = findNext(-1, str, open, 'x');
//now compute the move costs
while(leftIndex > -1){
total += open - leftIndex;
open--;
leftIndex = findNext(-1, str, leftIndex, 'x');
}
//now do the right
open = findNext(1, str, rightIndex, '.');
//find the first seated that needs to be moved
rightIndex = findNext(1, str, open, 'x');
//now compute the move costs
while(rightIndex < 15){
total += rightIndex - open;
open++;
rightIndex = findNext(1, str, rightIndex, 'x');
}
return total
}
private static int findNext(int interval, String str, int currPos, char c){
int index = currPos + interval;
while(index < str.length() && index > -1){
char checkC = str.charAt(index);
if(checkC == c){
return index;
}
index+= interval;
}
return index;
}
public int minimumMove(String str) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'x') {
list.add(i);
}
}
if (list.size() <= 1) {
return 0;
}
int minsum = Integer.MAX_VALUE;
int size = list.size();
int from = list.get(0);
int to = list.get(list.size() - 1);
for (int i = from; i <= to - size + 1; i++) {
int sum = 0;
for (int j = 0; j < size; j++) {
sum += Math.abs(list.get(j) - i - j);
}
if (sum < minsum) {
minsum = sum;
}
}
return minsum;
}
Please consider this approach and improve on it if possible.
(a) let total number of seats occupied be x;
(b) find the window of x such that in the given arrangement number of seats occupied are maximum.
(c) fill the remaining seats by doing the following -> start from 0 to i and if there are any seats occupied move it to first available seat in the window. do the same when we pass from n - 1to i+k, fill the first available seat from right in the window.
1. Let there be x no of occupied positions, store these positions(1 to n) in an array say posx[](index- 1 to n) .
2. Now, implement the following
steps=0; //ans
for(int i=1;i<=x;i++)
{
int temp=posx[i+1]-posx[i]; //difference between two consequetive positions
if(i<x-i) //checks no of elemts on both sides, side with
steps+=(i*(temp-1)); //lesser no of elemnts is moved
else
steps+=((x-i)*(temp-1));
}
1. Let there be x no of occupied positions, store these positions(1 to n) in an array say posx[](index- 1 to n) .
2. Now, implement the following
steps=0; //ans
for(int i=1;i<=x;i++)
{
int temp=posx[i+1]-posx[i]; //difference between two consequetive positions
if(i<x-i) //checks no of elemts on both sides, side with
steps+=(i*(temp-1)); //lesser no of elemnts is moved
else
steps+=((x-i)*(temp-1));
}
1. Let there be x no of occupied positions, store these positions(1 to n) in an array say posx[](index- 1 to n) .
2. Now, implement the following
steps=0; //ans
for(int i=1;i<=x;i++)
{
int temp=posx[i+1]-posx[i]; //difference between two consequetive positions
if(i<x-i) //checks no of elemts on both sides, side with
steps+=(i*(temp-1)); //lesser no of elemnts is moved
else
steps+=((x-i)*(temp-1));
}
1. Let there be x no of occupied positions, store these positions(1 to n) in an array say posx[](index- 1 to n) .
2. Now, implement the following
steps=0; //ans
for(int i=1;i<=x;i++)
{
int temp=posx[i+1]-posx[i]; //difference between two consequetive positions
if(i<x-i) //checks no of elemts on both sides, side with
steps+=(i*(temp-1)); //lesser no of elemnts is moved
else
steps+=((x-i)*(temp-1));
}
My Logic
Take two arrays say left ans right.
each position in left array will store count of number of X seen before that position
each position in right array will store count of number of X seen after that position
it can been done in O(n) time
then answer will be sum of all positions ans+= (min(L[i],R[i]) for all i
Can be done in O(n) using the prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'
string s;
int pad[N];
int pax[N];
ll ans=0;
ll MOD(ll x)
{
if(x<0)
return MOD(x+mod);
else
return x%mod;
}
int main()
{
cin>>s;
int up=s.length()-1;
pad[0]=(s[0]=='.');
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
pad[i]=pad[i-1]+(s[i]=='.');
pax[i]=pax[i-1]+(s[i]=='x');
}
//calculate no of push if centre at 0
ll la=0;
ll ra=0;
FOR(i,1,up)
{
if(s[i]=='x')
{
//cout<<"pad[i]="<<pad[i]<<endl;
ra = ra + 1ll*pad[i];
//cout<<"----------------"<<endl;
}
}
ans=ra;
//cout<<ans<<endl;
FOR(i,1,up)
{
if(s[i-1]=='.')
{
ra-=1ll*(pax[up]-pax[i-1]);
la+=1ll*pax[i-1];
}
ans = min(ans, la+ra);
//cout<<"i="<<i<<" ans="<<ans<<" la="<<la<<" ra="<<ra<<endl;
}
cout<<MOD(ans)<<endl;
}
Can be done in O(n) using prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'
string s;
int pad[N];
int pax[N];
ll ans=0;
ll MOD(ll x)
{
if(x<0)
return MOD(x+mod);
else
return x%mod;
}
int main()
{
cin>>s;
int up=s.length()-1;
pad[0]=(s[0]=='.');
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
pad[i]=pad[i-1]+(s[i]=='.');
pax[i]=pax[i-1]+(s[i]=='x');
}
//calculate no of push if centre at 0
ll la=0;
ll ra=0;
FOR(i,1,up)
{
if(s[i]=='x')
{
//cout<<"pad[i]="<<pad[i]<<endl;
ra = ra + 1ll*pad[i];
//cout<<"----------------"<<endl;
}
}
ans=ra;
//cout<<ans<<endl;
FOR(i,1,up)
{
if(s[i-1]=='.')
{
ra-=1ll*(pax[up]-pax[i-1]);
la+=1ll*pax[i-1];
}
ans = min(ans, la+ra);
//cout<<"i="<<i<<" ans="<<ans<<" la="<<la<<" ra="<<ra<<endl;
}
cout<<MOD(ans)<<endl;
}
Can be done in O(n) using prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'
string s;
int pad[N];
int pax[N];
ll ans=0;
ll MOD(ll x)
{
if(x<0)
return MOD(x+mod);
else
return x%mod;
}
int main()
{
cin>>s;
int up=s.length()-1;
pad[0]=(s[0]=='.');
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
pad[i]=pad[i-1]+(s[i]=='.');
pax[i]=pax[i-1]+(s[i]=='x');
}
//calculate no of push if centre at 0
ll la=0;
ll ra=0;
FOR(i,1,up)
{
if(s[i]=='x')
{
//cout<<"pad[i]="<<pad[i]<<endl;
ra = ra + 1ll*pad[i];
//cout<<"----------------"<<endl;
}
}
ans=ra;
//cout<<ans<<endl;
FOR(i,1,up)
{
if(s[i-1]=='.')
{
ra-=1ll*(pax[up]-pax[i-1]);
la+=1ll*pax[i-1];
}
ans = min(ans, la+ra);
//cout<<"i="<<i<<" ans="<<ans<<" la="<<la<<" ra="<<ra<<endl;
}
cout<<MOD(ans)<<endl;
}
A brute force solution is to, for each seat S, shift each person to the unoccupied seat closest to S and remember which choice of seat results in the minimum number of shifts. Complexity is O(n^2). A faster solution is to find the median person M and shift each person to the unoccupied seat closest to M. Complexity is O(n). Here are both solutions in Java.
- gudujarlson November 04, 2014