Flipkart Interview Question for Senior Software Development Engineers


Country: India
Interview Type: Phone Interview




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

O(n) time algorithm: Use the same classic algorithm for Longest Increasing Subsequence, breaking when you find a subsequence of length 3.

(See wiki page for details)

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

Actually this is the best solution for the question...Get the Longest Increasing Subsequence ... either by

-Using Patience Sort --- O(n) OR
-Using Dynamic Programming --- O(n*n)

- peechus July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the wiki it says algorithm runs O(n log n).

- elber.kam July 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an elegant and straightforward answer to this problem. I think longest increasing subsequence is O(n log n).

- Anonymous July 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

make a binary search tree from a given array
try to get right side of node which full fill this condition

- shikhil July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Wonderful! While building the tree, if a node is inserted as a right child of a right child, the ancestor, parent and child form the required triplet.

- Murali Mohan July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

In this case, wont we need to track indices?

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

make a binary search tree from a given array try to get right side of node which full fill this condition. Make binary search tree can’t solve problem because it does not maintain the order of the array.

- neelabhsingh October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Create two arrays;
One will store the input numbers.
Other array will contain the index. Inaitally {0, 1,2,3, ..}

Sort the input array and while sorting also change the index array whenever these is swap in the input array.

Now traverse both the sorted input array and the index array.
For every number check the 2 numbers after it and there original indexes in the index array.
If the indexes are such tht i < j < k. Then this is a required triplet.

Complexity is O(nlogn + n) = O(nlogn)

- subahjit July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I thought about the same solution, but then realized the second half of the solution won't work in O(n) a simply chcking the next two consecutive number won't do here.
Please recheck, rather we need to scan the index array, and see, if any triplet exist such that a<b<c

- Varun July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I guess get the common subsequence between sorted array and original array

- shsf July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Varun
Why do you think that the second part will not work?
It just checking in the sorted array and the index array that the 3 numbers are such that a < b < c and index a < index b < index c.

- subahjit July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@subajit

Varun is correct. Simply checking the next consecutive numbers wont work, because the elements of a triplet can be more than a unit distance apart from one another.

As a counter-example, consider the following sequence of numbers and their indices

numbers: 3 2 1 5 4 6
indices: 1 2 3 4 5 6

After sorting, the numbers and indices change to:

numbers: 1 2 3 4 5 6 
indices: 3 2 1 5 4 6

The algorithm that checks 2 consecutive elements will not detect any of the triplets: {3,5,6} {3,4,6} {2,5,6} {2.4.6} {1,5,6} & {1,4,6} that are present in the original array.

- Murali Mohan July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Dumbo I got it.
Then in that case, I guess the binary search tree solution will be the correct one.

- subahjit July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findTriplet(vector<int> &v)
{
    int a[3];

    int size = v.size();
    a[0] = v.at(0);
    int cur = 0;

    for(int i = 1; i<size; ++i)
    {
        int next = v.at(i);
        if(next <= a[0])
        {
            a[0] = next;
        }
        else
        {
            if(next > a[cur])
            {
                if(cur == 1)
                {
                    //found the triplet
                    cout<<a[0]<<" "<<a[1]<<" "<<next<<endl;
                    return;
                }
                else
                {
                    cur++;
                    a[cur] = next;
                }
            }
            else
            {
                a[cur] = next;
            }
        }
    }
    cout<<"No such numbers"<<endl;
}

- Seeker July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a little correction in the above code. time complexity is O(n) without modifying the array input.

void findTriplet(vector<int> &v)
{
    int a[3];
    int p;

    int size = v.size();
    a[0] = v.at(0);
    int cur = 0;

    for(int i = 1; i<size; ++i)
    {
        int next = v.at(i);
        if(next <= a[0])
        {
            a[0] = next;
        }
        else
        {
            if(next > a[cur])
            {
                if(cur == 1)
                {
                    //found the triplet
                    cout<<p<<" "<<a[1]<<" "<<next<<endl;
                    return;
                }
                else
                {
                    cur++;
                    a[cur] = next;
                    p = a[cur-1];
                }
            }
            else
            {
                a[cur] = next;
                p = a[cur-1];
            }
        }
    }
    cout<<"No such numbers"<<endl;
}

- Seeker July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is java program which will print all touples with the combinations

package com.bala.logical;

import java.util.ArrayList;
import java.util.List;

