Amazon Interview Question
Backend DevelopersCountry: United States
import java.util.Arrays;
public class MissingElement
{
public static void main(String[] args)
{
int[] intArray = {2,3,5,7,8,9,11,12,13};
int k = 3;
System.out.println(missingK(intArray,k));
}
static int missingK(int[] arr, int k){
int m = arr[1]-arr[0];
int x = 0;
int val = 0;
do{
for(int i=0;i<arr.length;i++){
val = arr[i]+m;
if(!contains(arr,arr[i]+m)){
x++;
if(k==x)break;
}
}
}
while(k!=x);
return val;
}
public static boolean contains(final int[] array, final int v) {
boolean result = false;
for(int i : array){
if(i == v){
result = true;
break;
}
}
return result;
}
}
public int findKthMissing(int[] arr, int k){
return kthMissingHelper(arr, 0, arr.length-1, k);
}
public int kthMissingHelper(int[] arr, int low, int high, int k){
int numRange = arr[high] - arr[low];
int numPresent = high - low;
int totalMissing = numRange - numPresent;
if(totalMissing == 0)
return arr[low] - 1;
if(k > totalMissing)
return -1;
int middle = (low + high)/2;
int missingCountInLeft = (arr[middle] - arr[low]) - (middle - low);
if(missingCountInLeft >= k)
return kthMissingHelper(arr, low, middle, k);
else
return kthMissingHelper(arr, middle+1, high, k - (missingCountInLeft));
}
Ok, I missed the log(n) part last time, my bad. Following code uses binary search style solution and has log(n) average time. worst case is still O(n/2). For example when K = 0 and no K exists in the list.
static int FindK(int [] list, int K){
if(list.length < 2)return -1;
int d = list.length - 1;
int m = d/2, dif = 0;
while(d >= 0 && d < list.length){
d = m;
dif = (list[d] - list[0]) - d;
if(K == dif){
for(m = d; m < list.length - 1; m++)
if(list[m + 1] - list[m] > 1)
return ++list[d];
break;
}
if(K < dif){
m = d - (m + 1)/2;
}else{
m = d + (m + 1)/2;
}
}
return -1;
}
import org.junit.Test
import org.junit.Assert._
class Problem {
def findMissingElement(array: Array[Int], target: Int, current: Int = 0): Option[Int] =
if (current == (array.length - 1)) {
None
} else {
val missingCount = array(current + 1) - array(current) - 1
if (missingCount >= (target + 1)) {
Some(array(current) + target + 1)
} else {
findMissingElement(array, target - missingCount, current + 1)
}
}
@Test
def test(): Unit = {
val numbers = Array(2, 3, 5, 7)
assertEquals(Some(4), findMissingElement(numbers, 0))
assertEquals(Some(6), findMissingElement(numbers, 1))
assertEquals(None, findMissingElement(numbers, 2))
assertEquals(None, findMissingElement(numbers, 3))
}
}
public void findNthMissingNum(int[] nums,int n){
int low = 0;
int high = nums.length - 1;
while(low < high){
if(high - low == 1){
System.out.println(nums[low]+n);
break;
}
int mid = low + (high - low)/2;
int missingOnLeft = nums[mid] - nums[low] - 1;
int presentOnLeft = mid - low - 1;
if(n > missingOnLeft - presentOnLeft){
//go right
low = mid;
n -= missingOnLeft;
}else{
//go left
high = mid;
}
}
}
public void findNthMissingNum(int[] nums,int n){
int low = 0;
int high = nums.length - 1;
while(low < high){
if(high - low == 1){
System.out.println(nums[low]+n);
break;
}
int mid = low + (high - low)/2;
int missingOnLeft = nums[mid] - nums[low] - 1;
int presentOnLeft = mid - low - 1;
if(n > missingOnLeft - presentOnLeft){
//go right
low = mid;
n -= missingOnLeft;
}else{
//go left
high = mid;
}
}
}
public class App7 {
public static void main(String... arg) {
System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 0, 0, 8));
System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 1, 0, 8));
System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 2, 0, 8));
System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 3, 0, 8));
}
public static int countingSort(int[] arr, int k, int s, int e) {
int mid = s + ((e - s) / 2);
if (mid == s) {
return arr[mid] + 1;
}
int i1 = arr[mid]-((mid - s) + arr[s]);
if (i1 >= (k + 1)) {
return countingSort(arr, k, s, mid);
} else {
return countingSort(arr, k - i1, mid, e);
}
}
}
Similar to Binary Search
- Misc1 April 18, 2018