## Walmart Labs Interview Question for Senior Software Development Engineers

Team: R&D
Country: India
Interview Type: Written Test

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

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.

``````// Brute force. For each chair, shift all people to it. Remember which chair requires the least shifts.
// O(n^2)
int minJumps(String s) {
int minCount = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); ++i) {
int count = shift(s.toCharArray(), i);
if (count < minCount) {
minCount = count;
}
System.out.println(new String(s) + " " + count);
}
return minCount;
}

// Optimized. Find the median person and shift everyone to them.
// O(n)
int minJumpsOptimized(String s) {
int i = findMedian(s.toCharArray());
if (i == -1) {
return 0;
}
return shift(s.toCharArray(), i);
}

// Shifts each person the the unoccupied seat closest to seat i.
int shift(char s[], int i) {
int count = 0;
int j = 0;
int k = i;
while (j < k) {
if (s[j] == '.') {
j++;
}
else if (s[k] == 'x') {
k--;
}
else {
s[k] = s[j];
s[j] = '.';
count += k-j;
j++;
k--;
}
}
j = s.length - 1;
k = i;
while (j > k) {
if (s[j] == '.') {
j--;
}
else if (s[k] == 'x') {
k++;
}
else {
s[k] = s[j];
s[j] = '.';
count += j-k;
j--;
k++;
}
}
return count;
}

// Finds the median person.
int findMedian(char s[]) {
int count1 = 0;
for (char c : s) {
if (c == 'x') {
count1++;
}
}
if (count1 == 0) {
return -1;
}
count1 = (count1 + 1) / 2;
int count2 = 0;
for (int i = 0; i < s.length; ++i) {
if (s[i] == 'x') {
count2++;
if (count2 == count1) {
return i;
}
}
}
throw new RuntimeException("yuk!");
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@gudujarlson, please see a proof below.

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

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

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

Vikram, Your solution looks good. I will try it in java. Thanks for posting it.

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

@gudujarlson points out median is the fast way to go. I'll give a
proof here.

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

Comment hidden because of low score. Click to expand.
0

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.

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

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.

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

looks like a DP problem

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

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)

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

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;

}``````

Comment hidden because of low score. Click to expand.
0

This does not work in all cases. See my comment below.

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

//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';
}``````

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

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';
}``````

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

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

Comment hidden because of low score. Click to expand.
0

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.....``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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

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

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

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

``````public int minimumMove(String str) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'x') {
}
}
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;
}``````

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

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.

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

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

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

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

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

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

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

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

}

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

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

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

Can be done in O(n) using the prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'

string s;
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;
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
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<<"----------------"<<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;
}

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

Can be done in O(n) using prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'

``````string s;
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;
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
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<<"----------------"<<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;
}``````

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

Can be done in O(n) using prefix array concept.
pax -> prefix array for 'x'
pad -> prefix array for '.'

``````string s;
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;
pax[0]=(s[0]=='x');
FOR(i,1,up)
{
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<<"----------------"<<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;``````

}

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

Can be done in O(n) using prefix array concept.

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.

### 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.