CareerCup

Here is my answer in python.

Running time: O(N Log N)

import sys

def find_closest_bigger_number(array, target, next_closest):
    if(len(array) == 1):
        return array[0] if (array[0] > target) and (next_closest - target) > (array[0] - target) else next_closest
    
    half = len(array)/2

    if array[half] > target:
        next_closest = array[half] if (next_closest - target) > (array[half] - target) else next_closest
        return find_closest_bigger_number(array[:half], target, next_closest)
    else:
        return find_closest_bigger_number(array[half+1:], target, next_closest)

def find_shortest_sentence(keywords, words):
    keywordHash ={}
    answer =[]
    shortest = sys.maxint
    keyword_occurrence_map = []

    for pos, keyword in enumerate(keywords):
        keywordHash[keyword] = pos
        keyword_occurrence_map.append([])

    #go through the words and count the occurrence, O(N)
    for p, word in enumerate(words):
        matched_key_word_pos = keywordHash.get(word, -1)
        if matched_key_word_pos == -1:
            continue
        keyword_occurrence_map[matched_key_word_pos].append(p)

    for first_pos in keyword_occurrence_map[0]:
        prev_pos = first_pos
        last_pos = sys.maxint
        for next_word_occurrence_map in keyword_occurrence_map[1:] :
            next_word_pos = find_closest_bigger_number(next_word_occurrence_map, prev_pos, sys.maxint)
            if (next_word_pos == sys.maxint):
                last_pos = sys.maxint
                break
            last_pos = next_word_pos

        if last_pos == sys.maxint:
            continue

        if (last_pos - first_pos < shortest):
            shortest = last_pos - first_pos
            answer= [first_pos, last_pos]
    return answer

Here is C++ solution to the first question running in O(n log n).

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool compare(int prev, int next)
{
	return prev >= next;
}

void swap(vector<int>& list, int prev, int next)
{
	int tmp = list[prev];
	list[prev] = list[next];
	list[next] = tmp;
}

void sort_to_waveform(vector<int>& input)
{
	sort(input.begin(), input.end(), compare);
	int pos = 1;
	while(pos < input.size()-1)
	{
		swap(input, pos, pos+1);	
		pos+=2;
	}
}

void print(vector<int>& list)
{
	for(int i =0; i <list.size(); i++)
		cout<<list[i]<<" -> ";
	cout<<endl;
}

int main ()
{
	vector<int> input;
	input.push_back(1);
	input.push_back(6);
	input.push_back(3);
	input.push_back(7);
	input.push_back(2);
	input.push_back(10);
	input.push_back(9);
	input.push_back(4);
	input.push_back(5);
	input.push_back(11);

	print(input);
	sort_to_waveform(input);
	print(input);
	return 1;
}

Here is C++ solution. I am not proud of this algorithm but could not come up with the working algorithm for the following input:

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

struct node {
	int value;
	int pos;
	int source;
	bool visited;
	node(int v, int p, int s):value(v), pos(p), source(s), visited(false){}
};

bool compare(node& a, node& b)
{
	return (a.value > b.value);
}

bool search_max(vector<node>& list, int pos_a, int pos_b, int length_a, int length_b, vector<int>& result, int k)
{
	if (result.size() == k)
		return true;

	int left_a = length_a - pos_a - 1;
	int left_b = length_b - pos_b - 1;

	if ((left_a+left_b) < (k - result.size()))
		return false;

	int new_a = pos_a;
	int new_b = pos_b;

	for (int i = 0; i< list.size(); i++)
	{
		if (list[i].visited)
			continue;

		if (list[i].source == 1 && list[i].pos > pos_a)
		{
			new_a = list[i].pos;
		} else if (list[i].source == 2 && list[i].pos > pos_b)
		{
			new_b = list[i].pos;
		} else {
			continue;
		}
		list[i].visited = true;
		result.push_back(list[i].value);
		if (search_max(list, new_a, new_b, length_a, length_b, result, k))
			return true;
		result.pop_back();
		list[i].visited= false;
		new_a = pos_a;
		new_b = pos_b;
	}
	return false;
}

void find_max_with_relative_order(vector<int>& array1, vector<int>& array2, int k)
{
	int pos_a = INT_MIN;
	int pos_b = INT_MIN;
	vector<node> merged;
	vector<int> result;
	for (int i = 0; i < array1.size(); i++)
		merged.push_back(node(array1[i], i, 1));

	for (int i = 0; i < array2.size(); i++)
		merged.push_back(node(array2[i], i, 2));

	sort(merged.begin(), merged.end(), compare);
	search_max(merged, pos_a, pos_b, array1.size(), array2.size(), result, k);

	if (result.size() == k)
	{
		for (int i =0; i <result.size(); i++)
			cout<<result[i];
		cout<<endl;
	}	else {
		cout<<"failed to find number"<<endl;
	}
}

int main() {

	vector<int> array1, array2;
	array1.push_back(3);
	array1.push_back(4);
	array1.push_back(6);
	array1.push_back(5);

	array2.push_back(9);
	array2.push_back(1);
	array2.push_back(2);
	array2.push_back(5);
	array2.push_back(8);
	array2.push_back(3);

	find_max_with_relative_order(array1, array2, 5);

	array1.clear();
	array2.clear();

	array1.push_back(3);
	array1.push_back(4);
	array1.push_back(5);
	array1.push_back(6);

	array2.push_back(2);
	array2.push_back(1);
	array2.push_back(5);
	array2.push_back(3);
	array2.push_back(8);
	array2.push_back(9);

	find_max_with_relative_order(array1, array2, 5);
	return 1;
}

This code does not work with the following input:

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

This code does not work with the following input:

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

I am not sure this algorithm would work for the following cases(Maybe I am wrong):
In this algorithm, the sum of number is dependent on which way a next number is merged with previous sum. (whether left or right).

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

I am not sure your selection criteria is correct. In the following code,

min(dp(n-1,f-Sn%f,k-1),dp(n-1,r,k-1))

I guess f is F in the question, but what does r stand for?
Can you explain what is your selection criteria to choose which one is smaller?

Here is the C++ solution running at K*N^(k-1)*log N, which I am not really proud of.

#include<math.h>
#include<set>
#include<vector>
#include<climits>
#include<iostream>

using namespace std;

