CareerCup

@rganeyev
e.g. because Floyd-Warshall doesn't work with negative cycles as bellmann ford doesn't
an intuitive prove of this is that if you walk through the negative cycle once more, you will get an even "longer" path with the words of the question or a even "shorter path" in terms of the original algorithms.

Further, it has been shown that the problem can be deduced to a known NP complete problem.

but anyway, I don't agree it's a useless exercise, sometimes even an exponential algo is okay as long as you know it is exponential and if you can roughly prove it's in NP in an interview, I suppose some companies would love you ;-)

see here question?id=5765581773996032

I have just looked quickly and saw the following points:
1) They asked for the dot-product of a matrix, you implemented it for a special case, a vector. Not sure if that was the question or clarification you got.

2) I guess, if you need a data structure for dot-product it's not so cool to use a map because of the O(m*log(n)) nature of your algo. With 24h I had expected a O(n) solution - e.g. using the hashtable, there is no real advatage in keeping the order, I totally don't understand your 2nd comment on this.

Then, if you use only a vector, you get away with a linked list, that will keep the index and value, which is then not optimized for setValue but multiplication can be done in a merge-sort kind of way.

How to improve: Just keep solving problems, buy gayle's book she has a nice, pragmatic approach. Code more, read code from pros (e.g. github projects)

3) c++:
- an iterator with it++ instead of ++it. Which a c++ programmer must know.
- getValue and getSize should be const-methods, just good practice, should go automatic, I guess if they give you time to do so, they expect it, on the white board, I think nobody really cares that much.
- worst is your constructor, it leaks unnecessary new (sorry, but it's really bad)
- How to Improve: Read stroubstrub, effective c++, more effective c++ and effective modern c++ (if it has to be C++)

Coding style: there is this if in the s_dotProduct-Method which essentially doubles code, since you want to minimize the amount of lookups in the map. Here it would be better to have pointers to the two maps and just swap them and have the multiplication code only once. This copy/paste kind of code is not good!
- How to Improve: Whenever you copy / paste such a block of code, ask yourself, can I put it into a helper method, might be inline, or can I just swap some arguments or anything to not double code.

OO-design, in some way a taste thing, I would Expect the Matrix class having a multiplication method so you can write vect1.mul(vetc2) instead of vector::multiply(vec1, vec2). The template method s_toString, I'm not sure it belongs into the vector class

And an other thing, if you get so much time, why don't you write some unit-test like test cases, I mean this case is neat to show you understand TDD and you have passion and are willing to work.

@NoOne: sure, it could be incomming requests on a server, but still, a heap is not necessary, since requests will arrive in sequential order. So, they are already ordered in the sense that the oldest is next on a FIFO, there is no need to change the order. One can just consume in the order they arrived and only process them if they are younger than a second. Seems a bit simple, well, I maybe just didn't get the question at all...

@NoOne: The thing with this problem is, that 99% of the requests will probably be super fast and they aim to cut off the long tail latency (just interpretation). Now with a heap I see two issues:
- How to remove an item from the heap, e.g. how to identify it since the heap is modified, if a response comes back, we have to find that item in the heap to remove it. How do you do this fast?
- O(Lg(N)) on insert and remove might not be such a big thing, since the insert can be optimized to O(1)

What does he mean? From the context of google, I would assume they mean requests from a client to a back-end server that have not gotten a response for a second or more. This would be RPC requests sent from a "client" (e.g. a front end server) to a "server" (e.g. a back end server). This can be 10 thousands of requests but it's probably save to assume it's less than 100'000 or let's say 500'000 requests in any 1 second timeframe: < 500K RQS

I'd pretend requests are executed strictly sequential so I place them in a queue together with the timestamp. New requests are placed at the head (front), requests at tail that are >= 1 second can be canceled and removed. I would use a ring buffer with 500K entries fix allocated with a start and end index. So, the index I'd get for a call is as well an identifier that I need back on the request's response so I can mark the request as completed. If a request is completed that is = to the tail, I can advance the tail as far as there are entries marked completed.

Complexity: O(1) to insert, O(1) to find > 1s and O(1) amortized to complete a call.
The problem with the apporach is, that a call that really takes 1s compared with other calls being returned in fractions of milliseconds will keep the queue from being emptied, so the queue can get full because of only one call. If it can be restricted in terms there are never more than 500'000 requests a second, this can still be a good solution, but if the number of calls lasting long increases and if the accepted timeout is changed to maybe 10 seconds, the solution starts to break.

I'd assume the age is in years, so there are at most 120 different ages = buckets. I can now store, the count of ages in an array with index age where the age addreses a "bucket". I maintain as a total count. To get the mean, I just count through the 120 buckets until I reach n/2. I'd assume for simplicity that the floor median is fine, so I don't have to add 0.5 in case of even count where floor median is in one bucket and ceiling median is in the next.
Insert-complexity will be constant: O(1)
Same with delete, if ever wanted.
Query median is as well O(1) since the number of buckets is constant
--
This can be optimized in terms of number of operations required to determine the mean if mean is maintained when inserting. This might be interesting if the ratio query/inserts is not very small.
--
An other interesting aspect is, how big is the error if calculated as described above...

# assume due to feedbacks, zig-zag means 
# diagonals starting from upper-left, going down until 
# lower and if at bottom-left go to bottom-right 
# printing the elements into up-left diagonale
#
# e.g- the desired order in this case:
# [[0, 1, 2, 3, 4],
#  [5, 6, 7, 8, 9],
#  [a, b, c, d, e]] 
# is: 0, 5, 1, a, 6, 2, b, 7, 3, c, 8, 4, d, 9, e
# 
# or in this case:
# [[0, 1]
#  [2, 3]
#  [4, 5]]
# 0, 2, 1, 4, 3, 5
#
# in python3:
def traverse(matrix):
    cols = len(matrix[0])
    rows = len(matrix)
    print('matrix {0}:'.format(matrix), end=' ')

    for i in range (0, rows):
        for j in range (0, min(i + 1, cols)):
            print(matrix[i - j][j], end= ' ')
    
    for j in range (1, cols):
        for i in range (0, min(cols - j, rows)):
            print(matrix[rows - i - 1][j + i], end=' ')

    print()
        
traverse([[1,2,3],[4,5,6],[7,8,9]])
traverse([[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14]])
traverse([[0,1],[2,3],[4,5]])
traverse([[1],[2],[3]])
traverse([[1, 2, 3]])

#output:
#matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]: 1 4 2 7 5 3 8 6 9 
#matrix [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]: 0 5 1 10 6 2 11 7 3 12 8 4 13 9 14 
#matrix [[0, 1], [2, 3], [4, 5]]: 0 2 1 4 3 5 
#matrix [[1], [2], [3]]: 1 2 3 
#matrix [[1, 2, 3]]: 1 2 3

a2i is the string to integer in c:
- overflow depending on integer size of that machine, e.g. max and min of integer
- two "--" like "--1234"
- "123-32"
- decimal "." or "," or "..", or ",,"
- thousand seperators, depending on cultural settings (e.g. . or ' ...)
- what surounds the integer, spaces, end of string, other characters like "124zoo"
- whitespaces at the beginning, which of them
- only base 10, or octal, binary, hex with suffix, prefix
- white spaces, like line breaks, back spaces in between
- encodings, like utf8 etc...
- special characters like chinese, japanese (ichi, ni, etc..)
...

Assuming the random string forms some kind of natural language flow text with words and spaces and no formatting such as line breaks, paragraphs, headings, tables etc. and no word division (hyphenation) or maybe with the strategy would almost stay the same.

Basic strategy:
1) estimate a font size by guessing
2) Layout based on the estimate, correct into either direction

1) Estimate
- there are unknowns like word wraps, average character width, but line height is given by the font size, e.g. 1.5 times max_height
- assume average word size (in characters) that is either typical or by analyzing the given text
- assume average charachter width either typical or by analyzing given text
- from the given screen width and each font characteristics you can now estimate the number of lines which in return gives yout the hight needed.
- calculate this characteristics for each font if n is reasonable small or binary search the font size and pick the biggest where the desired height fits within the bounds given

2) now layout with real text and adjust font until it overlaps or fit... when the string is really random, you might, after running some samples be able to bypass the last step or only correct font size downwards in case it overlaps in rare cases... how ever the estimations might need to be language sensitive.

@Ankita: some pivot will divide into half, most often not the first of course, see partitionAroundKth:

int partition(int *array, int first, int last)
{
// typical partition code
// returns arbitrary index in the range [first, last] which is the
// index of the pivot
}

void partitionAroundKth(int *array, int first, int last, int k)
{
int pi = -1;
while(pi != k)
{
pi = partition(array, first, last);
if(pi > k) last = pi - 1;
if(pi < k) first = pi + 1;
}
}

1) use quicksorts partition method to split into half, this will separate your array into elements: < median and >= median
2) on the upper half of this array, use the same partition method to separate on kth position, you will then have an array of median ... median + k in O(n) time
3) this array you need to sort which will lead to the O(n + k * log(k))

things to consider:
- median is ambigious as there exists a median element if the array is of odd size, if of even size, there is an floor-median and a ceiling median and in statistics the real median is the average of them, here either the floor or ceiling is ment I suppose.
- the partition method has a few properties that are not so nice if implemented in a primitive way and applied for example on a sorted array or an array with all the same elements in it. Randomization is an approach, and split into three parts < = > is an alternative

I could think of two mayjor things going wrong:
- something with the player
- something with the page, like an animation, layout, css property, no idea that is not compatible
--> how, play the video in a page that has nothing else than the HTML5 player, which I think youtube uses. If it plays, then it's the page, if it doesn't probably a codec, player, what ever thing... should be easy to solve
--> if it's the page, good luck, maybe some W3C compatibility check..., place the player in a div that's marked yellow etc. etc. etc... after having some narrowing information, I would defintely try to find somebody who knows more...

anyway what does amazone has to do with youtube ;-)

1) Approach with HT (not so good)
One approach could be to have the dictionary in a hashtable and then create varions of the original string that miss one character, two characters etc.

if k is numbers of characters to be deleted and n length of the search string, there are n choose k possibilities (= n!/((n-k)! * k!):
1 possibilities to remove 0
n possibilities to remove 1
etc...

as an example, lets assume the input text is 20 characters and all possibilities up to 19 removed characters are tried:
this is ~2^n possibillities: ~1 Mio
but, if a word is expected to be found by removing at most
5 characters, "only" 20 choose 0 + 20 choose 1
+ ... + 20 choose 5 = ~22K possibilities need to be tried

2) Approach with trie (better in practice)
it can be improved by doing a kind of a breath dept search
in a trie. This is essentially equal to the hash-table approach but the number of options will not grow as fast becasue only mutations of the original input are followed that actually are prefexis of a real world. How much better this is should be verified by a real dictionary and examples to collect some statistical information. How ever, it will have an impact due to the redundancy of the language. The approach can be improved by limitting max number of characters that are allowed to be removed.

It works as follows, consider this example dictionary:
-fellow
-hello
-one
-hell
-fhel (a fictionary word)
--
and the searchstring input = "fhellowne"

