CareerCup

assumption: wanted is the successor of a node and it's a binary search tree, whose
inorder traversal would lead to a increasing sequence like the sample
(thus left node <= this <= right).

class Node
{
	Node *parent = nullptr;
	Node *left = nullptr;
	Node *right = nullptr;
	char value;

	Node* next() // = sucessor
	{
		if(right != nullptr) return right->min();
		Node *c = this;
		while(c->parent != nullptr && c->parent->left != c) c = c->parent;
		return c->parent; // may be nullptr, if there is none
	}

	Node* min()
	{
		Node* c = this;
		while(c->left != nullptr) c = c->left;	
		return c;
	}
}

what are the id's used for? is it desired that they are sequential (e.g. used for keys) or rather randomly distributed? How much of the range can we leave unused without overusing the range? How many keys per second? Bursts? Is a conflict acceptable or must the keys be truely unique for ever?

An approach I could imagine works is, if we have a slower transactional storage, where we can store block assignments to servers. A server picks such a block and generates sequential numbers. If he runs out of numbers (obviously k cycles before) in his blocks, he picks the next block. This has the advantage that if a server goes down, we use max blocksize numbers, usually such a transactional storage is around in the infrastructure - they are comparably slow, reliable for little data. Alternatively, the block assignment can be implemented on this same machines that delivers the key using a protocol (such as PAXOS) that allows machine failures as long as a majority of machines stays online.

I would as well try to persist the current block counter, so in the worst case, it can be read and a safe offset can be added that will waste a lot of numbers but since it should never occure it's an acceptable safety mechanism.

@ kanukadze
it looks ok to me. I don't get your constants 1 << 21 (roughly 16 MB memory, can't you use more?) The hash function has no upper limit, so it creates you an int 2^32 or 2^64 (don't kow c# that well anymore), anyway best case is 32 - 6 bits: 2^26 is > 2^21 so you will sooner or later access elements that aren't there... a remainder % would help although it messes up the hash distribution a bit, better is a hash function that takes the range into account and perfectly distributes in this range...
what are actually this ";6" ";21" close to the shift operators?
the idea was certainly right, I find it elegant to invert the array and work with OR before inverting the whole thing. What interview was it? was it just one or several?

how much memory do we have? how many words?
this quesion wants optimal memory usage, since we accept false negatives, we should minimize the probability of false negatives by maximizing a hash value and picking a "good" hash function. Hashtables are not optimal for such a problem due to the overhead not required in this problem (e.g. for a given hash-value we just need a bit, conflicts don't matter, no bucket lists or open addressing required, filling all possible values is just a huge overhead - not in terms of big-O but practically). Use a bit-array and index it with a hash value. Scale the size of the array to the memory available to minimize probability of false negatives.

Preparation step:
1) create an array of max size n with int's (n ints with b bits)
2) fill the table with 0xffffffff (depending on int size)
3) for each word compute a hash: 0<= hash < n*b and unmaks the bit hash%b of array[hash/b]

Query:
compute hash for word
check if bit hash%b of array[has/b] is set. If set word is for sure not in there
If not set word is probably in there (or an other word colliding with the same hash-value is in there...)

/* Interpretation of the question: Given an N-ary tree, find 
   the longest sequence (path) in it.
   Longest sequence: Longest sequence of vertices without 
   using a vertice twice by following the edges of the tree. 
   That is the longest path from one leave to an other leave or, 
   if no two leaves exist the path from the leave to the root.
 
   Solution idea:
 
   1) brute force: do from every Vertex a bfs to any other vertex
      time: O(V*V)
	  disadvantage besideds time complexity: does not work well on 
	  usual tree structure, so I had to construct a graph first. 
   2) improved brute force: just do it from every leave 
      (vertex with degree 1): minor improvement
   3) Use tree structure and do it top down in O(V):
      start with root
	  do a postorder traversal, ask each child for the maxBranchPath 
	  and the maxDiametrePath
	  -maxBranchPath is the longest path from any leave of the tree 
	  rooted at a specific node to that specific node, not includinig 
	  that node
	  -maxDiametrePath is the longest path from any leave of the 
	  tree rooted at a specific node to either any other leave of that 
	  node or to that node (latter is equal to the maxBranchPath)
	  but not including that node 
	  
  	  Keep track of the two largest maxBranchPath from the children
	  if the length of the sum of this two branch paths + 1 > 
	  maxDiameterePath a new maxDiametere is found.

	Implementation for simplicity with raw pointers
*/

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

class NNode
{
public:
	using Path = std::vector<const NNode*>;

private:
	int value_;
	std::vector<NNode*> children_;
	
	// maxDiametrePath and maxBranchPath are out parameteres
	void getMaxDiametreMaxBranch(Path& maxDiametrePath, Path& maxBranchPath) const
	{		
		maxDiametrePath.clear();
		maxBranchPath.clear();

		Path maxBranchPath2;

		for(auto c : children_)
		{
			Path diametrePath, branchPath;			
			c->getMaxDiametreMaxBranch(diametrePath, branchPath);
			if(diametrePath.size() > maxDiametrePath.size())
			{
				maxDiametrePath = std::move(diametrePath);
			}
			if(branchPath.size() > maxBranchPath.size())
			{
				maxBranchPath2 = std::move(maxBranchPath);
				maxBranchPath = std::move(branchPath);
			} 
			else if(branchPath.size() > maxBranchPath2.size())
			{
				maxBranchPath2 = std::move(branchPath);
			}
		}

		if(maxDiametrePath.size() == 0) 
		{
			maxDiametrePath.push_back(this);
		}
		maxBranchPath.push_back(this);

		int newDiametrePathSize = maxBranchPath.size() + maxBranchPath2.size(); 
		if(newDiametrePathSize > maxDiametrePath.size())
		{
			maxDiametrePath.resize(newDiametrePathSize);
			std::copy(maxBranchPath.begin(), maxBranchPath.end(), maxDiametrePath.begin());
			std::copy(maxBranchPath2.rbegin(), maxBranchPath2.rend(), 
				maxDiametrePath.begin() + maxBranchPath.size());
		}
	}

public:
	NNode(int value) : value_(value) { }

	Path getMaxDiametrePath() const
	{
		Path maxPath, maxBranch;
		getMaxDiametreMaxBranch(maxPath, maxBranch);
		return maxPath;
	}

	void addChild(NNode* child)  
	{
		children_.push_back(child);
	}	

	int getValue() const { return value_; }
};


int main()
{
	NNode n1(1);
	NNode n2(2);
	NNode n3(3);
	NNode n4(4);
	NNode n5(5);
	NNode n6(6);
	NNode n7(7);
	NNode n8(8);
	NNode n9(9);
	NNode n10(10);
	NNode n11(11);
	NNode n12(12);
	NNode n13(13);
	NNode n14(14);
	NNode n15(15);

	n14.addChild(&n15);
	n11.addChild(&n14);
	n9.addChild(&n13);
	n7.addChild(&n11);
	n7.addChild(&n12);
	n7.addChild(&n10);	
	n7.addChild(&n9);
	n6.addChild(&n8);
	n2.addChild(&n6);
	n2.addChild(&n7);
	n1.addChild(&n2);
	n1.addChild(&n3);
	n1.addChild(&n4);
	n1.addChild(&n5);

	std::cout << "max diametre path from n1" << std::endl;
	for(auto n : n1.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl << std::endl << "max diametre path from n6" << std::endl;
	for(auto n : n6.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl << std::endl << "max diametre path from n5" << std::endl;
	for(auto n : n5.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl;
	return 0;

}

/* output:
max diametre path from n1
15 14 11 7 2 6 8 

max diametre path from n6
8 6 

max diametre path from n5
5
*/

what is a subnet? Is he refering to the class a,b,c,d,(e) networks?
If so, you can determine the class of the network by the ip address.
This would reduce data, since you are not required to count the hosts within the network
(there are roughly ~2.1 Mio class a+b+c+d networks). If he want to identify potential
subnets or even hosts (belongig to a botnet?) inside the a-b-c-d networks he will not get
what he wants by spliting on 8.bit boundaries but we need to guess a subnet everywhere.
for a given IP, ignoring class a,b,c,d, there are *theoretically* 32 subnets (from single machine
to whole IP v4 range)

To simplify I would create an integer, lets call it subnet-id with the subnet-size and
the remaining subnet id:
1st bit set: remaining 32 bit contain the ip
1st bit 0, 2nd bit 1: remaining 31 bits will contain the subnet (actually that does not exist in practice)
1st, 2nd 0, 3rd 1: remaining 30 bits will contain the subnet id...

With 33 bits all potential subnets are covered, each ip will create 32 such subnet-ids.

To actually count, I would create a self balancing tree in memory to count frequencies
by above subnet-id. If memory gets full, write id:frequency into a file, ordered by id
(thus no HT, whereas a HT could be used but before writing I have to sort it in-place
(no more memory) which is not a standard HT use case ... it could be done by a custom
HT that uses open addressing... which is prefered over a tree)

Continue untill all has been processed and we have m sorted files. Merge them by key.
Traverse final file to find 4 highest values.

Can be implemented using map-reduce to scale to many machines.

Data can be appended if more logfiles come without the need to re-process prior .processed
data.

"group together dishes with common ingredients" is ambiguous and the sample doesn't really help. Following interpretations are possible:
1) For every ingredient list common dishes, e.g. two dishes that share two ingredients get listed twice
2) For every ingredient list common dished, but avoid listing a pair twice
3) For the latter one, we could as well prefer to list the dishes which share most ingredients first