int find_sum(int target, int prev, vector<int>& inputs, set<int>& selected, set<int>& hash, int left)
{
  if (left == 1)
  {
    set<int>::iterator found;
    if((found=hash.find(target-prev))!= hash.end())
    {
      if (selected.find(*found)== selected.end())
        return target;
      else INT_MIN;
    } else
      return INT_MIN;
  }

  for (int i = 0; i < inputs.size(); i++)
  {
    if (selected.find(inputs[i])== selected.end())
    {
      selected.insert(inputs[i]);
      prev += inputs[i];
      if (find_sum(target, prev, inputs, selected, hash, left-1)!= INT_MIN)
        return target;
      selected.erase(inputs[i]);
      prev -= inputs[i];
    }
  }
  return INT_MIN;
}


int pickMatch(vector<int> inputs, int k, int f)
{
  int result = INT_MIN;
  int target = f;
  int i = 1;
  set<int> hashmap;

  for (int i = 0; i < inputs.size(); i++)
    hashmap.insert(inputs[i]);

  for(int i = 1; i <= k; i++)
  {
    set<int> selected;
    result = find_sum(f*i, 0, inputs, selected ,hashmap, k);
    if (result != INT_MIN)
      return result;
  }
  return -1;
}

int main()
{
  vector<int> inputs;
  inputs.push_back(1);
  inputs.push_back(2);
  inputs.push_back(3);
  inputs.push_back(4);
  inputs.push_back(5);

  cout<< "found = " <<pickMatch(inputs, 3, 5) << endl;
  return 1;
}

Here is the C++ solution running in O( n log n).
Approach is to sort the numbers in alphanumerical order and concatenate them.
e.g.) 9 come earlier than 918 since second number '1' in 918 is smaller than first number '9' of '9'.
Likely, 112 comes earlier than 1 because '2' of 112 is larger than '1' of '1'.

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

using namespace std;

bool compare(string left, string right)
{
  int lpos=0, rpos=0;
  int len = (left.length()>right.length())? left.length(): right.length();
  for (int i = 0; i < len; i++)
  {
    lpos = (i< left.length())? i: left.length()-1;
    rpos = (i< right.length())?i: right.length()-1;
    if (left[lpos] != right[rpos])
      return left[lpos]> right[rpos];
  }
}


void concatenate_biggest(vector<string> inputs)
{
  string result;
  sort(inputs.begin(), inputs.end(), compare);
  for (int i = 0; i < inputs.size(); i++)
    result+= inputs[i];
 
  cout<<"resut = " <<result<<endl;
}

int main()
{
  vector<string> inputs;
  inputs.push_back("9");
  inputs.push_back("918");
  inputs.push_back("917");
  concatenate_biggest(inputs);

  inputs.clear();
  inputs.push_back("1");
  inputs.push_back("112");
  inputs.push_back("113");
  concatenate_biggest(inputs);
  return 1;
}

How would you find the end nodes given vertices and edges?

Here is C++ solution running in O(n log n).
I wonder whether I misunderstood the problem or this question was not from Google interview. (considering its difficulty) Please, correct me if I am wrong.

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

using namespace std;

bool compare(int prev, int next)
{
	return (prev< next);
}

void processResult(vector<int>& p1, vector<int>& p2, int states)
{
	sort(p1.begin(), p1.end(), compare);
	sort(p2.begin(), p2.end(), compare);

	for (int i = 0; i < states; i++)
	{
		if (p1[i] < 0 || p2[i] <0)
		{
			cout<<"Invalid"<<endl;
			return;
		} else if (p1[i] != p2[i]) {
			cout <<"inequal"<<endl;
			return;
		}
	}
	cout<<"equal"<<endl;
}

int main()
{
	int states = 7;
	vector<int> p1;
	vector<int> p2;

	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(-11);

	p2.push_back(5);
	p2.push_back(12);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();


	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(11);

	p2.push_back(5);
	p2.push_back(12);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);	

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();

	p1.push_back(12);
	p1.push_back(11);
	p1.push_back(5);
	p1.push_back(2);
	p1.push_back(7);
	p1.push_back(5);
	p1.push_back(11);

	p2.push_back(5);
	p2.push_back(0);
	p2.push_back(5);
	p2.push_back(7);
	p2.push_back(11);
	p2.push_back(2);
	p2.push_back(11);	

	processResult(p1, p2, states);

	p1.clear();
	p2.clear();

	return 1;
}

Here is C++ version of solution running in O(n logN).
using heap to keep the node with max value.

#include<cstdint>
#include <string>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

struct node {
	char value;
	int count;
	node(char v, int c):value(v), count(c){}
};

bool larger(char prev, char next)
{
	return prev < next;
}
string find_norepeat_str(vector<char>& input)
{
  string result;
  vector<node*> nodes;
  sort(input.begin(), input.end(), larger);
  char cur = INT8_MIN;
  int left = input.size();
  int count = 0;
  for(int i = 0; i < input.size(); i++)
  {
    if (cur == INT8_MIN)
    {
      cur = input[i];
      count++;
    } else if (cur == input[i])
    {
      count++;
    } else {
      nodes.push_back(new node(cur, count));
      cur = input[i];
      count = 1;
    }
  }
  nodes.push_back(new node(cur, count));
  Heap heap(nodes);
  node * longest = 0;
  while (left>0)
  {
    if (!longest || longest->count == 0)
    {
      longest = heap.extract();
    }

    while (longest && longest->count>0)
    {
      node * next = heap.extract();
      if (!next)
      {
        if (longest->count == 1)
        {
          result.push_back(longest->value);
          return result;
        }else
          return "invalid input";
      }
      if(result.length()==0 || (result.length() > 0 && result[result.length()-1] != longest->value))
      {
          result.push_back(longest->value);
          longest->count--;
          left--;
      }
      result.push_back(next->value);
      next->count--;
      left --;
      if (next->count)
        heap.add(next);

    }
  }
  return result;
}

Here is C++ version of solution.

Running in log n.

#include<iostream>
#include <cstdint>
using namespace std;

class Account {

public:	
	Account(uint16_t amount):left(amount){}

	uint16_t withdraw(uint16_t value)
	{
		if (left < value)
			return 0;
		else
		{
			left -= value;
			return value;
		}
	}

	uint16_t print()
	{
		cout<<"left = " <<left<<endl;
	}

private:
	uint16_t left;
};


