## A9 Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Use Quickselect to select the Kth smallest element in array,
average: O(n)
worst case: O(n^2)

implementation:

``````public static void solveKthSmallest() {
Integer[] a = {12, 3, 17, 0, 9, 6, 100};

int k = 3;
System.out.println(quickSelect(a, k-1, 0, a.length-1));
}

private static <E extends Comparable<? super E>> int partition(E[] arr,
int left, int right, int pivot) {
E pivotVal = arr[pivot];
swap(arr, pivot, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i].compareTo(pivotVal) < 0) {
swap(arr, i, storeIndex);
storeIndex++;
}
}
swap(arr, right, storeIndex);
return storeIndex;
}

private static <E extends Comparable<? super E>> E quickSelect(E[] arr,
int n, int left, int right) {
Random rand = new Random();
while (right >= left) {
int pivotIndex = partition(arr, left, right,
rand.nextInt(right - left + 1) + left);
if (pivotIndex == n) {
return arr[pivotIndex];
} else if (pivotIndex < n) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return null;
}

private static void swap(Object[] arr, int i1, int i2) {
if (i1 != i2) {
Object temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
}``````

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

I would propose modified quick sort as follows:
(i) Shuffle array
(ii) Select pivot
(iii) Partition the array and get rank of the pivot
(iv) If rank is 'k' done otherwise go to (ii) and repeat on sub array

``````public static int findRank(int x[], int rnk) {
int a = new int[x.length];
// Defensive copy, avoid side effect on x
for (int k=0; k < x.length; k++)
a[k] = x[k];

shuffle(a);
return findRank(a, rnk, 0, a.length-1);
}
private static int findRank(int a[], rnk, int lo, int hi) {
int mid = partition(a, lo, hi);

if (rnk < mid) 	return findRank(a, rnk, lo, mid-1);
if (rnk > mid) 	return findRank(a, rnk, mid+1, hi);

return a[mid];
}
private static int partition(int[] a, int lo, int hi) {
int p = a[lo];
int i = lo;
int j = hi+1;

while (true) {
while (a[++i] <= p) 	if (i == hi) 	break;
while (a[--j] >  p) 	if (j == lo) 	break;
if (i >= j) 	break;
swap(a, i, j);
}

swap(a, lo, j);
return j;
}``````

The methods swap and shuffle are omitted for brevity. The algorithm is probabilistic guaranteed of O(N) with the worse case quadratic performance.

I know there exist an algorithm for median which has guaranteed worse case performance O(N), maybe this algorithm can be modified and used. It would be nice if someone post and explain this solution.

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

``````public static int findMinKth(int[] A, int k) {
return findMinKth(A, k, null);
}

private static int findMinKth(int[] A, int k, Integer maxToSkip) {

assert(0 < k && k <= A.length);

Integer min = null;

for(int i = 0; i < A.length; i++) {
if(maxToSkip != null && maxToSkip >= A[i]) {
continue;
}

if(min == null || min > A[i]) {
min = A[i];
}
}

if (k == 1) {
return min;
} else {
return findMinKth(A, k - 1, min);
}
}``````

Could also be optimized for the case when k > (A.length / 2).
In this case searching for (A.length - k + 1)th max element will decrease the number of recursive calls.
Also doesn't require extra memory.

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

- Create max heap of K, in this case 3
- scan through array, if next element is smaller than root, replace with element and then max-heapfiy on root
- repeat till end of array
- now from heap of K element, you an easily get kth smallest

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

Assumption:
1. Elements are greater or equal 0.
2. There is a known maximum M for elements.

DP algorithm O(n)
1. Create an array dp of size M + 1.
2. Go through input array, put 1 to array dp by index corresponding to the input array element.
3. Go through dp second time and count 1s. When count equals to K, return index.

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

Your runtime would be O(M) worst case then. This is because you have to do the final iteration through your array dp. This is a really bad runtime.

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

So all these responses are great but knowing the implementation of arrays in java, why not merge sorting the array which takes O(n log n) and retrieving the element at index i-1? both of these operations combined give you efficiency of O(n log n + 1) => O(n log n). Java keeps references of each indexed values in the array so it accesses it in constant time, resolving your solution in O(n log n)

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

Ruby impl

``````def kth_smallest(array,k)
return nil if k<=0 || array.nil? || !array.kind_of?(Array) || array.length==0

puts "Find rank index: #{k-1}"
puts

lo=0
hi=array.length-1

rankIndex=nil

while rankIndex != k-1 && lo<=hi
puts "Lo: #{lo}. Hi: #{hi}"
rankIndex = partition(array,lo,hi)
puts "Partitioned: #{array}. Rank index: #{rankIndex}. Rank value: #{array[rankIndex]}"
puts

lo = rankIndex+1 if rankIndex < k-1
hi = rankIndex-1 if rankIndex > k-1
end

array[rankIndex]
end

def partition(array,lo,hi)
return -1 if lo>hi || array.nil? || !array.kind_of?(Array) || array.length==0

pivotIndex=(hi-lo)/2+lo
pivotValue=array[pivotIndex]
storeIndex=lo
swap(array,pivotIndex,hi)

for iter in (lo..hi-1)
if array[iter] < pivotValue
swap(array,iter,storeIndex)
storeIndex+=1
end
end

swap(array,storeIndex,hi)
storeIndex
end

def swap(array,first,second)
return array if first==second || array.nil? || !array.kind_of?(Array) || array[first]==array[second]

array[first]=(array[first]^array[second])
array[second]=(array[first]^array[second])
array[first]=(array[first]^array[second])

array
end

array=[12,3,17,0,9,6,100]
k=3

puts "Array: #{array}"
puts "#{k} smallest: #{kth_smallest(array,k)}"``````

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

Running time: O(nlogn). Space: O(1)

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

Not required to sort the array for this case.

``````int findKthSmallest(int array[], int size, int k)
{
int smallest = 9999999;
int index = size;

for(int i = 0; i < size; i++)
{
index = size;
for(int j = 0; j < size; j++)
{
if(array[i] < array[j])
index--;
}

if(index == k)
return array[i];
}
return -1;
}``````

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

``````def findKthSmallestElement(self,nums,k):

nums.sort()
return nums[k-1]``````

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

sort the array first in ascending order.If they ask for kth smallest the element in (k-1)th index will give the answer.

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

We can use selection sort. In first iteration, selection sort put smallest element in 1st position, next iteration 2nd smallest element in 2nd position and so on. So to put kth smallest element in its position we need k iteration.

However complexity of this algorithm will be O(k*n)l

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

I would sort the array and return the item at index [k-1] if allowed, if not all allowed I would try to use a sorted set to store my three lowest and keep kicking out the top element when the set reaches k+1 size.

``````private Integer findkthLowest(int[] a, int k) {
if (k <= 0 || k > a.length)
return null;

TreeSet<Integer> ts = new TreeSet<>();

for (int i = 0; i < a.length; i++) {
ts.add(a[i]);
if (ts.size() > k)
ts.pollLast();
}

if (ts.size() != k)
return null;
return ts.pollLast();
}``````

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More