1) is easy: create a hashtable with ingredient as key and dishes as list. then out put this lists if they are bigger than 1
2) I would approach as 1) but then I could keep a matrix which stores the already output pairs (for an ingredient that is used in k dishes this is (k-1)! pairs) making the whole thing exponential in time and quadratic in space (matrix), which is clearly not acceptable

I'm interested in approaches...I can't see it.

/*
solution idea (inspired by merge sort)

1) make sure both, arrival and departure times are sorted. Arrival 
times are already, departure time aren't.
Then think of the arrivals and departures as of 
queues and look at their first elements. The smaller one wins, if equal, 
the departure wins.
if the winner is departure, a gate is freed (assume, it can go below 0)
if the winner is arrival, a gate is used
sort departure time ascending()

2) assume the arrival and departure time can be converted into some
form that allows easy comparsion of > (string representation as given
won't do it). Leave this "parsing step out" but do something like 
houre*60+minute.

time complexity: O(n*lg(n)) assuming #departures and #arrivals are equal
*/

#include <vector>
#include <algorithm>

int GetGates(std::vector<int>& arrivals, std::vector<int>& departures)
{
	std::sort(departures.begin(), departures.end());
	int n=arrivals.size();
	if(n != departures.size()) throw "#arrivals should equal #departures";
	if(arrivals[n-1] >= departures[n-1]) throw "last departure must be after last arrival";

	int a=0, d=0, mg=0, cg=0; // mg: max # gates, cg: current # gates
	
	while(a<n) 
	{
		if(arrivals[a] < departures[d]) 
		{ 
			cg++; 
			a++;
		}
		else 
		{
			cg=std::max(cg-1,0);
			d++;
		}
		mg=std::max(cg,mg);			
	}
	return mg;
}

/*
Given a string consisting only of digits, find the missing number. 
For instance, given the string 596597598600601602 
the missing number is 599. You may assume all the numbers are 
positive integers and the sequence increases by one at each number 
except the missing number. The numbers will have no more 
than six digits and the string will have no more than 
four hundred characters.

Your task is to write a function to find the missing number in the sequence. 
If there should no missing number whatsoever, return a value of -1


/*
Solution:
consider sequences like 9|10|11|13 or 98|100|101|102

just try the starting number and then try for the next+1 and next+2, 
if more than one next+2 were found stop, etc...

relatively straight forward, considering the special cases

runtime: at most 6*n (which is not possible): anyway it is O(N)
space: O(1)
*/

#include <string>
#include <iostream>

using namespace std;

// gets the integer at position i with length m, returns it or -1, if none
int GetValue(const string& str, int i, int m)
{
	if (i + m > str.length()) return -1;
	int value = 0;
	for (int j = 0; j < m; j++)
	{
		int c = str[i + j] - '0';
		if (c < 0 || c > 9) return -1;
		value = value * 10 + c;
	}
	return value;
}

int FindMissingNumber(const string& str)
{
	// note: it's easy to get rid of the logs but the code is just 
	// not understandable with all those counters
	for (int m = 1; m <= 6; ++m)
	{
		int n = GetValue(str, 0, m);
		if (n == -1) break;
		int missingNo = -1;
		bool fail = false;
		for (int i = m; i != str.length(); i += 1 + log10l(n)) 
		{
			if ((missingNo == -1) &&
				(GetValue(str, i, 1 + log10l(n + 2)) == n + 2))
			{
				missingNo = n + 1;
				n+=2;
			}
			else if (GetValue(str, i, 1 + log10l(n + 1)) == n + 1)
			{
				n++;
			}
			else 
			{
				fail = true;
				break;
			}
		}
		if (!fail) return missingNo; 
	}
	return -1; // not found or no missing number
}


int main()
{
	cout << "596597598600601602: " << FindMissingNumber("596597598600601602") << endl;
	cout << "89101113: " << FindMissingNumber("89101113") << endl;
	cout << "11111211311411511: " << FindMissingNumber("11111211311411511") << endl;
	cout << "909192939495969798100101: " << FindMissingNumber("909192939495969798100101") << endl;
	cout << "9899101102: " << FindMissingNumber("9899101102") << endl;
}

/*
1) all elements on the left must be <= than the element in the 
   middle after n such mirror operations.
2) Most perumtations that are possible are 2^(n/2), that is, 
   swap index 0 with n-1, index 1 with n-2, etc... 
   (independently if given mirror operation is performed outwards inwards)
3) Every element, except the middle one has two possible values, 
   it's value at index or it's value at mirrored index

Solution: 
  f[i] = min(a[i], a[n-1-i]) for 0<=i<n/2
  e[i] = max(a[i], a[n-1-i]) for 0<=i<n/2

  Iterate through the array 1 to n/2-1 and check if:
    f[i]>=f[i-1] AND e[i]>=e[i-1]

  If that succeeded and length of a is odd, only need to check 
  f[n/2-1] <= a[n/2] <= e[n/2+1] if that's true, its sortable, 
  obviously if array length is even, if above iteration succeeded with all checks
  it is sortable.

  Time complexity O(N)
  Space complexicty O(1)
*/

#include <iostream>
#include <algorithm>

using namespace std;

// array with n-elements
bool IsSortable(const int a[], int n)
{
	for (int i = 1; i < n/2; ++i)
	{
		if (min(a[i], a[n - i - 1]) < min(a[i - 1], a[n - i])) 
			return false;
		if (max(a[i], a[n - i - 1]) > max(a[i - 1], a[n - i])) 
			return false;
	}
	if (n & 1 == 1)
		return min(a[n / 2 - 1], a[n / 2 + 1]) <= a[n / 2] &&
			   max(a[n / 2 - 1], a[n / 2 + 1]) >= a[n / 2];
	return true;
}



int main()
{
	int a1[]{ 1,2,3,4,5 };
	cout << "a1: " << IsSortable(a1, sizeof(a1)/sizeof(int)) << endl;
	
	int a2[]{ 5,4,3,2,1 };
	cout << "a2: " << IsSortable(a2, sizeof(a2) / sizeof(int)) << endl;

	int a3[]{ 1,2,6,3,4 };
	cout << "a3: " << IsSortable(a3, sizeof(a3) / sizeof(int)) << endl;

	int a4[]{ 4,2,1,2 };
	cout << "a4: " << IsSortable(a4, sizeof(a4) / sizeof(int)) << endl;

	int a5[]{ 9,8,7,6,5,4,3,2,1 };
	cout << "a5: " << IsSortable(a5, sizeof(a5) / sizeof(int)) << endl;

	int a6[]{ 9,8,7,6,5,4,5,2,1 };
	cout << "a6: " << IsSortable(a6, sizeof(a6) / sizeof(int)) << endl;
}