void withdraw_all(uint16_t amount)
{
	uint16_t value = UINT16_MAX;
	Account a(amount);

	uint16_t total = 0;
	int count = 0;

	while (total != amount)
	{
		int returned = a.withdraw(value);
		if (!returned)
			value = value/2;
		else if (returned < value)
		{
			value = (returned > value/2)? returned: value/2;
		} 
		total += returned;
		count++;
	}
	cout <<"withdrew : "<< total<<" from "<<amount <<" in "<<count<< " attampts"<<endl;
}

Here is C++ solution running in O(n log n)

uint64_t find_expressible(vector<int>& prime_set, int pos)
{
  set<uint64_t> result;
  list<uint64_t>queue;
  queue.push_back(1);
  while(queue.size()> 0)
  {
    uint64_t cur  = queue.front();
    queue.pop_front();

    if (cur != 1 && result.find(cur) == result.end())
    {
      result.insert(cur);
      cout<<cur<<","<<endl;
    }
    for (int i = 0; i < prime_set.size(); i++)
    {
      int next = cur*prime_set[i];
      if (result.size() < pos*2)
      {
        queue.push_back(next);
      }
      else
        break;
    }
    if (result.size() >= pos*2)
      break;
  }
  //put numbers in the heap
  MinHeap heap(result);
  uint64_t found =0;
  //remove last big numbers as many as pos
  for (int i = 0; i < pos; i++)
      found = heap.extract();;
  return found;
}

Here is C++ version of the solution running in O (n log n) using merge sort.

#include <vector>
#include <iostream>

using namespace std;

struct node {
  int value;
  int count;
  int pos;
  node(int v, int p):value(v), count(0), pos(p){}
};

vector<node*> merge_sort(vector<node *>& input, int s, int e)
{
  vector<node*> temp;

  if (s == e)
  {
    temp.push_back(input[s]);
    return temp;
  }

  int half = s+ (e-s)/2;

  vector<node*> left = merge_sort(input, s, half);
  vector<node*> right = merge_sort(input, half+1, e);
  int lpos = 0, rpos = 0;
  while (lpos < left.size() && rpos<right.size())
  {
    if (left[lpos]->value < right[rpos]->value)
    {
      left[lpos]->count += (right[rpos]->count + 1);
      temp.push_back(left[lpos++]);
    } else {
      temp.push_back(right[rpos++]);
    }
  }

  if (lpos < left.size())
    temp.insert(temp.end(), left.begin()+lpos, left.end());
  else if (rpos < right.size())
    temp.insert(temp.end(), right.begin()+rpos, right.end());
  return temp;
}

void count_larger_numbers_in_rest(int* input, int len)
{
  vector<node*>list;
  for (int i = 0; i < len; i++)
  {
    list.push_back(new node(input[i], i));
  }

  vector<node*> result = merge_sort(list, 0, len-1);
  int* counts = new int[len];
  for (int i = 0; i < len; i++)
    counts[result[i]->pos]= result[i]->count;
  for (int i = 0; i < len; i++)
    cout<<counts[i]<<", ";
}

int main()
{
  int input[7] = {3,4,5,9,2,1,3};

  count_larger_numbers_in_rest(input, 7);
  return 1;
}

Here is C++ solution running in O(N)

#include <string>
#include <iostream>

using namespace std;

int MinInsertsForBalance (const string&s)
{
	int left = 0;
	int right = 0;
	int missing_left = 0;

	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(') 
		{
			left++;
		} else if ( s[i] == ')')
		{
			if (left > 0) left--;
			else {
				//can't be matched at all
				missing_left++;
			}
		}
	}
	return (left+missing_left);
}

int main ()
{
	string input = "(((((())))))))";
	cout << "(((((()))))))) => min = " << MinInsertsForBalance(input) <<endl;

	string input2 = "))(((";
	cout << "))((( => min = " << MinInsertsForBalance(input2) <<endl;
	
	return 1;
}

Here is the C++ version of solution. Using vector<int> to store the numbers.

#include <vector>
#include <iostream>
using namespace std;

class BigInt{

public:
	vector<int> numbers;
	bool sign;

	BigInt():sign(true)
	{
		sign = true;
	}

	BigInt(string value)
	{
		for (int i = 0 ; i < value.length(); i++ )
		{
			if (i == 0 && value[i] == '-')
				sign = false;
			else {
				numbers.push_back('0'+value[i]);
			}
		}
	}

	BigInt(const BigInt& b)
	{
		this->sign = b.sign;
		this->numbers = b.numbers;
	}

	BigInt& operator=(const BigInt& r)
	{
		sign = r.sign;
		numbers = r.numbers;
		return *this;
	}

	BigInt(vector<int> number, bool s)
	{
		numbers = number;
		sign = s;
	}

	BigInt operator+ (BigInt& r)
	{
		BigInt result;
		int lpos = (*this).numbers.size() -1;
		int rpos = r.numbers.size() -1;
		int carry = 0;

		if (this->sign && r.sign)
			result.sign = true;
		else if (!this->sign && !r.sign)
			result.sign = false;
		else if (!this->sign)
			return r - *this;
		else 
			return (*this) - r;

		while (rpos >= 0 || lpos >= 0)
		{
			int left = (lpos >= 0)? this->numbers[lpos] :  0;
			int right = (rpos >= 0)? r.numbers[rpos]  :  0; 		
			int sum = left + right + carry;
			carry = sum/10;
			result.numbers.insert(result.numbers.begin(), sum%10);
			lpos--;
			rpos--;
		}

		if (carry > 0)
			result.numbers.insert(result.numbers.begin(), carry);
		return result;
	}

	BigInt operator- (BigInt& r)
	{
		BigInt result;
		int carry = 0;

		if (!this->sign && !r.sign)
		{
			r.sign = true;
			return r - *this;
		}else if (!this->sign && r.sign)		
		{
			r.sign = false;
			return (*this)+r;
		}
		else if (this->sign && !r.sign)
		{
			r.sign = true;
			return (*this)+r;
		}		
		BigInt* left = this;
		BigInt* right = &r;

		int c = compare(*this, r);
		if (c == 0)
		{
			result.numbers.push_back(0);
			return result;
		} else if (c == -1)
		{
			left = &r;
			result.sign = false;
			right = this;
		}
		int lpos = left->numbers.size() -1;
		int rpos = right->numbers.size() -1;

		int diff = 0;
		while (rpos >= 0 || lpos >= 0)
		{
			int lvalue = (lpos >= 0)? left->numbers[lpos] :  0;
			int rvalue = (rpos >= 0)? right->numbers[rpos]  :  0; 		

			if (lvalue == 0 && lpos < 0)
			{
				diff = rvalue + carry;
				if (result.sign) result.sign = false;
				carry = 0;
			}else if (lvalue < (rvalue + carry))
			{
				diff = 10+lvalue - rvalue - carry;
				carry = 1;
			} else {
				diff = lvalue  - rvalue - carry;
			}
			result.numbers.insert(result.numbers.begin() ,diff);	
			lpos--;
			rpos--;
		}
		return result;

	}