public class FindTouple {
	static int[] array = new int[] { 3, 2, 1, 6, 5, 4, 9, 8, 7 };
	static String finalString = "";

	public static void main(String[] args) {

		List<String> touples = new ArrayList<String>();
		for (int i = 0; i < array.length; i++) {
			getAllTouples(touples, i, 0);
		}
		System.out.println(touples);
	}

	public static List<String> getAllTouples(List<String> touples, int index,
			Integer pos) {
		int pivotElement = array[index];
		for (int i = index + 1; i < array.length; i++) {
			if (pivotElement < array[i] && pos < i) {
				finalString = finalString + pivotElement;
				if (finalString.length() == 2) {
					finalString = finalString + array[i];
					touples.add(finalString);
					finalString = finalString.substring(0,
							finalString.length() - 2);
					pos = i;
					i = index;
				} else {
					getAllTouples(touples, i, pos);
					finalString = finalString.substring(0,
							finalString.length() - 1);
				}
			}
		}

		return touples;
	}
}


Output:

[369, 368, 367, 359, 358, 357, 349, 348, 347, 269, 268, 267, 259, 258, 257, 249, 248, 247, 169, 168, 167, 159, 158, 157, 149, 148, 147]

- Balakrishna Konduri July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Create one array of original one and sort it
- Find common subsequence between original and sorted array using dp

- shsf July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First create an array called max, where max[i] is the maximum value from arr[i] to the tail of the array. We can construct this array by iterating from the end.
Now start iterating from the beginning, and use a variable called min to keep track of the minimum value from the beginning of the array up to the previous element. With both min & max[i+1], we can easily check whether (min, arr[i], max[i+1]) satisifies the tuple condition or not.

static int[] findTuple(int[] arr) {
  int len = arr.length;
  int[] max = new int[len];
  max[len-1] = arr[len-1];
  for(int i=len-2; i>=0; i--) {
    max[i] = Math.max(arr[i], max[i+1]);
  }
  int min = arr[0];
  for(int i=1; i<len-1; i++) {
    if(min < arr[i] && arr[i] < max[i+1]) {
      int[] result = new int[3];
      result[0] = min;
      result[1] = arr[i];
      result[2] = max[i+1];
      return result;
    }
    min = Math.min(min, arr[i]);
  }
  return null;
}

- Sunny July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution.

main()
{


int arr[]={1,2,3,4,5};
int len=5,a,i,b,h,flag=1;

for(i=0;i<3;i++)
{
h=i;
a=h+1;
b=h+2;
while(b<5)
{
if(arr[a]>arr[h])
{
if(arr[b]>arr[a])
{
printf("%d %d %d ",arr[h],arr[a],arr[b]);
flag=0;
b=b+1;

}

else
{
b=b+1;
}
}
else
{
a=a+1;
b=b+1;
}
}
}

if(flag==1)
{
printf("No such Number Exists");
}

}

- JammY July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(N) Running time algo:

main()
{
    
    
    int arr[]={1,2,3,4,5};
    int len=5,a,i,b,h,flag=1;
    
    for(i=0;i<3;i++)
    {
        h=i;
        a=h+1;
        b=h+2;
        while(b<5)
        {
        if(arr[a]>arr[h])
        {
            if(arr[b]>arr[a])
            {
                printf("%d %d %d  ",arr[h],arr[a],arr[b]);
                flag=0;
                b=b+1;
            
            }
            
            else
            {
                b=b+1;
            }
        }
        else
        {
            a=a+1;
            b=b+1;
        }
        }
    }

if(flag==1)
{
    printf("No such Number Exists");
}

}

- ycleptjammy July 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.zhuyu_deng.test;

public class Test
{
	static int a[] = new int[] { 3, 2, 1, 6, 5, 4, 9, 8, 7 };
	static int c[] = new int[a.length];

	public static void main(String args[])
	{

		int b[] = new int[a.length];
		for (int i = 0; i < b.length; ++i)
			b[i] = 1;

		for (int i = 1; i < a.length; ++i)
		{
			int maxLen = 1;
			for (int j = 0; j < i; ++j)
			{
				if (a[j] < a[i] && b[j] + 1 > maxLen)
				{
					maxLen = b[j] + 1;
					b[i] = maxLen;
					c[i] = j;
				}
				if (maxLen >= 3)
					break;
			}
			if (maxLen >= 3)
			{
				print(i);
				System.out.println();
				break;
			}
		}

	}