/*
Linear Solution (O(N)):
- at start, let a be minimum of BST and b the maximum of BST
  while(a <= b):
  - If a+b > desired sum: decrease b to the next lower value
    why: because if the smallest and the largest overshoot the desired sum,
	every combination with the largest element will overshoot, so we can ignore 
	it in the future.
  - If a+b < desired sum: increase a to the next higher value
    why: because if the largest and the smallest will not reach the desired sum, 
	the smallest will not be of any help to ever reach the sum, so we can ignor
	it in the future.
  - If a+b = desired sum: return a,b
  if loop terminates without having found anything, there is no pair that has 
  as sum the desired sum the "=" in the while loop assumes taking two times 
  the same node to build a sum is correct either.

  O(N) because finding min and max takes O(lg(N)) if BST is balanced and O(N) 
  if it's a chain but finding aprox. N-k Predessors and k Successors takes O(N) 
  amortized. so it's O(N). It does not matter if BST is balanced or not.


Logarithmic solution (O(Lg(N))): 
- Make a to be minimum of BST
- Make b to be maximum of BST
  while (a <= b)
	 if a = b: return a,b
	 if a+b > desired sum: find bigest b that satisfies b <= desired sum - a 
	 if a+b < desired sum: find smallest a that that satisfies a >= desired sum - b 

  reasoning is the same as with linear solution, just that finding those limitting values is 
  faster if we use binary search in a supposedly balanced BST . 
  The question here is how many tries are required until it converges or knows it doesn't. 
  I assume it is logarithmic, but I haven't managed to come up with a prove or disprove in
  the time taken for this problem.
*/

#include <utility>
#include <iostream>

using namespace std;


class Node
{
private:
	int _value;
	Node* _left;
	Node* _right;
	Node* _parent = nullptr;

public:
	Node(int v, Node* left, Node* right)
		: _value{ v }, _left{ left }, _right{ right }
	{
		if (left != nullptr) left->_parent = this;
		if (right != nullptr) right->_parent = this;
	}

	Node(int v) : Node(v, nullptr, nullptr) {}

	int get_Value() const { return _value; }

	pair<Node*, Node*> FindSumLinear(int sum)
	{
		Node *a = Min();
		Node *b = Max();
		while ((a != nullptr) && (b != nullptr) &&
			(a->_value <= b->_value))
		{
			int s = a->_value + b->_value;
			if (s > sum) b = b->Predecessor();
			else if (s < sum) a = a->Successor();
			else return pair<Node*, Node*>(a, b);
		}
		return pair<Node*, Node*>(nullptr, nullptr);
	}

	pair<Node*, Node*> FindSumLogarithmic(int sum)
	{
		Node *a = Min();
		Node *b = Max();
		while ((a != nullptr) && (b != nullptr) &&
			(a->_value <= b->_value))
		{
			int s = a->_value + b->_value;
			if (s > sum)
			{
				int db = sum - a->_value;
				b = BinarySearchAprox(db);
				if (b->_value > db) b = b->Predecessor();
			}
			else if (s < sum)
			{
				int da = sum - b->_value;
				a = BinarySearchAprox(da);
				if (a->_value < da) a = a->Successor();
			}
			else
			{
				return pair<Node*, Node*>(a, b);
			}
		}
		return pair<Node*, Node*>(nullptr, nullptr);
	}

private:
	// returns the min note of this subtree
	Node * Min()
	{
		Node *c = this;
		while (c->_left != nullptr) c = c->_left;
		return c;
	}

	// returns the max node of this subtree
	Node * Max()
	{
		Node *c = this;
		while (c->_right != nullptr) c = c->_right;
		return c;
	}

	// returns predecessor or null if none
	Node *Predecessor()
	{
		Node *c = this;
		if (_left != nullptr) return _left->Max();
		while (c->_parent != nullptr && c->_parent->_left == c) c = c->_parent;
		return c->_parent;
	}

	// resturns successor or null if none
	Node *Successor()
	{
		Node *c = this;
		if (_right != nullptr) return _right->Min();
		while (c->_parent != nullptr && c->_parent->_right == c) c = c->_parent;
		return c->_parent;
	}

	// the function returns either the node with it's value or if that value
	// doesn't exist in the tree a node with it's next higher or next lower value 
	Node* BinarySearchAprox(int value)
	{
		Node *n = this;
		while (true)
		{
			if (value > n->_value && n->_right != nullptr) 
				n = n->_right;
			else if (value < n->_value && n->_left != nullptr) 
				n = n->_left;
			else return n; // either a match or we just can't get any closer
		}
	}
};



int main()
{
	const char* tree = "\n"\
	"           8\n"\
	"         /   \ \n"\
	"       4      12\n"\
	"      /  \\       \\\n"\
	"     2    7      14\n"\
	"         /      /   \\\n"\
	"        5     13     15\n";

	Node n2 = Node(2);
	Node n5 = Node(5);
	Node n7 = Node(7, &n5, nullptr);
	Node n4 = Node(4, &n2, &n7);
	Node n13 = Node(13);
	Node n15 = Node(15);
	Node n14 = Node(14, &n13, &n15);
	Node n12 = Node(12, nullptr, &n14);
	Node root = Node(8, &n4, &n12);

	cout << "tree: " << tree << endl << endl;
	for (int i = 1; i < 32; ++i)
	{
		auto result = root.FindSumLinear(i);
		auto result2 = root.FindSumLogarithmic(i);
		cout << endl << "result for sum " << i << ": " << endl;
		if (result.first == nullptr) cout << "LIN: no two nodes found that sum up to " << i << endl;
		else cout << "LIN: " << i << " = " << result.first->get_Value() << " + " << result.second->get_Value() << endl;
		if (result2.first == nullptr) cout << "LOG: no two nodes found that sum up to " << i << endl;
		else cout << "LOG: " << i << " = " << result2.first->get_Value() << " + " << result2.second->get_Value() << endl;
	}
}

