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

- guilhebl April 27, 2015 | Flag Reply
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.

- autoboli April 28, 2015 | Flag Reply
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.

- Paul Kramchaninov April 28, 2015 | Flag Reply
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

- Anonymous April 27, 2015 | Flag Reply
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.

- encoded May 08, 2015 | Flag Reply
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.

- Sam November 19, 2015 | Flag
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)

- Arnaud Somda May 17, 2015 | Flag Reply
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)}"

- Yev June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Yev June 26, 2015 | Flag
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;
}

- Mahmut January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findKthSmallestElement(self,nums,k):
        
        nums.sort()
        return nums[k-1]

- Anonymous April 24, 2017 | Flag Reply
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.

- anjandudda April 28, 2015 | Flag Reply
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

- Mritunjay Kumar April 28, 2015 | Flag Reply
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();
	}

- jninety May 04, 2015 | Flag Reply


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