CareerCup

For sorted:

int max_value = A[0], max_count = 1;
int value = A[0], count = 1;
for(int i=1; i<N; ++i)
    if(A[i] == A[i-1]) 
    {
        ++count ;
        if(max_count <count )
        {
            max_value  = value ; 
            max_count  = count ;
        }
    }
    else
    {
        value  = A[i];
        count = 1;
    }

Time: O(N)
Space: O(1)

For unsorted:

Data structure: treap (tree+heap)

http://en.wikipedia.org/wiki/Treap   
http://e-maxx.ru/algo/treap

sorted tree by value + max-head by count
root will be the answer

Time: O(N Log(N))
Space: O(N)

IPv4 is X1.X2.X3.X4 where X can be from 0 to 255, that's mean it can take 2^8 values.
4*X - is 4*8 bit and is it 4 byte.

1. we can use 4 byte as key for one element. In this case we will never have collisions.
2. we can use less then 4 byte, then the best way to impliment hash function will be to ignore first numbers, and use last (X4, X3.X4 or X2.X3.X4 dependence of how many memory we want to use) as hashkey.
We use only end of id address, because in real life ip addresses usually in one area have same first 3 digits, more over in one (home/work) network they usually have same 3*3 digits.
So collisions will be more evenly distributed if we skip first part.

Obviously, this is reqursion/dynamic problem. So we need formula.

Let's say, that F(i, j) - is max possible coins that 'first' player can collect on board with packets from i to j. And by 'first' player I mean player whos turn now.
F(0, n-1) - will be the answer.

Ok, now for F(i, j), first player can take v[i] or v[j].

x = v[i] + (Sum[i+1, j  ] - F(i+1,   j  ) );
y = v[j] + (Sum[  i , j-1] - F(  i,    j-1) );

And he will collent x or y coints. Of course he will choose the maximum option:

F(i, j) = MAX(x, y);

Why (Sum[i+1, j ] - F(i+1, j ) )? Thats simply. After the first player took the coins, the turn passes to the second. And he also wnat to win. And now he is the first player but on the board (i+1, j) or (i, j-1). The Sum is fixed, so all that he will not take - is our coins.
_________________________________________________
But do we really need to calculate Sum? No!
Lets go deeper! in recursion : ) I skip here computing. In two words:
If we 'open' F(i+1, j ) and F( i, j-1) - sum will be reduced and using that

-Max[-a, -b] == Min[a, b]

and we will get:

a = F(i+2, j); b = F(i+1, j-1); c = F(i, j-2);
x = v[i] + MIN(a, b); y = v[j] + MIN(b, c);
F(i, j)  = MAX(x,  y);

On each iteration size of board will be reduced on 2.
_________________________________________________
To avoid re-computation, we need to store all done computation:

ArrayInfo optimal_subset_sum;  //optimal_subset_sum( i, j ) = F(i, j)

ArrayInfo can be simply int[n][n]. if you don't care about the amount of memory used.
But we'll get to that later.

First, we need to initialize the smallest boards answers. There are two different situation.
If N is odd, then F(i, j) = F(i, i) = v[i]

for(int i=0; i+1<n; ++i)
	optimal_subset_sum(i, i+1) = data[i];

If N is even, then F(i, j) = F(i, i+1) = MAX(v[i], v[i+1])

for(int i=0; i+1<n; ++i)
	optimal_subset_sum(i, i+1) = MAX(data[i], data[i+1]);

And now, we increasing the size of the board for 2 and calculate answers for all possible boards:

for(int k = smallest_lenght + 2; k<=n; k+=2)
	for(int i=0, j=k-1; j<n; ++i, ++j)
	{
		int a = optimal_subset_sum( i+2,   j   );
		int b = optimal_subset_sum( i+1, j-1 );
		int c = optimal_subset_sum(   i,    j-2 );	
		int x = data[i] + MIN(a, b); int y = data[j] + MIN(b, c);
		optimal_subset_sum(i, j) = MAX(x, y);
	}

_________________________________________________
Returning to the ArrayInfo.
There is only 1 sub-board starting fron i=n-1. (n-1, n-1)
There are only 2 sub-board starting fron i=n-2. (n-2, n-2) and (n-2, n-1)
...
Additionaly, we have only odd or only even lenght sub-boards, because we reduce it on 2 each time.
So we don't need N*N space. We can impliment ArrayInfo such way:

