## Amazon Interview Question for Software Engineer / Developers

Country: India

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

``````a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array:
a      =4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8

Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)``````

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

Nice solution. I implemented it.
But its not showing all the triplets of integers with the criterion mentioned. I know that the problem statement just needs one. But what do we do if we want all the triplets ?

Its not printing out triplets like :
{4,5,8}, {4,5,6}, {1,3,8}, {1,3,6}, etc.

Here is my java code :

``````public class Find3OrderedIntegersInArray
{
// Given an array find 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time.
public static void main (String args[])
{
int[] arr = new int[]{4,7,5,1,3,8,9,6,2};
int size = 9;
int[] mini = new int[size];
int[] maxi = new int[size];
mini = 0;
maxi[size-1] = size-1;

int min = arr;
int max = arr[size-1];
for (int i = 1; i < size; i++)
{
if (arr[i] < min)
{
min = arr[i];
mini[i] = i;
}
else
mini[i] = mini[i-1];
// System.out.print (mini[i] + "  ");
}
System.out.println();
for (int i = size-2; i >= 0; i--)
{
if (arr[i] > max)
{
max = arr[i];
maxi[i] = i;
}
else
maxi[i] = maxi[i+1];
// System.out.print (maxi[i] + "  ");
}
System.out.println();

System.out.println("The output : ");
for (int i = 0; i < size; i++)
if (arr[mini[i]] < arr[i] && arr[i] < arr[maxi[i]])
System.out.println(arr[mini[i]] + " < " + arr[i] + " < " + arr[maxi[i]]);

}
}``````

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

It is not printing--
{4,5,8}, {4,5,6}, {1,3,8}, {1,3,6}, etc

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

When we are creating two array,you will be iterating through all elements of array....so to create two arrays from existing one will take at least o(n) ....and after that again iterating through them to find a[LMin[i]] < a[i] < a[RMax[i] will take another o(n)...so it will be o(n+n)

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

This does work. It will only print one, with the leftmost i, the leftmost j, and the rightmost k.

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

This is very nice algorithm which allows us to print all such sequences not just one of them.

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

``````a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array:
a=4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8
Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)``````

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

Nice solution

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

Elegant!

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

Great solution!
One tiny suggestion:
I think you can only check you need not check the first and last element of the array (i.e 1 and n) as they can never be the middle element.

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

``````void order_numb(vector<int> array){
int N=array.size();
int result;
result=-1;
result=-1;
result=-1;
result=array;
for(int i=1;i<N;i++){
if(array[i]<result && result==-1){
result=array[i];
continue;
}else if(array[i]>result && (result == -1 || result>array[i])){
result=array[i];
continue;
}
if(array[i]>result && array[i]>result){
result=array[i];
cout<<result<<" "<<result<<" "<<result<<endl;
return;
}
}
cout<<"NO SUCH SUBSEQUENCE"<<endl;
}``````

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

A small modification for the corner cases when the array size is less than 3 add a check at the start of the function.
if(N<3)cout<<"NO SUCH SUBSEQUENCE"<<endl;

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

Will not work try with 5 10 1 3 4 7

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

Modify if(array[i]<result && result==-1) to
if(array[i]<result)

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

public static void findIndex(int [] iArray)
{
int [] result = new int;

if(iArray.length < 3)
System.out.println("NO SUCH SEQUENCE");

result = iArray;
result = -1;
result = -1;

for(int i= 1;i<iArray.length;i++)
{
System.out.println(iArray[i] + "->" + result + "->" + result+"->"+result);
if(iArray[i] < result)
{
result = iArray[i];
result = -1;
result = -1;
continue;
}
else if(iArray[i] > result && (result == -1 || result > iArray[i] ))
{
result = iArray[i];
result = -1;
continue;
}
else if(iArray[i] > result && iArray[i] > result)
{
result = iArray[i];
System.out.println("ORDER -->"+result+"-->"+result+"-->"+result);
return;
}
}

System.out.println("NO SUCH SEQUENCE");
}

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

this still wont work for <4,3,6,1,7> or <5,10,1,11>
i.e when there are fewer numbers than 2 when first 2 are already filled in temp array.

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

// Here is a c++ solution that guarantees correctness and is able to handle duplicate.
// However, it is not a O(n) solution. I do not think this problem can be solved in linear time tho. Correct me if I am wrong.