initialize a min priority queue with the root trie-item, index 0, and priority 0 (note the priority is # of characters deleted):
- this gives a queue (prio:pointer to trie,next index):
0:root-item,0
- while the trie is not empty
- take index, trie-item from the prio queue's top
- if input[index] exists in the trie-item,
get the next node of the trie and store it with the
same priority and index + 1.
- if index == input.length -> terminate
- if input[index+j] match a next character in the trie-item:
- create a branch for all following single letters with
lower priority+j (assuming skiping/deleting characters)
- after first iteration queue now looks something like:
0:f(ellow),1
f(hel)
1:h(ell),2
h(ello)
5:o(ne),6
- at the next step:
0:fh(el),2
1:f(ellow),2
etc...

string findWordWithMinimalDeleting(const string& input, TrieItem* dict) 
{
	priority_queue<PrioQItem, vector<PrioQItem>, PQItemLess> q;
	int n = input.length();

	// initialize priority queue	
	q.push(PrioQItem(0, 0, dict)); 

	while(q.size() > 0)
	{
		TrieItem* cti = q.top().tItem; // current trie item
		int i = q.top().index; // index in input string
		int p = q.top().prio; // prio = delete char counter
		q.pop(); // remove item
		if(i == n) return cti->word(); // if we matched all and it's word
		TrieItem* ntim = cti->getNext(input[i]);
		if(ntim != nullptr)  
		{ 	// next trie itme if match
			q.push(PrioQItem(p, i + 1, ntim));
			if(ntim->isWord()) 
			{
				q.push(PrioQItem(p + n - i - 1, n, ntim));				
			}
		}
		while(i < n - 1) 
		{	// try by deleting up to the end and create branch if 
			// there is continuation in the trie
			TrieItem* ntid = cti->getNext(input[i + 1]);
			if(ntid != nullptr) 
			{
				q.push(PrioQItem(p + 1, i + 2, ntid));
			}
			i++;
			p++;
		} 
	}
	return string("");
}

I assume the delete "in order" is a hint that tells you
if your search string is "Hellzuo" and you decide to
delete the "z" for your second delete only "u" and "o"
are options...

complete code:

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

// primitive, unoptimized trie with mem. leak etc.
class TrieItem
{
private:	
	unordered_map<char, TrieItem*> next_;
	string word_ = ""; // simplification, should be only a flag
	char letter_;

public:
	TrieItem() : TrieItem('\0') { }
	TrieItem(char letter) : letter_(letter) { }

	void addWord(const string& word) { addWord(word, 0); }
	TrieItem* getNext(char letter) 
	{
		auto it = next_.find(letter);
		if(it != next_.end()) return it->second;
		return nullptr;
	}
	bool isWord() const { return word_.length() > 0; }
	string word() const { return word_; }
	char letter() const { return letter_; }

private:
	void addWord(const string& word, int index)
	{
		if(index == word.length())
		{ 
			word_ = word.substr(0, index + 1);
		}
		else
		{
			auto it = next_.find(word[index]);
			TrieItem *item;
			if(it != next_.end())
			{ 
				item = it->second;
			}
			else
			{ 
				item = new TrieItem(word[index]);
				next_[word[index]] = item;
			}
			item->addWord(word, index + 1);
		}
	}
};

// priority queue item
struct PrioQItem 
{
	int prio;
	int index;
	TrieItem* tItem;

	PrioQItem(int p, int i, TrieItem* ti) 
		: prio(p), index(i), tItem(ti) {}
};

// priority queue less predicate 
struct PQItemLess
{
	bool operator() (const PrioQItem& a, const PrioQItem& b) const 
	{
		return a.prio > b.prio;
	}
};

string findWordWithMinimalDeleting(const string& input, TrieItem* dict) 
{
	priority_queue<PrioQItem, vector<PrioQItem>, PQItemLess> q;
	int n = input.length();

	// initialize priority queue	
	q.push(PrioQItem(0, 0, dict)); 

	while(q.size() > 0)
	{
		TrieItem* cti = q.top().tItem; // current trie item
		int i = q.top().index; // index in input string
		int p = q.top().prio; // prio = delete char counter
		q.pop(); // remove item
		if(i == n) return cti->word(); // if we matched all and it's word
		TrieItem* ntim = cti->getNext(input[i]);
		if(ntim != nullptr)  
		{ 	// next trie itme if match
			q.push(PrioQItem(p, i + 1, ntim));
			if(ntim->isWord()) 
			{
				q.push(PrioQItem(p + n - i - 1, n, ntim));				
			}
		}
		while(i < n - 1) 
		{	// try by deleting up to the end and create branch if 
			// there is continuation in the trie
			TrieItem* ntid = cti->getNext(input[i + 1]);
			if(ntid != nullptr) 
			{
				q.push(PrioQItem(p + 1, i + 2, ntid));
			}
			i++;
			p++;
		} 

	}
	return string("");
}

int main()
{
	TrieItem trie;
	trie.addWord("fellow");
	trie.addWord("hello");
	trie.addWord("one");
	trie.addWord("hell");
	trie.addWord("fhel");

	cout << "the word is \"" << findWordWithMinimalDeleting("fhellowne", &trie) << "\"" << endl;
}

/*
Solution:
- the powerset is the set of all subsets
- all or no element can be part of and all combination
- per element two possibilities: be part of or not, 2 elements
  so 2^n possibilities

How to compute:
lets assume the set is given as a string:
*/

#include <iostream>
#include <string>

using namespace std;

void printPowersetRec(const string& prefix, 
					  const string& remaining)
{
	
	if(remaining.length() == 0) 
	{ 
		cout << "{" << prefix << "} ";
	}
	else 
	{
		string newRemaining = remaining.substr(1);
		string newPrefix = prefix;
		newPrefix.append(1, remaining[0]);
		printPowersetRec(prefix, newRemaining); // included
		printPowersetRec(newPrefix, newRemaining); // excluded
	}	 
}

void printPowerset(const string& input)
{
	printPowersetRec("", input);
}

int main()
{
	printPowerset("ABCD");
}

/*
Assumptions:
- He means add characters to the front 
  of the given input to form a palindrome.
- Instead of "bcabc" he meant "cbabc" because
  "bcabc" is not a palindrome  
- I assume, he as well means inserting minimum characters,
  because it would otherwise just being addinig
  n - 1 characters assuming the character at 
  position 0 of input is the middle character, which
  would satisfy all the samples and description.
- Because of the many assumptions, I add a simplification
  to only consider "odd-size" palindromes (which have 
  mirror character, -> do not mirror in-between characters)

Solution O(n^2)
- Adding minimal amount to the front, means finding 
  the longest palindrome that mirrors the front part 
  of the input completely.
  e.g. "abzbahik" would be "abzba" "hik" needs to be 
  reversed and inserted at the front  
- Then "insert" the missing characters to the front
- There is a O(n) solution for finding the palindrome
  you may look it up, I didn't include it here...
*/

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string extendPalindrome(const string& input)
{
	if(input.length() <= 1) return input;

	// find mirror point (as mentioned only consider odd palindrome for simplicity)
	int pos = 0;
	for(int i = 1; i <= input.length() / 2; i++) // i: mirror point
	{		
		for(int j = 1; i + j < input.length() && i - j >= 0; j++)
		{
			if(input[i + j] != input[i - j]) break;
			if(j == i) pos = i;				
		}
	}

	// insert at beginning
	int rem = input.length() - (pos + pos + 1);
	if(rem == input.length()) return input;
	string result = input.substr(pos + pos  + 1, rem);
	reverse(result.begin(), result.end());
	result.append(input);
	return result;
}

int main()
{
	cout << "a: " << extendPalindrome("a") << endl; 
	cout << "ab: " << extendPalindrome("ab") << endl; 
	cout << "abc: " << extendPalindrome("abc") << endl; 
	cout << "bazabc: " << extendPalindrome("bazabc") << endl; 
	cout << "cbazabc: " << extendPalindrome("cbazabc") << endl; 
}
/* output 
a: a
ab: bab
abc: cbabc
bazabc: cbazabc
cbazabc: cbazabc
*/

I assume it's a level order traversal where you build two sums, one of even levels and one of odd. levels
I used a nullptr as a marker element to seperate levels in the queue, tiny trick is to ensure the termination
works.

int maxLevelSum(Node *root) 
{
	queue<Node*> q;
	q.push(root);
	q.push(nullptr);
	int level = 0;
	int sums[2]{0, 0};
	while(q.size() > 0)
	{
		Node *current = q.front(); q.pop();
		if(current == nullptr) 
		{ 
			level ^= 1;
			if(q.size() > 0) q.push(nullptr);
			continue;
		}
		sums[level] += current->value;
		if(current->left != nullptr) q.push(current->left);
		if(current->right != nullptr) q.push(current->right);
	}
	return max(sums[0], sums[1]);
}

oops ;-) NoOne is right, here my update, maybe it helps
to understand the recursion although everything has already been
said by NoOne that's worthwhile.

Recap of question:
- it asks how many hop combinations are possible to go the distance of n steps
- a hop can be either 1,2 or 3 steps
- hoping 2-1 is not the same as 1-2

therefore we can express is recursively:
S(n) = S(n-1) + S(n-2) + S(n-3)

I thought of it as follows, let S(n) be the # of combinations
to go n steps
a) to go n+3 is the S(n+2) + the hop with distance 1
b) to go n+3 is the S(n+1) + the hop with distance 2
c) to go n+3 is the S(n) + the hop with distance 3
d) S(n+3) = S(n) + S(n+1) + S(n+2)
<=> S(n) = S(n-3) + S(n-2) + S(n-1)

it can be computed recursively if you memoize in O(n), otherwise
big-O of S < big-O of T(n) = 3*T(n-1) = O(3^n) (closer bound
is possible with the master theorem or a more complex prove)

iterative computation will be something like Fibonacci:

int combinations(int n)
{
  if(n<=1) return 1;
  if(n==2) return 2;
  if(n==3) return 3;
  int sn_3 = 1;
  int sn_2 = 2;
  int sn_1 = 3;
  int s = 0;
  for(int i=3; i<=n; i++) {
    s = sn_3 + sn_2 + sn_1;
    sn_3 = sn_2;
    sn_2 = sn_1;
    sn_1 = s;      
  }
}
return s;

what are the total number of possible combination?
- is 1-2-3 equal 2-1-3? (does order matter?)
- is 3-3-1 equal 3-2-2? (same distance?)

there are 3^n combination if order matters

the longest path will be from a leave to an other leave or from a leave to the root. So, all inner nodes, except the root are not the end points.
One way to find it, is to go from each leave upwards, storing the max. distance to a leave for each subtree and maximize left+right+1 at each node. This takes O(n) time and O(n) space.

/*
Solution:
- looks like from hackerrank/topcoder, sure it was an interview?
- if you are at position (x,y) you can go either
  to (x+1,y) or (x,y+1) both has an assosiated cost depending on
  the direction you will be looking (0,1) where 0 means facing down
  and 1 facing to the right:
  - if you come from the left field, you will look right and only cost
    is move cost
  - if you come from top you will look down only cost is move
    cost
  - if facing right is cheaper when coming from top + 
    turning, use this cost
  - same from coming from left + turning for facing down
  so, there are two cost per field, one is reaching it facing
  down and the other is reaching it and facing right.
  ...
- The O(n*m) iterative solution is as follows:
  - c(d,x,y) denotes the cost at field x,y facing d: (d=0: down, d=1: 
    right), 0 <= x < M, 0 <= y < N	
	for(int y = 0; y < M; y++)
		for(int x = 0; x < N; x++)
			int c0 = MAX;
			int c1 = MAX;
			if(x > 0) 
			{
				c1 = c[1][y][x-1] + move_cost[y][x];
				c0 = c1 + turn_cost[y][x];
			}
			if(y > 0)
			{
				c0 = min(c0, c[0][y-1][x] + move_cost[y][x])
				c1 = min(c1, c0 + turn_cost[y][x])
			}
			if(x == 0 && y == 0) 
			{ // start case
				c0 = 0;
				c1 = 0;
			}
			c[0][y][x] = c0;
			c[1][y][x] = c1;
	
	return min(c[0][N-1][M-1], c[1][N-1][M-1]);

	complete solution in c++11:
*/

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <cassert>
#include <limits>

using namespace std;

int findMinCostToTraverseWithTurn(const vector<vector<int>>& move_cost, const vector<vector<int>>& turn_cost) 
{
	assert(move_cost.size()  > 0 && turn_cost.size() == move_cost.size());
	assert(move_cost[0].size()  > 0 && turn_cost[0].size() == move_cost[0].size());
	int n = move_cost.size();
	int m = move_cost[0].size();

	vector<vector<vector<int>>> c(2, 
		vector<vector<int>>(n,
		vector<int>(m, numeric_limits<int>::max())));

	// start case
	c[0][0][0] = 0;
	c[1][0][0] = 0;

	for(int y = 0; y < n; y++)
	{
		for(int x = 0; x < m; x++)
		{
			if(x > 0) 
			{
				c[1][y][x] = c[1][y][x - 1] + move_cost[y][x];
				c[0][y][x] = c[1][y][x] + turn_cost[y][x];
			}
			if(y > 0)
			{
				c[0][y][x] = min(c[0][y][x], c[0][y - 1][x] + move_cost[y][x]);
				c[1][y][x] = min(c[1][y][x], c[0][y][x] + turn_cost[y][x]);
			}
			// cout << "(" << c[0][y][x] << "," << c[1][y][x] << ") ";
		}
		// cout << endl;
	}
	return min(c[0][n - 1][m - 1], c[1][n - 1][m - 1]);
}


int main()
{
	vector<vector<int>> move_cost { 
		{0,1,2},
		{1,2,1},
		{2,1,2}
	};
	vector<vector<int>> turn_cost { 
		{0,2,3},
		{1,0,1},
		{0,0,1}
	};
	cout << findMinCostToTraverseWithTurn(move_cost, turn_cost);
}

/*
Clarification: 
input intervals are half open "[)"

Solution:
there are two fundamental different approaches I considered:
1) sorting the intervals, start with i = 0:
   - the interval i turns it on
   - it stays on as long as there are intervals j > i that 
     start before the last end time of all intervals [i..j]
   - i = j + 1, repeat until i >= n

   this is O(lg(n)) time and O(1) space

2) if we know we care only about 24 hours and the time resolution 
   is an hour, we can create a come / leave array and count the 
   hours where more than 0 people are in the room:
   - create array a[0..23] initialize with 0, 
     peopleintheroom = 0, usedHours = 0
   - for each interval: a[start]++ a[end]--
   - for i = 0 to 23: 
    	peopleintheroom += a[i]
		if(peopleintheroom > 0) usedHours++

   this is still O(1) space, if its always 24 hours ... and 
   O(n) runtime where n is the number of intervals in the input    

1) is better if there are generally fewer than h*lg(h) intervals 
   where h is the number of time slices the potential interval 
   range is divided into (e.g. 24 hours) 
2) is better if memory is not an issue and there are many more 
   intervals than time slices  
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cassert>

using namespace std;

// helper struct to deal with interval
struct Interval
{
	int start_;
	int end_;

	Interval() : Interval(0, 0) { }
	Interval(int start, int end) : start_(start), end_(end) { }
};

// Option 1)
int getUsedHours(const vector<Interval>& ivals)
{
	vector<Interval> intervals(ivals);
	sort(intervals.begin(), intervals.end(), 
		[](const Interval& a,  const Interval& b) { return a.start_ < b.start_; });

	int i = 0;
	int totalHours = 0;
	while(i < intervals.size())
	{
		int start = intervals[i].start_;
		int end = intervals[i].end_;
		i++;
		while(i < intervals.size() && intervals[i].start_ < end)
		{
			end = max(end, intervals[i].end_);
			i++;
		}
		totalHours += end - start;
	}
	return totalHours;
}

// Option 2)
int getUsedHoursLin(const vector<Interval>& ivals)
{
	vector<int> change(24, 0);

	for(Interval i : ivals) 
	{
		assert(i.start_ < i.end_ && i.end_ < 24);
		change[i.start_] ++;
		change[i.end_] --;
	}

	int hours = 0;
	int p = 0;
	for(int c : change)
	{
		p += c;
		if(p > 0) hours++;
	}

	return hours;
}

int main()
{
	cout << "case 1 with sort: " << getUsedHours(vector<Interval>{ {1, 4}, {2, 3}}) << endl;
	cout << "case 2 with sort: " << getUsedHours(vector<Interval>{ {4, 6}, {1, 2} }) << endl;
	cout << "case 3 with sort: " << getUsedHours(vector<Interval>{ {1, 4}, {6, 8}, {2, 4}, {7, 9}, {10, 15}}) << endl;

	cout << "case 1 linear: " << getUsedHoursLin(vector<Interval>{ {1, 4}, {2, 3}}) << endl;
	cout << "case 2 linear: " << getUsedHoursLin(vector<Interval>{ {4, 6}, {1, 2}}) << endl;
	cout << "case 3 linear: " << getUsedHoursLin(vector<Interval>{ {1, 4}, {6, 8}, {2, 4}, {7, 9}, {10, 15}}) << endl;			
}

/*
Solution in O(N) runtime and O(1) space
1) step through the list to determine the size
2) invert 2nd half of the list
3) shuffle together
*/

#include <iostream>

struct Item
{
	Item* next_;
	int value_;
	Item(int value, Item* next) : next_(next), value_(value) { }
};