/*
Solution approach:
- it looks like a DP problem which seems to work
- How ever, I found it easier to think of it as a parsing problem:
  - match first word, then progress to the next one, start with the smallest word
  - store in a list the word-index or word length
  - if we reach the end without being able to further match, obviously at some point 
    the matching was wrong, as long as we still have alternatives at some point, so 
	we go back one word and retry our luck, if that fails again, go back further
	everytime, when coming back try with a longer word etc...
  - We could think of it as a parser if it can't decide on the next temrinal which
    production it is, so it does look ahead, here it does backtrack, which is the 
	passive version (try all possibilities and back track vs. try o find out be 
	looking ahead)
- Looking at it from a runtime perspective, one could argue, the natural language is 
  built to require little backtracking since if it accidentially finds a word that 
  is part of an other word as it progresses the possibility is getting very small 
  that it comes very far. Whereas in a language where all combintions of letters
  lead to a valid word, this wouldn't be the case.

  I find it a cool question!
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>

using namespace std;

const size_t MAX_WORD_LENGTH = 80;
const char* SAMPLES[] = { "thisisavalidsentence", "thisisavalidsentencewhichrequiresautomaticbacktrack"};
const char* WORD_TABLE[] {"this", "is", "a", "valid", "sentence", "auto", "automatic", 
"with", "sample", "backtrack", "which", "requires", 
"of", "the", "back", "track", "require", "sau"}; //"sau is pig in german :-)

// primitive and not performant, returns if [s, e) is a word
bool IsWord(const string& str, int s, int e)
{
	string ss = str.substr(s, e - s);
	for (auto w : WORD_TABLE)
		if (ss.compare(w) == 0) return true;
	return false;
}

// tries to find a word starting at s, with minimal length minl int the string str
// using IsWord function, returns the length of the found word which is the 
// shortest matching word with length >= minl
int FindWord(const string& str, int s, int minl)
{
	int maxl = min(str.length() - s + 1, MAX_WORD_LENGTH);
	for (int l = minl; l < maxl; l++)
		if (IsWord(str, s, s + l)) return l;
	return 0;
}

// modifies the string str to contain spaces between words, throws exception
// (of type const char*) if failed to reconstruct whole string
void ReconstructSentence(string& str)
{
	vector<int> wordl; // contains the found word lengths
	int i = 0; // current position
	int n = str.length(); 
	int m = 1; // minimal word size to be matched

	while (i < n)
	{
		int l = FindWord(str, i, m); 
		if (l > 0)
		{ // found a word
			wordl.push_back(l);
			i += l;
			m = 1;
		}
		else
		{ // didn't find a word, need to backtrack
			if (wordl.size() == 0) throw "can't find a solution";
			m = wordl.back();
			wordl.pop_back();
			i -= m; // back track word length in string
			m++; // word needs to be longer
		}
	}

	i = 0;
	for (int l : wordl) 
	{
		i += l;
		str.insert(i, " ");
		i++;
	}
}

int main()
{
	for (auto s : SAMPLES)
	{
		string str(s);
		ReconstructSentence(str);
		cout << "sample :" << s << endl << "is: " << str << endl << endl;
	}

	getchar();
	return 0;
}

/*
Assumptions:
- two dimensional due to given coordinates
- move in any of the 8 directions possible, if the field is a "1" , -1,-1, -1, 0, -1, 1 
- from {0,0} to {n-1, n-1} to keeps things more conventional
- {0,0} and {n-1, n-1} are both 1

Example 
{
{1, 0, 1, 1, 0, 0},
{0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 0, 1},
{1, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1},
{0, 0, 1, 1, 0, 1},
}

Solution:
- If we create a graph G=(V,E) where V are the coordinates (positions) in
  the array marked with 1 and E are the edges between two adjecent 
  coordinates that are 1, we can use bread first search to find the
  shortest path between any two vertices that are connected by edges.
- V and E do not need to be objects or form a graph in a classical
  representation such as adjecent list or adjecent matrix, it is 
  created on the fly, coordinates being the vertices and adjecents being
  the list of coordinates one can go from a certain coordinate.
- the BFS traversal tree is kept in a parent array with coordinates, where
  each entry has an associated coordinate with it's parent from the 
  tree traversal.
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>

using namespace std;


class MatrixShortestPath
{
	struct Position
	{
		int x;
		int y;
	};

private:
	vector<vector<bool>> _field;
	int _n;

public:
	MatrixShortestPath(vector<vector<bool>>&& field) : _field{field}, _n(field.size())
	{
		_field[0][0] = true;
		for (int i = 0; i < _n; i++) 
			if (_field[i].size() != _n) 
				throw invalid_argument("field size");
		_field[_n - 1][_n - 1] = true;
	}

	// creates an adjecents list with positions on the fly based on the values of 
	// the field array
	vector<Position> GetAdjecents(Position pos)
	{
		static const int move[8][2]{ {-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1} };
		vector<Position> adj;
		for (int i = 0; i < 8; i++)
		{
			Position np{ pos.x + move[i][0], pos.y + move[i][1] };
			if (np.x >= 0 && np.y >= 0 && np.x < _n && np.y < _n && _field[np.x][np.y])
				adj.emplace_back(np);
		}
		return adj;
	}

	// returns the path as a string containing each position e.g. (0,0) (1,1) etc...
	// using breath first search
	string ComputeShortestPath()
	{
		vector<vector<Position>> parent(_n, vector<Position>(_n, Position{ -1,-1 }));

		// push start into queue and mark parent of start to it self 
		// (0,0) = (root of BFS traversal tree)
		deque<Position> q;
		parent[0][0] = Position{ 0,0 };
		q.emplace_front(Position{ 0, 0});

		while (!q.empty())
		{
			auto u = q.back();
			q.pop_back();
			for (auto v : GetAdjecents(u))
			{
				if (parent[v.x][v.y].x == -1)
				{
					parent[v.x][v.y] = u;
					if (u.x == _n - 1 && u.y == _n - 1)
					{
						q.clear();
						break;
					}
					q.emplace_front(v);
				}
			}
		}

		// case where destination wasn't reached
		if (parent[_n - 1][_n - 1].x == -1) 
			return "no path exists";

		// backtrack the BFS tree from destination to start
		Position pos{_n-1, _n-1};
		vector<Position> path;
		path.emplace_back(pos);
		while (pos.x != 0 || pos.y != 0)
		{
			pos = parent[pos.x][pos.y];
			path.emplace_back(pos);
		}

		// reverse the path and print it to string
		stringstream ss;
		for (int i = path.size() - 1; i >= 0; i--)
		{
			ss << string("(") << path[i].x << "," << path[i].y << ") ";
		}

		return ss.str();
	}
};

int main()
{
	MatrixShortestPath sp( {
		{ 1, 0, 1, 1, 0, 0 },
		{ 0, 1, 0, 0, 1, 0 },
		{ 1, 0, 1, 0, 0, 1 },
		{ 1, 1, 0, 1, 0, 1 },
		{ 0, 1, 1, 1, 0, 1 },
		{ 0, 0, 1, 1, 0, 1 } } );

	cout << sp.ComputeShortestPath();
}

/*
I noticed the task was quite exactly specified with the few words, but it needed some repetition:
- unidirected graph with weights and no cycles: -> that can be viewed as a tree
- the sum of the weight of each path: means one value for the whole structure
- shortest path between two vertices: in this setup, it's as well the shortest 
  weighted path because no forward and backward edges exist (would create cycles 
  on unidirected graph)
  --> no need for Djikstra or other heavy weight algos 
  --> negative weights don't matter

Solution approach:
- pick an arbitrary node as root to start, traverse down until first leave, 
  note it's total tree size (=1) propagate that size to the parent, so parent 
  can keeps track of it's total tree size etc. While doing this for every completely 
  visited node store in a list it's tree size and weight of edge to parent
- when tree is completely traversed, go through the above created list 
  (with length n) with pairs that contain tree size (s) and edge-weight (w):
  sum += (n-s)*s*w
  (node: an edge kind of cut's the tree in two, if a leave is cut, 
  it's sub-tree is 1, so 1*n paths to all vertices, if the subtree is 2, it's 2*(n-2), 
  because from each of the two nodes goes a path to each of the remaining n-2 nodes)

The solution looks still complicated, maybe there is an easy algo for it. 

Time-Complexity: O(|V|+|E|) = O(|V|+[V]) = O(|V|) due to constraints given
Space-Complexity: O(|V|)
*/


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

using namespace std;


class Node
{
private:
	string _id;
	vector<pair<int, Node*>> _adj;
	
	Node *_parent = nullptr; // parent
	int _size = 1; // subtree sisze
	int _wtop = 0; // weight to parent
	bool _visited = false;

public:
	Node(string id) : _id{ id } {}

	void Connect(Node *adj, int w)
	{
		_adj.emplace_back(pair<int, Node*>(w, adj));
		adj->_adj.emplace_back(pair<int, Node*>(w, this));
	}

	int SumAllPairWeight()
	{
		ClearAll();
		vector<pair<int, int>> nodes; //1st: treesize, 2nd: weight to parent
		stack<Node*> s;
		s.push(this);
		while (!s.empty())
		{
			auto u = s.top();
			bool visit = true; 
			for (auto e : u->_adj)
			{
				auto v = e.second;
				auto w = e.first;
				if (v != u->_parent && !v->_visited)
				{
					visit = false;
					s.push(v);
					v->_parent = u;
					v->_wtop = w;
					v->_size = 1;
				}
			}
			if (visit)
			{
				u->_visited = true;
				s.pop();
				nodes.emplace_back(pair<int, int>(u->_size, u->_wtop));
				auto p = u->_parent;
				if (p != nullptr)
				{
					p->_size += u->_size;
				}
			}
		}

		int sum = 0;
		int n = nodes.size();
		for (auto u : nodes)
		{
			int s = u.first;
			int w = u.second;
			sum += (n - s)*s*w;
		}
		return sum;
	}

private:
	void ClearAll()
	{
		unordered_set<Node*> vis;
		stack<Node*> s;
		s.push(this);
		while (!s.empty())
		{
			auto u = s.top();
			s.pop();
			u->_visited = false;
			u->_parent = nullptr;
			u->_wtop = 0;
			u->_size = 1;
			vis.emplace(u);
			for (auto e : u->_adj)
			{
				auto v = e.second;
				if (vis.find(v) == vis.end())
				{
					s.emplace(v);
				}
			}
		}
	}
};

int main()
{
	Node a{ "A" };
	Node b{ "B" };
	Node c{ "C" };
	Node d{ "D" };

	a.Connect(&b, 1);
	b.Connect(&c, 2);
	b.Connect(&d, 3);

	cout << "sum (from a): " << a.SumAllPairWeight() << endl;
	cout << "sum (from b): " << b.SumAllPairWeight() << endl;

	getchar();
}

/*
Dynamic programming problem since j[i] >= j[i-1], i[i] >= i[i-1]
can only move from left to right and top down

dp[i,j] = max( 
               dp[i-1,j], // if i>0
               dp[i,j-1], // if j>0
			   0 // if i=0 and j =0
			  ) + c[i,j]



Timecomplexity: O(n^2)
Spacecomplexity: O(n^2), can be optimized to O(n) (need vector of size n+1)
*/

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

using namespace std;

vector<vector<int>> ParseHouses(int n, const string& houses);

int MaxCollect(int n, const string& houses)
{
	auto c = ParseHouses(n, houses);
	vector<vector<int>> dp(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int c1 = i > 0 ? dp[i - 1][j] : 0;
			int c2 = j > 0 ? dp[i][j - 1] : 0;
			dp[i][j] = max(c1, c2) + c[i][j];
		}
	}
	return dp[n - 1][n - 1];
}