	int compare(BigInt & l, BigInt & r)
	{
		if (l.numbers.size() == r.numbers.size())
		{
			for ( int i = 0; i < l.numbers.size(); i++)
			{
				if (l.numbers[i] != r.numbers[i])
					return (l.numbers[i] > r.numbers[i])? 1 : -1;			
			}		
		}
		else
			return (l.numbers.size() > r.numbers.size())? 1 : -1;

		return 0;
	}

	string to_string()
	{
		string result;
		if (!this->sign)
			result.push_back('-');

		for (int i = 0; i < this->numbers.size(); i++)
			result.push_back('0'+this->numbers[i]);
		return result;
	}
};


int main()
{
	vector<int> int1;
	int1.push_back(1);
	int1.push_back(9);
	int1.push_back(2);
	int1.push_back(8);
	BigInt bint1(int1, true);
	
	vector<int> int2;
	int2.push_back(2);
	int2.push_back(0);
	int2.push_back(0);
	int2.push_back(0);
	BigInt bint2(int2, true);
	
	BigInt bint3;
	bint3 = (bint1 + bint2);
	cout << "result = " << bint3.to_string().c_str()<<endl;

	BigInt bint4 = (bint2 - bint1);
	cout << "result 2 = " << bint4.to_string().c_str()<<endl;

	BigInt bint5 = (bint1 - bint2);
	cout << "result 2 = " << bint5.to_string().c_str()<<endl;

	vector<int> int6;
	int6.push_back(5);
	int6.push_back(2);
	BigInt bint6(int6, true);

	BigInt bint7 = bint6 - bint2;

	cout <<" "<<bint6.to_string().c_str()<<" - " << bint2.to_string().c_str()<<" = " << bint7.to_string().c_str()<<endl;

	BigInt answer  = BigInt("675") - BigInt("899");
	cout <<"675 - 899 =" <<answer.to_string().c_str() <<endl;

	BigInt answer2  = BigInt("675") - BigInt("-899");
	cout <<"675 - (-899) =" <<answer2.to_string().c_str() <<endl;
	return 1;
}

This is the C++ solution.

Running time is O(n log n) due to the sorting.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct range {
	int start;
	int end;
	range(int s, int e): start(s), end(e) {}
};

bool compare(range* prev, range* after)
{
	return prev->start <= after->start;
}

void merge_range (vector<range*>& input)
{
	std::sort(input.begin(), input.end(), compare);
	vector<range*>::iterator iter = input.begin();
	range* cur = 0;
	while (iter != input.end())
	{
		if (!cur)
		{
			cur = *iter;
			iter++;
		} else if (cur->end >= (*iter)->start)
		{
			cur->end = (cur->end > (*iter)->end)? cur->end : (*iter)->end;
			iter = input.erase(iter);
		} else {
			cur = *iter;
			iter++;
		}			
	}
}

int main()
{
	vector<range*> input;
	input.push_back(new range(2,6));
	input.push_back(new range(3,5));
	input.push_back(new range(7,21));
	input.push_back(new range(20,21));
	merge_range(input);
	for (int i= 0; i < input.size(); i++)
		cout<<"( "<<input[i]->start<<", "<<input[i]->end<<" )"<<endl;

	return 1;
}

I think the following case will be the problem

original string = "petepeter"
sub string = "peter"

I wish I can add the graphical diagram in the answer.

Anyway, I will do my best.
It is frustrating to put textual diagram here though. Sorry for the messy diagram.

|------------------|																	
  |	Client   A  | <-----------------     
  |------------------| 	    		 | query to connect live feeder
     	  |					 | 
	  |					 |					  |---------------|
	  |					 |					  |	Client B|
	  |					 |					  |---------------|
      	  | PUSH com                   |							|
	  |	(live feeds)    		V							|
	  |		      	  |--------------------------------|  				|	
	  |			  |	Live feed router 1..n |				|
	  |			  |--------------------------------|				|
	  |			  									|
	  |												|
	  |			  |--------------------------|					|  Status change
	  |-------------------|	Live feeder 1..n |  					|
				  |--------------------------|					|
					^								|
					| subscribe						|
					|								|
	|-----------------------------|								|											
    	| Message Bus      1..n|     							|	
    	|-----------------------------|								|
			|										V
			|   publish		     			   |----------------------------|																	
			------------------------------------------ | application layer      |     
						     			   |----------------------------|

The followings are description of the components depicted in the diagram.

- Client A, Client B : represents client browsers
- Live feed router : is responsible for telling client which live feeder it should connect to.
it also checks the load level of live feeders. There can be mutiple live feed routers.
- Live feeder: is responsible for keeping COMET style push notification connection with the clients. Certain number of connections will be assigned by routers and it subscribes the changes that currently connected clients are interested from the message bus. This is either stateful or stateless. In case of the later, the client should keep track of which live feed it has now. We can assign GUID for each live feed.

- Message bus: is the intermediate channel allowing the application layer to publish the status change and live feeder to subscribe for the change.
Tricky part will be how we can handle too many subscribers for the celebrities who has lots of followers.
I think this can handled in many ways. For the simplicity, I would assume we set up the multi-layer subscription for these users' status.

- Application layer is business logic handling the write/read from the clients. Additional job this application layer also does is to publish the user's status to the message bus upon the write/update requests.

Assumptions made in this design are as follows:
-We don't develop push notification framework (a.k.a Commet)
-We have highly salable storage(DB) available.

Given that assumption, Live feeder, message bus, and Live feed router can be linearly scalable.

Here is C++ version of solution with running time of O(N). Space complexity is also O(N).

prepare takes O(nlogn) due to the quicksort.

find () takes O(N).

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

using namespace std;

struct node {
	int value;
	int pos;
	bool include;
	node (int v, int p): value(v), pos(p), include(false){}
	node(int v): value(v), pos(-1), include(false){}
};

vector<node> org;
vector<node> sorted;

bool compare(node prev, node after)
{
	return prev.value < after.value;
}

