Flipkart Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

DP O(n) solution:

Let S[k] = maximum sum of the subsequence that: (1) finishes at position k, and (2) satisfies the constraint.

Init values:

S[0] = arr[0];
S[1] = arr[1];
S[2] = arr[2] + arr[0];

Recursive formula:

S[k] = arr[k] + max(S[k-2], S[k-3]),  for k >=3;

Note: we don't need to care about S[k-4], since if it is in optimal solution, it must be included in S[k-2] already.

The answer is

ans = max (S[n], S[n-1], S[n-2]);

DP table can be computed in O(n) time.

To print the subsequence, we need to record the position where the maximum is achieved, using an array Prev[], like this:

S[k] =  arr[k] + max(S[k-2], S[k-3]);
Prev[k] = (S[k-2] > S[k-3] ? k-2 : k-3);

- ninhnnsoc April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

very nyc solution

just 1 doubt ...ans = max (S[n], S[n-1], S[n-2]);
can u provide the test case where S[n-2] ll get selected

Thanks,

- kartikkhatri01 April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@kartikkhatri01: You are correct! S[n-2] < S[n] always!
Should be:

ans = max (S[n], S[n-1]);

- ninhnnsoc April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What will be the solution for the question, if there were negative numbers also in the array? the current dp will not work.

- Shrima April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good question, Shrima!
For negative numbers, we need to change the DP formula. Obviously we can ignore the negative numbers, since they reduce the sum.

Define the optimization function:

S[k] = the maximum sum of the satisfied sub-sequence for the input array from A[0] to A[k];

Initial values:

S[0] = max (A[0], 0);
S[1] = max (A[1], S[0]);

Recursive formula:

For k>=2:
S[k] = S[k-1], if A[k] <=0; 		    //i.e.: ignore A[k]
S[k] = max(A[k] + S[k-2], S[k-1]) , if A[k]>0		//i.e.: consider whether picking A[k] gives better sum.

From the definition of S[k], we can infer that:

S[u] >= S[u-1], for all u;

Thus, the recursive formula can be deduced to

S[k] = max( A[k] + S[k-2],  S[k-1]);

The answer will be

ans = S[n];

To print out the sequence, we need to find out which position is picked in order to get the maximum sum. This can be done back-ward basing on the S[k] formula.

- ninhnnsoc April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is an other way to work with NEGATIVE numbers. Just set all negative numbers to be 0:

For all u:
A[u] = 0, if A[u] <0;

Then apply the same DP approach in my original post.
When printing out the sub-sequence, just exclude all 0 numbers.

- ninhnnsoc April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc
Formula you have given for DP would not work for input
9,2,8,1
because it will give 18,though its correct answer is 17

ex
s[0]=9
s[1]=2
s[2]=17

s[3]=1+17=18

correct DP formula should be
s(n)=s(n-2)+a(n),s(n-1)
where
//initilization
s[0]=9
s[1]=2

s[2]=17

s[3]=17
please correct me,if i am somewhere wrong.

- Anonymous April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My S[3] = 10, not 18 as you calculated. Please look again at the recursive formula.

- ninhnnsoc April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

sorry
s(n)=max(s(n-2)+a(n),s(n-1) )

- Anonymous April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose your init values are:
S[0] = a[0];
S[1] = a[1]; (?)

Let calculate S[] by your formula for this input: 9,2,1,8:
S[0] = 9;
S[1] = 2; (?)

S[2] = max(S[0] + 1, S[1]) = max(9 + 1, 2) = 10. Good!
S[3] = max(S[1] + 8, S[2]) = max(2 + 8,10) = 10, Not good!