void Match(istream& iss, char c)
{
	char r = '\0';
	while (!iss.eof() && (r == ' ' || r == '\n' || r == '\r' || r == '\0')) iss >> r;
	if (r != c) throw "syntax error";
}

vector<vector<int>> ParseHouses(int n, const string& houses)
{	
	vector<vector<int>> res(n, vector<int>(n, 0));
	stringbuf sb(houses);
	istream iss(&sb);

	for (int i = 0; i < n; i++)
	{
		Match(iss, '(');
		for (int j = 0; j < n; j++)
		{
			int c;
			iss >> res[i][j];
			if (j != n - 1) Match(iss, ',');
		}
		Match(iss, ')');
		if (i != n - 1) Match(iss, ',');
	}

	return res;
}



int main()
{
	cout << MaxCollect(4, "(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)");
}

/*
1. Copy the two arrays into one (v3)
2. Sort it according to it's Id's
3. Remove duplicates
4. Resize 
5. Sort again according to weights

note: the fact the input is sorted was not used, there might be a better solution I couldn't spot
*/

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

using namespace std;

struct Item
{
	int id;
	int weight;
};

vector<Item> Merge(const vector<Item>& v1, const vector<Item>& v2)
{
	vector<Item> v3(v1.size() + v2.size());
	copy(v2.begin(), v2.end(), copy(v1.begin(), v1.end(), v3.begin()));
	sort(v3.begin(), v3.end(), [](Item& a, Item&b) { return a.id < b.id; });
	int j = 0;
	for (int i = 1; i < v3.size(); ++i)
	{
		if (v3[j].id == v3[i].id)
		{
			v3[j].weight += v3[i].weight;
		}
		else
		{
			v3[++j] = v3[i];
		}
	}
	v3.resize(j+1);
	sort(v3.begin(), v3.end(), [](Item& a, Item& b) {return a.weight < b.weight; });
	return v3;
}


int main()
{
	vector<Item> v1{ {1,2}, {2,3}, {4, 8}, {-1, 2} };
	vector<Item> v2{ {3,1}, {2,7}, {9, 2}, {-1, 1}, {-1,1} };
	auto res = Merge(v1, v2);
	for_each(res.begin(), res.end(), [](Item& a) { cout << "item id: " << a.id << " weight " << a.weight << endl; });
}

/*
1. Count character occurence in input per character with a hash table
2. Construct palindrome by taking two characters out and placing them at the start and end
3. If at least one character has odd occurence, place one of it in the middle
*/

#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

string ConstructPalindrome(const string& input)
{
	int size = 0; // size of the resulting palindrome
	unordered_map<char, int> cm; // character count map

	// count each character, if a character occures an even amount of time, 
	// increase the palindrome size by that size (2 each time)
	for (char c : input)
	{
		unordered_map<char, int>::iterator it;
		if ((it = cm.find(c)) != cm.end())
		{
			it->second++;
			if (it->second % 2 == 0) size += 2;
		}
		else
		{
			cm[c] = static_cast<int>(1);
		}
	}

	// fix size for the case there is at least one character with an odd count
	// and reserve space for result
	if (size < input.size()) size++; 
	string result(size, ' ');

	// construct result
	int i = 0;
	int j = size - 1;
	for (auto p : cm)
	{
		while (p.second > 1) 
		{
			result[i++] = p.first;
			result[j--] = p.first;
			p.second -= 2;
		}
		if (p.second == 1) result[size / 2] = p.first;
	}
	return result;
}



int main()
{
	cout << "aha: '" << ConstructPalindrome("aha") << "'" << endl;
	cout << "ttaatta: '" << ConstructPalindrome("ttaatta") << "'" << endl;
	cout << "abc: '" << ConstructPalindrome("abc") << "'" << endl;
	cout << "gggaaa: '" << ConstructPalindrome("gggaaa") << "'" << endl;

	getchar();
}

imagine a crane and ,loading docks as the question sugest:
1) minimize moves, assuming sorted order means that the empty dock is at the end and not in the midle somewhere after sort, it is easy:
- start with i = 1
- while i <= n-1
- if box in dock i is not box i, take that box and move it to the empty dock n+1
- get box i and move it to dock i, thereby freeing dock j
- while j is not n+1: get box j and move it to dock j, asign new empty dock to j
- increment i

2) minimize distance of move
I doubt there is a perfect solution in polynominial time. I see no common subproblem, greedy choice etc. It reminds me to the rubik cubes problem. I guess best one can do is somehow try to minimize, but I wouldn't be able to come up with a solution in the remaining time without hints.

/* For the fun of it, here Dijkstra's shunting-yard version
   reference: wikipedia / Shunting-yard_algorithm
   
   Simplified for the problem:
   - two stack, one for the numbers that need to be fed into a binary-operation
   - the other for operators/open parentesis (=elements) that haven't been used

   - While there are tokens:
		- Read a token (number, parentesis, operator)
		- if token is number: push on number stack      
			> explanation: 
			> since we read infix notation, we do not know where this number binds to
			> to until we see the next operator or a closing parentesis
		- if token is binary operator (let's say o1):	
			- while o1.precedence <= elementstack.top.precedence: Evaluate() 
			  > we know now, that no operation with a higher precedence was binding to these 
			  > numbers we have seen before, so we can safely evaluate			  
			  > e.g. when the o1.precedence was higher, it was clear that top of number 
			  > stack would be used with the next "number" (or term) and the current o1
			  > (note the = is only valid because we only consider left associative, if 
			  > o1 was right associative it could take the argument away ... ... see wikipedia article
			- push o1 on stack
			  > o1 needs to be evaluated later, of course
		- if open parentesis: push on element stack
		  > explanation this is just a marker, so we know when to stop when the parentesis close
		- if close parentesis: 
			- while(elemenstack.top != closeparentesis: Evaluate()
			  > a closed parentesis tells us that we must evaluate to it's left, regardless 
			  > what follows on the right
			- remove open parentesis from stack
			  > it's been matched with a right parentesis
   - Evaluate until no Bin-Operators are left on elementstack

   Note this version doesn't deal with the unary - eg. -12+24 won't work as well -12+-34 does not work :-)  
*/

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>

using namespace std;

class ExpressionEval
{
private:
	enum class ExprElemType { OpenPar, ClosePar, BinOp };
	struct ExprElem
	{
		char Identifier; // +,-,/, ...
		ExpressionEval::ExprElemType ElementType; 
		int Precedence; // 1,2, ... for Binary Operations
		bool LeftAssocicative; // not used yet
		bool RightAssociative; // not used yet
		int(*BinOperation)(int, int); // the function to do the operation
	};

	istream& _input; // input stream
	stack<const ExprElem*> _elementStack; 
	stack<int> _numStack;

	static const ExprElem ElementTable[6];

public:
	ExpressionEval(istream& input) : _input(input) {}

	int EvaluateExpression()
	{
		// read expression piece by piece
		while (!_input.eof())
		{
			if (_input.peek() == '\n') // get rid of the new line in the input string at the end of expression, in case...
			{
				_input.get();
				break;
			}

			// see if it is an 
			const ExprElem* nextElement = GetExpressionElemenet();
			if (nextElement == nullptr)
			{ // assume it's a number
				int num;
				_input >> num;
				_numStack.push(num);
			} 
			else if (nextElement->ElementType == ExprElemType::BinOp)
			{
				while (!_elementStack.empty() &&
						_elementStack.top()->ElementType == ExprElemType::BinOp && 
						nextElement->Precedence <= _elementStack.top()->Precedence )
					Eval();
				
				_elementStack.push(nextElement);
			}
			else if (nextElement->ElementType == ExprElemType::ClosePar)
			{
				while (!_elementStack.empty() &&
						_elementStack.top()->ElementType != ExprElemType::OpenPar)
					Eval();

				if (_elementStack.empty()) throw "parentesis mismatch";
				_elementStack.pop();
			}
			else if (nextElement->ElementType == ExprElemType::OpenPar)
			{
				_elementStack.push(nextElement);
			}
		}

		// evaluate remainings
		while (!_elementStack.empty()) Eval(); 
		return _numStack.top(); 
	}

private:
	// evaluate expression on the stack (operation on elementstack, numers on numberstack) 
	void Eval()
	{
		if (_elementStack.empty()) throw "operationstack empty";
		if (_numStack.size() < 2) throw "more operators than operands";
		const ExprElem *op = _elementStack.top(); _elementStack.pop();
		if (op->ElementType != ExprElemType::BinOp) throw "support only binary operation at the moment";
		int b = _numStack.top(); _numStack.pop(); 
		int a = _numStack.top(); _numStack.pop();
		_numStack.push(op->BinOperation(a, b));
	}