void prepare(int * input, int len)
{
	for (int i = 0; i < len; i++)
	{
		org.push_back(node(input[i]));
		sorted.push_back(node(input[i], i));	
	}

	std::sort(sorted.begin(), sorted.end(), compare);

	for (int i = 0; i< len; i++)
	{
		org[sorted[i].pos].pos = i;
	}
}

int find (int s, int e, int pos)
{
	int result = INT_MIN;
	int order = 0;
	for (int i = s; i < e; i++)
	{
		sorted[org[i].pos].include = true;
	}

	for (int i = 0; i < sorted.size(); i++)
	{
		if (!sorted[i].include)
			continue;
		if (order == pos)		
			result = sorted[i].value;
		order++;
		sorted[i].include = false;
	}
	return result;	
}

int main()
{
	int input[6] = {3,4,5,0,1,2};

	prepare(input, 6);

	cout<<"find(2,5,2) = "<< find(2,5,2) <<endl;

	return 1;

}

Here is C++ version of solution with running time of O (N)

#include <list>
#include <iostream>

using namespace std;

void find_pairs(int * input, int len, int k)
{
	int s = 0;
	int e = 0;

	while(e < len)
	{
		int diff = input[e] - input[s];
		if (diff < k)
		{
			e++;
		} else if (diff > k)
		{
			s++;
			if (s == e) e++;
		}else 
		{
			cout <<"( "<<input[s]<<", "<<input[e]<<")"<<endl;
			s++;
			e++;
		}	
	}
}


int main()
{
	int input[10] = {1,2,3,5,6,8,9,11,12,13};		

	find_pairs(input, 10, 3);
	return 1;
}

Here is the C++ solution of the question.
BST should have left side of trees smaller than parent and right side of trees larger than the parent.
After inorder search, checking if the order is preserved can tell whether the tree is BST.

#include <iostream>
#include <vector>
using namespace std;

struct node {
  node* left;
  node* right;
  int value;
  node(int v):value(v), left(0), right(0){}
};

vector<int> results;

void inorder(node *n)
{
  if (!n)
    return;
  inorder(n->left);
  results.push_back(n->value);
  inorder(n->right);
}

bool check_order(vector<int>&result)
{
  int ascending = INT_MIN;

  for (int i = 1; i < result.size(); i++)
  {
    if (result[i-1]==result[i])
      continue;

    if (ascending == INT_MIN)
    {
      ascending = (result[i-1]< result[i]);
    }else if (ascending != (result[i-1]<result[i]))
    {
      return false;
    }
  }
  return true;
}

bool is_bst(node *r)
{
  inorder(r);
  return check_order(results);
}

Here is C++ version of algorithm running in O(N) with space complexity of O(N)

#include <map>
#include <vector>
using namespace std;

struct node {
	int data;
	node *next;
	node *random;
	node(int d):data(d), next(0), random(0){}
};

node * copy_list(node * r)
{
	map<node*, int> nmap;
	map<node*, int>::iterator found;
	vector<node*> copy;
	int pos = 0;
	node *cur = r;
	while (cur)
	{
		nmap[cur] = pos++;
		copy.push_back(new node(cur->data));
		cur = cur->next;
	}
	cur = r;
	for (int i = 0; i < copy.size(); i++)
	{
		if ((found = nmap.find(cur->random))!= nmap.end())
		{
			copy[i]->random = copy[found->second];
		}
		copy[i]->next = (i <copy.size()-1)? copy[i+1]: 0;
		cur= cur->next;
	}
	return copy[0];	
}

Here is the C++ solution running in O(K^3), where K i s the length of the keyword.

#include <set>
#include <string>
#include <iostream>
using namespace std;

#include <set>
#include <string>
#include <iostream>
using namespace std;

bool find_words(set<string>& hashtable, string& target)
{
	int next = INT_MIN;	
	set<string>::iterator iter;
	if (target.length() == 0)
		return true;

	bool *m = new bool[target.length()+1];
	m[0] = true;

	for (int i = 0; i < target.length(); i++)
	{	for (int j = i; j >=0; j--)
	{
		string sub = target.substr(j, i-j+1);
		if (hashtable.find(sub) != hashtable.end())
		{
			if (m[j]) m[i+1] = true;
		}
	}
	}
	return m[target.length()]== true;
}

bool FindInDic(string* words, int N, string input)
{
	set<string> hashtable;
	for (int i =0; i <N; i++)
		hashtable.insert(words[i]);

	return find_words(hashtable, input);
}

Here is faster and simpler solution running in O(N).

// O(N) solution
bool one_edit_apart(string src, string dst)
{
	int w1 = src.length();
	int w2 = dst.length();
	
	if (src.length() > dst.length())
		return one_edit_apart(dst, src);
	if (src.length()+1 < dst.length())
		return false;

	for (int i = 0; i < src.length(); i++)
	{
		if (src[i] != dst[i])
		{
			if (src.length() == dst.length())
				return (i <src.length()-1)? src[i+1] == dst[i+1] : true;
			else
				return src[i] == dst[i+1];
		}
	}
	return (src.length()+1 == dst.length());
}

Here is the C++ solution using dynamic programming.

Running time is O(NM) where N is the length of the first string and M is for the second string.

#include <math.h>
#include <string>
#include <iostream>

using namespace std;

bool one_edit_apart(string src, string dst)
{
	int w1 = src.length();
	int w2 = dst.length();
	int **w = new int*[w1+1];
	for (int p = 0; p <= w1; p++)
		w[p] = new int[w2+1];
	for (int x = 0; x <= w1; x++)
		w[x][0] = x;
	for (int y = 0; y <= w2; y++)
		w[0][y] = y;		

	for (int i = 1; i <= w1; i++)
	{
		for (int j = 1; j<= w2; j++)
		{
			int m = (src[i-1] != dst[j-1])+ w[i-1][j-1];
			if ( m > min(1+ w[i-1][j], 1+ w[i][j-1]))
				m = min(1+ w[i-1][j], 1+ w[i][j-1]);
			w[i][j] = m;
		}
	}
	cout<<"count = " << w[w1][w2]<<endl;
	return (w[w1][w2] ==1);
}