Your formula is correct or not depends on how you define the meaning of S[k], and the initiated values.
(In my definition above, I force the subsequence must be ending at k, it's easier for logic and for printing out subsequence later).

You will correct if you define S[k] as the maximum sum of the satisfied subsequence of the array a[0] .. a[k], where the subsequence may or may not ending at k.

And the init value should be:
S[0] = a[0];
S[1] = max(a[0], a[1]); (!)

Recursive formula can be:
S[k] = max(S[k-1], S[k-2] + a[k]), for k>=2;

The answer will be:
ans = S[n];

However, it's a little bit more complicated for printing out the subsequence.

- ninhnnsoc April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just notice that this DP formula can work for negative numbers as well, only need to change the initial values.

- ninhnnsoc April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we just make two arrays with alternative numbers and find max subset in both of them using kande's algo.
Whichever is max thats the answer.

- rv April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

9,2,1,8

max ld be 17 ... but in ur case it ll be 10 ..

- Anonymous April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

begginer ..cldnt think bettr den dis :o

sort the array (NlogN)

Start from the end ... pick 1 .. check for avalabilty of the next element from the end . nd so on
Now Start for 2nd last element check for avalabilty of the next element from it. nd so on..

- kartikkhatri01 April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For Maximum Subsequence, we have

int[] findSubsequence(int[] array, int start, int end) {

	if(start > end || start < 0 || end >= array.length )
		return {0};

	if(start == end)
		return {array[start]};


	Below case is satisfied implicitly
	// if(start >= 0 && end < array.length)

	int max = Integer.MIN_VALUE;
	int[] maxArray = {};
	// Let k be in the range start and end
	for(int k = start; k <= end; k++) {
	
		int[] a1 = findSubsequence(array, start, k - 2);
		int[] a   = {array[k]};
		int[] a2 = findSubsequence(array, k+ 2, end);

		int[] A = Merge(a1, Merge(a, a2));

		int sum = 0;
		for(int i = 0; i < A.length; i++) {
			sum = sum + A[i];
		}

		if(sum > max) {
			maxArray = A;
			max = sum;
		}

	}

	return maxArray;

}

I didn't implement Merge algorithm, I hope it is simple and anyone would be able to write it.

- Piyush April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since the given array contains positive numbers we have make use of that information

int maxSequence(int[] array, int endingAt) {

	if(endingAt < 2) {
		return;
	}

	int maxIndex = 0;

	if(endingAt - 2 == 0) {
		maxIndex = 0;
	}
	else if(array[endingAt -2]   >= array[endingAt - 3]) {
		maxIndex = endingAt - 2;
	}
	else {
		maxIndex = endingAt - 3;
	}
	
	System.out.print(new String(array[maxIndex]) + " ");

	return (array[maxIndex] + maxSequence(array, maxIndex));

}


// Inside main method

public static void main(String[] args) {

	int array[] = {......................................}
	int endingAt = array.length - 1;

	if(array.length < 2)
		System.out.println("No such sequence Possible");

	if(array[endingAt] < array[endingAt - 1]) {
		endingAt = endingAt - 1;
	}

	System.out.println(maxSequence(array, endingAt));
}

- Piyush April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

yeah, simple recursive solution.

S(k) = max(S(k-2) + a[k], S(k-1).

public int sum(int[] input) {
        return sum(0, input)
    }
    private int sum(int index, int[] input) {
        if (index >= input.length) return 0;

        return Math.max(
                sum(index+1, input),
                sum(index+2, input) +input[index]
        );
    }

If you bother about printing subsequeunce also, you can pass a list and add input[index] to list if sum(index+2, input) is greater.

Only problem with the recursive solution is you would be computing S(k) over and over again. You can get rid of this by memorization.

store S(k) in maxIndex when you compute S(k). So next time you can get S(k) from it. You have to initialize maxIndex with all -1.

public int sum(int index, int[] input, int[] maxIndex) {
        if (index >= input.length) return 0;

        if (maxIndex[index] != -1) {
            return maxIndex[index];
        }

        int result =  Math.max(
                sum(index+1, input, maxIndex),
                sum(index+2, input, maxIndex) +input[index]
        );
        maxIndex[index] = result;
        return result;
    }

- ajit@ajitk.in April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

def maxSub(arr):
        start = 0
        top = (0,0)
        for x in range(len(arr)):
                if x == len(arr)-1 or arr[x] == arr[x+1]:
                        if sum(arr[start:x+1])>sum(arr[top[0]:top[1]+1]):
                                top = (start, x)
                        start = x+1
	print sum(arr[top[0]:top[1]+1]), arr[top[0]:top[1]+1]

Since the array contains only positive integers, there's no need to break out recursion (if there were negative numbers, it's possible that a shorter subsequence of a larger non-repeating sequence could have a higher sum, which recursion would help catch). Just iterate through the array finding the subsequences that don't have any repeated numbers and record the highest sum. Basically a modified linear search.

- Grendus April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# code

public void GetMaxSub( int[] numbers )
        {
            int[] sum = new int[numbers.Length];
            int[] prev = new int[numbers.Length];

            for( int i = 0; i < numbers.Length; i++ )
            {
                int maxSum = 0;
                int bestPrev = -1;
                for( int j = 0; j < i - 1; j++ )
                {
                    if( sum[j] > maxSum )
                    {
                        maxSum = sum[j];
                        bestPrev = j;
                    }
                }
                sum[i] = maxSum + numbers[i];
                prev[i] = bestPrev;
            }

            int maxPos = 0;
            int prevMax = 0;
            for( int i = 0; i < sum.Length; i++ )
            {
                if( sum[i] > prevMax )
                {
                    prevMax = sum[i];
                    maxPos = i;
                }
            }

            Console.WriteLine( prevMax );
            while( maxPos >= 0 )
            {
                Console.Write( numbers[maxPos] + " ");
                maxPos = prev[maxPos];
            }
        }

- at April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a array A[] = {1,2,5,10,11,3,9}

n is the length of A; n = A.length

with an exemption n >=3

A[k]= 5
A[k-1] = 2
A[k-2] = 1
previous = A[k-2]; 2
max(A[k-1],A[k-2]) = 2

max(A[k-1],A[k-2]) + A[k] on a condition max(A[k-1],A[k-2]) != previous

if(max(A[k-1],A[k-2]) != previous)
{
sum[counter] = max(A[k-1],A[k-2]) + A[k]

counter++;
}else
{
sum[counter] = A[k]
counter++;
}
previous = A[k-2]

After this iterate over sum array and find the maximum number.

- jassi.srmcem May 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MAX(int a, int b)
{
    return a>b?a:b;
}

int GetMax(int input[], int size)
{
    int sumL1 = input[0];
    int sumL2 = input[1];
    int max = 0;
    for(int i = 2; i<size; i++)
    {
        max = MAX(sumL2, input[i]+sumL1);
        sumL1 = sumL2;
        sumL2 = max;
    }
    return max;
}

int main()
{
   cout << "Hello World" << endl; 
   int input[]={1,2,3,4,15,6};
   cout<<GetMax(input, 6);
   return 0;
}

- Amit June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MAX(int a, int b)
{
    return a>b?a:b;
}

int GetMax(int input[], int size)
{
    int sumL1 = input[0];
    int sumL2 = input[1];
    int max = 0;
    for(int i = 2; i<size; i++)
    {
        max = MAX(sumL2, input[i]+sumL1);
        sumL1 = sumL2;
        sumL2 = max;
    }
    return max;
}

int main()
{
   cout << "Hello World" << endl; 
   int input[]={1,2,3,4,15,6};
   cout<<GetMax(input, 6);
   return 0;
}

- Amit June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
            Console.WriteLine(FindMaxSequence(new int[] { 2,1,5,3,1,7,9,8,2,8 }));
            Console.WriteLine(FindMaxSequence(new int[] { 9,2,8,1 }));
        }

        /// <summary>
        /// Contributed by Pramod Chandoria
        /// We will devide the problem and solve it recursively
        /// </summary>
        /// <param name="sequence"></param>
        /// <param name="startIndex"></param>
        /// <returns></returns>
        static int FindMaxSequence(int[] sequence, int startIndex = 0)
        {
            int elements = sequence.Length - startIndex;
            if (elements <=0)
            {
                return 0;
            }
            
            if (elements == 1)
            {
                return sequence[startIndex];
            }
            int max1 = FindMaxSequence(sequence, startIndex + 1);
            int max2 = sequence[startIndex] + FindMaxSequence(sequence, startIndex + 2);
            return Math.Max(max1, max2);
        }
    }

