Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
Time Complexity: O(n) where n is the size of the input array. Space: O(n)
public class FindNumSvc {
public static int findNum(int[] arr){
if(arr == null || arr.length < 2){
throw new IllegalArgumentException();
}
int[][] minMax = new int[2][arr.length];
int max = arr[0];
for(int i = 1; i < arr.length; i++){
minMax[0][i] = max;
max = Math.max(arr[i], max);
}
int min = arr[arr.length - 1];
for(int i = arr.length - 2; i >= 0; i--){
minMax[1][i] = min;
min = Math.min(arr[i], min);
}
for(int i = 1; i < arr.length - 1; i ++){
if(minMax[0][i] < arr[i] && minMax[1][i] > arr[i]){
return i;
}
}
if(minMax[0][arr.length - 1] < arr[arr.length - 1]){
return arr.length - 1;
}
return minMax[1][0] > arr[0]? 0:-1;
}
public static void main(String[] args) {
int[] arr = {-1,4,-3,6,-2,5,8,9};
System.out.println(findNum(arr));
}
}
As per my understanding,
We have to find a number in array which is greater than all numbers lies on left side and lesser than all numbers lies on right side in the array.
e.g.
arr[] = 5,4,3,7,4,1,2,8,10
Output - 8 (all elements at left side are lesser than 8 and all elements at right side are greater than 8).
My solution-
I will create 2 arrays-
1- First array will hold max value in array before that index.(Traverse from left side to get the values), for above array , the array will be -
lmax = 5,5,5,5,7,7,7,7,8 (Take first element as it is in origin array)
2- Second array will hold min value in array after the index.(Traverse from right side to get the values), For above array, the second array will be -
rmin = 1,1,1,1,1,2,8,10,10 (Take last element as it is in origin array)
Now traverse the origin array and check condition-
if(arr[i] >= lmax[i] && arr[i] <= rmin[i]){
print(arr[i])
}
Space complexity O(2n) - Need to create min max array
Time complexity - O(n)
My version of required function is:
/**
*
* @param a
* @return position of the first element with property that all elements in previous positions
* are less than this element - from the left side, and all elements in positions
* that greater or equal goes after the element - from the right side
*/
static int findMiddleElementPosition(int[] a) {
if (a == null) {
return -1;
}
int[] max = Arrays.copyOf(a, a.length);
for (int i = 1; i < a.length; i++) {
if (max[i] < max[i - 1]) {
max[i] = max[i - 1];
}
}
for (int j = a.length - 1; j >= 0; j--) {
if (a[j] < max[j]) {
// additional check if it is the latest element in the array
return j + (j != a.length - 1 ? 1 : 0);
}
}
return 0;
}
Samples in format array:position
{null, -1},
{new int[]{1}, 0},
{new int[]{1, 2}, 0},
{new int[]{1, 2, 3}, 0},
{new int[]{2, 1, 3}, 2},
{new int[]{-1, 2, -3, 4, 5, 6}, 3},
{new int[]{-1, 4, -3, 6, -2, 5, 8, 9}, 6},
{new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 0},
{new int[]{-1, -2, -3, -4, -5, -6, -7, -8, -9}, 8},
{new int[]{-1, -1, -1, -1, 3, 3, 3, 3}, 0},
{new int[]{-1, 2, -1, 3, -1, 4, 4, 4, 4}, 5}
Use a modified quick sort partition function:
function partition (index, A) {
var i = 0
var j = A.length - 1
var partition = A[index]
while (i <= j) {
while (A[i] < partition) {
i++
}
while (A[j] > partition) {
--j
}
if (i <= j) {
if (A[i] !== A[j]) {
return false
}
// Don't need all this...
//
// var tmp = A[j]
// A[j] = A[i]
// A[i] = tmp
// i++
// j--
}
}
return true
}
module.exports = function (sequence) {
for (var i = 0; i < sequence.length; ++i) {
if (partition(i, sequence)) {
return sequence[i]
}
}
return null
}
var sequence = [4, 3, 2, 7, 12, 11, 15, 22, 18, 9, 13]
var solution = module.exports(sequence)
console.log(solution)
C++ solution. Tricky but fun problem!
#include <array>
#include <limits>
#include <iostream>
int main(void)
{
std::array<int, 10> values {0, 1, 5, 3, 2, 8, 9, 9, 0, 11};
int maxLeft = std::numeric_limits<int>::min();
int maxIndex = 0;
int minRight = std::numeric_limits<int>::max();
int minIndex = 0;
int leftIndex = 0;
int rightIndex = values.size()-1;
for(;;)
{
auto leftValue = values[leftIndex];
auto rightValue = values[rightIndex];
if(leftValue > maxLeft)
{
maxLeft = leftValue;
maxIndex = leftIndex;
}
if(rightValue < minRight)
{
minRight = rightValue;
minIndex = rightIndex;
}
leftIndex++;
rightIndex--;
if(leftIndex >= rightIndex)
break;
}
if(maxLeft < minRight)
{
std::cout << "#" << minRight << " at index " << minIndex << " is a match!" << std::endl;
}
else
{
std::cout << "no match!" << std::endl;
}
return 0;
}
public static int? FindFirstPartition(int[] arr)
{
if (arr == null)
return null;
if (arr.Length == 0)
return arr[0]; // the single ellement is in fact a "partition"
var minValues = new Stack<int>();
for (var i = arr.Length - 1; i > 0; i--)
{
if (minValues.Count == 0)
minValues.Push(arr[i]);
else
{
var min = minValues.Peek();
if (arr[i] <= min)
minValues.Push(arr[i]);
}
}
var leftMax = int.MinValue;
foreach (var current in arr)
{
if (current >= leftMax && (minValues.Count == 0 || current <= minValues.Peek()))
return current; // found it!
// Otherwise, advance!
if (leftMax <= current)
leftMax = current;
if (minValues.Peek() == current)
minValues.Pop();
}
return null;
}
public static int TheNumberXBalance(ArrayList TheListToCheck )
{
if (TheListToCheck==null && TheListToCheck.isEmpty())
return -1;
for(int k=0;k<TheListToCheck.size();k++)
{
if(partBalance(TheListToCheck,k,0,TheListToCheck.size()-1))
System.out.println("Value:"+TheListToCheck.get(k)+" at index["+k+"]");
}
return 1;
}
public static boolean partBalance(ArrayList TheListToCheck,int index_pivot,int start,int end)
{
int pivot=(int)TheListToCheck.get(index_pivot);
int indexinitLeft= start;
int indexendLeft=index_pivot-1;
int indexinitRight= pivot+1;
int indexendRight=end;
int leftval=(int)TheListToCheck.get(indexinitLeft);
int rightval=(int)TheListToCheck.get(indexendRight);
while(index_pivot>indexinitLeft)
{
leftval=(int)TheListToCheck.get(indexinitLeft);
//System.out.println("Compare:"+pivot+" with:"+leftval);
if(pivot<=leftval)
{
return false;
}
else {
indexinitLeft++;
}
}
while(index_pivot<indexendRight)
{
rightval=(int)TheListToCheck.get(indexendRight);
//System.out.println("Compare:"+pivot+" with r"+rightval);
if(pivot>=rightval)
{
return false;
}else
{
indexendRight--;
}
}
return true;
}
}
package careerCup;
import java.util.Arrays;
public class SortCollectionInHalf
{
int sortData(int [ ] inp, int elm)
{
Arrays.sort( inp, 0, inp.length / 2 );
Arrays.sort( inp, inp.length / 2, inp.length );
System.out.println( Arrays.toString( inp ) );
int mid = 0;
int left = 0;
int right = inp.length - 1;
while ( right >= left )
{
mid = ( left + right ) / 2;
if ( inp[ mid ] == elm )
{
System.out.println( "Element " + +inp[ mid ]
+ " found at index: " + mid );
return mid;
}
else if ( inp[ mid ] > elm )
{
right = mid - 1;
}
else if ( inp[ mid ] < elm )
{
left = mid + 1;
}
else
{
return -1;
}
}
return mid;
}
public static void main(String [ ] args)
{
int [ ] inp = { -2, 4, -3, 6, -1, 5, 8, 9 };
SortCollectionInHalf so = new SortCollectionInHalf( );
so.sortData( inp, -2 );
}
}
Time Complexity - O(n)
import java.util.Scanner;
public class two {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int[] arr = new int[size];
for(int i =0;i< size;i++){
arr[i] = scan.nextInt();
}
scan.close();
findIndex(arr, size);
}
private static void findIndex(int[] arr, int size){
Integer pivot=null;
int pivotIndex = 0;
int max=Integer.MIN_VALUE;
for(int i=0;i< size;i++){
if(pivot==null)
{
if(max<arr[i])
{
max=arr[i];
pivotIndex=i;
pivot=arr[i];
}
}
else{
if(pivot.intValue()>arr[i])
{
pivot=null;
}
else{
max=arr[i];
}
}
}
System.out.println(pivot==null?"No Element available" :pivotIndex);
}
}
int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
Time Complexity: O(n)
Space Complexity: at max O(n) - case if the input is a sorted array.
This problem can have more than one solution.
int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
Time Complexity: O(n)
Space Complexity: at max O(n) - case if the input is a sorted array.
This problem can have more than one solution.
int currentMax = 0;
HashSet<int> possibleSols = new HashSet<int>();
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
Notes: This problem may contain more than one solution.
Time complexity - O(n)
Space Complexity - O(n) - if the input is a sorted array, then every elements in the array could be a possible solution.
int currentMax = int.MinValue;
hashset<int> possibleSolutions = new Hashset<int>();
foreach(var num in input)
{
if(num > currentMax)
{
possibleSolutions.Add(num);
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}
Notes: This problem may contain more than one solution.
Time complexity - O(n)
Space Complexity - O(n) - if the input is a sorted array, then every elements in the array could be a possible solution.
int currentMax = int.MinValue;
hashset<int> possibleSolutions = new Hashset<int>();
foreach(var num in input)
{
if(num > currentMax)
{
possibleSolutions.Add(num);
currentMax = num;
}
else if(num < currentMax)
{
possibleSolutions.Remove(I=>I > num);
}
}
foreach (var num in input)
{
if (num > currentMax)
{
possibleSols.Add(num);
currentMax = num;
}
else if (num < currentMax)
{
possibleSols.RemoveWhere(i => i > num);
}
}
if(possibleSols.Count > 0)
{
Console.WriteLine($"Possible solutions: {string.Join(",",possibleSols)}");
}
else
{
Console.WriteLine("No such element exists");
}
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int A[] = {5, 4, 6, 10, 7, 8, 9, 11, 23, 40};
int size = sizeof(A) / sizeof(A[0]);
int B[100];
for (int i = 0; i < size; i++) {
B[i] = A[i];
}
sort(A, A + size);
for (int i = 0; i < size; i++) {
if (A[i] == B[i])
cout << i << " " << A[i] << endl;
}
return -1;
}
solution in C#:
int[] myArr = new int[] { -1, 2, -1, 3, -1, 4, 7, 8, 6 };
int[] myArr1 = new int[myArr.Length];
int iVal = 0;
int iVal1 = 0;
int iMA;
for (iMA = 1; iMA < myArr.Length - 1; iMA++)
{
if (myArr[iMA] > myArr[iMA - 1] && myArr[iMA] < myArr[iMA + 1])
{
iVal = 0;
iVal1 = 0;
for (int iMA1 = iMA; iMA1 < myArr.Length - 1; iMA1++)
{
if (myArr[iMA] < myArr[iMA1 + 1])
{
iVal++;
}
}
for (int iMA2 = iMA; iMA2 >= 0; iMA2--)
{
if (myArr[iMA] > myArr[iMA2])
{
iVal1++;
}
}
}
if ((iVal + iVal1) == (myArr.Length - 1))
{
break;
}
}
if ((iVal + iVal1) != (myArr.Length - 1))
{
iVal = 0;
iVal1 = 0;
}
if (iVal1 == 0 && iVal == 0)
{
Console.WriteLine("No Such element");
}
else
{
Console.WriteLine("Element at position " + iMA + " has all digits less than it to the left anf all digits greater than it to the right");
}
Console.Read();
public static void main(String[] args) {
int[] a = {1,2,5,9,6,8};
boolean blnFlagLess = true;
boolean blnFlagGreat = true;
for(int i=1; i<a.length; i++) {
for(int j=0; j<i; j++) {
if(a[i]<a[j]) {
blnFlagLess = false;
}
}
for(int k=i+1; k<a.length; k++) {
if(a[i]>a[k]) {
blnFlagGreat = false;
}
}
if(blnFlagLess && blnFlagGreat) {
System.out.println(a[i]);
blnFlagLess = true;
blnFlagGreat = true;
}
}
}
Here output will be 2 & 5.
public class SortCollectionHalf {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a [] = {-2,4,-3,6,-1,5,8,9 };
int x= -2;
int i = 0;
int j = a.length - 1;
while (i < j) {
if (a[i] < x) {
i++;
}
if (a[j] > x) {
j--;
}
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
for (int k = 0; k < a.length; k++) {
// System.out.println(" array after sorted");
System.out.print(" " + a[k]);
}
}
public int SortArray(int [] arr){
if(arr == null || arr.length == 0){
return -1;
}
int [] left = new int [arr.length];
int [] right = new int [arr.length];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i = 0 ; i < arr.length ; i++){
left[i] = Math.max(max , arr[i]);
max = Math.max(arr[i] , max);
}
for(int i = arr.length -1 ; i >=0 ; i--){
right[i] = Math.min(min , arr[i]);
min = Math.min(arr[i] , min);
}
int target = 0;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i] >= left[i] && arr[i] <= right[i]){
return i;
}
}
return -1;
}
Time Complexity : O(n)
- SANTHOSH0605 February 22, 2017Algorithm:
Take arr as input array
Initialise 2 pointers
value_under_test to the index position "0"
Ptr1 to the index position "value_under_test + 1"
while (Ptr1 < max_array_size)
{
If (arr[Ptr1] > arr[value_under_test])
{
Keep advancing Ptr1 to next position
}
Else
{
advance value_under_test to position "Ptr1 + 1"
advance Ptr1 to position "value_under_test + 1"
}
}
//Once this while loop is completed, we know for sure that all values lying after position "value_under_test" is greater
//now all we have to do is to ensure that anything lying behind position "value_under_test" is smaller
loop from "value_under_test - 1" to 0
{
if any item is greater than value in position "value_under_test"
{
Inform user that no such number exist in this array
}
}
//if this loop runs fully, it means that the value at position "value_under_test" is the number that we are looking for!!!
So, return arr[value_under_test]