Palantir Technologies

www.palantir.com

Interview Question

Business Development Engineer Interview Palo Alto, CA

given an array of n unsorted integers and each number is at

  most k positions away from its final sorted position, give an efficient sorting algorithm.
Answer

Interview Answer

4 Answers

1

Insertion sort works best for nearly sorted arrays.

Jack on Apr 19, 2012
5

Use minheap on first k elements, and extract min and insert the next element. Keep doing until the end of the array. This takes O(nlogk).

Chandra on Apr 23, 2012
0

if each element is k positions "away" then you could simply circular rotate the array

k = 4

orig - 1 2 3 4 5 6 7

4-away - 5 6 7 1 2 3 4

Akshay on Aug 4, 2012
0

k away doesnt necessarily mean it is rotated. it means almost sorted.

Anonymous on Oct 9, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.