class ArrayInfo
{
public:
	ArrayInfo(size_t n) 
	{
		data = new int*[n]();
		for(int i=0; i<n; ++i)
		{
			data[i] = new int[(n-1-i)/2+1]();
			for(int j=i; j<n; ++j)
				data[i][j] = -1;
		}
	}
	int& operator() (int i, int j)
	{
		return data[i][(j-i)/2];
	}
private:
	int** data;
};

And it will used

Sum[(N-i-1)/2 + 1, { i, 0, N-1 } ] = N*(3+N)/4 = n^2/4 + 3*n/4

that's in 4 time less.

working code: http://ideone.com/ZzbMRt

you will lose the order

sum array will be: 0 1 1 1 1
longest sub-set is from 1 to 4

you can find an explanation by looking closely at the function Range::add
first time we will set both - first && last positions to the current. and the lenght of array will be 0.
then we will set only last position.

So, we want to find sub-set [i, j], such that

( a[i]+a[i+1]+ ... a[j] ) % k = 0

with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:

s[i] = (a[1] + a[2] + ... + a[i]) % k

And we can note that, if there is such [i, j] that we are looking for, then:

s[j]-s[i] == (a[1]+...+a[j]) - (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0

So, for each s[i] == s[j], sum of sub-set [i, j] is divisible by k.

Now we need to find the most appropriate range.
If we are looking for the longest set, then

struct Range
{
	int first_position = -1;
	int last_position = -1;
	
	void add(int position)
	{
		if(first_position == -1)
			last_position=first_position = position;
		else
			last_position = position;
	}
	friend bool operator<(const Range& r1, const Range& r2)
	{
		int r1_lenght = r1.last_position-r1.first_position;
		int r2_lenght = r2.last_position-r2.first_position;
		return r1_lenght  < r2_lenght ;
	}
};

for each modulo of k: we need find first and last position (in sum-array), and select the largest range from them.

Range searchRange[k];
int sum = 0, max_range_id = 0;
for(int i=0; i<n; ++i)
{
	sum=(sum+data[i])%k;
	searchRange[sum].add(i);
	if(searchRange[max_range_id] < searchRange[sum])
		max_range_id = sum;
}

Here is working full code: http://ideone.com/VvWSkT

Well, we have sorted Matrix M*N.

int data[N][M] = ...;

The idea is to start sorting matrix using Megre Sort algo and stop when we find K-th element.
_____________________________________________
That's the interface for our class.

class IMegreSort2D 
{
	MegreSort2D(const int** data, int n, int m);
	int next(size_t count = 1);
};

We can use it such:

int k_sorted_element = MegreSort2D(data, N, M).next(k);

or such (to sort all matrix):

MegreSort2D sort(data, N, M);
for(int i=0; i<N*M; ++i)
	cout<<sort.next()<<endl;

_____________________________________________
Now we need to impliment function "next".

Let's create support structure Link. It will store position and value from this position. Also we will override operator< for them to compate 2 Link by values.

struct Link 
{
	int i, j;
	const T& value;
	Link(const int** data, int i, int j) : i(i), j(j), value(data[i][j]) {}	
	friend bool operator<(const Link& l1, const Link& l2) { return l1.value > l2.value; }
};

Of course, we can use str::pair<int,int> and get value from data. But, as for me, this version is more readable.
_____________________________________________
Now, our MergeSord need Min/Max Heap. In c++ we can use std::priority_queue.

priority_queue<Link> min_heap;

Firstly, we put there only smallest/biggest element:

min_heap.push(Link(data, 0,0));

Then, on each call 'next', we will take smallest/biggest element from this heap, and put next element from the same row to them:

int next()
{
	const Link& link  = min_heap.top(); //get smallest/biggest element from heap
	T value = link.value; //save to return
		
	if(link.i<(N-1)) //if it is not the last element of the row
		min_heap.push(Link(data, link.i+1,link.j)); //add next value from this row
		
	if(link.i==0 && link.j<(M-1)) //if it was first element from the row
		min_heap.push(Link(data, 0,link.j+1)); //add first value from next row
		
	min_heap.pop();
	
	return value;
}

Also we put first element from the next row, when take first element from previouse row.

Here is full working code: ideone.com/xZqt51

The task is not clear, but i guess, that we are speaking about finding K-th sum from a[i]+b[j] for ANY {i, j}. Becouse if i==j, it is simply binary search, and there is no reason to complicate the task description.
___________________________

This task reduced to another popular task, which has been discussed here many times:
Find K-th element in Sorted Matrix.

Let's imagine that we have N*M Matrix: S[i][j] = a[i]+b[j];

a[0]+b[0]	a[0]+b[1]	...	a[0]+b[m]
a[1]+b[0]	a[1]+b[1]	...	a[1]+b[m]
...
a[n]+b[0]	a[n]+b[1]	...	a[n]+b[m]

A and B was sorted list. So each column and each row is sorted too.
Here is the link to solution:

question?id=6335704
or you can find it, as the most commented question from Google's interview.

I use word 'imagine', becouse we don't need to build it for real.
To solve derivative problem, all numbers from matrix are needed only once, so we can calculate sum in runtime, without saving to matrix.

Here is counterexample

L1: 0, 10, 20, 30, 40, ... (Total N elements)
L2: 1, 2, 3, 4, 5, 6, 7, 8, 9 (Total M=9 elements)

Well, we have

int input[n] = {7, 5, 6, 3, 4, 1, 2, 9, 11};

we want to get

int answer[n]; // = {9, 6, 9, 4, 9, 2, 9, 11, -1}
for(int i=0; i<n; ++i)
	answer[i] = -1;

I mark numbers that doesn't have bigger at right side as -1.
We can replace -1 with anything we need later.

We will save all positions, for which we still didn't find answers in stack.
At the start, stack is empty.

stack<int> still_without_answer;

Now, we are going to iterate throw the array.

for(int i=0; i<n; ++i)

For each number, we will find all numbers on the left sife, that less then current.
We will delete them from the stack.
So after that, all numbers in the stack will be bigger then current.
That mean that our stack is decreasing order and we can check only the top value, instead of iteration throw stack.

int smallest_without_answer = still_without_answer.top();
while(!still_without_answer.empty()&&input[smallest_without_answer]<input[i])
{
	answer[smallest_without_answer ] = input[i];
	still_without_answer.pop();
}
int smallest_number_without_answer = still_without_answer.top();

After setting current number as answer for smaller numbers, we push them to stack. Now it is the smallest number without answer.

still_without_answer.push(i);

This is O(n), becouse we iterate 1 time throw each elements, 1 time put each element to the stack for O(1), and 1 time delete from the stack for O(1).

You solution will fail on something like this:

0 0 0 0 0
0 1 0 1 0
0 1 x 1 0
0 0 0 1 0

in both case - whether we can go to 4 direction or 8.

Because, when you find path from A to X it will be:

p p p 0 0
0 1 p 1 0
0 1 x 1 0
0 0 0 1 0

and where is no path from X to B not including first path.

Two words are anagrams IF AND ONLY IF they have the same set of letters.
Let's create a class representing a collection of letters. We can implement it several ways: by sorting set of letters, or by array or some another way. Here is implementation by array:

class CharSet
{
private:
	static const int alphabet_lenght = 'z' - 'a' + 1;
	size_t letters[alphabet_lenght];

public:
	void add(char letter)
	{
		++letters[letter - 'a'];
	}
	class Comparer; class Hasher;
};

We need to define Comparer and Hasher for this class to effectively use later.
Comparer should simply iterate over array and check whether they equal;
Here is sample of Hasher:

class CharSet::Hasher
{
private:
	const size_t PRIME = 31;
public:
    size_t operator()(const CharSet& word) const 
	{ 
		size_t hash=0;
		for(size_t i=0; i<alphabet_lenght; ++i)
			hash= hash * PRIME + word.letters[i];
		return hash; 
	}
};

Now, we can say, that if two words have equal CharSet then they are anagrams.
But it is a too long to compare CharSet completely each time.
The two CharSet NEVER equal if
a. they contain different number of chars
b. or their hash doesn't equal.
It is much faster to compate two numbers (lenght and hash) instead of 2 arrays.
Lets create class AnagramPatern, that can faster compare CharSets:

class AnagramPatern
{
private:
	size_t hash, lenght;
	CharSet letters;
public:
	AnagramPatern(const string& word) : lenght(word.size())
	{
		for(const char& letter : word)
			letters.add(letter);
		
		hash=CharSet::Hash()(letters);
	}
	class Comparer; class Hasher;
};

We will count hash only 1 time - on creating, and save it. Hasher will simply return it.
And Comparer will first compare length and hash, and only if they equal, that compare full CharSet. Actually, for small alphabet we can implement hash without collision, and comparing arrays will be not needed.

class AnagramPatern::Comparer
{
public:
	bool operator() (const AnagramPatern& first, const AnagramPatern& second) const
	{
		if(first.lenght != second.lenght || first.hash != second.hash)
			return false;
		
		return CharSet::Comparer()(first.letters, second.letters);
	}
};

Now we need HashTable. Words will be values, and AnagramPatern will be th key.

class AnagrammGrouper
{
private:
	typedef unordered_map<AnagramPatern, list<string>, AnagramPatern::Hasher, AnagramPatern::Comparer> Collection;
	Collection groups;
public:
	void add(const string& word)
	{
		AnagramPatern format(word);

		auto it = groups.find(format);
		if(it == groups.end()) //first time for such pattern we need to create list
			it = groups.emplace(format, list<string>()).first;
		it->second.push_back(word);		
	}
	Collection::const_iterator begin() { return groups.begin();	}
	Collection::const_iterator end() { return groups.end();	}
};

Here is full code with test:
http://ideone.com/buzjGP

First check whether number is power of 2:

x = 2^k
x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

x != 2^k
x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

If it is not power of 2 - then it is not power of 4.
If it power of 2 - then it have exactly one 1 in binary record.

1   = 000000001 
4   = 000000100 
16  = 000010000 
64  = 001000000 
256 = 100000000

If it is power of 4 - position of this single 1 will be odd.

bool isPowerOfTwo = x && !(x & (x - 1));
//101010100 = 0x5...554
int mask = 0x5...554; //(or 0x5...555 is 1 should be included as 4^0) 
return isPowerOfTwo  && (x & mask );

There are two different situations in unspecified condition:
Whether we should consider duplicate one or more times.

- If the expected result without duplicates:
1. HashSet, not HashTable. Its similar but not identical structures.
2. We should remove elements from HashSet after they was founded - otherwise we can find them a few times.
- If the expected result with counted-duplicates
1. HashTable should save as values duplicates-count

if you simply converting it to 1D and then sorting it - it will be N^2*lg(N^2).

Maybe it will work (i did not check), but it is not enough 45-minute interview to prove that it is correct and working solution.

This is a simple and intuitive solution.

But we can replace string with bit-storage.
There are (2n)!/(n!(n+1)!) total combination for parentheses and copying string is very time-consuming operation.

Here is the comparing of work time (in ms) for string and bit implimintation:

n		bit				string
5		0				2
10		8				869
11		28				3164
12		97				11450
13		358 (< 1 sec)	40892 (40 sec)
14		1300 (1 sec)	146235 (2 min)
15		4788 (5 sec)	537079 (8 min)

I hope, I assure you that it is bad to copy strings

class Parentheses /*save as binary */
{
public:
	Parentheses() : parentheses(0), n(0) {}
	Parentheses add(bool bracket) //return new object
	{
		if(bracket) return Parentheses(parentheses | (1 << n), n + 1);
		else return Parentheses(parentheses, n + 1);
	}
	void print()
	{
		for(size_t i = 0; i<n; ++i)
			if(parentheses & (1 << i)) cout<<"("; else cout<<")";
		cout<<endl;
	}
private:
	Parentheses(unsigned long long parentheses, size_t n) 
		: parentheses(parentheses), n(n) {}
	unsigned long long parentheses;
	size_t n;
};

void find(int n, int left=0, int right=0, Parentheses s= Parentheses())
{        
    if(left+right==2*n)
    {
        s.print(); return;
    }
	if(left != n)
		find(n, left+1, right, s.add(true));
	if(right < left)
		find(n, left, right+1, s.add(false));
}

The faster solution is merge sort by all rows (or columns) at the same time.
To do this, we need min-heap.
Here is how to *use* MinHeap for sorting. MinHeap does not implemented is this code. You can find the implamantation in google if you need.

template<class T> class MegreSort2d 
{
struct Link 
{
	Link(const T** data, int i, int j) 
		: i(i), j(j), value(data[i][j]) {}
	const int i, j;
	const T& value;
};
static void sort(const T** data, T* outData, int n) 
{
	MinHeap<Link> heap;
	current_mins.add(Link(data, 0,0));
		
	for(size_t i=0; i<n*n; ++i)
	{
		const Link& link  = heap.getMinValue();
		outData[i]=link.value; //save as sorted
			
		if(link.i<(n-1))
			heap.add(Link(data, link.i+1,link.j)); //add next value from this row
			
		if(link.i==0 && link.j<(n-1))
			heap.add(Link(data, 0,link.j+1)); //add first value from next row

		heap.remove(link);
	}
}
};

There is no solution faster that O(n^2 * Log n) where n - is the size of matrix.

Check you solution on something like this:

a a a a b
a a a b c
a a b c c
a b c c c
b c c c c

Where
a - different values in range (x1, x2)
b - different values in range (x2+1, x3 - 1)
c - different values in range (x3, x4)

I mean, all values upper diagonal is less than diagonal. And all values then down than diagonal - is more than diagonal.