	// lookup the expression element table and return a pointer to the element or nullptr
	inline const ExprElem* GetExpressionElemenet()
	{
		char op = _input.peek();
		for (auto& elem : ElementTable)
		{ 
			if (elem.Identifier == op) 
			{ 
				_input.get();
				return &elem;
			}  
		}
		return nullptr;
	}
};

// operator table
const ExpressionEval::ExprElem ExpressionEval::ElementTable[6] =
{
	{ '+', ExpressionEval::ExprElemType::BinOp, 1, true, true, [](int a,int b) { return a + b; } },
	{ '-', ExpressionEval::ExprElemType::BinOp, 1, true, false, [](int a,int b) { return a - b; } },
	{ '*', ExpressionEval::ExprElemType::BinOp, 2, true, true, [](int a,int b) { return a * b; } },
	{ '/', ExpressionEval::ExprElemType::BinOp, 2, true, false, [](int a,int b) { return a / b; } },
	{ '(', ExpressionEval::ExprElemType::OpenPar, 0, false, false, nullptr },
	{ ')', ExpressionEval::ExprElemType::ClosePar, 0, false, false, nullptr },
};


int main()
{
	string test = "3\n"
		"19+12/4-((4-7)*3/1)\n"
		"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
		"((2+4)/3-2+1)\n";


	stringstream ss(test);
	int n;
	ss >> n;
	ss.get(); // get that newline
	for (int i = 0; i < n; i++)
		cout << ExpressionEval(ss).EvaluateExpression() << endl;
}

/*
 Solution approach
 Using a handmade LL(1) Parser without real lexical analysis, 
 so whitespaces must not occure in the input string and token
 recogniztion is primitive

 It's a bit an overkill since it doesn't make use of all the information 
 given by the interviewer one can assume there is a "shortcut" 

 however, I find it rather exotic to try to find a special solution for a 
 problem that fits so cleanly into a theory space well understood. 

 Interesting situation in an interview :-)
 
 --
 EBNF
 PROGRAM	= INT, NEWLINE, {EXPRLINE}
 EXPRLINE	= EXPR, NEWLINE
 EXPR		= EXPR OP1 TERM | TERM
 TERM		= TERM OP2 FACT | TERM
 FACT		= INT | '(' EXPR ')' 
 OP1		= '+' | '-' 
 OP2		= '*' | '/'
 INT		= ['-'] DIGITS
 DIGITS		= DIGIT {DIGIT}
 DIGIT		= '0' | '1' | '2' | '3' | ... | '9'
 NEWLINE	= '\n'

 EXPR  and TERM are not LL(1), so convert into LL1:
 EXPR		= TERM {OP1 TERM}
 TERM		= FACT {OP2 FACT}

 --
 NOTE: 
 - {x}: x repated n times, 0<=n
 - [y]: y occures 0 or 1 times
 */
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Parser
{
private:
	string _buffer;
	int _position;

public:
	Parser(string buffer) : _buffer(buffer), _position(0) {}

	vector<int> Parse()
	{
		vector<int> result;
		Program(result);
		return result;
	}

private:
	//Production: PROGRAM	= INT, NEWLINE, {EXPRLINE}
	void Program(vector<int>& res)
	{
		int count = 0;
		if (!Int(count)) throw "E1";
		if (count < 0) throw "E2";
		if (!NewLine()) throw "E3";
		for (int i = 0; i < count; i++)
		{
			int eres = 0;
			if (!ExprLine(eres)) throw "E4";
			res.emplace_back(eres);
		}
	}

	// Production: EXPRLINE	= EXPR, NEWLINE
	bool ExprLine(int& res)
	{
		if (!Expr(res)) return false;
		if (!NewLine()) throw "E5";
	}

	// Production: EXPR = EXPR OP1 TERM | TERM --> EXPR := TERM {OP1 TERM}
	bool Expr(int& res)
	{
		int t2 = 0;
		char op;
		if (!Term(res)) return false;
		while (Op1(op))
		{
			if (!Term(t2)) throw "E7";
			if (op == '-') res -= t2; // should check for overflow, e.g. using safeint... 
			else res += t2; // may overflow...
		}
		return true;
	}

	// Production: TERM = TERM OP2 FACT | TERM --> TERM = FACT {OP2 FACT}
	bool Term(int& res)
	{
		int f2;
		char op;
		
		if (!Fact(res)) return false;
		while (Op2(op))
		{
			if (!Term(f2)) throw "E9";
			if (op == '*') res *= f2; // may overflow...
			else res /= f2;
		}
		return true;
	}

	// Prodcution:  FACT = INT | '(' EXPR ')' 
	bool Fact(int &res)
	{
		if (Int(res)) return true;
		if (ReadIf('('))
		{
			if (!Expr(res)) throw "E10";
			if (!ReadIf(')')) throw "E11";
			return true;
		}
		return false;
	}

	// Production: OP1 = '+' | '-' 
	bool Op1(char& res)
	{
		res = Peek();
		return ReadIf('+') || ReadIf('-');
	}

	// Production: OP2 = '*' | '/' 
	bool Op2(char& res)
	{
		res = Peek();
		return ReadIf('*') || ReadIf('/');
	}

	// NEWLINE
	bool NewLine()
	{
		return ReadIf('\n');
	}

	// INT
	bool Int(int& res)
	{
		res = 0;
		int sign = 1;
		string digits;

		if (ReadIf('-'))
		{
			sign = -1;
			if (!Digits(digits))
			{
				UnRead(1);
				return false;
			}
		}
		else 
		{
			if (!Digits(digits)) return false;
		}
		
		for (int i = digits.size()-1, f=1; i >=0 ; i--, f*=10)
		{
			res += (digits[i] - '0') * f; // should check overflow with safeint or manually
		}

		res *= sign;
		return true;
	}

	// DIGITS
	bool Digits(string& digits)
	{
		char d;
		digits.clear();
		while (Digit(d))
		{
			digits.append(1, d);
		}
		return digits.size() > 0;
	}

	// DIGIT
	bool Digit(char& c)
	{
		return ReadIfInRange('0', '9', c);
	}

	// Gets the current character (0 at the first call, after Read 1, etc..)
	// returns '\0' if at end
	char Peek() 
	{
		if(_position < _buffer.size()) return _buffer[_position];
		return '\0';
	}

	// Reads the current character if it is =1 (advances the current position)
	bool ReadIf(char a)
	{
		char b;
		return ReadIfInRange(a, a, b);
	}

	// reads the current character if in range [a..b] 
	// e.g. a='0' b='2', reads it if Peek()=='0' or Peek()=='1' or Peek()=='2'
	bool ReadIfInRange(char a, char b, char& c)
	{
		c = Peek();
		if (c >= a && c <= b) 
		{
			Read();
			return true;
		}
		return false;
	}
	
	// Read the current character
	// advances current position unless at end of string
	// note, '\0' may not occure in the string as symbol other then EOF
	char Read()
	{
		char p = Peek();
		if(p != 0) _position++;
		return p;
	}

	// To go back 
	void UnRead(int n)
	{
		_position -= n;
	}
};

int main()
{
	string s1 = "1\n1+2+3*4\n";
	string s2 = "3\n"
		"19+12/4-((4-7)*3/1)\n"
		"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
		"((2+4)/3-2+1)\n";

	cout << "test string s1:" << endl << s1 << endl << endl;
	for (auto i : Parser(s1).Parse()) cout << i << endl;

	cout << endl << endl << "test string s2:" << endl << s2 << endl << endl;
	for (auto i : Parser(s2).Parse()) cout << i << endl;

}

Approach 1: use a hashtable, O(1) to insert and O(n) to check
Approach 2: any form of sorted container, AVL, B-Tree, ... for O(lg(n)) insert and with vucuong020195 method to test

From the big-o 1) looks better, I'm not sure if that's really the case in real world - how ever, depends very much on the tree implementation, could be quite bad if with lots of pointers etc...