size_t getSize(Item* item);
Item* getKthItem(Item* item, size_t k);
Item* invertList(Item* item);
void printList(Item* item);

void shuffleList(Item* item)
{
	size_t n = getSize(item);
	if(n <= 2) return;
	Item* lastFirstHalf = getKthItem(item, n / 2 - 1);	
	Item* lastSeconHalf = lastFirstHalf->next_; 
	Item* secondHalf = invertList(lastSeconHalf);
	Item* firstHalf = item;
	lastFirstHalf->next_ = nullptr;
	while(firstHalf != nullptr) {
		Item* current = firstHalf;
		firstHalf = firstHalf->next_;
		current->next_ = secondHalf;
		secondHalf = secondHalf->next_;
		current->next_->next_ = firstHalf;
	}
}

int main()
{
	Item *list = new Item(1, 
				new Item(2, 
				new Item(3, 
				new Item(4,
				new Item(5,
				new Item(6, nullptr))))));
	shuffleList(list);
	printList(list);
}

Item* invertList(Item* item)
{
	Item* prev = nullptr;
	Item* next = nullptr;
	while(item != nullptr) {
		next = item->next_;
		item->next_ = prev;		
		prev = item;
		item = next;
	}
	return prev;
}

Item* getKthItem(Item* item, size_t k) {
	while(k > 0 && item != nullptr) {
		item = item->next_;
		k--;
	}
	return item;
}

size_t getSize(Item* item) {
	size_t size = 0;	
	while(item != nullptr) {
		item = item->next_;
		size++;
	}
	return size;
}

void printList(Item* item)
{
	while(item != nullptr) {
		std::cout << item->value_ << " ";
		item = item->next_;
	}
}

/*
	Assumptions:
	- no cylces exist
	- no multiple disconnected components (forest of max 1 tree)

	Solution:
	- we want to print a tree, post-order traversal
	  should do it
	- the representation as graph allows for cycles
	- finding the root is required

	1) find the root:
	   traverse all items and count incoming edges
	   with -1 and the fact that there are any outgoing
	   edges with +1
	   --> the root will have count +1
	   --> if there are several vertices with +1, multiple
	       disconnected components exist
	
	2) on the single root (see assumption) perform a DFS
	   and print the employee, maintaining the level in the
	   hirarchy (traversal depth) in the stack
*/

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <utility>
#include <stack>

using namespace std;

void printEmployee(string name, int indent); 

// doesn't handle multiple disconnected components right 
string findRoot(unordered_map<string, vector<string>> input) 
{
	unordered_map<string, int> fr;
	for(auto e : input) 
	{
		fr[e.first]++;
		for(auto e2 : e.second) fr[e2]--;
	}
	
	for(auto e : fr) if(e.second == 1) return e.first;
	return string("");
}

void printEmployeeStructure(unordered_map<string, vector<string>> input) 
{
	string current = findRoot(input);
	if(current.length() == 0) 
	{
		cout << "error cyclic" << endl;
		return;
	}

	// perform a DFS and do cycle detection
	stack<pair<string, int>> s;
	unordered_set<string> visited; 
	s.push(pair<string, int>(current, 0));	
	while(s.size() > 0)
	{
		pair<string, int> u = s.top();
		s.pop();
		if(visited.find(u.first) != visited.end()) 
		{
			cout << "error cycle" << endl;
			break;
		}
		visited.insert(u.first);
		printEmployee(u.first, u.second);
		for(auto v : input[u.first]) // inefficient if input[u.first] doesn't exist
		{
			s.push(pair<string, int>(v, u.second + 1));
		}
	}
}

int main()
{
	unordered_map<string, vector<string>> input;
	input["AAA"] = vector<string>({"BBB", "CCC", "EEE"});
	input["CCC"] = vector<string>({"DDD"});
	// input["EEE"] = vector<string>({"AAA"}); // cycle on root 
	// input["BBB"] = vector<string>({"CCC"}); // cycle within structure
	
	printEmployeeStructure(input);
}

void printEmployee(string name, int indent)
{
	for(int i=0; i<indent; i++) cout << " ";
	cout << "-" << name << endl;
}

What does it mean "you are not allowed to traverse the tree"?
I assume it means you are not allowed to walk the tree node-by-node to get the k-th element or to calculate the sum (so no O(n) solution...)

1) how to find the kth element
if the tree is very large, finding the k-th element with in-order traversal is slow. It takes O(k). Faster is, if you store on each node the size of the subtree and modify the in-order traversal to skip whole subtrees if theire size is larger than k-remaining, this takes O(lg(n)), where n is the
number of nodes (it becomes a pre-order traversal, BST assumed to be balanced):

2) how to calculate the sum
Similar to 1) maintain the sum of the subtree, in addition of the tree-size, per nodes. Now the whole tree is the sum of all nodes. Everytime you skip a subtree, you remove that subtree's
sum from the current sum:

long long getRemainingSum(Node* node, int k)
{
	long long currentSum = node->treeSum;
	stack<pair<Node*, bool>> s;
	s.push(pair<Node*, bool>(node, false));
	while(s.size() > 0) {
		Node *c = s.top().first; 
		if(c->treeSize == k) return currentSum;
		if(c->treeSize < k) {
			// subtree can be jumped over
			k -= c->treeSize;
			currentSum -= c->treeSum;
			s.pop();
		} else if(!s.top().second) {
			// go first left
			s.top().second = true;
			if(c->left != nullptr) s.push(pair<Node*, bool>(c->left, false));
		} else {
			// go right
			s.pop();
			if(c->right != nullptr) s.push(pair<Node*, bool>(c->right, false));			
		}
	}
	return -1; // assume -1 clearly indicates k is out of range
}

3) This requires two additional fields per Node, so space complexity is O(n). Time complexity
is therefore O(lg(n)). In addition all tree operations must maintain this additional fields which has no impact on the big-O of the run-time of insert, delete, update of known self-balancing BSTs like RGB, AVL, 2-3 etc. Further it's worth mentioning it only makes sense if the tree is roughly balanced...

/*
A producer continuously produces a stream of characters. 
There are multiple consumer threads which read the chars
and match to one of known strings and increment the counter
for that pattern. Write the consumer function. 
Show how you will synchronize and maintain parallelism. 

Ex: Producer: abcdegabccaabbaacv ...... 
Known strings[] = {"ab", "aa", "fff" ... } 
patternMatchCount[] = {3, 2, 0 ... }

/*
Solution:
1) Clarification of patternMatchcount is required: do overlaping 
   patterns count or not: e.g. in "AAA" how many times does "AA"
   occure 1 or 2 times? assumption: 2, overlaping counts

2) The syncronization can depend on the pattern matching approach:
   a) The use of brute force or Rabin-Karp requires to hold
      a buffer of length of the pattern to verify if it's a
	  match.
	  Such a buffer can be held by each consumer-thread which
	  can be efficient in terms of synchronization but inefficient
	  in terms of memory usage (if there are a lot of patterns)
   b) If it's automaton based, no buffer is required. Automaton
      based is preferable, but much more complicated to implement
	  (I doubt it is expected to derive the algorithm in an 
	  interview...)

3) For simplicity I would assume the first implementation is that
   each consumer has his own buffer and later on I would correct
   this with an automaton based approach.

4) Synchronization in this case is now, the producer has to 
   push a character to all consumers, this can be done using
   a waitable queue. The waitable queue will be inefficient 
   in terms of syncrhonization needed and because it may 
   dynamically create items, thus a critical section is 
   held over a heap allocation etc...   
   
   It could be improved
   with a lockless buffer which is going to be quite tricky 
   to implement in a non-managed language such as C++ if 
   multicore support is required. If you're not a hard core
   C++ low level programmer with experience in writing drivers
   and lockless stuff it's maybe a good idea to point out 
   that you wont get it error-free and efficient.

5) An other thing to consider is how the system shuts down
   once the producer decides to terminate (reaches the end of 
   the input stream)  

   Here the rather messy code in C++ 11
*/

#include <memory>
#include <iostream>
#include <string>
#include <queue>
#include <thread>
#include <mutex>
#include <condition_variable>

using namespace std;

class WaitableQueue
{
private:
	mutex mutex_;
	condition_variable signal_;
	queue<char> queue_;

public:
	void push(char item) 
	{
		{
			unique_lock<mutex> cs(mutex_);
			queue_.push(item);
		}
		signal_.notify_one();
	}

	char pop() 
	{
		unique_lock<mutex> cs(mutex_);
		signal_.wait(cs, [&](){ return queue_.size() > 0; });
		char result = queue_.front(); 
		queue_.pop();
		return result;
	}	
};

class Consumer
{
private:
	WaitableQueue queue_;
	string pattern_;
	string buffer_;
	int bufferEnd_;
	int counter_;
	thread thread_;

public:
	Consumer(const string& pattern) : counter_(0), 
		bufferEnd_(0), pattern_(pattern)
	{ 
		thread_ = thread([&]{
			while(true) {
				char item = queue_.pop();
				if(item == '\0') break; // end signal
				if(matchNext(item)) counter_++;
			}
		});
	}

	WaitableQueue* getQueue() { return &queue_; }	
	int getCounter() const { return counter_; } 
	string getPattern() const { return pattern_; }
	void join() { thread_.join(); }

private:
	bool matchNext(char next) 
	{
		// this match code is inefficient, improvements possible 
		// by using Rabin-Karp or an automaton based approach
		int m = pattern_.length();
		if(buffer_.length() < bufferEnd_ + 1) buffer_.append(1, next);
		else buffer_[bufferEnd_] = next;
		bufferEnd_ = (bufferEnd_ + 1) % m;
		bool match = buffer_.length() == m; 
		for(int i = 0; i < m && match; ++i) 
			match = buffer_[(bufferEnd_ + i) % m] == pattern_[i]; 
		return match;
	}
};

class Producer
{
private:
	vector<WaitableQueue*> queues_;
	string input_;
	thread thread_;

public:
	Producer(const vector<WaitableQueue*>& queues, const string& input) 
		: queues_(queues), input_(input)
	{
		thread_ = thread([&] {
			// send input
			for(auto ch : input_) { 
				for(auto co : queues) co->push(ch);
			}
			
			// signal end of input
			for(auto co : queues) co->push('\0');		
		});
	}

	void join() { thread_.join(); }	
};


int main()
{
	// create consumers
	vector<Consumer*> consumers({
		new Consumer("ab"),
		new Consumer("aa"),
		new Consumer("ffff")
	});
	
	// get queues from consumers
	vector<WaitableQueue*> queues;
	for(auto& co : consumers) queues.push_back(co->getQueue());

	// create producer
	Producer p(queues, "abcdegabccaabbaacv");
	
	// wait for producer
	p.join();	

	//  wait and print result of consumer
	for(auto& co : consumers) {
		co->join();
		cout << "pattern: " << co->getPattern() 
			<< " count: " 
			<< co->getCounter() << endl;
	}
}

/*
Note: 
- it's a linked list, not double linked
- the list is altered, so, one should do it in place
- best conceivable runtime is O(n)

Solution in O(N) runtime and O(1) space
1) step through the list to determine the size
2) invert 2nd half of the list
3) shuffle together
*/

#include <iostream>

struct Item
{
	Item* next_;
	int value_;

	Item(int value, Item* next) 
		: next_(next), value_(value) { }
};

size_t getSize(Item* item);
Item* getKthItem(Item* item, size_t k);
Item* invertList(Item* item);
void printList(Item* item);

void shuffleList(Item* item)
{
	size_t n = getSize(item);
	if(n <= 2) return;
	Item* lastFirstHalf = getKthItem(item, n / 2 - 1);	
	Item* lastSeconHalf = lastFirstHalf->next_; 
	Item* secondHalf = invertList(lastSeconHalf);
	Item* firstHalf = item;
	lastFirstHalf->next_ = nullptr;
	while(firstHalf != nullptr) {
		Item* current = firstHalf;
		firstHalf = firstHalf->next_;
		current->next_ = secondHalf;
		secondHalf = secondHalf->next_;
		current->next_->next_ = firstHalf;
	}
}

int main()
{
	Item *list = new Item(1, 
				new Item(2, 
				new Item(3, 
				new Item(4,
				new Item(5,
				new Item(6, nullptr))))));
	shuffleList(list);
	printList(list);
}

Item* invertList(Item* item)
{
	Item* prev = nullptr;
	Item* next = nullptr;
	while(item != nullptr) {
		next = item->next_;
		item->next_ = prev;		
		prev = item;
		item = next;
	}
	return prev;
}

Item* getKthItem(Item* item, size_t k) {
	while(k > 0 && item != nullptr) {
		item = item->next_;
		k--;
	}
	return item;
}

size_t getSize(Item* item) {
	size_t size = 0;	
	while(item != nullptr) {
		item = item->next_;
		size++;
	}
	return size;
}

void printList(Item* item)
{
	while(item != nullptr) {
		std::cout << item->value_ << " ";
		item = item->next_;
	}
}

I would solve it using BFS starting from both friends simultaneously instead of just from one friend.

Further I would ask if it's allowed to stop if, e.g. there is no connection of 4th or 5th grade. Let's assume everybody has 80 new friends in average:
- After expanding the frontier 4 times, starting at one friend there are ~40 Mio people covered.
- If expanding 2 times, starting at both friends, there are roughly 13 tousand people and it has the same effect.
If not terminating after a certain search depth, it eventually ends up hitting a lot of people.

