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 sub-array)
swap this element with its previous one until it becomes bigger than its prev.
continue on the next index on the second sub-array until the end.
in-place 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++;
}
}
knuth (Fisher-Yates) algorithm:
initialize array of size n with integers from 0 to n-1
for (int i = n - 1 ; i >= 0 ; --i)
{
int j = getRandomNum(0, i);//random between 0 and i
swap(array[i], array[j]);
}
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)
kd-tree is the answer and can guarantee O(lg(n)) complexity for queries. However I think it takes O(nlg(n)) pre-computation 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!)