/*
Idea: 
- dynamic programming, we are interested in the max free square at x,y = FLS(x,y)
  - if (x,y) is free: the new point can form a new free square of min(FLS(x+1,y),FLS(x,y+1),FLS(x+1,y+1)) 
	note: the last FLS(x+1, y+1) can be optimized but it would work like this
  - if (x,y) is not free: it will never participate in an other free square
    note: even if x,y is not free, x+1,y / x,y+1 can very well contain a max square, so we need to look there
  - base case(s), sigle square with size one at the right and bottom border of the matrix, if free: 1 if there is a tree: 0

matrix mxn: boolean two dimensional array, 0<=x<m, 0<=y<n

FLS stands for find largest free square
FLS(x,y) returns the edge size of the free square starting at (x,y) not the max edge size of any square within square (x,y)(m,n)

             / if M[x,y] = 1: 0, FLS(x+1, y), FLS(x, y+1)   | the recursion is needed to search further, the max size at x,y is 0
            /  if M[x,y] = 0 and 
FLS(x,y) = |       if x = m-1: 1
            \      if y = n-1: 1
             \ all other cases: min(FLS(x+1, y), FLS(x,y+1), FLS(x+1,y+1)) + 1
			     
				 while going through the FLS - recursion, remember largest square

time complexity O(n*m) / don't see any optimization
space complexity O(n*m) / can be optimized with a bottom up method to something like min(m,n) + 1
max stack depth O(n+m) / can be optimized if doing bottom up instead of memozation
*/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

using namespace std;

class FLS
{
private:
	int m; // matrix x dimension
	int n; // matrix y dimmension
	const vector<vector<bool>>& matrix; // matrix with free/occupied squares (free=false, occupied=true)
	vector<vector<int>> mt; // memotable that holds the already calculated squares
	int maxs = 0; // greates so far seen sidelength
	int maxs_x = 0; // x position where the greates sidelength was seen
	int maxs_y = 0; // y position where ... 

public:
	FLS(const vector<vector<bool>>& amatrix) : matrix(amatrix)
	{
		n = matrix.size();
		if (n == 0) throw invalid_argument("matrix y-dimension = 0");
		m = matrix[0].size();
		if (m == 0) throw invalid_argument("matrix x-dimension = 0");
		mt = vector<vector<int>>(n, vector<int>(m, -1)); // memotable
	}

	int Solve(int x, int y)
	{
		int i = 0;

		int res = mt[y][x]; // check memoization table
		if (res != -1) return res; // we hit a memoized entry, return it

		if (x == m - 1 || y == n - 1)
		{
			res = matrix[y][x] ? 0 : 1; // basecase
		}
		else if (!matrix[y][x])
		{
			int s1 = Solve(x + 1, y);
			int s2 = Solve(x, y + 1);
			res = min(s1, s2);
			if (res > 0) // optimze min(s1,s2,s3) by only looking at the single point the recursion didn't look
			{
				if (!matrix[y + res][x + res]) res++;
			}
			else 
			{
				res = 1;
			}
		}
		else 
		{
			Solve(x + 1, y);
			Solve(x, y + 1);
			res = 0;
		}

		if(res > maxs) 
		{
			maxs = res;
			maxs_x = x;
			maxs_y = y;
		}

		mt[y][x] = res; // memoize
		return res;
	}

	int get_M() const { return m; }
	int get_N() const { return n; }
	int get_X() const { return maxs_x; }
	int get_Y() const { return maxs_y; }
	int get_S() const { return maxs; }
};

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

	FLS fls(matrix);
	fls.Solve(0, 0);

	cout << "matrix of dimension " << fls.get_M() << "x" << fls.get_N() << endl
		<< " -found largest square with side length: " << fls.get_S() << " at position " << fls.get_X() << ", " << fls.get_Y() << endl;
}

1) it is finding the k-thary element and return it and all that are smaller
2) A modified quick-sort partition method will do it in O(n)
3) I did it in place of the original array/vector for simplicity

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
	int x; int y;
	Point(int ax, int ay) : x(ax), y(ay) {}
	int get_DistSq() { return x*x + y*y; }	
};
ostream& operator << (ostream& os, Point& p) { return os << "{" << p.x << "," << p.y << "("  << p.get_DistSq() << ")" << "}"; }

// quick-sorts partition function, returns k
// partitions array [s..e] into [s..k][k+1..e] where every element in [s..k] < than every element in [k+1..e]
int Partition(int s, int e, vector<Point>& pts)
{
	int p = (s + e) / 2; // pick pivot element, improvement: randomize or at least check overflow
	swap(pts[p], pts[e]); // swap pivot with end element

	int i = s-1; // all in [s..i] <= p < all in [i+1..j] 
	int pv = pts[e].get_DistSq();
	for (int j = s; j < e; ++j)
	{
		if (pts[j].get_DistSq() <= pv)
		{ 
			i++;
			swap(pts[i], pts[j]);
		} 
	}

	swap(pts[i+1], pts[e]);
	return i+1;
}

// changes the vector to contain the k-smallest elements at position 0..k
// smallest in this contect is the distance of the points to {0,0}
void Find(vector<Point>& pts, int k)
{
	int s = 0; 
	int e = pts.size()-1;
	int m = 0;
	do
	{
		m = Partition(s, e, pts);
		if (m < k) s = m + 1; // on the left of m are not enough elements
		if (m > k) e = m - 1; // on the left of m are too many elements
	} while (m != k);
}

int main()
{		
	int k = 2;
	auto pts = vector<Point>{ Point(1,2), Point(2,2), Point(5,3), Point(4,2), Point(3,2), Point(2,0), Point(1,1), Point(2,1), Point(9,9) };

	cout << "all points:" << endl;
	for (int i = 0; i < pts.size(); i++) cout << pts[i] << " ";

	Find(pts, k);

	cout << endl << endl << k << " smallest point(s):" << endl;
	for (int i = 0; i < k; i++) cout << pts[i] << " ";

	getchar();
}

1) use BFS (shortest path with no weights on edge)
2) implement no nodes and no edges, just keep the parent-pointer of the BFS traversal tree as coordinates in the chess-board

from collections import deque

N = 8
board_p = [[(-1,-1) for f in range(0,N)] for i in range(0,N)]