	private static void print(int x)
	{
		if (x != 0)
		{
			print(c[x]);
			System.out.print(a[x] + " ");
		} else
		{
			System.out.print(a[x] + " ");
		}
	}
}

- zhuyu.deng July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int minElem = min(arr[0], arr[1]);
    int* maxElems = new int[len];
    int maxElem = arr[len - 1];
    maxElems[len - 1] = maxElem;
    for(int i = len - 2; i >= 0; i--)
    {
        if(maxElem < arr[i]){
            maxElem = arr[i];
        }
        maxElems[i] = maxElem;
    }
    
    for(int i = 1; i < len - 1; ++i){
        if(minElem < arr[i] && maxElems[i] > arr[i]){
            cout << "(" << minElem << ", ";
            cout << arr[i] << ", " << maxElems[i];
            cout << ") is found" << endl;
            delete[] maxElems;
            return;
        }

        if(minElem > arr[i])   minElem = arr[i];
    }

    delete[] maxElems;
    cout << "Nothing is found" << endl;

- Anonymous July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sites.google.com/site/spaceofjameschen/home/search/find-a-tuple-in-ascending-order---flipkart
Let i = current index, len = the length of array
1. Find min in the range of (0, i);
2. Find max in the rante of (i, len - 1)
3. If current value > min && current value < max, print it and exit
4. Loop to next elements

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

int minElem = min(arr[0], arr[1]);
int* maxElems = new int[len];
int maxElem = arr[len - 1];
maxElems[len - 1] = maxElem;
for(int i = len - 2; i >= 0; i--)
{
if(maxElem < arr[i]){
maxElem = arr[i];
}
maxElems[i] = maxElem;
}

for(int i = 1; i < len - 1; ++i){
if(minElem < arr[i] && maxElems[i] > arr[i]){
cout << "(" << minElem << ", ";
cout << arr[i] << ", " << maxElems[i];
cout << ") is found" << endl;
delete[] maxElems;
return;
}

if(minElem > arr[i]) minElem = arr[i];
}

delete[] maxElems;
cout << "Nothing is found" << endl;
- Anonymous on July 09, 2013 | Flag

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

O(n) = 2n

- Anonymous July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in o(n) with space o(2n)

Algo as follows:-

1.create 2 arrays maxTillNow and minTillNow
where Maxtillnow[i]=max{maxTillNow[i+1],A[i]}
and MaxTillnow[n]=A[n]

MinTillNow[i]=min{MinTillNow[i-1],A[i]}

and MinTillNow[0]=A[i]


2.Now again traverse the array
if a[i]!=minTillnow[i] && a[i]!=maxtillnow[i]

print mintillnow[i] a[i] maxtillnow[i]


plus the above condition can also be written as
if a[i]>minTillnow[i] && a[i]<maxtillnow[i]

- blackfever July 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array

while checking for a number n%3=0 put n into new array

then check for e first 3 iterations in th new array

- Darlington July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class FindTuple {
public static void main(String... args){
int arr[]={3, 2, 1, 6, 5, 4, 9, 8, 7};
Arrays.sort(arr);
for(int a : arr){
System.out.print(a);
if(a%3==0){
System.out.println();
}
}
}
}

- Naveen Sharma November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote

public static void main(String[] args) {

		int[] a = { 5, 1, 6, 1, 1, 7 };
		//int[] a2 = { 6, 7, 3, 4, 8 };
		triplet(a);

	}

	public static void triplet(int[] a) {

		int[] triplet = new int[3];
		int min = triplet[0] = a[0];
		triplet[1] = triplet[2] = Integer.MAX_VALUE;

		for (int i = 1; i < a.length; i++) {
			if (a[i] <= min)
				min = a[i];
			else if (a[i] <= triplet[1]) {
				triplet[0] = min;
				triplet[1] = a[i];
			} else {
				triplet[2] = a[i];
				System.out.println("T1: " + Arrays.toString(triplet));
				break;
			}
		}
	}

- thelineofcode July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is giving only 1,6,7 but there is also other tuples 5,6,7 it is not giving.
Your logic is first find min value from the array then find a[1] and a[2] which is after the min element for example
suppose array is given like a[]={2,6,1,5,3,8,1,1,7,9,10};
your logic will produce like [1,3,8], [1,3,7], [1,3,9], [1,3,10]
and other tuples like [2,6,7] , [2,5,7]......etc

- neelabh October 22, 2013 | 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