- pc October 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And This is optimized solution

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FindMaxSequence(new int[] { 2, 1, 5, 3, 1, 7, 9, 8, 2, 8 }));
            Console.WriteLine("Count=" + called + " for n=10");
            called = 0;

            Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
            Console.WriteLine("Count=" + called + " for n=5");
            called = 0;

            Console.WriteLine(FindMaxSequence(new int[] { 9, 2, 8, 1 }));
            Console.WriteLine("Count=" + called + " for n=4");
            called = 0;
            
            var sequence = new int[]
                                 {
                                     1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 3, 3, 4, 5, 6, 7, 8, 9, 6, 5, 3, 2, 1, 4, 4, 100,
                                     12, 1, 34, 45
                                 };
            Console.WriteLine(FindMaxSequence(sequence));
            Console.WriteLine("Count=" + called + " for n=" + sequence.Length);
            called = 0;

        }

        static int FindMaxSequence(int[] sequence)
        {
            int secondSum = 0;
            int firstSum = 0;
            FindMaxSequence(sequence, 0, out firstSum, out secondSum);
            return Math.Max(firstSum, secondSum);
        }

        
        static int called = 0;
        /// <summary>
        /// Contributed by Pramod Chandoria
        /// We will devide the problem and solve it recursively
        /// </summary>
        /// <param name="sequence"></param>
        /// <param name="startIndex"></param>
        /// <param name="firstSum"></param>
        /// <param name="secondSum"></param>
        static void FindMaxSequence(int[] sequence, int startIndex, out int firstSum, out int secondSum)
        {
             called++;
            int elements = sequence.Length - startIndex;
            if (elements <=0)
            {
                secondSum = 0;
                firstSum = 0;
                return;
            }
            
            if (elements == 1)
            {
                secondSum = 0;
                firstSum = sequence[startIndex];
                return;
            }
            else if (elements == 2)
            {
                secondSum = sequence[startIndex + 1];
                firstSum = sequence[startIndex];
                return;
            }

            FindMaxSequence(sequence, startIndex + 2, out firstSum, out secondSum);
            firstSum = sequence[startIndex] + Math.Max(firstSum, secondSum);
            secondSum = sequence[startIndex + 1] + secondSum;

            return;
        }

- pc October 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution in Time complexity O(n) and space compexity O(1)

def maxSeq(lst):
    maxSum = 0
    sum = lst[0];
    i = 0
    j = 1
    l = len(lst)
    start = 0
    end = 0
    while True:
        if j == l:
            break;
        if lst[j - 1] == lst[j]:
            i = j
            j += 1
            sum = lst[i]
        else:
            sum += lst[j]
            j += 1
        if sum > maxSum:
            maxSum = sum
            start = i
            end = j
    print maxSum, seq[start:end]

seq = [1,2,10,11,3,4,4,15,15,6]

maxSeq(seq)

- Anonymous November 03, 2014 | 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