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

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

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)

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

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

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

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

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

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.

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

In this case, wont we need to track indices?

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

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.

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)

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

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

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

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

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.

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

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

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

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

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

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];
finalString = finalString.substring(0,
finalString.length() - 2);
pos = i;
i = index;
} else {
getAllTouples(touples, i, pos);
finalString = finalString.substring(0,
finalString.length() - 1);
}
}
}

}
}

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]

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

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

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

}

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

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

}

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

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

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;

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

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

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

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

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

O(n) = 2n

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]

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

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

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

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

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

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.