int main()
{
	cout << "xyz, xz: " << one_edit_apart("xyz", "xz") <<endl;
	cout << "xyz, xyk: " << one_edit_apart("xyz", "xyk")<<endl;
	cout << "xy, xyz: " << one_edit_apart("xy", "xyz")<<endl;


	cout << "xyz, xyz: " << one_edit_apart("xyz", "xyz") <<endl;
	cout << "xyz, xzy: " << one_edit_apart("xyz", "xzy")<<endl;
	cout << "x, xyz: " << one_edit_apart("x", "xyz")<<endl;
	return 1;
}

Here is C++ version of solution

#include <iostream>
using namespace std;
bool powerOf3(int input)
{
  if (input == 1)
    return true;
  else if (input == 0 || (input % 3)!=0)
    return false;
  return powerOf3(input/3);
}

Here is C++ version of solution using BFS.
Running time O(N), Space complexity O(N).

#include<iostream>
#include<list>
using namespace std;

struct node {
  int value;
  node *left;
  node *right;
  node(int v):value(v), left(0), right(0){}
};

list<int> addup(node* r)
{
  list<int> result;
  list<node*> queue;
  int cur_level= 0;
  int next_level = 0;
  int total = 0;

  if (!r)
    return result;

  queue.push_back(r);
  cur_level++;
  while(queue.size())
  {
    node *cur = queue.front();
    queue.pop_front();
    if (cur->left)
    {
      queue.push_back(cur->left);
      next_level++;
    }
    if (cur->right)
    {
      queue.push_back(cur->right);
      next_level++;
    }
    cur_level--;
    total += cur->value;
    if (cur_level==0)
    {
      result.push_back(total);
      cur_level = next_level;
      next_level = 0;
      total = 0;
    }
  }

Here is C++ solution

#include<iostream>
#include <string>
#include <math.h>

using namespace std;

bool isChar(char c)
{
  return (c>='a' && c<='z')||(c>='A' && c<='Z');
}

bool isSame(char s, char d)
{
  return (s == d)|| (abs(s-d)=='a'-'A');
}

bool isPalindrom(string input)
{
  int s = 0;
  int e = input.length()-1;

  while (s < e)
  {
    if (!isChar(input[s]))
      s++;
    else if (!isChar(input[e]))
      e--;
    else if(!isSame(input[s++], input[e--]))
      return false;
  }
  return true;
}

Here is the C++ solution.
Running time is O( N ) or O (N/2).

#include <iostream>
#include<math.h>

using namespace std;

bool is_double_square(int x)
{
	for (int i = 1; i < x/2; i++)
	{
		double squared = sqrt(i);
		int whole = (int)squared;
		if ( squared == whole)
		{
			int left = x - i;
			squared = sqrt(left);
			whole = (int)squared;
			if (squared == whole)
			{
				cout << "found = " << i << ", " << left<< endl;
				return true;
			}
		}
	}
	return false;
}

If we follow the same logic as "look-and-say" sequence.
"111221" is "three 1s" + two 2s than one 1", which is 5. But example said its count is 4.

I don't know how "111221" is the same as "312211", whose count is 5.

Here is C++ version of solution.

#include<string>
#include<iostream>

using namespace std;

string pattern(int input)
{
string result = "1";
char prev=' ';
char cur;
for (int i = 1; i<= input; i++)
{
string next;
int count = 0;
for (int j = 0; j < result.length(); j++)
{
cur = result[j];
if (j > 0 && prev != cur)
{
next.push_back('0'+count);
next.push_back(prev);
count =1;
} else {
count++;
}
prev = cur;

if (j == result.length()-1)
{
next.push_back('0'+count);
next.push_back(cur);
}
}
result = next;
}
return result;
}

int main ()
{
cout <<"pattern = " << pattern(4)<<endl;
cout <<"pattern = " << pattern(5)<<endl;
return 1;
}

Here is C++ version of solution.

This algorithm performs the following two steps.
Given the list of M words, whose longest one is N.
1) constructed directed graph of letters based on words O(MN)
2) performs BFS to find the topological ordering. Running time O(N), Space O(N)

#include <set>
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

struct vertex {
	char v;
	bool visited;
	set<vertex *> dst;
	vertex(char c): v(c), visited(false){}
};

void dfs (vertex * s, string& buffer)
{
	if (s->dst.size() == 0)
	{
		return;
	}
	set<vertex *>::iterator iter;
	for (iter = s->dst.begin(); iter != s->dst.end(); iter++)
	{
		if (!(*iter)->visited)
		{			
			(*iter)->visited = true;
			dfs((*iter), buffer);
		}
	}
	buffer.insert(0, 1, s->v);
}

void extract_orders(vector<string> input)
{
	map<char, vertex *> hashtable;
	map<char, vertex *>::iterator iter;
	string buffer;
	for (int i = 0; i < input.size(); i++)
	{
		char src = input[i][0];
		for (int j = 1; j <input[i].length(); j++)
		{
			vertex * v = 0;
			vertex * w = 0;
			char dst = input[i][j];
			map<char, vertex *>::iterator vfound;
			map<char, vertex *>::iterator wfound;

			if ((wfound = hashtable.find(dst)) == hashtable.end())
			{
				w = new vertex(dst);
				hashtable[w->v] = w;
			} else
			{
				w = wfound->second;
			}

			if ((vfound =hashtable.find(src))== hashtable.end())
			{
				v = new vertex(src);
				hashtable[v->v] = v;
			} else {
				v = vfound->second;
			}

			if (v->dst.find(w) == v->dst.end())
				v->dst.insert(w);			
			src = dst;
		}
	}
	
	dfs(hashtable[input[0][0]], buffer);
	cout<<"sequence = "<<buffer<<endl;
}

int main()
{
	vector<string>input;
	input.push_back("abcdefo");
	input.push_back("begz");
	input.push_back("hijk");
	input.push_back("abcedefgh");
	input.push_back("ikjom");

	extract_orders(input);
	return 1;
}

Here is the C++ solution. Running time is O(N)

#include <iostream>
using namespace std;
void swap(int * list, int s, int d)
{
	int tmp = list[s];
	list[s] = list[d];
	list[d] = tmp;
}

void partition(int *list, int len)
{
	int zero = len-1;
	int i = 0;
	while(i <zero)
	{
		if (list[zero] == 0)
		{
			zero--;
		} else if (list[i] != 0)
		{
			i++;
		}
		else if (i < zero)
		{	
			swap(list, i, zero--);
		}
	}
}

int main()
{
	int  input[8] = {1,0,6,0,3,0,0,1};
	partition(input, 8);
	for (int i = 0; i < 8; i++)
		cout<<input[i]<<",";
	cout<<endl;
}