static vector<int> findAscElements(int a[], int l) {
vector<int> r;
for (int i = 0; i < l; i++) {
if (r.size() == 0) { r.push_back(a[i]); }
else if (r.size() == 1) {
if (a[i] < r.front()) { r.pop_back(); r.push_back(a[i]); }
else if (a[i] > r.front()) { r.push_back(a[i]); }
}
else if (r.size() == 2) {
if (a[i] <= r) {
vector<int> d = findAscElements(a + i, l - i);
if (d.size() == 3) { return d; }
}
else if (a[i] < r) { r.pop_back(); r.push_back(a[i]); }
else if (a[i] > r) { r.push_back(a[i]); break; }
}
}
return r;
}

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

garimaa.blogspot.in/2012/04/program-4th-in-c.html

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

A solution in C# based on the idea of keeping the minimum array of length 1, and the minimum array of length 2 in memory and then expanding or updating either until we find an element that would extend the array of length 2 to an array of length 3:

``````static IList<int> FindTriplet(int[] input)
{
int minL1 = int.MaxValue;
int[] minL2 = new int { int.MaxValue, int.MaxValue};

for (int i = 0; i < input.Length; i++)
{
//3 cases:
// 1.) input[i] < minL2 and input[i] > minL2 -> replace array length 2 second number
// 2.)  input[i] > minL1 && input[i] < minL2  -> replace array length 2 with (minL1, input[i])
// 3.) input[i] < minL1 -> replace minL1 with input[i]

if (input[i] > minL2)
{
//success:
return new List<int>() { minL2, minL2, input[i] };
}
else if (input[i] < minL2 && input[i] > minL2)
{
//case 1:
minL2 = input[i];
}
else if (input[i] > minL1 && input[i] < minL2)
{
//case 2:
minL2 = minL1;
minL2 = input[i];
}
else if (input[i] < minL1)
{
minL1 = input[i];
}
}
return null;
}``````

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

Hi Kiruba!

It doesn't work as expected for {15,18,13,17,9,6,20,1,25};
It doesn't print the triplet:
{17,20,25}

Let me know whats wrong!

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

This finds the first 3 elements that meet the requirement with a single loop:

``````def find3(a):
if len(a) == 0:
return []

# first : a[i], second: a[j]
# minel: minimum element encountered so far
first = minel = a
second = None

for n in a[1:]:
if second == None:
if first < n:
second = n
elif first > n:
first = n
elif n > second:
return [first, second, n]
elif n > first:
first, second = minel, n

minel = min(minel, n)

return []``````

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

whitespace wasn't preserved correctly in the solution above. this is the main loop:

``````for n in a[1:]:
if second == None:
if first < n:
second = n
elif first > n:
first = n
elif n > second:
return [first, second, n]
elif n > first:
first, second = minel, n

minel = min(minel, n)``````

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

Here is a solution which has time complexity O(n) and space complexity O(1):

``````#include <iostream>
#include <vector>
#include <iterator>

void push_back(std::vector<int>& v1, std::vector<int>& v2, int value){
if(v1.size() == 0){
v1.push_back(value);
} else if(v1.size() == 1){
if(v1 < value){
v1.push_back(value);
} else {
v1 = value;
}
} else if(v1.size() == 2) {
if(value < v1){
if(v2.size() == 0){
v2.push_back(value);
} else { // v2.size() == 2
if(value > v2){
v2.push_back(value);
v1.swap(v2);
v2.clear();
} else {
v2 = value;
}
}
} else if(value > v1){
v1.push_back(value);
} else if(value > v1){
v1 = value;
}
}
}

void find3(std::vector<int>& v){
if(v.size() < 3){
return;
}
std::vector<int> r1;
std::vector<int> r2;
r1.reserve(3);
r2.reserve(2);
for(size_t i = 0; i < v.size(); ++i){
push_back(r1, r2, v[i]);
if(r1.size() == 3)
break;
}
std::ostream_iterator<int> os(std::cout, " ");
std::copy(r1.begin(), r1.end(), os);
std::cout << std::endl;
}

int main(){
int ar[] = {1,2,1,4,6};
//int ar[] = {6,10,4,2,7,3,1,8};
//int ar[] = {4,3,2,1};
//int ar[] = {8,9,6,7,2,3,10};
//int ar[] = {4,5,3,6};
//int ar[] = {5,4,7,1,2,8};
//int ar[] = {5,4,7,1,2,3,8};
//int ar[] = {5,4,7,1,2,3};
size_t N = sizeof(ar) / sizeof(ar);
std::vector<int> v(ar, ar + N);
find3(v);
return 0;
}``````

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

