CareerCup

you are using O(Rows+Cols) additional memory, you can avoid that too.

Space complexity would be O(N^2) since you're caching all possible pairs

And a running time is exponential.
It is possible to solve this in polynomial time.

What do you mean by constant time ?
Just to read file with N lines and with K elements in each line you have to do O(N*K) operations. Looks like you didn't understand the problem correctly dude.
Big minus for this.

This approach wouldn't work in following case
10 -20 8 7 6 5 4 3 2 1

The problem with it is that if triplet around mid is decreasing, we still need to recurse into both halves, to make sure there were no "break" there (see the case above). And it makes complexity linear in worst case.

Implementing predecessor and successor is an awesome idea in case if you have parent pointer. Now try to solve it without parent pointer :)

the problem says "check ALL corner cases". You didn't take into account that number can be negative, which makes it a little bit complicated. Otherwise adding 2 positive numbers is too easy problem for an interview.

you'll have 2*N comparisons. Look into my solution below – it uses 1.5*N comparisons. Both of them are O(N), but I guess problem is about to find second min with less number of comparisons.

Sorting is not an option here.
1. One option is to look for min element, and then again look for min which doesn't equal to found one. Complexity – exactly 2*N comparisions
2. Keep two variables, and compare each element to each of them - still 2*N comparisons
3. Keep two variables as min1 and min2, and then proceed through array as follows – pick 2 elements from array, compare them (1 comparison), and then compare the smallest of those with min1 and min2 (another 2 comparisons) . In this case we will have N/2 * 3 = 1.5*N comparisons. Still O(N), but I guess this is what expected from this problem.

Solution with heap is a nice one, but complexity is O(N*K). Using randomized K-selection algorithm (order statistic) will make it linear.

Ashot, of course I'm suggesting to modify it to work with file system. Something like
1. Choose a pivot element
2. Start reading a file, write elements less than pivot into one file, and elements greater than pivot into another file. Depending on position of pivot (less than or greater than K) recurse into one of output files.

Working with files will make it really slow, but there is no other choice here. The only optimisation we can do here is to read an input file by blocks of maximum size which can fit into memory instead of reading one element at a time.
So, basically idea is same as in external sort, when you have to sort a file which doesn't fit in memory.

Does it matter ? :) if you're looking for K-th largest element by partitioning array every time, after finding a K-th largest element, the elements in array after K will be K largest elements. In this caser array=file.

Well, assuming that using a heap already violates problem statement (remember, we can't store even K elements in memory ?), my solution is follows (also violates the property that file cannot fit in memory)

1. read all numbers into memory
2. Create MAX HEAP out of that elements (O(N))
3. Attention.... Extract MAX K times !

total complexity – O(N) + O(k*logN), memory - O(N)

Using the min heap you'll use less memory ( O(K) ) but algorithm will be O(N*logK), which is greater than O(k*LogN) if K < N (which obviously is).

Just implementing the K-th order statistic algorithm to work with files will solve this problem. Complexity - O(N)

in fact linear solution is possible, see my answer below

-1 to all commenters in this thread.
1. First of all, the solution posted on top does something weird, but does't solve the problem
2. Max heap will not help here, since problem says that even K elements wouldn't fit in the memory
3. If they would fit, max heap is the solution, not the min heap.

Just rephrased problem of finding common ancestor of two nodes in a tree (an easy version, since there is parent pointer). Don't believe that Google asks such an easy questions

Did you take into account that you may have millions of requests for one hour ?

More simple

Node delete(Node head, int value)
{
	if(head == null)
		return;

	if(head->value == value){
		return head->next;
	}

	Node next = head->next;
	while(next){
		if(next->value == value){
			next->next = next->next->next;
			break;
		}
	}

	return head;
}

nice example of ill-formed singleton class. Just imagine what will happen in case if 100 threads will call to this method – it will block all of them one by one just to check that singleton instance is not null.

Another option
1. if servers of that site is distributed geographically, you might be hit to a server which is far from you (for some reason, like the closest server is down, or it is under high load and the balancer routed you to the further less busy server)

the solution above is 3 passes, the problem states that it should be 1 pass. And it is possible to do it in exactly 1 pass

The solution above is wrong. There are enough cases presented above which prove that. Wondering, why people are voting for it ?

-1 for just not reading question at all. I says - GENERATE random number, and you're trying to mess here with (wrongly implemented) reservoir sampling.

well, he discussed interesting problems. The problem is that he is telling the material like to stupid idiots :)