Further accelleration for the positive case may be possible by using some heuristic to expand the frontier asymetrically towards the expexted other person (this how ever will then no guarantee to find the shortest path in the sense of # of hops and from here it starts to get philosophical)

EDITED 22.11.'16
I went through everything again, it took much more than 45 minutes.
/*
Assumption and sumary:
- the enemeis have to be fought in order (1st, 2nd, ...) order isn't 
  free to choose
- assume to maximize on money after fighting all enemies

Approach:
- dp(i, s, m) = max money at i, after proceeding through i-th enemy 
- s = remaining strength at i, s0 is given
- m = remaining money at i, m0 is given 
- s[i] = strength used to fight enemy i (0 <= s[i])
- m[i] = money used to bribe enemy i (0 <= m[i])
- game starts with dp(0, s0, m0)

Recursion:                                         
                   / dp(i+1, s-s[i], m)        , if s >= s[i]
dp(i, s, m) = max /  dp(i+1, s+s[i], m - m[i]) , if m >= m[i]
                  \  = -1, if m < m[i] and s < s[i]
				   \ = m0, if i == n-1

Prove of NP-completness: let's try to deduce knap-sack to 
this problem:
	The knapsack recursion:    
	dp(i, space) = 	
	  max / dp(i+1, space-size[i])+value[i], if size[i]<=space 
	      \ dp(i+1, space) 
    
    The problem (1) is a knap-sack problem (2):
	- 1: if we fight an enemy we use strength
	  2: if an item is included, it uses space
	- 1: if we can't fight an enemy due to lack of strength, 
	     we have to us money
	  2: if the item doesn't fit into the bag, we "loose"
	     the value of the item
	- 1: if we bribe an enemy, we gain strength
	  2: if we leave an item behind, we do not use space
	     actually we have to modify this to, if an item is 
		 left behind, it will make additional space in the
		 knap-sack (which is totally not real-world)	     
	  2: Additions needed on knapsack:
		 - an item can only be excluded if the total
		   value of excluded items is not higher than
		   a given arbitrary value
		 - pack the items in order and an item that 
		   is not packed increases the space of the 
		   knap-sack

	or the other way around, if we wouldn't add the strength
	of a bribed enemy, order wouldn't matter and we had a pure 
	knap-sack problem. 

	Concluding, this problem is at least as hard as knap-sack 
	and thus it is NP-complete.

A pseude polynomial algorith for knap-sack exists. 
That is exponential in the number of bits used to represent 
the space of the knap-sack - thus polynomial to the actual 
space. 

our initial recursion was:
                   / dp(i+1, s-s[i], m)        , if s >= s[i]
dp(i, s, m) = max /  dp(i+1, s+s[i], m - m[i]) , if m >= m[i]
                  \  = -1, if m < m[i] and s < s[i]
				   \ = m0, if i == n-1

while writing this with memoization is okay, there is a problem with
it:
  a subproblem is only reused if it has the exact same strength and 
  money at a certain position. It would be better, 
  if we do not consider solutions that lead to less
  money at the same strength level at a certain index i.

An iterative approach can solve it:
  create an array dp of size n + 1 (n=amount of enemeies)
  every entry has an array reaching from 0..MAX-STRENGTH
  that entry carries the max-money for that strength

  then initialize that first array with the start condition that is:
  dp[0][0..s0] = m0;
  dp[0][s0+1..MAX_STRENGTH+1] = -1;

  int maxmoney = -1;
  for(i = 0; i < n; i++)
  {
	  int s = s[i]; // strength of the enemy
	  int m = m[i]; // cost to bribe it
	  
	  maxmoney = -1;
	  for(int j = MAX_STRENGTH; j >= 0; j++)
	  {
	      if(j >= s) maxm = max(maxm,  dp[i][j - s] - m); // bribe				
		  if(j <= MAX_STRENGTH - s) maxm = max(maxm, dp[i][j + s]); // fight
		  dp[i + 1][j] = maxm; // note, the money will be reused as "higher bar" 
		                       // for less strength case 
	  }	  
  }

  maxmoney contains the result

  this code can further be optimized:
  1) there is no need for MAX_STRENGTH as we can dynamically calculate it at every step and only use
     as much
  2) we do not need a matrix on space, but only the last result and the current result, so 
     two alternating buffers are okay, see implementation below  

  runtime: O(n*MAX_STRENGTH)
  space (optimized): O(MAX_STRENGTH)
*/

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

// iterative version, turns out to be very similar to knap-sack
// iterative approach
class MaximizeMoney_Iterative
{
private:	
	vector<int> strength_;
	vector<int> money_;
	int steps_; // calculation step counter
	int maxMoney_;

public:
	int getSteps() const { return steps_; }
	int getMaxMoney() const { return maxMoney_; }  

	void solve(const vector<int>& money, const vector<int> strength, int m0, int s0)
	{
		steps_ = 0;
		strength_ = strength;
		money_ = money;
		
		vector<vector<int>> dp(2, vector<int>());
		for(int j = 0; j <= s0; j++) dp[0].push_back(m0);

		int maxm = -1; // max money at step i		
		for(int i = 0; i < strength_.size(); i++)
		{
			int s = strength_[i]; // strength of the enemy
			int m = money_[i]; // cost to bribe it
			int maxs = dp[i & 1].size() + s  - 1;
			maxm = -1;
			dp[(i + 1) & 1].clear(); 
			for(int j = maxs; j >= 0; j--)
			{
				if(j >= s) maxm = max(maxm,  dp[i & 1][j - s] - m);				
				if(j < dp[i & 1].size() - s) maxm = max(maxm, dp[i & 1][j + s]);
				if(maxm >= 0)
				{
					if(dp[(i + 1) & 1].size() == 0)
					{ 
						dp[(i + 1) & 1] = vector<int>(j + 1, 0);
					}
					dp[(i + 1) & 1][j] = maxm;
				}
				steps_ ++;
			}
		}

		maxMoney_ = maxm;
	}	
};

// the recursive version with memoization, much harder to analyze
// and understand
class MaximizeMoney_RecursiveMemo
{
private:	
	vector<int> strength_;
	vector<int> money_;
	unordered_map<int, int> memo_;
	int steps_; // calculation step counter
	int maxMoney_;

public:
	int getSteps() const { return steps_; }
	int getMaxMoney() const { return maxMoney_; }  

	void solve(const vector<int>& money, const vector<int> strength, int m0, int s0)
	{
		steps_ = 0;
		memo_.clear();
		strength_ = strength;
		money_ = money;
		maxMoney_ = maxMoney(0, m0, s0);
	}

private:
	int maxMoney(int i, int m, int s)
	{
		if(m < 0 || s < 0) return -1;
		if(i == strength_.size()) return m; // through..

		int key = createKey(m, s, i);
		auto mi = memo_.find(key);
		if(mi != memo_.end()) return mi->second;
			
		steps_++; // count calculation steps 
		int res = max(maxMoney(i + 1, m - money_[i], s + strength_[i]), 
					maxMoney(i + 1, m, s - strength_[i]));

		memo_[key] = res;
		return res; 
	}

	static int createKey(int m, int s, int i)
	{
		assert((s < 1024) && (m < 1024) && (i < 1024));
		return (s << 20) | (m << 10) | i;
	}
};


void runCase(const string& tcase, const vector<int>& s, const vector<int>& m, int m0, int s0)
{
	MaximizeMoney_RecursiveMemo mmr;	

	cout << "\n" << tcase << endl;
	cout << "  problem has at most " << (1ULL << s.size()) << " combinations " << endl; 
	mmr.solve(m, s, m0, s0);
	cout << "  recursive algo with memoization solved in #steps:" << mmr.getSteps() << " money@end:" << mmr.getMaxMoney() << endl;

	MaximizeMoney_Iterative mmi;
	mmi.solve(m, s, m0, s0);
	cout << "  iterative algo solved in #steps:" << mmi.getSteps() << " money@end:" << mmi.getMaxMoney() << endl;	
}


int main()
{
	runCase("simple case 1",
		{1, 2, 1, 4, 2, 3, 1, 5, 6, 7, 8, 1, 2, 3, 5, 3, 5, 3, 2, 1},
		{5, 4, 1, 2, 3, 7, 8, 1, 2, 3, 4, 2, 6, 1, 3, 1, 6, 5, 3, 2},
		16, 6);

	runCase("simple case 2",
		{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
		100, 100);  

	runCase("simple case 3",
		{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		50, 50);  

/* output:
simple case 1
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:834 money@end:4
  iterative algo solved in #steps:486 money@end:4

simple case 2
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:2838 money@end:84
  iterative algo solved in #steps:3188 money@end:84

simple case 3
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:2647 money@end:14
  iterative algo solved in #steps:2859 money@end:14
*/
}

Assumption: "if a repetition, shoud not store it" means only store the number once, if repetition should flag the number as not being printed, below discussion requires double the memory.

1. Option, big-O-optimized version:
- Store the numbers in a bit-vector, that is aprox 1.3 MB of Memory for range 1-10 Mio
since 1 - 10 Mio is given this is O(1) ...
- Printing, iterate over 1..10Mio and print the number if flagged, this is O(1), too

If this fits into memory, is it better than storing a btree or something on disc? It most certainly is, because we insert n times, and printing requires about 160'000 iterations over a 64 bit integer and only needs to drill into the integer if it is not 0. This is all in data and execution cache.

If only a few numbers, like 10000 or so occure before -1, it is slower. Depending on the memory size, we could optimize the small amount of numbers with some sort of tree and throw the tree away as soon as we exceed a certain amount of numbers.

Going to disc is an alternative, there it makes sense to create a number of files with fixed size (according to the available memory), each sorted and merge sort them when printing on the fly. This solution now is O(n) because we create constant size files and sort them which is O(1) due to the constant but we require to traverse each number when printing (whether it was a dublicate or not).

Conclusion:
if n is expected to be > 100'000 (or even >> 10 Mio) and almost uniform: use bitfield if oyu can afford that memory.
if n is >> 10 Mio: use bitfield on disc
if n << 10 Mio: use the merge sort approach on disc (maybe one get's lucky often and the -1 comes before the first file was written...)

@ppz, you are totally right with the money, I oversaw that.
But it doesn't change so much, in my opinion (while it is still a mistake), remove the +m[i] / money[i] from the recursion and the rest stays the same but has now optimization potential. We can still deduce it from knap-sack, it's even easier that way.

I think I consider the order (i in the recursive method) mean, it sais you have to fight them in order, that's what the algo does. So the re-use (memoization) is a certain amount of money and strength at a certain position. If money only decreases or stais the same over time, I think I can get rid of a paramter in the memoization.

could you maybe code your greedy based algo, I can't see how you can do this without trying all options and re-using options you explored.

The problem is, that sometimes one needs to make a local bad decision which still leads to the overal best result and this is difficult with greedy technique.

/*
1) Burute force, go to every square and check how much left, right, up and down one can go, at most which gives O(n*m*n + n*m*m) runtime
   which is O(n³) if n = m
2) Hint to use DFS/BFS hints that O(n*m) is best conceivable worst case runtime unless some heuristic is used to accellerate the search, 
   which wouldn't increase worst case runtime. Such a heursitic could draw the search towards the center of the matrix where the largest
   crosses are expected but I don't really think this is wanted or advantegous here.
3) While there is certainly an approach with BFS and DFS, anyway we need to store the length into each direction, without storing that
   information how far to the left, right, top, down one can go from one point, there is not much of subproblem reuse possible.

   At this point I suggest an easier to implement approach than BFS/DFS using some sort of dynamic programming:
   let's say, left(x, y) is an integer denoting how much we can go left from a certain point, then left(x + 1, y) = left(x, y) + 1
   if matrix(x + 1, y) is 1 or 0 if matrix(x + 1, y) is 0. 
   we can create a left, right, top and down matrix. Creating each of those will cost at max O(n^2)
   Maximizing over all n² the min(right(x, y), top(x, y), ...) will lead to the desired result in O(n^2)
   So, runtime is O(5*n²) which is O(n²) as is the upper bound on space
   This will lead to the best conceivable runtime.

   Note: One can save one of the 4 matrices, at the last step, but for simplicity and readability I didn't implement it that way, besides
   it wouldn't make the O(n*m)

*/

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

pair<int, pair<int, int>> findBiggestPlus(const vector<vector<bool>>& field)
{
	pair<int, pair<int, int>> result(-1, pair<int, int>(-1, -1));
	int m = field.size();
	if(m == 0) return result;
	int n = field[0].size();
	if(n == 0) return result;
	vector<vector<int>> left(m, vector<int>(n));
	vector<vector<int>> right(m, vector<int>(n));
	vector<vector<int>> up(m, vector<int>(n));
	vector<vector<int>> down(m, vector<int>(n));

	for(int y = 0; y < m; y++)
	{
		left[y][0] = field[y][0] ? 1 : 0;
		for(int x = 1; x < n; x++) left[y][x] = field[y][x] ? left[y][x - 1] + 1 : 0;
		
		right[y][n - 1] = field[y][n - 1] ? 1 : 0; 
		for(int x = n - 2; x >= 0; x--) right[y][x] = field[y][x] ? right[y][x + 1] + 1 : 0;
	}

	for(int x = 0; x < n; x++)
	{
		up[0][x] = field[0][x] ? 1 : 0;			
		for(int y = 1; y < m; y++) up[y][x] = field[y][x] ? up[y - 1][x] + 1 : 0;

		down[m - 1][x] = field[m - 1][x] ? 1 : 0; 
		for(int y = m - 2; y >= 0; y--) down[y][x] = field[y][x] ? down[y + 1][x] + 1 : 0;
	}
	
	for(int x = 0; x < n; x++)
	{
		for(int y = 0; y < m; y++)
		{
			int s = min(left[y][x], min(right[y][x], min(up[y][x], down[y][x])));			
			if(s > result.first) result = pair<int, pair<int,int>>(s, pair<int, int>(x, y));
		}
	}
	return result;
}


int main()
{
	vector<vector<bool>> m {
		{0, 0, 1, 0, 0, 1, 0}, 
		{1, 0, 1, 0, 1, 0, 1},
		{1, 1, 1, 1, 1, 1, 1},
		{0, 0, 1, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0}
	};

	auto result = findBiggestPlus(m);
	cout << "side length: " << result.first << " x:" << result.second.first << " y:" << result.second.second << endl; 
}

yea, this is really a white board task, be creative,

I would approach it like this:
- think about usecases, what does the user, who is the user, what is the result expected, what does the system do, what should happen if something fails, try to understand the expectations to the system.
- entities: router, job, job-result, user, protocol, job-status, job-queue...
- deployable components / existing infrastructure: job scheduler / executer, front-end (e.g. web server, console programm to talk to executer), router directory (like LDAP), user directory with rights,
- protocols: front-end - executer (some sort of RPC, how to do it, if there are multiple executers for scaling, fail over, redundancy, ...) executer among each other, e.g. to identify what's the next task for each executer, data-storage, maybe MySQL and some db midleware, user directory may be LDAP, router directory may be LDAP, etc...
- interesting topics:
- how many different type of jobs? If there are a lot, and if they are changing often, it might be a good idea to create some abstract way to create the API-calls or XML data based on a simple meta language or a set of helper functions etc... discuss a few approaches here, it's advantages and disadvantes
- if a job needs to be executed on all routhers what are the time constraints and what should be done if it fails on a few routhers, should then everything be rolled back, retried, protocollled, a ticket raised, a person paged, etc?
- I fmultiple executions happen simulatenously, maybe the execution should be done from multiple machines to be faster, can we loose some how locality information, so the machine and router are close to each other, would it matter, maybe not, but thinking of it loud may be good...
- need for authentication and autorization of the user scheduling a job, but how about the execution to the routers? How is this done?
etc....

@guangsumengmianxia
be carefull in an interview with these statement it shows some ignorance to important details even if your answer is very practical and fast.

But your shuffle has a problem the way you wrote it (I once thought it would be easier that way you wrote it and got suspicious, so I checked it a while ago and it wasn't good at all). If your variable "ind" was uniform, your swap will not lead to a uniform distribution, because the elements in front are more likely to be swapt multiple times. Essentially, the index 0 has probability 1/n to land at any place in the interval [0..n) at the first iteration (which is good). But, if it is swaped with any of the elements in [1..n) the element which originates from index 0, has another chance to go back to it's original position thus pulling the probability slightly towards staying at it's original position.
You can prove it or you can write a monte carlo to show it. I did both, the shuffle will not produce a random permutation (which is usually understood as every permutation has exactly the same probability to occure, which is 1/(n!)) although it is close to one.

2) doing the modulo will not be truely uniform except when n is a power of 2. While this is minor there are situations where it matters. So it's essential to be aware of and advantageous to know a way out.

yea, you are right, there is no need for a new random number generator, but for a function that uses the existing one and makes one whre you can define the interval. Be it in a function or just a line of code is really not the question here.

Assumption 1st natural numbers include 0: 0,1,2,3,4,5 would be a valid result if n = 6

1. we need a function to produce a random number between 0..k-1 interval: [0..k)
let's suppose we had this.
2. choose the element for the first position in the array with 1/n probability
3. choose the element for the second position the array with 1/(n-1) probability etc...

// forward declaration: produces random number between 0..k-1
int random(int k);

vector<int> createPermutedArray(int n)
{
	vector<int> a(n);
	for(int i = 0; i < n; i++) a[i] = i;
	for(int i = 0; i < n - 1; i++)
	{
		int j = i + random(n - i); 
		swap(a[i], a[j]);
	}
	return a;
}

now let's think how can we create the random function that returns [0..k) from a random function that returns [0..1), at first glance, just multiply by k, right?

int random(int k)
{
	double r = random(); // [0..1)
	return r * k;
}

the question is, is the distribution 0..k-1 truely uniform if random [0..1) is uniform?
let's see:
everything between [0..1/k) maps to 0
between [1/k .. 2/k)) maps to 1
between [(k-1)/k .. k/k) maps to k-1
k/k = 1, it seems uniform at this point, but double is represented in binary and thus if k is not a power of 2 the number space cannot be seperated in exactly same sized spaces.
Let's for a moment think a double would be 8bit fixed point and k would be 3
[0..85)-> 0, p(0) = 85/255
[85..170) -> 1, p(1) = 85/255
[170..256) -> 2, p(2) = 86/255
this is not uniform. So it turns out above int random(int k) is not truely uniform either. How to get it uniform (if that little non-uniformity would matter)
first of all I would get rid of the double and just use the mantissa which is an integer, I think of about 54 bits on a 64 bit system for simplicity, how ever, let's assume it's 8 bits and scale it up later and let's suppose our k is 7
- floor((2^8) / 7) = 36
- 36 * 7 = 252

int r;
	while((r = randomInt()) >= 252);
	return r / 7;

now create randomInt to extract the mantisa from the double and replace the calculation's constants
appropriately. There is almost certainly a solution while keepting the double as well, maybe somebody could point it out.

@tryhard, thanks, oh yea, the interval can be solved much better and I noticed you treated the intervals end > start as well different (I checked, it's correct, but by far not intuitive, and be aware that the count is wrong, but the maximized index is correct).
full credits on tryhard, the shortest and fastest solution is as follows

// the best solution in O(n)
int getIndexForMaxAmazingNo(const vector<int>& a)
{
	int n = a.size();
	vector<int> change(n, 0);

	// find for every element the interval that makes it an amazing number
	for(int i = 0; i < n; i++) 
	{
		if(a[i] >= n) continue;  // it will never participate
		int s = (i + 1) % n; 
		int e = (n + i - a[i]) % n; 
		change[s] ++;
		if(e + 1 < n) change[e + 1] --;
	}

	// find index with max (note: the maxk will not contain
	// the count of amazing numbers, if we want that, we have
	// to consider intervals whose start%n > end%n differntly
	// by considering them as two intevals, from start%n - n-1
	// and from 0 to end%n.
	int k = 0;
	int maxk = 0;
	int maxki = 0;
	for(int i = 0; i < n; i++)
	{
		k += change[i];
		if(k > maxk)
		{
			maxki = i;
			maxk = k;
		}
	}
	return maxki;
}

/*
this is related to solving a sodoku but it seems to not require backtracking if a proper greedy strategy
is followed, that is, pick the field with the least options to choose a number from. 
e.g. in above sample there are 5 fields with numbers to choose from, 3 have 2 options, 2 have one option.
If choosing from one that has two options, maybe the choice is not good and backtracking is required.

I didn't find the prove that the greedy choice always leads to a solution without need for backtracking, 
but i failed to come up with a counter-sample. 

Below implementation is quite bad with O(n^5), here's how to optimize:
1. create for each cell a set containing the potential numbers. this takes O(n³) time and O(n³) space
2. go through all the sets and put them into a prio queue, so that the smallest set is on top (O(n²))
3. while this prio-queue is not empty, take the top element
   if the cell hasn't already been set, set the value of that cell it referes to to the first 
   potential value given by this set, update all sets in the row and column and place them into 
   the queue or, if you can, update original items in queue (bubble up, heapify, ...)
   this has an upper bound of O(n * lg(n³)) because the prio queue can contain O(n³) items

This brings it down to O(n³)  
*/

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <list>
#include <utility>
#include <limits>

using namespace std;

using Matrix = vector<vector<int>>; 
using SetMatrix = vector<vector<unordered_set<int>>>;

class MatrixCompleter
{		
private:	
	Matrix matrix_; // state of the matrix

public:
	MatrixCompleter(const Matrix& m) : matrix_(m) { }

	void solve()
	{
		while(true) // O(n^2)
		{
			int fv = -1;
			int fx = -1;
			int fy = -1;
			int fc = matrix_.size() + 1;		
			for(int x = 0; x < matrix_.size(); x++)
			{
				for(int y = 0; y < matrix_.size(); y++)
				{
					// O(n^4)
					unordered_set<int> fn = getFreeNumbers(x, y); // O(n^5)
					if(fn.size() > 0 && fn.size() < fc)
					{
						fx = x;
						fy = y;
						fv = *(fn.begin());
						fc = fn.size();					 
					}
				}
			}
			if(fx >= 0) matrix_[fx][fy] = fv;
			else break;
		}
	}

	void print()
	{
		for(int y = 0; y < matrix_.size(); y++)
		{
			for(int x = 0; x < matrix_.size(); x++)
			{
				cout << matrix_[x][y] << " ";
			}
			cout << endl;
		}
	}	

private:
	unordered_set<int> getFreeNumbers(int x, int y)
	{
		unordered_set<int> result;
		if(matrix_[x][y] != 0) return result;
		for(int i = 1; i <= matrix_.size(); i++) result.insert(i);
		for(int i = 0; i < matrix_.size(); i++)
		{
			if(matrix_[i][y] != 0) result.erase(matrix_[i][y]);
			if(matrix_[x][i] != 0) result.erase(matrix_[x][i]);
		}
		return result;
	}
};

int main()
{
	auto mc = MatrixCompleter(
		{
			{1, 2, 0},
			{0, 1, 0},
			{0, 0, 1}
		});
	cout << "\ncase 1 input" << endl;
	mc.print();
	mc.solve();
	cout << "\ncase 1 output" << endl;
	mc.print();

	mc = MatrixCompleter(
		{			
			{1, 0, 0},
			{0, 1, 0},
			{0, 0, 1}
		});
	
	cout << "\ncase 2 input" << endl;
	mc.print();
	mc.solve();
	cout << "\ncase 2 output" << endl;
	mc.print();
}

/*
1) obvious solution, try all sub-sequences which are n*(n-1) leading to O(n²) runtime with O(1) space
2) there is a better approach:
- for each element we can know for which interval of start index it will count as an amazing number
- so, we get n intervals and need to know what is the best start. start can be between 0 and n
- if we go through 0..n for each interval, when we have a list with all start and all ends, we can
  find the desired lowest start index if interval starts and ends are sorted
  
2) in detail, assuming the following array:

index: 0, 1, 2, 3, 4, 5, 6, 
value: 4, 2, 8, 2, 4, 5, 3, 
n = 7

value 4 at index 0: can be used if start index is between 1 and 3
    becaue there must be at least 4 elements before a[0] to satisfy
	a[0] >= index.	 
	that is 0 + 1 .. n + 0 - a[0]
value 2 at index 1: can be used if start index is between 2 and 6
    that is 1 + 1 .. n + 1 - a[1]
value 8 at index 2 can never be used because 8>n
	that is 2 + 1 .. n + 2 - a[2] => 3 .. 1 (which is not an interval)
value 2 at index 3 can be used if start index is between 4 and 8 (*), 
	that is 3 + 1 .. n + 3 - a[3]
value 4 at index 4 can be used if start index is between 5..7
    that is 4 + 1 .. n + 4 - a[4]
value 5 at index 5 can be used if start index is between 6..7
	that is 5 + 1 .. n + 5 - a[5]
value 3 at in dex 6 can be used if start index is between 7..10
	that is 6 + 1 .. n + 6 - a[6]

result: at index 6 (4 values are amazing)
        at index 7 (4 values are amazing)
		note index 7 = 0, 0 < 6, therefore the result is 0

(*) if index > 6 means basically just index - n, or more generic index mod n
    due to circular buffer characteristics of the problem
	create two intervals, one from start to n-1 and one from 0 to end mod n

sorting the two vectors with start and end index will allow to calculate the 
index at which the most intervals overlap which is essentially the index of 
interest.

Finding the index works as follows:
let k be the number of intervals covered by the current index
int k = 0;
int maxk = 0;
int maxki = 0;
int s = 0;
int e = 0;
for(int i = 0; i < n; i++)
{
	while(s < start.size() && start[s] == i)  { s++; k++; }
	if(k > maxk) // new found { ... } 
	while(e < end.size() && end[e] == i) { e++; k--; }  
}

runtime complexity:
creating the start and end vectors: O(n)
sorting start and end vectors O(n * log(n))
finding max index: O(n)
total runtime: O(n * log(n))

space complexity: O(n)
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// the smarter version in O(n * lg(n))
int getIndexForMaxAmazingNo(const vector<int>& a)
{
	int n = a.size();
	vector<int> start;
	vector<int> end;

	// find start index interval that makes this element an amazing no
	for(int i = 0; i < n; i++) 
	{
		int s = i + 1;
		int e = n + i - a[i];
		if(e >= s)
		{
			start.push_back(s);
			if(e < n) 
			{
				end.push_back(e);
			}
			else 
			{
				end.push_back(n - 1);
				start.push_back(0);
				end.push_back(e % n);				
			}
		}
	}

	// sort interval start and interval end
	sort(start.begin(), start.end());
	sort(end.begin(), end.end());

	// by counting the number of intervals for start index i
	int k = 0;
	int maxk = 0;
	int maxki = 0;
	int s = 0;
	int e = 0;
	for(int i = 0; i < n; i++)
	{
		// why this inner loop makes not O(n^2): start has max 2*n elements, 
		// so e.g. if first element is n and second is n, all the others are 0 
		// (compensated runtime of this inner loop thus is constant)		
		while(s < start.size() && start[s] == i)  { s++; k++; } 
		if(k > maxk)
		{
			maxki = i % n;
			maxk = k;
		}
		while(e < end.size() && end[e] == i) { e++; k--; }  
	}

	return maxki;
}

// the brute force version in O(n²)
int getIndexForMaxAmazingNoBf(const vector<int>& a)
{
	int n = a.size();
	int maxk = 0;
	int maxki = 0;		
	for(int i = 0; i < n; i++)
	{
		int k = 0;		
		for(int j = 0; j < n; j++)
		{
			if(a[(i + j) % n] <= j) k++;
		}		
		if(k > maxk)
		{
			maxki = i;
			maxk = k;
		}
	}
	return maxki;	
}

// some primitive validation by comparing bruteforce with optimized
void test(const vector<int>& a)
{
	cout << "test array:\n ";
	for(auto e : a) cout << e << " ";
	int bfr = getIndexForMaxAmazingNoBf(a);
	int r = getIndexForMaxAmazingNo(a);
	cout << "\nbrute force result: " << bfr << " optimized result: " << r << (bfr == r ? " MATCH" : " !!DO NOT MATCH!!") << endl;
}

int main()
{
	test({4, 2, 8, 2, 4, 5, 3});
	test({1, 2, 3, 4, 5, 6, 7});
	test({9, 8, 7, 6, 5, 4, 3, 2, 1});
	test({0, 0, 0, 0, 0, 0, 0, 0, 0});
	test({});
	test({1});
	test({1, 2});
	test({1, 2, 3, 4, 5, 1, 2, 9, 10, 11, 1, 2, 3, 4, 5, 6});
}

/* output
test array:
 4 2 8 2 4 5 3 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 2 3 4 5 6 7 
brute force result: 6 optimized result: 6 MATCH
test array:
 9 8 7 6 5 4 3 2 1 
brute force result: 0 optimized result: 0 MATCH
test array:
 0 0 0 0 0 0 0 0 0 
brute force result: 0 optimized result: 0 MATCH
test array:
 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 2 
brute force result: 1 optimized result: 1 MATCH
test array:
 1 2 3 4 5 1 2 9 10 11 1 2 3 4 5 6 
brute force result: 9 optimized result: 9 MATCH
*/

The O(n^2) solution checks for intersection among each pair.
To improve it, we have various options:
- If the radius is all the same for each circle, we can put the circles in a hash map that keys to y/r and x/r (this is essentially putting r-side length squares over the 2d space. Then for the remaining n-1 circles for each of the 8 adjacent sqaures of this circle check if one circle found in this squares intersect. There are at most 8*4 circles to compare per circle which makes it O(8*4*n) = O(n)
- If the radius is not the same for each square, a two dimensional segment tree could be used on the bounding box of the circle. If a potential intersection is detected, one has to check intersection of the k points which is if the distance of the centers is less than then the sum of the two radius. This has O(n*log(n)^2) for read and insert, therefore leading to O(n*log(n)^2) performance, where as it is assumed that the number of collisions in a bounding box is not significant. One has to carefully think if worst case isn’t O(n^2) due to collisions within the bounding box of circles that still don’t overlap (e.g. if k can be a factor * n, like n/2 n/4 n/f).

/*
as with my previous post, the solution here solves the problem with 
BFS and A*

The output shows the number of visits to each field. It's clear that
A* is faster, but it is with this paramter set not guaranteed to find
the absolute optimum: see in qiprio: d + h * 2, replace it with d + h
and A* will cover more land, but is still significant better than 
BFS. 

Expressing this in Big-O is not so meaningful, because it depends so
much on the grid now. A*'s worst case is worse than BFS, because of the 
priority queue. 

Anyway I don't think that is expected by an interview, it's more to 
maybe implement a BFS solution and come up with ideas how to improve and
maybe writing the heuristic function or outline how the algorithm
would fill the grid etc...
*/

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

// helper for point
struct Point
{
	int x_, y_;
	Point(int x, int y) : x_(x), y_(y) { }
	Point() : Point(0, 0) { }
};

// calculates manhatten distance between two points
int manhattend(const Point& a, const Point& b) 
{ 	
	return abs(a.x_ - b.x_) + abs(a.y_ - b.y_); 
}

int qiprio(const Point& current, const Point& expected, int d)
{
	int h = manhattend(expected, current);
	return d + h * 2; 
}

// queue item used for the A-Star approach
struct QI
{
	Point p_;
	int h_; 
	int d_;
	QI(int h, const Point& p, int d) : p_(p), h_(h), d_(d) { }
};

class Village
{
private:
	unordered_set<long long> bushes_; // x << 32 | y for O(1) test
	unordered_map<long long, int> houses4p_; // houses for printing 
	vector<Point> houses_;
	Point guessedMp_;
	int w_;
	int h_;

public:
	Village(int w, int h, const initializer_list<Point>& houses, const initializer_list<Point>& bushes) 
		: w_(w), h_(h), houses_(houses)
	{
		for(auto p : bushes) placeBush(p);		
		int hi = 1;
		for(auto h : houses) placeHouse(h, hi++);
		guessedMp_ = getPointOfGravityManhatten();
	}

	Point findByAstar()
	{
		int n = houses_.size();
		auto cmp = [this](const QI& a, const QI& b) -> bool 
		{   
			return qiprio(a.p_, guessedMp_, a.d_) > qiprio(b.p_, guessedMp_, b.d_);
		};

		vector<priority_queue<QI, vector<QI>, decltype(cmp)>> queues(n, 
			priority_queue<QI, vector<QI>, decltype(cmp)>(cmp)); 
		vector<unordered_set<long long>> visited(n); 
		vector<int> hid(n); // initial distance
		vector<int> c(n, 0); // counter 
		unordered_map<long long, int> visitedCount;

		// initialize queues
		for(int h = 0; h < n; h++)
		{			
			queues[h].push(QI(h, houses_[h], 0));	
			visited[h].insert(getKeyForPoint(houses_[h]));
		}

		int maxQueueSize = 1;
		while(maxQueueSize > 0)
		{
			// distance from best active to target tells how much
			// calculation that part gets
			int mhid = 0; // max initial distance 
			for(int h = 0; h < n; h++)
			{			
				if(queues[h].size() == 0) 
				{
					hid[h] = numeric_limits<int>::max();
				}	
				else
				{
					hid[h] = 1 + manhattend(queues[h].top().p_, guessedMp_) / 5;
					mhid = max(mhid, hid[h]);
				}
			}

			maxQueueSize = 0;
			for(int h = 0; h < n; h++)
			{
				if(queues[h].size() == 0) continue;
				int c = 0;
				while(!queues[h].empty() && c < mhid) // proceed every "house" proportional to initial distance steps
				{
					auto u = queues[h].top(); 
					queues[h].pop();
					visitedCount[getKeyForPoint(u.p_)]++;
					if(visitedCount[getKeyForPoint(u.p_)] == n)
					{ 
						print(visitedCount);
						return u.p_;
					}
					for(auto v : getAdjacents(u.p_))
					{
						if(visited[u.h_].find(getKeyForPoint(v)) != visited[u.h_].end()) continue;
						visited[u.h_].insert(getKeyForPoint(v)); 	
						queues[h].push(QI(u.h_, v, u.d_ + 1));					
					}
					c += mhid / hid[h];
				}
				maxQueueSize = max(maxQueueSize, static_cast<int>(queues[h].size()));
			}
		}

		cout << "couldn't find a solution" << endl;
		return Point(-1, -1); // no solution 	
	}

	// solution using BFS
	Point findByBFS()
	{
		int n = houses_.size();
		vector<queue<Point>> queues(n);
		vector<unordered_set<long long>> visited(n); 
		unordered_map<long long, int> visitedCount;

		for(int h = 0; h < houses_.size(); h++)
		{ 
			queues[h].push(houses_[h]); // start point of all BFS
			visited[h].insert(getKeyForPoint(houses_[h]));
		}
		int maxQueueSize = 1;
		while(maxQueueSize > 0)
		{
			maxQueueSize = 0;
			for(int h = 0; h < n; h++)
			{
				if(queues[h].size() == 0) continue;
				queues[h].push(Point(-1, -1)); // marker element to abort this expansion step
				while(true)
				{
					auto u = queues[h].front(); 
					queues[h].pop();
					if(u.x_ == -1) break; // abort after marker element was found				
					visitedCount[getKeyForPoint(u)]++; // this field is visited once more
					if(visitedCount[getKeyForPoint(u)] == n)
					{ 
						print(visitedCount);
						return u; // if n times visited, done
					}
					
					for(auto v : getAdjacents(u))
					{
						if(visited[h].find(getKeyForPoint(v)) != visited[h].end()) continue;
						visited[h].insert(getKeyForPoint(v)); // BFS starting at h will visit this field on next turn 						
						queues[h].push(v);					
					}
				}
				maxQueueSize = max(maxQueueSize, static_cast<int>(queues[h].size()));
			}
		}
		cout << "couldn't find a solution" << endl;
		return Point(-1, -1); // no solution  			
	}	

private:
	// returns the fields one can go from u considering dimensions of the village and bushes
	vector<Point> getAdjacents(const Point& u)
	{
		vector<Point> result;
		if(u.x_ > 0 && !isBush(Point(u.x_ - 1, u.y_))) result.push_back(Point(u.x_ - 1, u.y_)); // can go left 
		if(u.x_ < w_ - 1 && !isBush(Point(u.x_ + 1, u.y_))) result.push_back(Point(u.x_ + 1, u.y_)); // can go right 
		if(u.y_ > 0 && !isBush(Point(u.x_, u.y_ - 1))) result.push_back(Point(u.x_, u.y_ - 1)); // can go up 
		if(u.y_ < h_ - 1 && !isBush(Point(u.x_, u.y_ + 1))) result.push_back(Point(u.x_, u.y_ + 1)); // can go down
		return result; 
	}

	// place a bush
	void placeBush(const Point& p) 
	{
		bushes_.insert(getKeyForPoint(p));
	}

	// is point a bush?
	bool isBush(const Point& p)
	{
		return bushes_.find(getKeyForPoint(p)) != bushes_.end();
	}

	// finds the point that is equaly far from all houses, not considering
	// bushes etc. this is the optimal place and would be the solution if no 
	// bushes where there. The A* heuristic is set to try to get to this point
	Point getPointOfGravityManhatten()
	{
		Point g(0, 0);

		int mind = w_ + h_ + 1;
		while(true)
		{
			vector<Point> s({Point(g.x_ - 1, g.y_), Point(g.x_ + 1, g.y_), Point(g.x_, g.y_ - 1 ), Point(g.x_, g.y_ + 1)});
			int nd = mind + 1;
			Point ng;
			for(auto p : s)
			{
				int d = 0;
				for(auto h : houses_)
				{
					d = max(d, abs(h.x_ - p.x_) + abs(h.y_ - p.y_));					
				}
				if(nd > d)
				{
					nd = d;
					ng = p;
				}
			}
			if(nd >= mind) return g;
			mind = nd;
			g = ng;			
		}
	}

	inline static long long getKeyForPoint(const Point& p) 
	{
		return (static_cast<long long>(p.x_) << 32) | p.y_;
	}
	
	// infrastructure code for printing to console
	int getHouse(const Point& p)
	{
		auto it = houses4p_.find(getKeyForPoint(p));
		if(it == houses4p_.end()) return 0;
		return it->second;
	}

	// infrastructure code for printing to console
	void placeHouse(const Point& p, int no)
	{
		houses4p_[getKeyForPoint(p)] = no;
	}

	// infrastructure code for printing to console
	void print(const unordered_map<long long, int>& visitedCount)
	{
		for(int y = 0; y < h_; y++)
		{
			for(int x = 0; x < w_; x++)
			{				
				auto vcIt = visitedCount.find(getKeyForPoint(Point(x, y)));
				int vc = vcIt == visitedCount.end() ? 0 : vcIt->second;
				int hNo = getHouse(Point(x, y));
				bool isMeetingPoint = guessedMp_.x_ == x && guessedMp_.y_ == y; 
				if(hNo != 0) cout << static_cast<char>('A' + (hNo - 1));				 
				else if(isBush(Point(x, y))) cout << '#';
				else if(vc == 0) cout << (isMeetingPoint ? 'M' :' ');
				else if(vc < 9) cout << vc;
				else cout << '*';	
			}
			cout << endl;
		}
	}
};


int main()
{
	Village v(80, 40, 
		{{2, 30}, {8, 1}, {65, 19}}, // houses
		{
			// trees suround expected meeting point
			{26, 16}, {27, 16}, {28, 16}, {29, 16}, {30, 16}, 
			{30, 17}, {30, 18}, {30, 19}, {30, 20},
			{29, 20}, {28, 20}, {27, 20}, {26, 20}, 
			{26, 19}, {26, 18}, {26, 17}, {26, 16}, 
			// trees to block path from house 3 slightly (=C)
			{60, 15}, {60, 16}, {60, 17}, {60, 18}, {60, 19}, 
			{60, 20}, {60, 21}, {60, 22}, {60, 23}, {60, 24}, 
			{60, 25} 
		}
	);	
	cout << "find meeting point using BFS" << endl;
	v.findByBFS();

	cout << "\n\nfind meeting point using A*" << endl;	
	v.findByAstar();

	/* output 
	find meeting point using BFS
22222222222222211111111111111111111111111112222222111111111111111111111111111111
22222222B22222221111111111111111111111111122222222211111111111111111111111111111
22222222222222222111111111111111111111111222222222111111111111111111111111111111
22222222222222222211111111111111111111112222222221111111111111111111111111111111
22222222222222222221111111111111111111122222222211111111111111111111111111111111
22222222222222222222111111111111111111222222222111111111111111111111111111111111
22222222222222222222211111111111111112222222221111111111111111111111111111111111
22222222222222222222221111111111111122222222211111111111111111111111111111111111
22222222222222222222222111111111111222222222111111111111111111111111111111111111
22222222222222222222222211111111112222222221111111111111111111111111111111111111
22222222222222222222222221111111122222222211111111111111111111111111111111111111
22222222222222222222222222111111222222222111111111111111111111111111111111111111
22222222222222222222222222211112222222221111111111111111111111111111111111111111
22222222222222222222222222221122222222211111111111111111111111111111111111111111
22222222222222222222222222223222222222111111111111111111111111111111111111111111
222222222222222222222222222222222222211111111111111111111111#1111111111111111111
22222222222222222222222222#####22222111111111111111111111111#1111111111111111111
22222222222222222222222222#   #22221111111111111111111111111#1111111111111111111
22222222222222222222222222# M #22211111111111111111111111111#1111111111111111111
22222222222222222222222222#   #22111111111111111111111111111#1111C11111111111111
22222222222222222222222222#####21111111111111111111111111111#1111111111111111111
222222222222222222222222222222211111111111111111111111111111#1111111111111111111
222222222222222222222222222222111112211111111111111111111111#1111111111111111111
222222222222222222222222222221111122221111111111111111111111#1111111111111111111
222222222222222222222222222211111222222111111111111111111111#1111111111111111111
222222222222222222222222222111112222222211111111111111111111#1111111111111111111
22222222222222222222222222111112222222222111111111111111111111111111111111111111
22222222222222222222222221111111222222222211111111111111111111111111111111111111
22222222222222222222222211111111122222222221111111111111111111111111111111111111
22222222222222222222222111111111112222222222111111111111111111111111111111111111
22A22222222222222222221111111111111222222222211111111111111111111111111111111111
22222222222222222222211111111111111122222222111111111111111111111111111111111111
22222222222222222222111111111111111112222221111111111111111111111111111111111111
22222222222222222221111111111111111111222211111111111111111111111111111111111111
22222222222222222211111111111111111111122111111111111111111111111111111111111111
22222222222222222111111111111111111111111111111111111111111111111111111111111111
122222222222222211111111111111111111111  111111111111111111111111111111111111111
11222222222222211111111111111111111111    11111111111111111111111111111111111111
1112222222222211111111111111111111111      1111111111111111111111111111111111111
111122222222211111111111111111111111        111111111111111111111111111111111111


find meeting point using A*
                                                                                
        B11111111111111111111                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                            1                                                   
                           111                                                  
                           111                                                  
                           111                                                  
                          11111                                                 
                          11211                                                 
                          122221111111111111111111111111111111                  
                         112222211                          #111                
                         1#####21                           #11111              
                         1#   #21                           #111111             
                        12# M #31                           #1111111            
                         1#   #2                            #1111C11            
                         1#####1                            #111111             
                         1111111                            #11111              
                          11111                             #11                 
                          11111                             #                   
                          11111                             #                   
                           111                              #                   
                           111                                                  
                           111                                                  
                            1                                                   
                           11                                                   
  A11111111111111111111111111                                                   
*/
}

let n be the number of houses, w the width, and h the height of the grid and assume moving left, right, down and up us allowed (no diagonales).

the problem is essentially a graph problem, but additional information is given, e.g. the distance from upper-left to lower-right is at least w+h. Maybe this can be used for a heuristics to accellerate the search like in A*.

Let's first approach without heuristics:
Start a BFS from all the houses simultaneously, that means the frontier expands one by one starting at all houses. The first time all frontiers meet is the point for the meeting. It seems natural that this is O(w*h*n) since a BFS will visit all nodes which are w*h and it's run n times.

The problem with this approach is, that, suppose we have a very large map and only two houses that are placed e.g. at (w/4, h/4) and (3/4w, h/4) the BFS's run not only towards each other but as well in directions that won't help solve the problem but extend the frontier heavily, increasing complexity. So for two houses it is very easy to come up with a heuristic. But as soon as a heuristic is added, BFS doesn't work, so we need to switch to Djikstra to pick the element's with lowest distance from origin - heuristic. With several points, this is more difficult, but the expected meeting point will be the point of gravity and then instead of running BFS from each house, we can run Djikstra from each house using this heuristic, which is essentially running A* from each house. This can probably be further optimized by considering the lowest cost next point from each origin (e.g. imagine on the sample above, there is a house exaxtly in the middle between the two houses, around that point I wouldn't explore too much, because it is already close to the expected meeting point)
...
cool question (a bit heavy for an interview), I might code it, if I have time tonight

1. Let a[i] be the value of an element in the array: 0 <= a[i] <= n and n be the #elements in a
2. k = #bits to represent 0..n: k = ceiling(log2(N))
3. m = #bits of the datatype, e.g. 32
4. if k < m: we have at least n bits we can use to store some information
5. let value(i) be the value of a[i] that only uses k bits: value(i): a[i]&((1<<k)-1)

so we can iterate over the array and extract the value of a[i] = value(i)
if a[i] != value(i) that is a dublicate we have found a dublicate
if not store in a[value(i)] = value(i) + (1<<(k+1)) (or value(i) + n, or anything like this...)

following thoughts are important:
1) this is theoretically not O(1) space but practically it is O(1) space: why, it uses bits that are allocated but not used
2) since the array is modified, it might be a good idea to revert the change in the array after finding a dublicate, especially if the function name does not imply modifications of the array
3) even if you do redo the changes, the array will temporarily be changed, so in production, this
will have side effects if concurrent access to the array happens.

this given we can do:

// returns -1 if no dublicate was found
int getAnyDublicate(vector<int>& a)
{
	int result = -1;
	if(a.size() <= 1) return result; 
	int k = static_cast<int>(log2(a.size() - 1) + 1.0);
	assert(k < numeric_limits<unsigned int>::digits);
	unsigned int datamask = (1 << k) - 1;
	unsigned int seenmask = (1 << (k + 1));
	for(int e : a)
	{
	 	int v = e & datamask;
		if(a[v] & seenmask != 0) { result = v; break; }
		a[v] |= seenmask;
	}
	for(int& e : a) e &= datamask; // revert all changes
	return result;
}

a datastructure is driven by the operations one wants to perform on it. The question screams for clarification of this operations.

Since it's sparse, a pure array seems not the solution although in practice it depends on the expected size of the matrix (average, max) and the numbers of matrices to be stored.
For example if we have to deal with 3 sparse matrices of size10x10 with average 2 elements being not 0 in all cases I can think of the best representation is a two dimensional array. If we need to keep tenths or hunderts of thousands of such 10x10 matrices in memory or if a single matrix has large dimensions, say 100'000 x 100'000 this representation may not be good anymore.

Thinking about the operations one potentially may want to perform on such matrices like addition and multiplication we do not require random access to single elements but sequential access for addition and random access of a whole row / column where the elements of that row / column are accessed sequentially.

In case of addition we need m*n operations anyway, be it to add the elements or to initialize the result with 0.

For multiplication the thing is different. m x n * n x p matrix will result in a m x p matrix. So, if we have to trie to access every element we end up with O(m x n + n x p) compared to optimal if it is sparse that is O(n x p) assuming, for simplicity, the number of elements in both matrices that are not 0 is smaller than n x p.

It seems a linked list per row and per column may be a good choice for addition and multiplication. This would store the value and column-index for a row, or value and row-index for a column.

It is slow to insert/delete and random read single elments. As well attention to construction needs to be payed (how to fill the data structure initially). If we want to speed up random access (read) we could maintain a hashmap on top. If insert/delete of single elements needs optimization while still providing reasonable access to all elements of a column (in row order) and vice versa for a row the linked lists could be replaced by balanced search trees.

I forgot to post the explanation of above algorithm:

The key idea is to dynamically extend the graph to a graph g'. When ever we are on a vertex in the original graph g, there are the edges given + to every other vertex where no edge was given there exists the "bonus edge" (with extra weight). Once used we are in g' and can't use the "bonus edge" anymore.That is, in g' there exist only the original edges to vertices in g but to their "mirror" in g'.

Visually, I drew the original graph g and on top a layer with the graph g'... Besides this I could use dijkstra. A vertex is identified with an integer in this solution. A vertex in g has an id below a certain value and a vertex in g' has just an offset to that id. There are certainly more apealing designs to that, but it did work and I could verify some basic cases.

Runtime is: Dijkstra but with V^2 edges. So O(E V * lg(V)) become O(V^3*lg(V)) ... not that sexy ... (E is the number of edges and V is the number of vertices)

I think the problem statement is not complete due to the missing information what w_extra should do. Since I noticed its a dublicate I already solved (id=5721708662095872) I explain the question as I interpreted it first:

you get the graph as described. you get the w_extra which is the weight of an edge you can place between any two vertices that have not already a direct connection (an edge connecting them). You can only place that extra edge once.

I checked the two sample and it was right:
1) Path is 1->2->4 with weight 4 and no extra edge used
2) Path is 1->5->4 with extra edge used from 1 to 5 (path weight is 2+1 = 3)

I skiped the coding of parsing ala topcoder contest and handcoded the two samples.
The code is long because it has some convenience stuff around it.

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>
#include <iostream>

struct Edge
{
	int destId_, weight_;

	Edge(int destId, int weight) : destId_(destId), weight_(weight) { }	
};

struct TraversalItem
{
	int vertexId_, cost_, parentId_;
	TraversalItem(int vertexId, int cost, int parentId) 
		: vertexId_(vertexId), cost_(cost), parentId_(parentId) { }
	TraversalItem() : TraversalItem(-1, -1, -1) { }
};

using Path = std::pair<int, std::vector<std::pair<int, bool>>>;

class Graph
{
private:
	const int bonusVertexIdOffset = 100000;
	std::unordered_map<int, std::unordered_map<int, int>> edges_;
	std::unordered_set<int> vertices_;

public:
	void addEdge(int u, int v, int weight)
	{
		if (u >= bonusVertexIdOffset || v >= bonusVertexIdOffset) throw "id out of range";
		edges_[u][v] = weight;
		edges_[v][u] = weight;
		addVertex(u);
		addVertex(v);
	}

	void addVertex(int vertexId) 
	{ 
		if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";
		vertices_.insert(vertexId);
	}

	// main part of algorithm 
	// it returns the path cost and the visited vertice id's with a flag wether they were in g or g'
	Path getShortestPathWithBonusEdge(int start, int end, int bonusWeight)
	{
		auto tiComparer = [](const TraversalItem& a, const TraversalItem& b) -> bool { return a.cost_ > b.cost_; };
		std::priority_queue<TraversalItem, std::vector<TraversalItem>, decltype(tiComparer) > tqueue(tiComparer);
		std::unordered_map<int, TraversalItem> state;

		tqueue.push(TraversalItem(start, 0, -1)); // start with start
		state.emplace(std::pair<int, TraversalItem>(start, TraversalItem(start, 0, -1))); // start must be in state, too
		while (tqueue.size() > 0)
		{
			auto u = tqueue.top();
			tqueue.pop();

			int uId = u.vertexId_;
			if (uId == end || uId == end + bonusVertexIdOffset)
			{
				end = uId; // path end id, it might be in g'
				break; // if end is now the cheapest to reach: done
			}
			auto edges = getOutEdges(uId, bonusWeight);
			for (auto edge : edges)
			{
				int cost = u.cost_ + edge.weight_;
				int vId = edge.destId_;
				auto vStateIt = state.find(vId);
				if (vStateIt == state.end())
				{
					TraversalItem ti(vId, cost, uId);
					vStateIt = state.emplace(std::pair<int, TraversalItem>(vId, ti)).first;
					tqueue.push(ti); 
				}
				else if(vStateIt->second.cost_ > cost)
				{
					vStateIt->second.cost_ = cost;
					vStateIt->second.parentId_ = uId;
					tqueue.push(vStateIt->second); // since there's no update-key function... 
				}			
			}
		}

		// reconstruct path
		auto stateIt = state.find(end);
		if (stateIt != state.end())
		{
			// reached the end
			std::vector<std::pair<int, bool>> path;
			int vertexId = stateIt->second.vertexId_;
			int cost = stateIt->second.cost_;
			while (vertexId != -1)
			{
				bool gs = vertexId >= bonusVertexIdOffset;
				int vId = gs ? vertexId - bonusVertexIdOffset : vertexId;
				path.push_back(std::pair<int, bool>(vId, gs));
				vertexId = state[vertexId].parentId_;
			}
			return Path(cost, std::vector<std::pair<int, bool>>(path.rbegin(), path.rend()));
		}
		return Path(-1, std::vector<std::pair<int, bool>>()); // empty path
	}

private:
	std::vector<Edge> getOutEdges(int vertexId, int bonusEdgeWeight)
	{
		std::vector<Edge> edges;
		
		int u = vertexId;
		int vIdOffset = 0;
		if (u >= bonusVertexIdOffset)
		{
			u -= bonusVertexIdOffset;
			
			// bonusedge already used, so only original edges are possible
			auto edgeIt = edges_.find(u);
			if (edgeIt != edges_.end())
			{
				for (auto v : edgeIt->second)
				{
					// use orginial edge but stay in g'
					edges.push_back(Edge(v.first + bonusVertexIdOffset, v.second));
				}
			}
			return edges;
		}

		// a vertex that was reaches without bonus edge, so
		// every pair of edges is possible: either from the original 
		// graph or using the bonusEdge
		for (auto v : vertices_)
		{
			if (v == u) continue;
			auto edgeIt1 = edges_.find(u);
			if (edgeIt1 != edges_.end())
			{
				auto edgeIt2 = edgeIt1->second.find(v);
				if (edgeIt2 != edgeIt1->second.end())
				{
					// use original edge within g
					edges.push_back(Edge(v, edgeIt2->second));
					continue;
				}
			}
			// add bonus edge to g'
			edges.push_back(Edge(v + bonusVertexIdOffset, bonusEdgeWeight));
		}

		return edges;
	}
};

void printResult(int start, int end, int bonusWeight, const Path& path)
{
	std::cout << "shortes path from " << start << " to " << end 
		<< " with bonus edge weight " << bonusWeight << " is " << std::endl;
	std::cout << "  weight: " << path.first << std::endl;
	std::cout << "  path: ";
	for (auto v : path.second)
	{
		std::cout << v.first << (v.second ? "' " : " ");
	}
	std::cout << std::endl << std::endl;
}

int main()
{
	// sample 1
	Graph g1;
	g1.addEdge(1, 2, 2);
	g1.addEdge(2, 3, 1);
	g1.addEdge(2, 4, 2);
	g1.addEdge(3, 4, 3);
	printResult(1, 4, 5, g1.getShortestPathWithBonusEdge(1, 4, 5));

	Graph g2;
	g2.addEdge(1, 2, 2);
	g2.addEdge(1, 4, 4);
	g2.addEdge(2, 3, 1);
	g2.addEdge(3, 4, 3);
	g2.addEdge(4, 5, 1);
	printResult(1, 4, 2, g2.getShortestPathWithBonusEdge(1, 4, 2));

	/* Output
	shortes path from 1 to 4 with bonus edge weight 5 is
	weight: 4
	path: 1 2 4

	shortes path from 1 to 4 with bonus edge weight 2 is
	weight: 3
	path: 1 5' 4'
	*/
 }

/* 
   I solved it using dijkstra as in my previous post. I noticed how ever, the weight of the additional
   edge is not 0 but 2 and that you may go over an intermediate node since the node you currently are
   has a direct connection to end that is more expensive than when you would add the bonus-Edge to an 
   other node and go from there to the end.
   So, again, I noticed how important it is to verify the steps before coding and getting into depth or
   making wrong statements :-) The further I go with an error the more expensive to fix (in terms of 
   wasted time).

   The key idea is to dynamically extend the graph to a graph g'. When ever we are on a vertex in 
   the original graph g, there are the edges given + to every other vertex where no edge was given
   there exists the "bonus edge". Once used we are in g' and can't use the "bonus edge" anymore.
   That is, im g' there exist only the original edges to vertices in g but to their "mirror" in
   g'. 

   Visually, I drew the original graph g and on top a layer with the graph g'... Besides 
   this I could use dijkstra. A vertex is identified with an integer in this solution. A vertex
   in g has an id below a certain value and a vertex in g' has just an offset to that id. There
   are certainly more apealing designs to that, but it did work and I could verify some basic
   cases.
*/

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>
#include <iostream>

struct Edge
{
	int destId_, weight_;

	Edge(int destId, int weight) : destId_(destId), weight_(weight) { }	
};

struct TraversalItem
{
	int vertexId_, cost_, parentId_;
	TraversalItem(int vertexId, int cost, int parentId) 
		: vertexId_(vertexId), cost_(cost), parentId_(parentId) { }
	TraversalItem() : TraversalItem(-1, -1, -1) { }
};

using Path = std::pair<int, std::vector<std::pair<int, bool>>>;

class Graph
{
private:
	const int bonusVertexIdOffset = 100000;
	std::unordered_map<int, std::unordered_map<int, int>> edges_;
	std::unordered_set<int> vertices_;

public:
	void addEdge(int u, int v, int weight)
	{
		if (u >= bonusVertexIdOffset || v >= bonusVertexIdOffset) throw "id out of range";
		edges_[u][v] = weight;
		edges_[v][u] = weight;
		addVertex(u);
		addVertex(v);
	}

	void addVertex(int vertexId) 
	{ 
		if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";
		vertices_.insert(vertexId);
	}

	// main part of algorithm 
	// it returns the path cost and the visited vertice id's with a flag wether they were in g or g'
	Path getShortestPathWithBonusEdge(int start, int end, int bonusWeight)
	{
		auto tiComparer = [](const TraversalItem& a, const TraversalItem& b) -> bool { return a.cost_ > b.cost_; };
		std::priority_queue<TraversalItem, std::vector<TraversalItem>, decltype(tiComparer) > tqueue(tiComparer);
		std::unordered_map<int, TraversalItem> state;

		tqueue.push(TraversalItem(start, 0, -1)); // start with start
		state.emplace(std::pair<int, TraversalItem>(start, TraversalItem(start, 0, -1))); // start must be in state, too
		while (tqueue.size() > 0)
		{
			auto u = tqueue.top();
			tqueue.pop();

			int uId = u.vertexId_;
			if (uId == end || uId == end + bonusVertexIdOffset)
			{
				end = uId; // path end id, it might be in g'
				break; // if end is now the cheapest to reach: done
			}
			auto edges = getOutEdges(uId, bonusWeight);
			for (auto edge : edges)
			{
				int cost = u.cost_ + edge.weight_;
				int vId = edge.destId_;
				auto vStateIt = state.find(vId);
				if (vStateIt == state.end())
				{
					TraversalItem ti(vId, cost, uId);
					vStateIt = state.emplace(std::pair<int, TraversalItem>(vId, ti)).first;
					tqueue.push(ti); 
				}
				else if(vStateIt->second.cost_ > cost)
				{
					vStateIt->second.cost_ = cost;
					vStateIt->second.parentId_ = uId;
					tqueue.push(vStateIt->second); // since there's no update-key function... 
				}			
			}
		}

		// reconstruct path
		auto stateIt = state.find(end);
		if (stateIt != state.end())
		{
			// reached the end
			std::vector<std::pair<int, bool>> path;
			int vertexId = stateIt->second.vertexId_;
			int cost = stateIt->second.cost_;
			while (vertexId != -1)
			{
				bool gs = vertexId >= bonusVertexIdOffset;
				int vId = gs ? vertexId - bonusVertexIdOffset : vertexId;
				path.push_back(std::pair<int, bool>(vId, gs));
				vertexId = state[vertexId].parentId_;
			}
			return Path(cost, std::vector<std::pair<int, bool>>(path.rbegin(), path.rend()));
		}
		return Path(-1, std::vector<std::pair<int, bool>>()); // empty path
	}

private:
	std::vector<Edge> getOutEdges(int vertexId, int bonusEdgeWeight)
	{
		std::vector<Edge> edges;
		
		int u = vertexId;
		int vIdOffset = 0;
		if (u >= bonusVertexIdOffset)
		{
			u -= bonusVertexIdOffset;
			
			// bonusedge already used, so only original edges are possible
			auto edgeIt = edges_.find(u);
			if (edgeIt != edges_.end())
			{
				for (auto v : edgeIt->second)
				{
					// use orginial edge but stay in g'
					edges.push_back(Edge(v.first + bonusVertexIdOffset, v.second));
				}
			}
			return edges;
		}

		// a vertex that was reaches without bonus edge, so
		// every pair of edges is possible: either from the original 
		// graph or using the bonusEdge
		for (auto v : vertices_)
		{
			if (v == u) continue;
			auto edgeIt1 = edges_.find(u);
			if (edgeIt1 != edges_.end())
			{
				auto edgeIt2 = edgeIt1->second.find(v);
				if (edgeIt2 != edgeIt1->second.end())
				{
					// use original edge within g
					edges.push_back(Edge(v, edgeIt2->second));
					continue;
				}
			}
			// add bonus edge to g'
			edges.push_back(Edge(v + bonusVertexIdOffset, bonusEdgeWeight));
		}

		return edges;
	}
};

void printResult(int start, int end, int bonusWeight, const Path& path)
{
	std::cout << "shortes path from " << start << " to " << end 
		<< " with bonus edge weight " << bonusWeight << " is " << std::endl;
	std::cout << "  weight: " << path.first << std::endl;
	std::cout << "  path: ";
	for (auto v : path.second)
	{
		std::cout << v.first << (v.second ? "' " : " ");
	}
	std::cout << std::endl << std::endl;
}

int main()
{
	Graph g;
	g.addEdge(1, 2, 2);
	g.addEdge(1, 4, 4);
	g.addEdge(2, 3, 1);
	g.addEdge(3, 4, 3);
	g.addEdge(4, 5, 1);
	g.addEdge(5, 6, 8);
	g.addEdge(3, 6, 9);
	g.addEdge(1, 6, 99);
	g.addEdge(2, 6, 99);
	g.addVertex(20);

	printResult(1, 5, 2, g.getShortestPathWithBonusEdge(1, 5, 2));
	printResult(1, 4, 2, g.getShortestPathWithBonusEdge(1, 4, 2));
	printResult(1, 5, 50, g.getShortestPathWithBonusEdge(1, 5, 50));
	printResult(1, 6, 9, g.getShortestPathWithBonusEdge(1, 6, 9));
	printResult(1, 6, 7, g.getShortestPathWithBonusEdge(1, 6, 7));
	printResult(1, 20, 25, g.getShortestPathWithBonusEdge(1, 20, 25));

	/* Output
	shortes path from 1 to 5 with bonus edge weight 2 is
	weight: 2
	path: 1 5'

	shortes path from 1 to 4 with bonus edge weight 2 is
	weight: 3
	path: 1 5' 4'

	shortes path from 1 to 5 with bonus edge weight 50 is
	weight: 5
	path: 1 4 5

	shortes path from 1 to 6 with bonus edge weight 9 is
	weight: 12
	path: 1 2 3 6

	shortes path from 1 to 6 with bonus edge weight 7 is
	weight: 11
	path: 1 4 6'

	shortes path from 1 to 20 with bonus edge weight 25 is
	weight: 25
	path: 1 20'
	*/
}

/* Approach
   1) makae a bool-field and store for every light the rays. 
      Simple to code
	  takes O(N) to insert a light
	  take O(1) to query light (with very small constant factor)
	  Need to know size of grid in advance (which is given)
	  takes O(N*N) space and thus O(N*N) time to initialize 

   2) Just store which columns and rows are illuminated (e.g. in a set)
      Do the same with diagonals, store which diagonals (up and down, looking from the left boarder) are illuminated
	  takes O(1) to insert light
	  takes O(1) to query light (with higher constant factor than solution 1)
	  takes O(1) to initialize field
	  do not need to know field dimensions
	  
   So I choose approach 2

   (saw later it matches the exisitng solution...)
*/

#include <unordered_set>
#include <cassert>

class LightGrid
{
private:
	std::unordered_set<int> lightRow_;
	std::unordered_set<int> lightCol_;
	std::unordered_set<int> lightDiagDown_;
	std::unordered_set<int> lightDiagUp_;

public: 
	void placeLight(int col, int row)
	{
		lightRow_.insert(row);
		lightCol_.insert(col);
		lightDiagDown_.insert(getDiagonalDownId(col, row));
		lightDiagUp_.insert(getDiagonalUpId(col, row));
	}

	bool checkLight(int col, int row)
	{
		return lightRow_.find(row) != lightRow_.end() ||
			lightCol_.find(col) != lightCol_.end() ||
			lightDiagDown_.find(getDiagonalDownId(col, row)) != lightDiagDown_.end() ||
			lightDiagUp_.find(getDiagonalUpId(col, row)) != lightDiagUp_.end();
	}

private:
	inline static int getDiagonalUpId(int col, int row) { return row + col; }
	inline static int getDiagonalDownId(int col, int row) { return row - col; }
};



int main()
{
	LightGrid grid;

	grid.placeLight(1, 1);
	grid.placeLight(10, 50);

	assert(grid.checkLight(1, 1) == true);
	assert(grid.checkLight(1, 999) == true);
	assert(grid.checkLight(8812, 1) == true);
	assert(grid.checkLight(15, 15) == true);
	assert(grid.checkLight(2, -2) == false);
	assert(grid.checkLight(10, 22) == true);
	assert(grid.checkLight(10, 50) == true);
	assert(grid.checkLight(11, 51) == true);
	assert(grid.checkLight(8, 48) == true);
	assert(grid.checkLight(8, 52) == true);
	assert(grid.checkLight(12, 52) == true);
	assert(grid.checkLight(12, 48) == true);

	std::cout << "passed all" << std::endl;
}

#include <limits>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cmath>

/*	
	That's the story (took roughly more than 45 minutes...)

	result = base ^ exponent, where the exponent is double (meaning e.g. 2.14 ^ 10.1241 or -2.14 ^ -1.42 
	which is a complex number)

	I can't cover all the special cases, such as -inf + inf, NaN, negative base and negative exponent, 
	so I just assume base and exponent are positivie... it's complicated enough

	1) if the exponent is an integer it's easy base^8 = ((base^2)^2)^2 (note 3 instead 8 multiplications, 
	   roughly lg(exp) multiplications

	2) if the exponent has a decimal part e.g. base^8.5 we can write: base^(8+1/2) = base^8 * base^(1/2) 
	   (base^1/2 is the square-root of base, base^1/4 is the 4-th root of base etc...)
	   so after powering the integer part, we multiply it with the power of the decimal part.

	   powering the decimal part rquires us to have a root. root can be self-made by using newton method. 
	   newton method requires a good guess to converge and to not take long. a good guess can be done using 
	   binary search in the number range.

	   note we can write the decimal part of the power as base^dec_exponent = base^0.33333 (e.g.)
	   which is base^(0.25 + 0.0625 + 0.015625 + ...)
	   which is base^(1/4 + 1/16 + 1/64)
*/

// power with integer exponent
double mypow(double base, unsigned int exp) 
{
	if (exp == 0) return 1;
	if (exp == 1) return base;
	if (exp == 2) return base*base;
	double result = mypow(base, static_cast<unsigned int>(exp / 2));
	result *= result;
	if (exp % 2 == 1) result *= base;
	return result;
}

// takes the square root based on binary search (could use newton method, too)
double mysqrt(double value)
{
	if (value == 0) return value;

	// guess x using "binary search" to get close 
	double lo = 0.0; // root of something never get's below 0
	double hi = value;
	double x = (hi + lo) / 2;
	while (abs(hi - lo) > 0.001)
	{
		x = (hi + lo) / 2;
		double res = x * x;
		if (res > value) hi = x;
		else lo = x;
	}

	// with the reasonable accurate guess perform newton methode
	for(int i = 0; i < 20; i++)
	{
		x = x - ((x*x - value) / (2 * x));
	}

	return x;
}

// powerfunction as desired by the question
double mypow(double base, double exp) 
{
	if ((exp < 0) && (base < 0) && (exp - static_cast<int>(exp) > 0.0)) throw "no support for complex numbers";
	if (exp < 0) return 1.0 / mypow(base, -exp); // negative exponent is just 1/pow(base, -exp)

	double result = mypow(base, static_cast<unsigned int>(exp)); // power integer part
	double expdec = exp - static_cast<unsigned int>(exp); // remove integer part from exponent: 0 <= expdec < 1
	if (expdec >= 1.0) throw "exponent too high";

	if (expdec > 0.0)
	{
		double epsilon = 0.000000000000001;
		double currentRs = 1.0;
		double currentRt = mysqrt(base);
		double currentExp = 0.5;
		double remainingExp = expdec;

		while (remainingExp > epsilon && currentExp > epsilon)
		{
			if (remainingExp >= currentExp)
			{
				currentRs *= currentRt;
				remainingExp -= currentExp;
			}
			currentRt = mysqrt(currentRt);
			currentExp /= 2;
		}

		result *= currentRs;
	}
	return result;
}

// test helper function
void testMyPow(double base, double exp)
{
	double myresult = mypow(base, exp);
	double result = pow(base, exp);
	double error = abs(myresult - result);
	std::cout << "tested " << base << "^" << exp << " mypow returned " << myresult << " pow returned " << result << " error " << error << std::endl;
}

int main()
{
	testMyPow(2.0, 20.0);
	testMyPow(2.0, -5.0);
	testMyPow(2, 1.5);
	testMyPow(0.212, 91.231);
	testMyPow(891.212, 0.33333333333);
    return 0;
	/* output 
	tested 2^20 mypow returned 1.04858e+06 pow returned 1.04858e+06 error 0
	tested 2^-5 mypow returned 0.03125 pow returned 0.03125 error 0
	tested 2^1.5 mypow returned 2.82843 pow returned 2.82843 error 0
	tested 0.212^91.231 mypow returned 3.47494e-62 pow returned 3.47494e-62 error 2.59085e-77
	tested 891.212^0.333333 mypow returned 9.62337 pow returned 9.62337 error 3.55271e-15	
	*/
}

@Sergey
I am not sure I understood the quasi-trie-approach.
But you are right, if you can't inverse the problem statement to say "it's certainly not in there"
you may need to pack as many words into memory as possible. I researched a bit, Minimal Acyclic Finite State Automaton (DAWG) is a modification of the trie that could do it.
Anyway upvoted your post ;-)

since everybody can do above, I will just write the prove :-)
prove by induction: base case ''; '(' ')'
which class of grammair: you can write a BNF production like
programm = {expression}
expression = "(" expression ")" | "(" ")"

{prodcution} means n-times, where 0<=n
2nd prove, just write a dump parser like a LL1 or recursive descent

so it's at most a context free language, question is if its a regular grammar as well (finite automata) ... it's too long, but I think a regular automata can't parse it (not to be confused with modern regular expressions...) could somebone comment on the last please.