Previous one takes O(N^2), which is a shame.
This one takes O(N)

bool can_get_last(int * arr, int len)
{
	int pos = 0;
	int hops = arr[pos];
	while (hops)
	{
		pos++;
		hops--;
		if (pos == len -1)
			return true;
		if (hops < arr[pos])
			hops = arr[pos];		
	}
	return false;
}

Here is the C++ version of solution using DFS;

#include <iostream>
using namespace std;

bool dfs(int* arr, int len, int pos)
{
	cout<< pos <<endl;
	if (pos >= len -1)
		return (pos == len -1);

	int hops = arr[pos];
	for (int i = 1; i <= hops; i++)
	{

		if (pos+i < len)
		{
			pos+= i;
			if (dfs(arr, len, pos))
				return true;
			pos-= i;
		}
	}
	return false;
}

bool can_get_last(int * arr, int len)
{
	return dfs(arr, len, 0);
}


int main()
{
	int input[6] = {1,2,0,1,0,1};
	cout <<"can hop to the last = " << can_get_last(input, 6);
	return 1;
}

Can this handle the input as blow:

n = 8
m = 2
input = {2,3,4,5,6,7}

Here is C++ version of solution using modified binary search.

Running time is roughly O( log N), except for the corner case where missing numbers are on both end of array. (e.g. {2,3,4,5,6,7}). In that case, Running time is O(N).

#include<list>
#include<iostream>

using namespace std;

void find_missing(int* input, int s, int e, int m, int n, list<int>& result)
{
	if (s>e || result.size() == m)
		return;

	int half = s + (e-s)/2;
	if (half == 0)
	{
		for (int i = 1; i < input[half]; i++)
			result.push_back(i);
		result;
	}

	if (half == n-m-1)
	{
		for (int i = n; i > input[half]; i--)
			result.push_back(i);
		return;
	}

	if (half > s && input[half]-input[half-1] > 1)
	{
		for (int i = input[half-1]+1; i< input[half]; i++)
			result.push_back(i);
	}
	if (half < e && input[half+1] - input[half] > 1)
	{
		for (int i = input[half]+1; i<input[half+1]; i++)
			result.push_back(i);
	}

	if (s< half &&  (input[half-1]- input[s] > (half-1)-s || input[half-1]-1 > half-1))
		find_missing(input, s, half-1, m,n, result);

	if (e> half && (input[e] -input[half+1] > e - (half+1) || n - input[half+1] > (n-m -1) - (half+1)))
		find_missing(input, half+1, e, m, n, result);	
}

This is C++ version of solution, which run in O(m* nlog n) where M is # of words and N is the longest word length().

I am not sure the question is related to anagram.

#include<iostream>
#include<string>
#include<map>
#include<list>
#include<algorithm>
using namespace std;

map<string, list<string>>find_anagram_group(string * input, int len)
{
	map<string, list<string>> result;
	for (int i= 0; i<len; i++)
	{
		string sorted = input[i]; 
		sort(sorted.begin(), sorted.end());
		if (result.find(sorted)!= result.end())
		{
			result[sorted].push_back(input[i]);			
		} else {
			list<string> l;
			l.push_back(input[i]);
			result[sorted] = l;
		}		
	}
	return result;
}

Here is the C++ version of solution.

Running time is between O(M log N) and O(MN), where M is # of rectangles and N is number of points.
O(MN) is the worst case. I should say just O (MN).
I uses the binary search to find the point with x position within the given rectangle.
If it find it but its y position is not in rectangle it need to search both side, which leads to O(N).

bool bsearch(point *list, int s, int e, rect& target)
{
	if (s > e)
		return false;
	int half = s+ (e-s)/2;
	if (list[half].x >= target.low.x && list[half].x <= target.high.x )
	{
		if (list[half].y >= target.low.y && list[half].y <= target.high.y)
		{
			return true;
		}
		if (bsearch(list, s, half -1, target))
			return true;
		if (bsearch(list, half+1, e, target))
			return true;
	}	
	if (list[half].x < target.low.x)
		return bsearch(list, half+1, e, target);
	else
		return bsearch(list, s, half-1, target);
}

list<rect> find_intersect_rect(rect* input, int len, point * points, int plen)
{
	list<rect> result;
	//sort by x value
	quick_sort(points, 0, plen-1);

	for (int i = 0; i < len; i++)
	{
		if (bsearch(points, 0, plen -1, input[i]))
			result.push_back(input[i]);
	}
	return result;	
}

Here is C++ version of solution.
Since there are only three types, there is no needs for sorting.
I just put them in three lists. For simplification, I just take string as input.
Running time is O(N).

#include <string>
#include <vector>

using namespace std;
vector <string> sort_patient(string * input, int len)
{
	vector<string> result;
	vector<string> high;
	vector<string> med;
	vector<string> low;
	for(int i = 0; i < len; i++)
	{
		if (input[i] == 'high')
			high.push_back(input[i]);
		else if (input[i] =='med')
			med.push_back(input[i]);
		else if (input[i] == 'low')
			low.push_back(input[i]);
	}
	int h=0, m=0, l=0;
	while (h < high.size() || m < med.size() || l <low.size())
	{
		if (h <high.size())
			result.push_back(high[h++]);
		else if ( m < med.size())
			result.push_back(med[m++]);
		else if (l < low.size())
			result.push_back(low[l++]);
	}
	return result;
}

int main ()
{
	string input[6] = {"high", "low", "low", "med", "high", "low"};
	vector<string> result= sort_patient(input, 6);
	return 1;
}

Here is the C++ solution using quick sort to sort.
Running time is O( N log N). I wish there is a faster way.

double eucidean(int x, int y)
{
	return sqrt(pow((double)(x -5), 2.0)+pow((double)(y - 5), 2.0));
}


vector<point> find_closest(int** input, int len, int limit)
{
	vector<point> result;
	vector<point> points;
	for (int i = 0; i <len; i++)
		points.push_back(point(input[i][0],  input[i][1], eucidean(input[i][0], input[i][1])));
	quick_sort(points, 0, len-1);

	for (int j = 0; j < limit; j++)
		result.push_back(points[j]);
	return result;
}

Here is C++ version of solution.
I assumes the question is to return the number of unique events given list of random events.

