iman.goodarzi
BAN USERit is possible in O(n) and the idea is like Insertion Sort
in case of array of increasing integers:
find the first element in array that is smaller than its previous element. (start of the second sorted subarray)
swap this element with its previous one until it becomes bigger than its prev.
continue on the next index on the second subarray until the end.
inplace version:
void word_reverse()
{
string str = " a Hello World! another_word! ab c ";
char[] array = str.ToCharArray();
int word_start = 0;
int word_end = 0;
for (word_end = 0; word_end < array.Length; word_end++)
{
if (str[word_end] == ' ')
{
Reverse(ref array, word_start, word_end  1);
word_start = word_end + 1;
continue;
}
else if (word_end == array.Length  1 && array[word_end] != ' ')
{
Reverse(ref array, word_start, word_end);
break;
}
}
}
void Reverse(ref char[] array, int start, int end)
{
while (end >= start)
{
char tmp = array[end];
array[end] = array[start];
array[start] = tmp;
end;
start++;
}
}

iman.goodarzi
March 08, 2013 knuth (FisherYates) algorithm:
initialize array of size n with integers from 0 to n1
for (int i = n  1 ; i >= 0 ; i)
{
int j = getRandomNum(0, i);//random between 0 and i
swap(array[i], array[j]);
}

iman.goodarzi
March 07, 2013 Does it cover the case with all negative integer inputs? Anyway modification is easy: just keep track of the largest number in the input. That's the result.
 iman.goodarzi March 07, 20131) initialize max1 and max2 with int.minvalue
2) you need to handle cases when the largest number appears more than once in array.
if not having parent pointers: O(n) + O(h) = O(n)
if having parent pointers: O(h)
kdtree is the answer and can guarantee O(lg(n)) complexity for queries. However I think it takes O(nlg(n)) precomputation complexity.
 iman.goodarzi March 11, 2013Another option is: as the input data is location of cities we may be able to assume they're spreading normally through the whole grid (usually its not!). in this case a simple O(n) clustering works with less than O(n) search complexity. At least one can test this approach for the input data and see if this type of clustering works or not! (this will be a good thing to mention in interview!)