A9 Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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.
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.
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.
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)
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)}"
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;
}
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();
}
Use Quickselect to select the Kth smallest element in array,
average: O(n)
worst case: O(n^2)
implementation:
- guilhebl April 27, 2015