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

- gudujarlson November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gudujarlson November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gudujarlson, please see a proof below.

- Chenliang Xu November 06, 2014 | Flag
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

- Vikram Bhat November 04, 2014 | Flag Reply
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.

- ayaskant.swain November 04, 2014 | Flag
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.

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?

- Chenliang Xu November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gudujarlson November 06, 2014 | Flag
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.

- Chenliang Xu November 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like a DP problem

- Anonymous November 04, 2014 | Flag Reply
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)

- sc November 04, 2014 | Flag Reply
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;




}

- Navi November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gudujarlson November 05, 2014 | Flag
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';
}

- Sai Gudigundla November 05, 2014 | Flag Reply
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';
}

- Sai Gudigundla November 05, 2014 | Flag Reply
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)

- srikarbs November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gudujarlson November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad. I misinterpreted your solution.

- gudujarlson November 08, 2014 | Flag
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

- glebstepanov1992 November 05, 2014 | Flag Reply
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

- Kulwinder November 08, 2014 | Flag Reply
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
	//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;
}

- zortlord November 12, 2014 | Flag Reply
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') {
				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;
	}

- Anonymous November 15, 2014 | Flag Reply
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.

- krishna February 06, 2015 | Flag Reply
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));
}

- Anonymous August 17, 2015 | Flag Reply
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));
}

- Anonymous August 17, 2015 | Flag Reply
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));
}

- Anonymous August 17, 2015 | Flag Reply
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));

}

- aashima333 August 17, 2015 | Flag Reply
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

- Utkarsh Pagar September 20, 2017 | Flag Reply
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 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;
}

- Sushant Gokhale July 31, 2018 | Flag Reply
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 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;
}

- Sushant Gokhale July 31, 2018 | Flag Reply
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 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;

}

- Sushant Gokhale July 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sushant GOkhale July 31, 2018 | Flag Reply


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