Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
breaking logic is not correct. How about this
private static int findMissing(int[]arr, int s, int e)
{
int m = (s+e)/2;
int expVal = arr[s]+(m-s);
if (arr[m] > expVal )
return expVal ;
if(expVal<arr[m])
return findMissing(arr,0,m);
else
return findMissing(arr, m, e);
}
public static int getnumber(int arr[]){
int number=0;
int i=0;
while(i<arr.length-1){
if(arr[i+1]!=arr[i]+1){
number=arr[i]+1;
break;
}else{
i++;
}
}
return number;
}
i guess it will work for all type of array and in worse case its have complexity O(n)
public static int findMissing(int[] array,int start, int end)
{
if(end-start<2)
{
if(array[start]+1==array[end])
return -1;
else
return array[start]+1;
}
int min = array[start];
int max = array[end];
int midExpect = (max-min)/2;
int mid = (start+end)/2;
if(array[mid]>midExpect+min)
{
return findMissing(array,start,mid);
}
else
return findMissing(array,mid,end);
}
How to handle cases where there are duplicates? Wouldn't we end up doing a linear search in this case? Eg : 1,2,4,4,5,6,7,8,9
@Andi - Base conditions has to be changed. It will fail for input 1,2 where it should return something false or -1. but it would return 2
#include<iostream>
using namespace std;
#define SIZE 9
int a[SIZE];
int find_number(int s, int e)
{
if(e-s == 1)
return (a[s]+1);
else
{
int mid = (e-s)/2;
int expected = a[s]+mid;
cout<<"\nExpected : "<<expected;
mid = s + ((e-s)/2);
if(a[mid]<=expected)
return find_number(mid, e);
else
return find_number(s, mid);
}
}
int main()
{
cout<<"Enter the array : ";
for(int i=0; i<SIZE; i++)
{
cout<<"\nNumber "<<i+1<<" ";
cin>>a[i];
}
cout<<"Missing no = "<<find_number(0, SIZE);
return 0;
}
int missing(int arr[], int n)
{
int start=0, end=n-1;
int mid;
if(arr[end]==arr[start]+n-1)
{
printf("No number is missing\n");
return -1;
}
else
{
while(start<end)
{
mid=(start+end)/2;
if(mid==start)
{
return mid;
}
if(arr[mid]==arr[start]+mid-start)
{
start=mid;
}
else if(arr[mid]>arr[start]+mid-start)
{
end=mid;
}
}
}
}
int MissingNumber(int arr[], int low, int high)
{
int mid;
while(low <= high)
{
mid = (low + high)/2;
if(arr[mid] >(arr[low] + mid - low) )
{
if((mid - low) == 1)
return arr[mid] +1;
else
high = mid;
}
else
low = mid;
}
return -1;
}
Pls comment on solution
If any number is missing in range low to mid ..
then value at arr[mid] is more than arr[mid] + mid - low ..
Ex 1,2,3,4,6,7,8,9,10,11,14 ........first missing
low = 0 , high = 10, mid = 5
arr[mid] = 7 and (arr[low] = )1 + 5 - 0 = 6 .. so first missing number is between index [0 5]
in python
#http://www.careercup.com/question?id=14990308
x = [6,7,8,9,15,16,17,18,22,34]
x = [4,5,6,7,8,9,10,11,12,13,14,18,19]
x = [0,9,10,11,12,13,14,18,19]
#x = [1]
def has_missing(part_list):
#print part_list
if len(part_list) != (part_list[-1] - part_list[0]+1):
return True
return False
def find_missing(whole_list):
next_number = whole_list[0] + 1
if len(whole_list) == 1:
return next_number
left = whole_list[0:len(whole_list)/2]
right = whole_list[len(whole_list)/2:]
if has_missing(left): #missing
find_missing(left)
else:
next_number = left[-1] + 1
if next_number != right[0]: #find it
return next_number
else:
find_missing(right)
return next_number
if __name__ == '__main__':
print find_missing(x)
Assumptions : The array elements are increasing (not non decreasing).
Complexity: O(logn)
public static int findMissingElementIndex(int a[]) {
int low = 0, high = a.length - 1, mid;
int x = a[low] - 0;
while(low <= high) {
mid = low + (high - low)/2;
if(a[mid]-mid == x)
low = mid + 1;
else if(a[mid]-mid > x)
high = mid - 1;
}
return -(low + 1);
}
}
/*
* Created on: Dec 10, 2012
* Author: Kevin Li
*/
#include <cstdio>
#include <iostream>
using namespace std;
void findMissingNumber(int array[], int n)
{
int length = n;
int start = 0, stop = length - 1, mid = 0;
while (true)
{
mid = (start + stop) / 2;
if ((start == mid) || (start >= stop))
{
if (array[stop] - array[start] == stop - start)
{
cout << "no missing number";
return;
}
else
{
cout << "The missing number is " << array[start] + 1;
return;
}
}
if (array[mid] - array[start] == mid - start)
{
start = mid;
}
else
{
stop = mid;
}
}
}
O(logn) solution. Returns -1 in case original vector is empty or if no number is missing
int find_missing(vector<int> &vec, int from, int size)
{
if (size == 0)
return -1;
if (size == 1)
return (vec[from] == from + vec[0] ? -1 : from + vec[0]);
int half1_size = size / 2;
int half1_start = from;
int half1_end = from + half1_size - 1;
int half2_size = size - half1_size;
int half2_start = half1_end + 1;
if (vec[half1_start] == half1_start + vec[0]
&&
vec[half1_end] == half1_end + vec[0])
return find_missing(vec, half2_start, half2_size);
else
return find_missing(vec, half1_start, half1_size);
}
#define MAX 10
int main()
{
int a[MAX]={4,5,6,7,9,11,14,18,19};
int num=1, missed=0,duplicated=0;
while(num<=MAX)
{
if(num!=a[num-1])
{
missed=num;
duplicated=a[num-1];
}
num++;
}
if(missed && duplicated)
printf("missed number id %d, duplicated number is %d",missed,duplicated)
}
please share your ideas..its for both missed and duplicated in the array...
public class FindMissing {
/**
* @param args
*/
static int arr[] = {4,5,6,7,8,8,8,8,9,10,11,12,13,14,18,19};
public static void main(String[] args) {
System.out.print(find(0, arr));
}
private static int find(int counter , int[] array)
{
int diff = array[counter+1] - array[counter];
if(diff >1)
return array[counter]+1;
else
return find(counter+1 , array);
}
}
public class FindMissing {
/**
* @param args
*/
static int arr[] = {4,5,6,7,8,8,8,8,9,10,11,12,13,14,18,19};
public static void main(String[] args) {
System.out.print(find(0, arr));
}
private static int find(int counter , int[] array)
{
int diff = array[counter+1] - array[counter];
if(diff >1)
return array[counter]+1;
else
return find(counter+1 , array);
}
}
public class FindMissing {
/**
* @param args
*/
static int arr[] = {4,5,6,7,8,8,8,8,9,10,11,12,13,14,18,19};
public static void main(String[] args) {
System.out.print(find(0, arr));
}
private static int find(int counter , int[] array)
{
int diff = array[counter+1] - array[counter];
if(diff >1)
return array[counter]+1;
else
return find(counter+1 , array);
}
}
public static int findMissingElement(int a[]) {
int left;
int right;
for (int i = 0; i < a.length-1; i++) {
left = a[i];
right = a[i+1];
if (right - left != 1) {
return left+1;
}
}
return -1;
}
Please comment..
I have not clearly understand the differences between O(1), O(log n), O(n) etc...
#include <assert.h>
#include <iostream>
bool GetMissingNumber(int arr[], int N, int& val)
{
if(N <= 1)
return false;
int iLow = 0;
int iHigh = N-1;
while(iHigh-iLow > 1)
{
int iCur = (iHigh+iLow)/2;
if (arr[iCur] > arr[iLow] + (iCur-iLow))
iHigh = iCur;
else
iLow = iCur;
}
if (arr[iHigh]-arr[iLow] > 1)
{
val = arr[iLow]+1;
return true;
}
return false;
}
void Test(int arr[], int N, bool bRest, int val)
{
int valR;
bool bGot = GetMissingNumber(arr, N, valR);
bool bOK = true;
if (bRest)
bOK =(bRest==bGot)&&(valR==val);
else
bOK =(bRest==bGot);
std::cout << bOK << std::endl;
}
int main()
{
int arr1[9] = {4,5,6,7,9,11,14,18,19};
int arr2[10] = {4,5,6,7,8,9,11,14,18,19};
int arr3[6] = {4,5,6,7,8,9};
int arr4[11] = {4,5,6,7,8,9,10,11,14,15,16};
Test(arr1, 9, true, 8);
Test(arr2, 10, true, 10);
Test(arr3, 6, false, 100);
Test(arr4, 11, true, 12);
}
public static int findMissingNumber(int[] array) {
int low = 0;
int high = array.length - 1;
int mid = 0;
while (high - low != 1) {
mid = (low + high) / 2;
if (mid - low == array[mid] - array[low])
low = mid;
else
high = mid;
}
return array[low] + 1;
}
Please check the code above and let me know if it fails for any input. This finds the first missing number in O(log n).
Hi,
Can someone comment on this answer plz.. I have written this in JAVA
public class FirstMissingNumber {
static int firstMissingNumber(int[] array, int start, int end) {
if (start == end)
return -1;
if (end - start < 2) {
if (array[start] + 1 != array[end]) {
return array[start] + 1;
} else {
return -1;
}
} else {
int middle = (start + end) / 2;
if (array[middle - 1] + 1 != array[middle]) {
return array[middle - 1] + 1;
}
int retVal = firstMissingNumber(array, start, middle - 1);
if (retVal != -1) {
return retVal;
}
retVal = firstMissingNumber(array, middle, end);
return retVal;
}
}
public static void main(String[] args) {
int array[] = { 1, 2, 8, 9, 10, 20,30 };
System.out.println(firstMissingNumber(array, 0, 6));
}
}
Clean Code
public int sortedMiss(int arr[] , int low , int high , int k){
// error condis
if(arr==null || arr.length==0){
return -1 ;
}
// recursion base case
if(low==high){
if(arr[low]-low>k){
return arr[low-1]+1 ;
}
else
return arr[low]+1 ;
}
int mid = (low+high)/2;
if(arr[mid]-mid==k){
// recur right
return sortedMiss(arr,mid+1,high,k);
}
else if (arr[mid]-mid>k){
// recur left
return sortedMiss(arr,low,mid,k);
}
return -1 ;
}
Logic: It starts dividing array into half, checking ideal size of elements needs to be present in the sub-array and difference between the values at the bounds of the array (a[high] and [low]). If the ideal size of elements needs to be present is greater than difference then there's at least one element missing, since the elements are in increasing order and no dups are present (if the dups are present then linear search is inevitable)
Complexity: O(log n)
public static int missingNumber (int[] a) {
int low = 0, high = a.length - 1, mid;
int numberOfValues = high - low + 1;
while(low <= high && numberOfValues > 2) {
mid = (low+high)/2;
if(a[mid]-a[low] > (mid-low)) {
// first missing number is in this section
high = mid;
numberOfValues = mid-low;
} else if (a[high]-a[mid] > (high-mid)) {
low = mid;
numberOfValues = high-mid;
} else {
return -1;
}
}
System.out.println("low: " + low + " high: " + high);
for(int i = low; i < high; i++) {
if((i+1<a.length) && (a[i+1] - a[i]) > 1) {
return a[i] + 1;
}
}
return -1;
}
static int findMissingNumber (int [] array, int startPoint, int endPoint) {
int startValue = array[startPoint];
int endValue = array[endPoint];
if (startPoint != 0 && array[startPoint] - array[startPoint -1] >= 2) {
return array[startPoint -1] + 1;
}
if (endPoint - startPoint == 1 && endValue - startValue >= 2) {
return startValue + 1;
}
if (endValue - startValue != endPoint - startPoint) {
int middleIndex = (endPoint - startPoint) / 2 + startPoint;
int result = findMissingNumber (array, startPoint, middleIndex);
if (result < 0 ) {
result = findMissingNumber (array, middleIndex +1, endPoint);
}
return result;
} else {
return -1;
}
}
I believe that if the array is already sorted, finding the first missing number should be in O(n) and not in O(nlogn)
Algorithm would be
nextExpected = array[0]
for (i=1; i<array.size(); i++)
{
nextExpected++;
if (array[i] != nextExpected)
First missing number is the value of nextExpected
}
This approach involves one pass on the array, i.e. O(n).
Is there something I'm missing in the understanding of the question?
- Andi December 09, 2012private static int findMissing(int[]arr, int s, int e){ if((e-s)==1) return ((arr[s]+1)!=arr[s+1])?(arr[s]+1):-1; int m = (s+e)/2; int expVal = arr[s]+(m-s); if(expVal<arr[m]) return findMissing(arr,0,m); else return findMissing(arr, m, e); } public static int findMissing(int[] arr){ if(arr.length==0) return -1; if(arr.length==1) return arr[0]+1; return findMissing(arr, 0, arr.length-1); }