the question is not to find the longest sub-sequence. The question is to calculate ALL possible sequences of N elements having the described property.

So funny to read these comments :)
std::set is indeed red-black tree,which on it's turn is binary search tree (balanced), so overall complexity is NlogN (inserting N elements, logN for each insertion).

It didn't say that there will be ALL long numbers in file. Need to be more clear about possible number of elements and amount of memory. Anyways,if bit array wouldn't fit into memory as well, we may use trie with string representation of those numbers, which I presume should take a lot less memory, since a lot of numbers would have long common prefixes.

Radix sort with bit array

This problem is called "Counting number of inversions" and one of possible solutions is modified "merge" operation of mergesort. Google it :)

If they are sorted, it would be O(logn)

The keyword in this problem is PARALLEL. Every student knows how to implement simple DFS in a graph.

Ok, for example

for(int i = n; i > 1; ++i)
{
   int rnd = rand(i);
   swap(arr[i], arr[rnd]);
}

Yes, the range is between 1 and size. There is no word about max number in array...

@tito: In your example size of array A[]={7} is 1. How in array of size 1 could be 1..6 missing elements ??????
How do you decided that there should be 6 elements and not 1274 for example ????

It works even with duplicates...

Wrong...
What if ALL points are on the same vertical line ?

What do you mean by "find node" ? Which criteria shall be used for finding the node ? Node name ? it's attributes ? anything else ?

Composition...

Really interesting, what it can mean :)

void printMissing(int arr[], int n)
{
   for (int i = 0; i < n; ++i)
   {
      int k = i;

      while(arr[k] != (k+1))
      {
         if( arr[k] < 1 || arr[k] > n || arr[k] == arr[arr[k] - 1] )
         {
            arr[k] = -1;
            break;
         }

         std::swap(arr[k], arr[arr[k] - 1]);
      }
   }

   for (int i = 0; i < n; ++i)
   {
      if(arr[i] < 0 )
         std::cout << i+1 << " is missing" << std::endl;
   }
}

If the X < A[N], do binary search in A[0..N], otherwise linerar search in the rest of array...

Initializa the array with values from 1 to N. Shuffle it using provided rand(N) func.

Yeah, definitely distance between A and I is longer. Morover, I think the correct answer is I & C.
So the solution should just find the deepest nodes in left and right subrtrees

Really interesting, if someone can generate m*n sums in O(n) time...

Please don't be lazy and google it. For example here is the description of algo, I think writing the code will be quite simple
scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm

int MaxStockGain(int arr[], int size)
{
   if(size <= 0)
      return 0;

   int curMin = arr[0];
   int MaxGain = 0;

   for(int i = 1; i < size; ++i)
   {
      if (arr[i] < curMin)
      {
         curMin = arr[i];
         continue;
      }

      int currGain = arr[i] - curMin;
      if(currGain > MaxGain)
      {
         MaxGain = currGain;
      }
   }

   return MaxGain;
}

Quite simple by using two stacks. However should be careful during write this code during interview to avoid dummy mistakes...

It's easy to just say "Suffix tree", O(n), etc. bla-bla-bla. Could you please wirte WORKING solution using Suffix tree ? And please think that you have to do it during interview in 10-15 minutes...

/// finds largest palindrome which occures in given string
std::string largestPalindrome(const std::string& in)
{
   using namespace std;

   //every element contains length of palindrome
   // ending at this index
   vector<int> a;
   a.resize(in.size());
   std::fill(a.begin(), a.end(), 1);

   if(in[0] == in[1])
      a[1] = 2;
   //initialized to 1
   for(int i=2; i < a.size();i++)
   {
      if(in[i]==in[i-1])
         a[i]=2;

      if(in[i]==in[i-2])
         a[i]=3;

      if(i-a[i-1]-1 >=0)
         if(in[i]==in[i-a[i-1]-1])
            a[i]=a[i-1]+2;
   }

   int pos = 0, max = 0;

   for(int i = 0; i < a.size(); ++i )
   {
      if( a[i] > max )
      {
         max = a[i];
         pos = i;
      }
   }

   if( max > 1 )
   {
      return in.substr(pos-max+1, max);
   }

   return "";
}