Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Good solution.
One small correction.
>>print LMin[i],a[i],RMax[i]
should be
print LMin[i],i,RMax[i]
This answer outputs:
4 5 9
1 3 9
1 8 9
1 6 9
1 2 9
while the correct answer is supposed to be:
[4, 7, 8]
[4, 7, 9]
[4, 5, 8]
[4, 5, 9]
[4, 5, 6]
[4, 8, 9]
[7, 8, 9]
[5, 8, 9]
[1, 3, 8]
[1, 3, 9]
[1, 3, 6]
[1, 8, 9]
[3, 8, 9]
I got a solution of O(n) time and O(1) space. It doesn't need to finish going through the array.
The idea:
Go through the list from left to right. If k hasn't been found, I want to find i and j to be some numbers as small as possible. I use variable temp to store a potential smaller i. i and j will be updated at the same time when a smaller j has been found.
Use 4, 7, 5, 1, 3, 8, 9, 6, 2 as an example:
i, j, k, temp
----------
0,-1,-1,-1 // a[0] = 4
0, 1,-1,-1 // a[0] = 4, a[1] = 7
0, 2,-1,-1 // a[0] = 4, a[2] = 5
0, 2,-1, 3 // temp = 3
3, 4,-1,-1 // a[3] = 1, a[4] = 3
3, 4, 5,-1 // a[3] = 1, a[4] = 3, a[5] = 8
i<j<k: 3<4<5
a[i]<a[j]<a[k]: 1<3<8
class Ijk {
public static void main(String[] args) {
Integer[] a = { 4, 7, 5, 1, 3, 8, 9, 6, 2 };
Integer temp = -1, i = -1, j = -1, k = -1;
for (int n = 0; n < a.length; n++) {
if (i != -1) {
if (j != -1) {
if (a[n] > a[i] && a[n] < a[j]) {
j = n;
} else if (a[n] > a[j]) {
k = n;
break;
}
if (temp != -1) {
if (a[temp] < a[i] && a[n] < a[j] && a[n] > a[temp]) {
i = temp;
j = n;
temp = -1;
}
else if (a[temp] < a[i] && a[n] < a[j]
&& a[n] < a[temp]) {
i = n;
j = temp;
temp = -1;
}
} else {
if (a[n] < a[i]) {
temp = n;
}
}
} else {
if (a[n] > a[i]) {
j = n;
}else if (a[n] < a[i]) {
i = n;
}
}
} else {
i = n;
}
}
System.out.println(i + "<" + j + "<" + k);
System.out.println(a[i] + "<" + a[j] + "<" + a[k]);
}
}
Sure. Basically there are several rules that were described by those if and else if's.
(1) if i hasn't been initialized --> set i to the current number
(2) if j hasn't been initialized --> set it to the first number that is larger than a[i]
(3) when j hasn't been initialized, when a smaller number (i.e. a[n]) is found, update i.
(4) if i and j have been found; n represents the new number, if a[n] > a[i] and a[n]>a[j], update j; since a[j] is smaller, it is more likely to find a k.
(5) if i and j have been found, if a[n] > a[j] we find k!! Since we have found i<j<k and a[i]<a[j]<a[k] at this time, the loop can be terminated.
(6) if temp hasn't been initialized, if a[n] < a[i], we found a potentially smaller i, store the i in temp, temp = i
(7) if a number that is smaller than a[j] but larger than a[i] has been found, and temp is initialized, we update i and j at the same time. either, senario one, i=temp, j=the new number or, senario two, i=the new number, j=temp, depending on the relative maginitue of a[temp] and a[n];we reset temp to -1 after this.
I'm glad to see an idea similiar to mine.
I don't know why so many people vote for O(n) space algorithm while O(1) space algorithm exist.
The following is my implementation together with some simple tests:
class G211
{
public static int[] find(int[] array)
{
if (null == array) {return null;}
int[] result = new int[3];
result[0] = result[1] = result[2] = (-1);
for (int i = 0; i < array.length -1; i++)
{
if (array[i] < array[i + 1])
{
if ((-1) == result[0])
{
result[0] = i;
result[1] = i + 1;
}
else if (array[result[1]] < array[i + 1])
{
result[2] = i + 1;
return result;
}
else
{
result[0] = i;
result[1] = i + 1;
}
}
else if ((-1) != result[0])
{
if (array[result[0]] < array[i + 1])
{
result[1] = i + 1;
}
}
}
return null;
}
public static void main(String[] args)
{
int[] array1 = {7, 5, 3, 3, 9, 6, 7};
debug(find(array1));
int[] array2 = {4, 7, 5, 1, 3, 8, 9, 6, 2};
debug(find(array2));
}
public static void debug(int[] array) {debug(array, " ");}
public static void debug(int[] array, String separator)
{
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < array.length - 1; i++) {buffer.append(array[i] + separator);}
if (array.length > 0) {buffer.append(array[array.length - 1]);}
System.out.println(buffer.toString());
}
}
First of all when I was thinking O(N) space soln came to my mind, but when I read that O(1) will be possible, I tried and was able to do it. Here is my approach.
first of all lets see how we can do this if we only need to find 2 numbers in the whole array(i,j): let L be the second of two elements. L will be j if there is an element < L in 0 to L-1 so keep track of min in 0 to L-1. If L > min you have the answer. Run L = 1 to N-1. Min = a[0]. If (L>min) answer else try to update min.
Using the same approach for 3 elements with O(N) space : Find I,j,k : Let M be middle element. Maintain an MAX array and MAX[k] = max of k to N-1. This Max can be constructed in O(N). also mainitain that min variable. min = a[0]. Run M=1 to N-2, If(min<a[M]<MAX[M+1]) ans ; else try to update min.
O(1) : there will be two stages : if min2 is not defined try finding min2 (j) else try finding k . if min2 is defined , it means min < min2 and index(min) < index(min2)
//while running, min2 will get undefined, in case the index you are working on is the minimum of a[0]-a[index]. as such from index+1, you need to find min2(j)
run ind from 1 to N-1;
min=a[0];
min2 = undef ;
{
if(min2) : //find k
if a[ind] > min2 : ans
else : if(a[ind] < min) min = a[ind],min2 = undef //from next index onwards you have to find min2
else : min2= a[ind].
Else // find j // This is same as finding i,j pair for 2 element question
if(a[ind] >min) : min2 = a[ind];
else min=a[ind];
}
Code:
input = a[N];
min=a[0];
min2=-100000;
for(M=1;M<=N-1;M++)
{
if(min2!==-100000) / /this means some i,j pair is already found , lets see if a[M] can be k
{
if(a[M]>min2) //a[i]<a[j]<a[k]
return (min,min2,a[M]);
else if(a[M] > min) //a[i]<a[k]<a[j]
min2=a[M];
else //we have found the smallest element yet. next time we have to first find j/min2 : a[k]<a[i]<a[j]
{
min=a[M];
min2=-10000;
}
}
else
{
if(a[M] > min)
min2 = a[M];
else
min=a[M];
}
}
I hope nobody thinks I suck at coding. Lets not worry about the inequalities either :)
This idea is really clever. Code it in python:
def ijk(A):
"""Time: O(n), space: O(1)"""
n = len(A)
i = -1
j = -1
for m in xrange(n):
if j == -1:
if m == 0 or A[m] <= A[m - 1]:
i = m
else:
j = m
else:
if A[m] > A[m - 1]:
if A[m] > A[j]:
return (i, j, m)
else:
i, j = m - 1, m
return (-1, -1, -1)
Here's why we need to keep at most 3 states, e.g. O(3):
min: this is the minimal number seen so far, which makes a great candidate to be the first number in the triplet. however, min might be positioned really close to the right boundary without 2 bigger numbers at its right side. that's why keeping "min" is not enough.
min2: this used to be the minimal number till we found min. the reason we still keep track of min2 is min2_next.
min2_next: a number bigger than min2, which is positioned right of it (not necessarily right next). so by keeping the pair [min2,min2_next] we might be able to complete a triplet with a number positioned right of "min".
There are few possible scenarios:
1. we find a number min2_next_next which is bigger than min2_next and hence complete the triplet min2 < min2_next < min2_next_next.
2. we find a number min_next which is bigger than min (see the "switch").
3. we find a a number min2_next_better, which is between min2 and min2_next. in this case, we prefer min2_next_better as the new min2_next, because it has a bigger chance of creating a triplet (any number bigger than min2_next is also bigger than min2_next_better).
The "switch":
"min" is a candidate to replace min2 once we find min_next, a number bigger than min and smaller than min2_next, because at that point any number min_next_next bigger than min2_next may also complete the triplet min < min_next < min_next_next. once we do the switch, we can un-set "min" and start looking for a new minimum.
Important note: "-1" is not a valid notation for "unset", because negative numbers are allowed in this question. use a separate flag which has the semantics of "unset".
Im sorry. I found the solution on SO but i wasnt very clear on how to do. Here is izomorphius' solution to the problem:
int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));
int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
if (greatest_value_so_far > a[i]) {
greater_on_rigth[i] = greatest_index;
} else {
greatest_value_so_far = a[i];
greatest_index = i;
}
}
// Do the same on the left with smaller values
for (int i =0;i<n;++i) {
if (greater_on_rigth[i] != -1 && smaller_on_left[i] != -1) {
cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
}
}
How about we just use a stack?
Let the the max number of elements we are after is N, in this case N = 3.
Traverse the array, A, and do:
if (not stack.empty) and (A[i] < stack.top):
stack.pop()
stack.push(A[i])
If (stack.empty) or (A[i] > stack top):
stack.push(A[i])
if stack.size == N then we are done!
Time : THETA(n)
Space : 3
O(n) time and O(1) space is the best solution. Just keep track of the current smallest number A and currently smallest length-2 increasing piece B[0:1]. Updating it takes O(1) time.
Example: 5, 6, 1, 2, 0, 1, 0, 9.
Step 1:
A = 5, B = NULL
Step 2:
A = 5, B = [5, 6]
Step 3:
A = 1, B = [5, 6]
Step 4:
A = 1, B = [1, 2]
Step 5:
A = 0, B = [1, 2]
Step 6:
A = 0, B = [0, 1]
Step 7:
A = 0, B = [0, 1]
Step 8:
Bingo, B + 9 is length-3 increasing piece
You can do this in two iterations.
1. Iterate through the array once and make a note of the numbers which is lesser than the number on the right.
2. Iterate through the array again and make a note of the numbers which is greater than the number to its left.
Now the number (or numbers) are the numbers which are common to both these things.
My solution is following:
In first iteration let's try to compare each two neighbors with each other.
for (i=0;i<n-1;i++)
{if A[i+1]>A[i]
tmp=i+1;
}
for (j=tmp;j<n;j++)
{
if A[j]>A[tmp]
return true
}
I mean it is not possible to find any combination of suitable numbers without two neighbors that meet the condition of i<j and A[i]<A[j].
so with my solution the answer of [5, 1, 6, 1, 7] is (1,2,4) indices. This algorithm is not supposed to give you all possible combinations. It is only supposed to extract possible one.
Here is my implementation in C
#include <stdio.h>
#include <stdlib.h>
#define size 10
void search_index(int a[],int );
int main()
{int x;
int a[size]={10,5,6,4,4,2,25,15,35};
search_index(a, size);
scanf("%d",&x);
return 0;
}
void search_index(int a[],int asize)
{
int i,j;
int tmp1=0,tmp2=0;
for (i=0;i<asize-1;i++)
{
if (a[i+1]>a[i])
{
tmp1=i+1;
break;
}
}
for (j=tmp1;j<asize;j++)
{
if (tmp1!=0 && a[j]>a[tmp1])
{
tmp2=j;
break;
}
}
printf("%d %d %d\n",tmp1-1,tmp1,tmp2);
printf("%d %d %d",a[tmp1-1],a[tmp1],a[tmp2]);
}
Sounds like dynamic programming.
Let P[i][j] be true if j th value is bigger than i th value in the input array.
Traverse the input array and complete the P[][] array.
Also, try to store the number of 'trues' per each row as you build the P[][] array.
Once you have 2 trues in a row, you have found a possible candidate, so stop building the P array and return the two numbers with "true" and the starting index of that row.
So here is how you can solve the problem. You need to iterate over the array twice. On the first iteration mark all the values that have an element greater then them on the right and on the second iteration mark all the element smaller then them on their left. Now your answer would be with an element that has both:
int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));
int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
if (greatest_value_so_far > a[i]) {
greater_on_rigth[i] = greatest_index;
} else {
greatest_value_so_far = a[i];
greatest_index = i;
}
}
// Do the same on the left with smaller values
for (int i =0;i<n;++i) {
if (greater_on_rigth[i] != -1 && smaller_on_left[i] != -1) {
cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
}
}
This solution iterates 3 times over the whole array and is therefor linear. I have not provided the whole solution so that you can train yourself on the left to see if you get my idea. I am sorry not to give just some tips but couldn't figure out how to give a tip without showing the actual solution.
Hope this solves your problem.
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{ int a[100],n,i,mx,md,mn,d;
bool fl=0;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
mx=n-1;
md=-1;
mn=-1;
for(i=n-2;i>=0;i--)
{ if(a[mx]-a[i]>0)
{ if(md==-1)
md=i;
else
{ if(a[md]-a[i]>0)
{ mn=i;
cout<<a[mn]<<" "<<mn+1<<"\n"<<a[md]<<" "<<md+1<<'\n'<<a[mx]<<" "<<mx+1<<'\n';
fl=1;
break;
}
else
{ if(d>a[mx]-a[i])
{ md=i;
d=a[mx]-a[md];
}
}
}
}
else
mx=i;
}
if(fl==0)
cout<<"NO Solution\n";
getch();
}
O(N) time and memory
// Assuming arr.length >= 3
Triplet findAnyIncTriplet(int arr[]) {
// O(n) memory
int mins[] = new int[arr.length];
int maxs[] = new int[arr.length];
// O(n) time
mins[0] = 0;
for (int i = 1; i < arr.length; ++i) {
if (arr[i] < arr[ mins[i - 1] ]) {
mins[i] = i;
} else {
mins[i] = mins[i - 1];
}
}
maxs[a.length - 1] = a.length - 1;
for (int i = a.length - 2; i >= 0; --i) {
if (arr[i] > arr[ maxs[i + 1] ]) {
maxs[i] = i;
} else {
maxs[i] = maxs[i + 1];
}
}
for (int i = 1; i < a.length - 1; ++i) {
if (arr[ mins[i - 1] ] < arr[i] && arr[i] < arr [maxs[i + 1] ]) {
return new Triplet(mins[i - 1], i, maxs[i + 1]);
}
}
return null;
}
python
l=[1,2,8,4,0,-1,4,78,23,25,9]
firstbest=secondbest=thirdbest=0
for i in range(0,len(l)):
if l[firstbest] < l[i]:
thirdbest = secondbest
secondbest = firstbest
firstbest = i
print( thirdbest, secondbest, firstbest)
package One;
public class ThreeIncreasing {
public static void main(String[] args) {
int arr[]={5,8,2,10};
int a=arr[0];
int b=-1,c=-1,d=-1;
printArray(arr);
printVars(a,b,c,d);
int i=0;
boolean ra=false,rb=false;
while(c==-1 && i<arr.length-1)
{
++i;
if(arr[i]<a && b==-1)
{
a=arr[i];
continue;
}
if(arr[i]>a && b==-1)
{
b=arr[i];
continue;
}
if(b!=-1 && arr[i]<b && a<arr[i])
{
b=arr[i];
if(ra==true)
{
rb=true;
ra=false;
}
continue;
}
if(b!=-1 && arr[i]>b)
{
c=arr[i];
if(ra==true && rb==false)
{
a=d;
}
continue;
}
if(b!=-1 && arr[i]<a)
{
ra=true;
rb=false;
d=a;
a=arr[i];
continue;
}
}
if(c!=-1)
{
printVars(a,b,c,d);
}
else
{
System.out.println("NO Sol");
printVars(a,b,c,d);
}
}
public static void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+" , ");
}
System.out.println();
}
public static void printVars(int a,int b,int c,int d)
{
System.out.println(a+" , "+b+" , "+c+" , "+d+" , ");
}
}
It's so simple
int i=0,j=-1,k=-1;
for(int s=1;s<n;s++){
if(a[s]>a[i]){
j=s;break;
}
}
if(j!=-1){
for(int s=j+1,s<n;s++){
if(a[s]>a[j]){
k=s;break;
}
}
if(k!=-1) System.out.println(i+" "+j+" "+k);
else System.out.println("no such indices are available in given array");
}else System.out.println("no such indices are available in given array");
the above code runs at most n times since "break" statements are used and second loop starts from where first loop ends. o(n) time complexity. please let me know if I am wrong.
//program to find i,j,k in array such that i<j<k and a[i]<a[j]<a[k]
#include<iostream>
#include<cstring>
#define SIZE 100
using namespace std;
int main()
{
int a[SIZE];
int len=0;
cin>>len;
for(int i=0;i<len;i++)
cin>>a[i];
int j=1;
while(j<len-1)
{
if(a[j]<a[j+1])
{
if(a[j]>a[j-1])
{
cout<<j-1<<","<<j<<","<<j+1<<"\n";
}
j++;
}
else
j=j+2;
}
return 0;
}
static void FindIncreasingTriple(int[] arr)
{
int a = -1, b = -1;
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > arr[i-1])
{
if (a < 0)
{
a = i - 1;
b = i;
}
else
{
if (arr[i] > arr[b])
{
Console.WriteLine("Indices: {0}, {1}, {2}, Values: {3}, {4}, {5}", a, b, i, arr[a], arr[b], arr[i]);
}
else
{
a = i - 1;
b = i;
}
}
}
else
{
if (arr[i] < arr[b] && arr[i] > arr[a])
{
b = i;
}
}
}
Console.WriteLine("Not found!");
}
Posting implementation for feedback.
void foo(int[] a){
int length = a.length;
if(length < 3){
System.out.printf("Error: Array needs to have at least 3 entries");
reutrn;
}
int k = length-1;
int j = k-1;
int i = j-1;
int temp = i-1;
while(temp>0){
if(a[i]>=a[temp])
i = temp;
temp--;
}
temp = j-1;
while(temp>i){
if(a[temp]>=a[i])
j = temp;
temp--;
}
temp = k-1;
while(temp>j){
if(a[temp]>=a[j])
k = temp;
temp--;
}
if(a[i]<a[j] && a[j]<a[k])
System.out.printf("%d, %d, %d", i, j, k);
else
System.out.printf("No entries in array where i<j<k and a[i]<a[j]<a[k]");
}
int a[] = {4,3,2,1,0,4,7,5};
int j = 0, least = Integer.MAX_VALUE;
int indices[] = {-1,-1,-1};
for(int i=0; i < a.length -1; i++)
{
j = i+1;
if(a[i] > least) {
indices[2] = i;
break;
}
if(a[i] < a[j] && a[j] < least) {
least = a[j];
indices[0] = i;
indices[1] = j;
}
}
for(int i=0; i < 3; i++)
{
System.out.println(a[indices[i]] + " ");
}
Just add all bound checks.
My algorithm:
* an array imin[i] is the index of min element of subarray 0..i
* run from right to left, maintain imax is the index of the max element in subarray i..n-1
* a triplet: imin[i] < i < imax
Code in Python
def find_ijk(a):
if len(a) < 3:
return None
imin = [0]*len(a)
for i in xrange(1, len(a)):
imin[i] = imin[i - 1]
if a[i] <= a[imin[i]]:
imin[i] = i
imax = len(a) - 1
for i in xrange(len(a) - 2, 0, -1):
if a[i] < a[imax] and i > imin[i]:
return imin[i], i, imax
if a[i] > a[imax]:
imax = i
return None
#include <stdio.h>
#include <stdlib.h>
void search_index(int *);
int main()
{
int a[]={10,5,6,13,8,2,25,15,35};
search_index(a);
return 0;
}
void search_index(int * a)
{
int i;
int first,second,third;
first=second=third=0;
for(i=1;i<9;i++)
{
if(a[i]>a[first] && first<i)
{
first=i;
}
else
{
if(a[first]>a[second] && second<first)
{
second=i;
}
else
{
if(a[second]>a[third] && third<second)
third=i;
}
}
}
printf("%d %d %d\n",third,second,first);
printf("%d %d %d",a[third],a[second],a[first]);
}
I guess it is not correct it does not work for the following array
a[]={8,6,4,10,9,7,5};
Any thoughts on this implementation? It seems a lot simpler than what is posted here. Am I missing something?
int arr[]={5,8,7,10,3,12,2,32,33};
int i=1;
if ((arr[i-1]<arr[i]) && (arr[i]<arr[i+i]))
{
System.out.println(i-1+" "+i+" "+(i+1));
System.out.println(arr[i-1]+" "+arr[i]+" "+arr[i+1]);
}
else
for (i=1; i<arr.length-1;i++)
{
if ((arr[i-1]<arr[i]) && (arr[i]<arr[i+1]))
{
System.out.println(i-1+" "+i+" "+i+1);
System.out.println(arr[i-1]+" "+arr[i]+" "+arr[i+1]);
}
}
My Solution is O(n) for worst case (when traversing the entire array is required) & achieves the desired result, however the medium element finding logic is flexible (for change):
#include <stdio.h>
#define SIZE 7
int main()
{
int array[SIZE];
int max_index = 0;
int min_index = 0;
int med_index = 0;
int counter = 0;
for (counter=0; counter<SIZE; counter++)
{
printf ("\nEnter Array Element: ");
scanf ("%d", &array[counter]);
if (array[counter]>array[max_index])
{
/* Update Max Index */
max_index = counter;
}
if (array[counter]<array[min_index])
{
/* Update Min Index */
min_index = counter;
}
if (max_index-min_index>=2)
{
break;
}
}
if (max_index-min_index>=2)
{
med_index = max_index-1; /* or min_index+1 */
printf ("\nMin = %d, Med = %d, Max = %d\n", array[min_index], array[med_index], array[max_index]);
}
else
{
printf ("\nNo 3 Elements in this Array satisfy the desired property\n");
}
return 0;
}
this should work:
static Tuple<int, int, int> FindIjk(int[] numbers)
{
int i = 0, j = -1, k = -1, ip=-1;
for (var e = 1; e < numbers.Length; e++)
{
// if we have potential smaller i, and current position value smaller than current j position value
// move both i and j forward
if (ip != -1 && numbers[e] < numbers[j])
{
i = ip;
j = e;
}
// try to find as i and j couple as small as possible
if (numbers[e] > numbers[i])
{
// if we can find K to make to triple, then return the finding.
if (j != -1 && numbers[e] > numbers[j])
{
k = e;
break;
}
else
{
// get a smaller j
j = e;
}
}
else
{
// j never set, then move i to smallest place so far
// otherwise consider it as potential next i position
if (j == -1)
{
i = e;
}
else
{
ip = e;
}
}
}
return new Tuple<int, int, int>(i, j, k);
}
I has solved this as a geometry problem. The idea is to find three non-increasing sequences - to find to sequences and stop after third is being found. So I need only 2 array of size for 2 sequences < N*sizeof(element).
For example: 3 2 1 3 2 1 3 2 1. There is following sequences: 3 2 1 1 1, 3 2 2, 3. The last elements of each sequence form a solution.
/*
TASK:
Given a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
*/
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char **argv) {
if (argc <= 1) {
cout << "Wrong count of arguments" << endl;
return -1;
}
vector<int> arrays[2];
for (int arrayId = 0; arrayId < 2; arrayId++) {
int numbers = argc - 1;
arrays[arrayId].reserve(numbers);
}
bool found = false;
int value;
for (int i = 1; i < argc; i++) {
value = atoi(argv[i]);
cout << value << endl;
for (int arrayId = 0; arrayId < 2; arrayId++) {
if (arrays[arrayId].size() > 0) {
if (arrays[arrayId].back() >= value) {
arrays[arrayId].push_back(value);
break;
}
} else {
arrays[arrayId].push_back(value);
break;
}
if (arrayId == 1) {
// Has not pushed value into first and second array - there is a result
found = true;
}
}
if (found) {
break;
}
}
if (found) {
cout << "Result: " << arrays[0].back() << ", " << arrays[1].back() << ", " << value << endl;
} else {
cout << "Result has not been found" << endl;
}
return 0;
}
Correct program:
/*
TASK:
Given a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
*/
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char **argv) {
if (argc <= 1) {
cout << "Wrong count of arguments" << endl;
return -1;
}
vector<int> arrays[2];
for (int arrayId = 0; arrayId < 2; arrayId++) {
int numbers = argc - 1;
arrays[arrayId].reserve(numbers);
}
bool found = false;
int value;
int index;
int indices[2];
for (int i = 1; i < argc; i++) {
index = i - 1;
value = atoi(argv[i]);
cout << value << endl;
for (int arrayId = 0; arrayId < 2; arrayId++) {
if (arrays[arrayId].size() > 0) {
if (arrays[arrayId].back() > value) {
arrays[arrayId].push_back(value);
indices[arrayId] = index;
break;
} else if (arrays[arrayId].back() == value) {
break;
}
} else {
arrays[arrayId].push_back(value);
indices[arrayId] = index;
break;
}
if (arrayId == 1) {
// Has not pushed value into first and second array - there is a result
found = true;
}
}
if (found) {
break;
}
}
if (found) {
cout << "Indices: " << indices[0] << ", " << indices[1] << ", " << index << endl;
cout << "Values: " << arrays[0].back() << ", " << arrays[1].back() << ", " << value << endl;
} else {
cout << "Result has not been found" << endl;
}
return 0;
}
Python version. I use brute force way it is O(n^3) but it is sure the answer is right, getijk.
For getijk2. I use a algorithm
# -*- coding: utf-8 -*-
"""
Created on Tue Nov 27 14:26:17 2012
@author: qzhang
Given a array of integers , find 3 indexes i,j,k such that,
i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
"""
#brute force answer
def getijk(array):
length = len(array)
for i in range(0,length-2):
for j in range(i+1,length-1):
for k in range(j+1,length):
if (array[i]<array[j] and array[j]<array[k]):
#print "getijk i,j,k is:",i,j,k
print "while the value is: ",array[i],array[j],array[k]
#alogirthm answer
def getijk2(array):
length = len(array)
result = []
for item in array:
result.append([item])
for result_item in result:
if(len(result_item) == 3):
print result_item
result.remove(result_item)
elif (item > result_item[-1]):
a = result_item[:]
a.append(item)
result.append(a)
#print result_item
#print result
if __name__ == "__main__":
#array = [2,1,4,5,7]
#getijk(array)
#getijk2(array)
array = [4,7,5,1,3,8,9,6,2]
getijk(array)
print "another function:"
getijk2(array)
Let me know if anyone sees any issue with this one:
Algo:
Iterate over the array three times to determine index for: i, j and k.
Complexity:
Time: O(3n) ~= O(n)
Space = O(1)
print3Largest(int a[])
{
int i = 0, j =0, k = 0;
// assume a[0] is largest so far
i = j = k = 0;
// iterate to determine the indices for
// three largest elements in an array.
for (int index = 0; index < MAX; ++index) {
if (a[index] > a[i]) {
i = index;
}
}
for (int index = 0; index < MAX; ++index) {
if (a[index] > a[j] && a[index] < a[i]) {
j = index;
}
}
for (int index = 0; index < MAX; ++index) {
if (a[index] > a[k] && a[index] < a[j]) {
k = index;
}
}
cout << "First: " << a[i] << " ,Second: " << a[j] << " ,Third: " <<
a[k] << "\n";
}
I tried it with repeated array elements, it seems to work fine.
The code:
void FindThreeIncreasing(vector<int> my_array)
{
int N=my_array.size();
vector<int> X(N+1);
int L=0;
for(int i=0;i<N;i++)
{
int j;
if(L==0)j=0;
else
{
for(j=1;j<=L;j++)
{
if(my_array[X[j]]>my_array[i])
{
break;
}
}
j--;
}
if(j==L || my_array[X[j+1]]>my_array[i])
{
X[j+1]=i;
L=max(L,j+1);
if(L==3)
{
break;
}
}
}
for(int i=1;i<=3;i++)
{
cout<<my_array[X[i]]<<" ";
}
cout<<endl;
}
This question is answered in the Amazon questions
- coder October 27, 2012a[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)