Flipkart Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
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)
make a binary search tree from a given array
try to get right side of node which full fill this condition
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.
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)
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
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.
@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.
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;
}
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;
}
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]
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;
}
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");
}
}
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");
}
}
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] + " ");
}
}
}
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;
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
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
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]
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;
}
}
}
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
O(n) time algorithm: Use the same classic algorithm for Longest Increasing Subsequence, breaking when you find a subsequence of length 3.
- Anonymous July 07, 2013(See wiki page for details)