``````1 #!/usr/bin/python
2 #-*- encoding: utf-8 -*-
3
4 a = [4, 7, 5, 1, 3, 8, 9, 6, 2]
5
6 def find_max_until(a, max_value, max_index):
7     tmp_max = 0
8     tmp_index = 0
9     for index in range(max_index):
10         if tmp_max < a[index] and a[index] < max_value:
11             tmp_max = a[index]
12             tmp_index = index
13     return tmp_max, tmp_index
14 max_value = 100
15 max_index = len(a)
16 for i in range(3):
17     max_value, max_index = find_max_until(a, max_value, max_index)
18     print max_value, max_index``````

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

Looks like you are finding the largest element and its index, then the 2nd largest element up to that index, and finally the 3rd largest element up to the index of the 2nd largest. What if the input is something like {9 8 7 1 2 3}?

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

Can we say that the problem can be reduced to finding the min and max element in the array o given numbers
Once we have that in O(n) time, any number other than them can be taken to form a set of
min < a[i] < max

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

This expects indexOf(min) < indexOf (max) in the input !!

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````bool find3Elements(int ary[], int len, int &i, int &j, int &k)
{
if (len < 3) return false;

int minIdx = 0;
int maxIdx = len - 1;
int start = 1;
int end = len - 2;

while (start <= end)
{
if (ary[start] > ary[minIdx] && ary[start] < ary[maxIdx])
{
i = minIdx;
j = start;
k = maxIdx;
return true;
}
else if (ary[end] > ary[minIdx] && ary[end] < ary[maxIdx])
{
i = minIdx;
j = end;
k = maxIdx;
return true;
}
else
{
if (ary[start] < ary[minIdx]) minIdx = start;
if (ary[end] > ary[maxIdx]) maxIdx = end;
start++;
end --;
}
}

return false;
}``````

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

your code gives correct output only if i, j and k are consecutive not for case like { 6, 5, 4, 2, 11, 3, 4 } where 2, 3 n 4 are 3 nos.

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

If you switch the last two if statements in the else statement so

if (ary[start] < ary[minIdx])
minIdx = start;
start++;

if (ary[end] > ary[maxIdx])
maxIdx = end;
end--;

this will work and hold for all test cases

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

Please plea se why dont people understand that Code is Not the easiest thing in the world to read. IF you wish to really Contribute please write a very small pseudo Code atleast. IF you just want to show off then what should I Say.

Comment hidden because of low score. Click to expand.
-1
of 5 vote

This would work

``````def min3(a)
s1dash = a
s1 = nil
s2 = nil
for i in (1..a.length-1)
if a[i]<s1dash
s1dash = a[i]
elsif(a[i]>s1dash and (s2.nil? or s2>a[i]))
s1 = s1dash
s2 = a[i]
else
puts" #{s1} #{s2} #{a[i]}"
return
end
end
end``````

tested against
a = [15,16,13,14,10,9,6,7,8] ;[5,1,2,3,4];[5, 4, 3, 2, 1]

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

sorry your code will not work for input
[6,10,4,2,7,3,1,8]

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

Sorry again your code is correct ...

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

How this code will work ofr [5,4,3,2,1] initial if will be the only code
executed by loop, and at the end we ll print nothing on screen and ll come out of loop, please correct me if I am wrong.

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

How this code will work for [5,4,3,2,1] initial if will be the only code
executed by loop, and at the end we ll print nothing on screen and ll come out of loop, please correct me if I am wrong.

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

@naive
For input [5,4,3,2,1] the code will print nothing because for this array we cannot find 3 elements which will satisfy the criteria i<j<k and a[i]<a[j]<a[k]

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

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

will this work for 1,2,1,4,6?

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

@anonymous

``````def min3(a)
s1dash = a
s1 = nil
s2 = nil
for i in (1..a.length-1)
if a[i]<s1dash
s1dash = a[i]
elsif(a[i]>s1dash and (s2.nil? or s2>a[i]))
s1 = s1dash
s2 = a[i]
elsif(!s2.nil? and a[i]>s2)
puts" #{s1} #{s2} #{a[i]}"
return
end
end
end``````

modified to print only when we guarantee three increasing elements.

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

Does this work for [4, 8, 3, 9] ? I think that your code does not work in this case.

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

Does this work for [4, 8, 3, 9] ? I think that your code does not work in this case.

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

how would your code handle this input?
[15, 16, 13, 12, 10, 9, 6, 20]

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

@Andy - It will work. It will print 4,8,9
@Anonymous - It will work too. 15,16,20 will be printed.

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

i think,it will not work for this input (20,21,1,2,3).... will it?...

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

it will...123

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

Hi Kiruba,

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.