## Amazon Interview Question for Backend Developers

Country: United States

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

Similar to Binary Search

``````public class KMEFinder {

public int find(int[] sa, int k) {
return find(sa, 0, sa.length-1, k, 0);
}

private int find(int[] sa, int stIdx, int endIdx, int k, int leftmisses) {
if (endIdx - stIdx == 1) {
return sa[stIdx]+(k - leftmisses);
}

int midIdx = stIdx + (endIdx-stIdx)/2;
int lms = (sa[midIdx] - sa[stIdx]) - (midIdx - stIdx);
if (leftmisses + lms >= k) {
return find(sa, stIdx, midIdx, k, leftmisses);
} else {
leftmisses = leftmisses + lms;
return find(sa, midIdx, endIdx, k, leftmisses);
}
}
}``````

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

def findMissingElement(arr,k):
mid = int (len(arr)-1)/2
mid = int(mid)+k
if arr[mid+1] - arr[mid] > 1:
return arr[int(mid)]+1
else:
return 0

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

``````public static int findK(int [] list, int num){
int k = 0, val = 0;
if(list.length < 2)return -1;
val = list[0];
for(int i = 0; i < list.length - 1; val = list[++i])
while((list[i + 1] - val++) > 1)
if(k++ == num)return val;
return -1;
}``````

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

``````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;
}
}``````

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

``````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));
}``````

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

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;
}``````

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

``````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))
}
}``````

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

``````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;

}

}``````

}

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

``````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;

}

}
}``````

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

``````int find(int arr[], int k) {
int start = 0;
int end = arr.length-1;
int count = 0;

while (start <= end) {
int mid = start + (end-start)/2;
count = arr[mid] - arr[0] - mid;

if(count >= k) {
end = mid-1;
}else
start = mid+1;
}
return arr[end] + k - (arr[end]-arr[0]-end);
}``````

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

``````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);
}
}
}``````

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

A simple python solution use list comprehensive.

``````def findMissing(alist, k):
return [a for a in range(alist[0], alist[-1]+1) if a not in alist][k]``````

Comment hidden because of low score. Click to expand.

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.