def Adjacents(u):    
    adj = []
    for e in [(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(1,-2),(-1,2),(1,2)]:        
        v = (u[0] + e[0], u[1] + e[1])
        if v[0] >= 0 and v[0] < N and v[1] >= 0 and v[1] < N: adj.append(v)
    return adj;

def Moves(s,t):
    q = deque()
    q.append(s)
    board_p[s[0]][s[1]] = s # "root" of BFS-traversal points to it self (avoid loop over "back-edge" to s)
    while q:
        u = q.popleft()
        if u == t: break
        for v in Adjacents(u):
            if board_p[v[0]][v[1]] == (-1,-1):
                board_p[v[0]][v[1]] = u
                q.append(v)

    # walk the path back (using parent "pointers")
    path = [(t)]    
    while t != s:
        t = board_p[t[0]][t[1]]
        path.append(t)

    path.reverse()
    return path

   
print(Moves((1,1),(5,5)))

/*
Write program that takes integer, deletes one of two consecutive digits and return greatest of all results.

Assumption:
1) consecutive means, the same digit is repeated
2) only delete one digit of such a pair

Solution:
- straight forward 
- runtime O(log(n)*log(n)) / where n is the value of the integer ...

Example:
994141 --> 99414
141465 --> 14165
*/
#include <iostream>
using namespace std;

int RemoveConsecutiveDigit(int v)
{
	int ov = v / 10;
	while (ov > 0)
	{
		int iv = v;
		int ivc = 1;
		while (iv != ov)
		{
			if (ov % 10 == iv % 10)
			{
				return (v / 10 / ivc * ivc) + (v % ivc); // looks wierd, just removes the digit
			}
			iv /= 10;
			ivc *= 10;
		}
		ov /= 10;
	}
	return v;
}



int main()
{
	cout << RemoveConsecutiveDigit(994141) << endl;
	cout << RemoveConsecutiveDigit(141465) << endl;

	getchar();

}

Assumptions:
- use a binary representation in contrast to decimal
- do it portable (32, 64 bit)
- number can grow to no limit, except memory ...
- output has hex is sufficient
- only deal with unsigned representation
- only integers, since they are passed as integer-array

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

class LargeNumber;
ostream& operator << (ostream& os, const LargeNumber& ln);

class LargeNumber
{
	friend ostream& operator << (ostream& os, const LargeNumber& ln);
public:
	using dtype = unsigned int;

private:
	vector<dtype> _data; // in "little endian": (data[0]^1, data[1]^(sizeof(dtype)*8), ...

public:
	LargeNumber(initializer_list<dtype>&& data) : _data(data) {}


	LargeNumber& operator ++()
	{
		size_t i = 0; 
		bool overflow = true;
		while (overflow && i < _data.size())
		{
			_data[i]++; 
			overflow = _data[i] == 0;
			i++;
		}
		if (overflow)
		{// grow
			_data.resize(_data.size() + 1);
			_data[i] = 1;
		}
		return *this;
	}
};

int main()
{
	constexpr auto uintm = std::numeric_limits<LargeNumber::dtype>::max();

	LargeNumber n1({ 0 });
	LargeNumber n2({ uintm });
	LargeNumber n3({ uintm - 3, uintm, });

	cout << "n1 " << n1 << endl;
	cout << "++n1 " << ++n1 << endl;
	cout << "++n1 " << ++n1 << endl;
	cout << "n2 " << n2 << endl;
	cout << "++n2 " << ++n2 << endl;
	cout << "++n2 " << ++n2 << endl;
	cout << "n3 " << n3 << endl;
	cout << "++n3 " << ++n3 << endl;
	cout << "++n3 " << ++n3 << endl;
	cout << "++n3 " << ++n3 << endl;
	cout << "++n3 " << ++n3 << endl;

	
	getchar();
}

ostream& operator << (ostream& os, const LargeNumber& ln)
{
	constexpr auto nc = sizeof(LargeNumber::dtype) * 2; // nible count per int
	bool lz = true; // leading zero
	size_t i = ln._data.size()*nc;
	while (i > 0)
	{
		--i;
		auto sr = (i%nc) * 4;
		auto v = (ln._data[i / nc] >> sr) & 0xf;
		if (v != 0 || !lz)
		{
			cout << hex << v;
			lz = false;
		}
	}
	return os;
}

/* output 
n1
++n1 1
++n1 2
n2 ffffffff
++n2 100000000
++n2 100000001
n3 fffffffffffffffc
++n3 fffffffffffffffd
++n3 fffffffffffffffe
++n3 ffffffffffffffff
++n3 10000000000000000
*/

How about a wall follower maze solver that always has a wall to it's right? Below is a simple implementation. O(x*y*N) due the lame collision detection. But it finds it's way through dead ends etc.

Strategy is as follows:
1: find a place to start by scanning the start column (y=0, a<=x<c): there must be a point that is not surveillanced otherwise it can't start
2: go downwards so there is the left wall to it's right (looking into the "robots" direction)
3: if there is nothing on the right, go into that space (doesn't happen on the left wall)
4: if there is something ahead, turn left until way is free
5: if you somehow end up at the start position, the "maze" is not solveable

PS: There is an infinite loop if it has only one "pixel" to move at the start, we should cover that special case

Improvements:
1: proper termination
2: improve that lame collision detection to something smart, any idea?
3: Think about optimizing it, e.g. when returning from a dead end, some

#include <iostream>

using namespace std;

const int sensor_r = 2;
const int sensor_rr = sensor_r * sensor_r;

struct Pt {
	int x;
	int y;
	Pt(int ay, int ax) { x = ax; y = ay; }
};

bool Collision(int a, int b, int c, int d, int y, int x, const Pt* ss, int nss)
{
	if (y < a) return true; // hit left wall, right wall we don't check, since it is "open"
	if (x < b) return true; // hit top wall
	if (x >= d) return true; // hit bottom wall	
	for (int i = 0; i < nss; ++i) // lame collision detection on sensor
	{
		int dx = ss[i].x - x;
		int dy = ss[i].y - y;
		if (dx*dx + dy*dy <= sensor_rr)
		{
			return true;
		}
	}
	return false;
}

void FindWay(int a, int b, int c, int d, const Pt* ss, int nss, char* track)
{
	if (c-a <= 0) return;
	if (d-b <= 0) return;

	int y = a;
	int x = b;
	
	for (x = b, y = a; x <= d && Collision(a, b, c, d, y, x, ss, nss); ++x);	
	if (x == d) { cout << "can't start: all starting points are checked by sensors" << endl; return; }
	
	int ox = x;
	int oy = y;
	int dx = 1; 
	int dy = 0;
	while (y < c)
	{
		track[x*(c - a + 1) + y] = 'O'; // +1: due to \n 

		if (!Collision(a,b,c,d, y - dx, x + dy, ss, nss)) // there must be something on the right to follow the "wall"
		{
			// if not, turn right ... and do a step in this direction
			int t = dx;
			dx = dy;
			dy = -t;
		}
		else if (Collision(a, b, c, d, y + dy, x + dx, ss, nss))
		{
			// collision ahead, turn left and do not move
			int t = dx;
			dx = -dy;
			dy = t;
			continue;
		}
		// turned right into an empty space or just continue into the direction 
		x += dx;
		y += dy;

		if (x == ox && y == oy) 
		{
			cout << "can't solve it, way is blocked" << endl;
			return;
		}
	}
}

char *CreateTrackBuf(int a, int b, int c, int d);

int main()
{
	int a = 0;
	int b = 0;
	int c = 15;
	int d = 10;
	
	char *track = CreateTrackBuf(a,b,c,d);
	Pt ss[] = { {6,7} , {12,7}, {12,3} /*, {12, 2} */ };
	FindWay(0, 0, 15, 10, ss, sizeof(ss) / sizeof(ss[0]), track);
	
	cout << track;
	getchar();

}


char *CreateTrackBuf(int a, int b, int c, int d)
{
	if (c - a <= 0) return nullptr;
	if (d - b <= 0) return nullptr;

	// create a char buffer to record and print the path he went
	int y2 = c - a + 1; // +1: due to '\n'
	int x2 = d - b;
	int os = y2 * x2;
	char *po = new char[os];
	for (int i = 0; i < os; ++i) po[i] = ' ';
	for (int i = 1; i <= x2; i++)
	{
		po[i*y2 - 1] = '\n';
	}
	po[os - 1] = '\0';
	return po;
}

/* output on above sample:
O          OOO
O         OO OO
O        OO   O
O        O
O    OOO OO
O   OO OO OO
O  OO   OOO
O  O     O
O  OO   OOO
OOOOOO OOOOO

with the 12,2 sensor (blocked path)

can't solve it, way is blocked
OOOOOOOOOOOO
O        OO
O        O
O        O
O    OOO OO
O   OO OO OO
O  OO   OOO
O  O     O
O  OO   OOO
OOOOOO OOOOO

*/

it's a DP problem:
c[i]=max(c[i-l]+l, c[i-l]) / if a match (length l) was found, for all matches ending at position i
c[i]=c[i-1] / if no matches end in i
c[i]=0 / if i =0 (supose the input string starts at 0)

result is: c[n] *100 / input string length

the code:

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

using namespace std;

int StartsWith(const string& input, int off, const string& match);

int PercentageMatch(const string& input, const list<string>& dict)
{
	if (input.size() == 0) return 100;
	
	vector<int> c(input.size()+1, 0);
	for (int i = 0; i < input.size(); ++i)
	{
		for (list<string>::const_iterator di = dict.begin(); di != dict.end(); ++di)
		{
			int l = StartsWith(input, i, *di);
			if (l > 0) c[i + l] = max(c[i + l], c[i] + l);
		}
		c[i + 1] = max(c[i + 1], c[i]);
	}
	return 100 * c[input.size()] / input.size();
}


int main()
{
	list<string> dict1({ "dog", "frog", "cat" }); // it said a list in the question
	cout << "case 1: " << PercentageMatch("catdog", dict1) << "%" << endl;
	cout << "case 2: " << PercentageMatch("cardog", dict1) << "%" << endl;

	list<string> dict2({ "a", "b", "c", "da", "daf", "fghjkl" });
	cout << "case 3: " << PercentageMatch("abc", dict2) << "%" << endl;
	cout << "case 4: " << PercentageMatch("adaf", dict2) << "%" << endl;
	cout << "case 5: " << PercentageMatch("dafghjkl", dict2) << "%" << endl; // here he must backtrack, the greedy version will not have 100% because it takes daf and misses the fghjkl
}


int StartsWith(const string& input, int off, const string& match)
{
	// depending on the count of items and the length of the input string it may pay off creating a trie and using it character by character
	// from the outher loop below
	if (input.size() - off < match.size()) return 0;
	for (int i = 0; i < match.size(); ++i)
	{
		if (input[off + i] != match[i]) return 0;
	}
	return match.size();
}