int count_unique_events(vector<event*>& events)
{
	quick_sort(events, 0, events.size()-1);
	event * cur = 0;
	vector<event*>::iterator iter = events.begin();
	while(iter != events.end())
	{
		if (!cur)
		{
			cur = (*iter);
			iter++;
			continue;
		}

		if (cur->end >= (*iter)->start)
		{
			iter = events.erase(iter);
		} else {
			cur = (*iter);
			iter++;
		}		
	}
	return events.size();
}

Here is the C++ version of solution using in-order search and BFS.
Running time is O(N).
Printing the indentation was little tricky.

#include<list>
#include<iostream>
using namespace std;

struct node {
	int value;
	int offset;
	node * left;
	node* right;
	node(int v):value(v), left(0), right(0), offset(-1){}
};

int offset = 0;

void inorder(node *t)
{
	if (!t)
		return;
	inorder(t->left);
	t->offset = offset++;
	inorder(t->right);
}

void printTree(node *t)
{
	int cur_children = 0;
	int next_children = 0;
	int last_off = INT_MIN;
	inorder(t);

	list<node *> queue;
	queue.push_back(t);
	cur_children++;
	while(queue.size())
	{
		node * cur = queue.front();
		queue.pop_front();
		if (cur->left)
		{
			queue.push_back(cur->left);
			next_children++;
		}
		if (cur->right)
		{
			queue.push_back(cur->right);
			next_children++;
		}
		int gap = (last_off == INT_MIN)? (cur->offset) : (cur->offset - last_off -1);
		for(int i = 0; i < gap; i++)
			cout<<" ";
		cout<< cur->value;
		last_off = cur->offset;
		cur_children--;
		if (cur_children == 0)
		{
			last_off = INT_MIN;
			cout<<endl;
			cur_children = next_children;
			next_children = 0;
		}	
	}
}

C++ solution with binary search.
Running time is O(M log N), where N is the max occurrence of numbers and M is number of unique numbers.

#include<iostream>
#include<map>
using namespace std;

void count(int *input, int s, int e, map<int,int> &cnt)
{
	if (s>e)
		return;

	if (input[s] == input[e])
	{
		if (cnt.find(input[s]) != cnt.end())
			cnt[input[s]] = cnt[input[s]]+ (e-s+1);
		else
			cnt[input[s]] = (e-s+1);
	}else
	{
		int half = s+ (e-s)/2;
		if (cnt.find(input[half]) != cnt.end())
			cnt[input[half]] +=1;
		else
			cnt[input[half]] = 1;

		count(input, s, half-1, cnt);
		count(input, half+1, e, cnt);
	}
}

void count_occurrence(int *input, int len)
{
	map<int, int> cnt;
	map<int, int>::iterator iter;
	count(input, 0, len-1, cnt);
	for (iter = cnt.begin(); iter != cnt.end(); iter++)
		cout<<iter->first << ": "<<iter->second<<endl;
}

int main()
{
	int input[10] = {8,8,8,9,9,11,15,16,16,16};
	count_occurrence(input, 10);
	return 1;
}

C++ version of solution using BFS.

#include <list>
#include <iostream>
using namespace std;

struct node {
	node* left;
	node* right;
	int value;
	node(int v):value(v),left(0), right(0){}
};

void print_tree(node * root)
{
	list<node *>queue;
	int cur_children = 0;
	int next_children = 0;

	if (!root)
		return;

	queue.push_back(root);
	cur_children++;
	while(queue.size())
	{
		node* cur = queue.front();
		queue.pop_front();
		if (cur->left)
		{
			queue.push_back(cur->left);
			next_children++;
		}
		if (cur->right)
		{
			queue.push_back(cur->right);
			next_children++;
		}
		cout<<cur->value<<" ";
		if (--cur_children == 0)
		{
			cout<<endl;
			cur_children = next_children;
			next_children = 0;		
		}
	}
}

C++ solution with BFS.

#include <list>
#include <iostream>
using namespace std;

struct node {
	node* left;
	node* right;
	int value;
	node(int v):value(v),left(0), right(0){}
};

void print_tree(node * root)
{
	list<node *>queue;
	int cur_children = 0;
	int next_children = 0;

	if (!root)
		return;

	queue.push_back(root);
	cur_children++;
	while(queue.size())
	{
		node* cur = queue.front();
		queue.pop_front();
		if (cur->left)
		{
			queue.push_back(cur->left);
			next_children++;
		}
		if (cur->right)
		{
			queue.push_back(cur->right);
			next_children++;
		}
		cout<<cur->value<<" ";
		if (--cur_children == 0)
		{
			cout<<endl;
			cur_children = next_children;
			next_children = 0;		
		}
	}
}

Here is O(N^2) alogrithm. (assuming the hashtable gives O(1) lookup time).
In the current implementation, it would be O(N^2*logN).

#include <unordered_map>
#include <iostream>

using namespace std;

bool dfs(int* input, int left, int len, int depth, unordered_map<int, int>& map)
{
	if (depth == 2)
		return (map.find(-1*left) != map.end());		
	for (int i = 0; i < len; i++)
	{
		left += input[i];
		if (dfs(input, left, len, depth+1, map))
			return true;
		left -= input[i];
	}
	return false;
}

bool find_zero_sum(int * input, int len)
{
	unordered_map<int, int> hashtable;
	for ( int i = 0; i <len; i++){
		if (hashtable.find(input[i]) == hashtable.end())
			hashtable[input[i]] = input[i];
	}

	int left = 0;
	bool found = false;
	for (int i = 0; i <len; i++)
	{
		left += input[i];
		if ((found = dfs(input, left, len, 1, hashtable)))
			return found;
		left -= input[i];	
	}
	return found;
}

Here is C++ version of solution using in-order search.

Running time is O(N).
Space complexity is O(1).

#include<iostream>
using namespace std;

struct Node {
	Node *left;
	Node *right;
	int value;
	Node(int v): value(v), left(0), right(0){}
};

class FlattenTree {
	
private:
	Node * start;
	Node * last;


	void inorder(Node * node)
	{
		if (!node)
			return;
		inorder(node->left);
		if (!start) {
			start = last = node;		
		} else {
			last->right = node;
			last = node;
		}
		inorder(node->right);
	}

public:
	
	FlattenTree():start(0), last(0){}

	Node * flatten_tree(Node * root)
	{
		inorder(root);

		//connect left to prev;
		Node * cur = start;
		Node * prev = 0;
		while(cur)
		{
			cur->left = prev;
			prev = cur;
			cur = cur->right;	
		}
		return start;
	}

};