CareerCup

Here is C++ solution.
Assumption is that max drop is the difference between two elements, m and n, where m < n.
There for the drop is expressed as negative number.

Running time is O(N).

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

//O(N) algorithm
int find_max_drop(int * input, int len)
{
	int min = INT_MAX;
	int max_pos = 0;

	for (int i = 1; i <len; i++)
	{
		int drop = input[i] - input[max_pos];
		if (drop < min)
			min = drop;
		if (input[max_pos] < input[i])
			max_pos = i;	
	}
	return min;	
}

int main()
{
	int input[6] = {5,3,4,1,6,7};
	int min = find_max_drop(input, 6);
	cout <<" max drop = " << min <<endl;
	return 1;
}

Here is my brute force approach in C++;
Running time is O(N+M) where N is length of target word, and M is length of pattern.

/*	
	Implement the IsMatch producing the following results given the string and the pattern
	IsMatched('aa', 'a') = false
	IsMatched('aa', 'aa') = true
	IsMatched('aaa', 'aa') = false
	IsMatched('aa', 'a*') = true;
	IsMatched('aa', '*') =  true;
	IsMatched('ab', '*') =  true
	IsMatched('b*a', 'a') = true;
	IsMatched('aab', 'c*a*b') = true;

	took longer than 20 minutes and had to fix the bug while walking through the test cases.
	I wish I could come up with the initial algorithm quicker but understanding the question took a while.
	Also made silly mistakes like typos. Shame on you !!!.
	Still could not get the thing right after rewrite. Need to keep an eye on this problem.
*/

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

using namespace std;

struct token {
	char letter;
	int minLen;
	bool hasStar;
	token(char c, int l, bool s):letter(c), minLen(l), hasStar(s){}
};

vector<token> parse(string s)
{
	vector<token> result;
	bool bStar;
	char l;
	int i = 0;
	while (i < s.length())
	{
		l = 0;
		bStar = false;
		char cur = s[i];
		while (i< s.length())
		{
			if (s[i] == '*')
			{
				if (l == 0){
					cout<<"invalid string" <<endl;
					result.clear();
					return result;
				}
				l--;
				bStar = true;
			} else if (cur != s[i])
			{
				result.push_back(token(cur, l, bStar));
				break;
			} else {
				l++;
			}
			
			if (i == s.length()-1) 
			{
				result.push_back(token(cur, l, bStar));
				i++;
				break;
			}
			i++;
		}
	}
	return result;
}


bool IsMatched(string target, string pattern)
{
	if (target =="*" || pattern == "*")
		return true;

	vector<token> ttoken = parse(target);
	vector<token> ptoken = parse(pattern);

	int i = 0, j = 0;
	while (i < ttoken.size() && j < ptoken.size())
	{
		if (ttoken[i].letter == ptoken[j].letter)
		{
			if (ttoken[i].minLen == ptoken[j].minLen || (ptoken[j].hasStar && ttoken[i].minLen > ptoken[j].minLen) || (ttoken[i].hasStar && ttoken[i].minLen < ptoken[i].minLen) )
			{
					i++;
					j++;
			}
			else 
				return false;
		} else {
			if (ttoken[i].hasStar && ptoken[j].hasStar)
			{
				if (ttoken[i].minLen == 0)
					i++;
				else if (ptoken[i].minLen == 0)
					j++;
				else 
					return false;
			} else if (ttoken[i].minLen == 0)
			{
				i++;				
			} else if (ptoken[i].minLen == 0)
			{
				j++;
			} else
				return false;
		}
	}

	if (j < ptoken.size())
	{
		while (j < ptoken.size())
		{
			if (ptoken[j].minLen == 0)
				j++;
			else 
				break;
		}
	}
	return (i == ttoken.size() && j == ptoken.size());
}

int main()
{
	cout<<"IsMatched('aa', 'a') = " << IsMatched("aa", "a") <<endl;
	cout<<"IsMatched('aa', 'aa') = " << IsMatched("aa", "aa") <<endl;
	cout<<"IsMatched('aaa', 'aa') = " << IsMatched("aaa", "aa") <<endl;
	cout<<"IsMatched('aa', 'a*') = " << IsMatched("aa", "a*") <<endl;
	cout<<"IsMatched('aa', '*') = " << IsMatched("aa", "*") <<endl;
	cout<<"IsMatched('ab', '*') = " << IsMatched("ab", "*") <<endl;
	cout<<"IsMatched('b*a', 'a') = " << IsMatched("b*a", "a") <<endl;
	cout<<"IsMatched('b*', 'a*') = " << IsMatched("b*", "a*") <<endl;
	cout<<"IsMatched('b*', 'a*a') = " << IsMatched("b*", "a*a") <<endl;
	cout<<"IsMatched('aab', 'c*a*b') = " << IsMatched("aab", "c*a*b") <<endl;
	return 1;
}

It is O(N^3) algorithm. I don't know how this is O(nlongn) algorithm.
There are three for loops, searching N, N-1, N-2 respectively. Asymptotically, it is O( N^3) algorithm.

Here is the C++ version of solution.

Running time is O(N^3).

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

void dfs(int* input, int* marked, vector<int>& nums, int prev, int len)
{
  if (nums.size() == 3)
  {
    cout << nums[0] << ", " << nums[1] <<", " << nums[2]<<endl;
    return;
  }

  for (int i = prev+1; i < len; i++)
  {
    if (marked[i] != 1)
    {
      if (nums.size() == 2 && (nums[0]+nums[1]) <= input[i])
          continue;
      marked[i] = 1;
      nums.push_back(input[i]);
      dfs(input, marked, nums, i, len);
      marked[i] = 0;
      nums.pop_back();
    }
  }
}

int compare(const void *a, const void *b)
{
  return (*(int*)a - *(int*)b);
}

void find_triangles(int* input, int len)
{
  vector<int>nums;
  qsort(input, len, sizeof(int), compare);
  int *marked = new int[len];
  for (int i = 0; i <len; i++)
  {
    nums.push_back(input[i]);
    marked[i] = 1;
    dfs(input, marked, nums, i, len);
    marked[i] = 0;
    nums.pop_back();
  }
}

Here is C++ version of solution

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

bool is_sign(char c)
{
  return (c=='+' || c =='-');
}

bool is_num(char c)
{
  return (c>='0' && c<='9');
}

bool IsNumber(string num)
{
  bool hasDot = false;
  bool hasNum = false;
  for(int i = 0; i < num.length(); i++)
  {
    if (num[i] == ' ')
      continue;
    if (i ==0)
    {
      if (!is_sign(num[i]) && !is_num(num[i]))
        return false;
      hasNum = is_num(num[i]);
    } else if (num[i] == '.')
    {
      if (hasDot)
        return false;
      if (!hasNum)
        return false;
      if (i == num.length()-1)
        return false;
      hasDot =true;
    } else {
        if(!is_num(num[i]))
          return false;
        if (!hasNum)
          hasNum = true;
    }
  }
  return (hasNum);
}

Here is C++ version of solution

#include <iostream>
using namespace std;

bool find_array(int *input, int s, int e,  int target)
{
  if (s> e)
    return false;

  int half = s+ (e-s)/2;
  if (input[half] == target)
    return true;

  if (input[half] <target)
  {
    if (input[e] >= target)
      s = half+1;
    else
      e = half-1;
  } else {
    if (input[s] <= target)
      e = half -1;
    else
      s = half +1;
  }
  return find_array(input, s, e, target);
}

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

  cout << "find 1 = " <<find_array(input, 0, 5, 1)<<endl;
  cout << "find 5 = " << find_array(input, 0, 5, 5)<<endl;
  cout<< " find 2 = " << find_array(input, 0, 5, 2)<<endl;
  cout<< " find 0 = " << find_array(input, 0,5, 0)<<endl;
  return 1;
}

Here is C++ version of solution.

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

bool isOp(string op)
{
	return (op == "+" || op == "-"|| op =="/" || op=="*");
}

double compute(double l, double r, string op)
{
	if (op == "+")
		return (l+r);
	else if (op == "-")
		return (l-r);
	else if (op == "/")
		return (l/r);
	else if (op == "*")
		return (l*r);
	return INT_MIN;
}

double compute_expr (string* inputs, int len)
{
	list<double> stack;
	for(int i = 0; i < len; i++)
	{
		string cur = inputs[i];
		if (isOp(cur))
		{
			if (stack.size() > 1)
			{
				double result;
				double right = stack.back();
				stack.pop_back();
				double left = stack.back();
				stack.pop_back();
				result = compute(left, right, cur);
				stack.push_back(result);
			} else {
				cout <<"error happen. There should be at least two numbers before operand"<<endl;
				return INT_MIN;
			}
		} else {
			double num = std::stod(cur);
			stack.push_back(num);		
		}
	}
	if (stack.size() > 0)
	{ 
		return stack.back();
	} else 
		return INT_MIN;
}

Here is C++ version of solution.
If I can use the hashtable with load factor close to 1. This algorithm will run in O(N) where N is the number of elements in the hashtable.
In this solution, I used map, which gives O(log N) search time.
Therefore, the running time is O( N log N).

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

class TwoSum {
public:
	void store(int input)
	{
		if (hashtable.find(input) == hashtable.end())
		{
			hashtable[input] = input;
		}
	}

	bool test(int val)
	{
		map<int, int>::iterator iter;
		for (iter = hashtable.begin(); iter != hashtable.end(); iter++)
		{
			int cur = iter->second;
			int left = val - cur;
			if (hashtable.find(left) != hashtable.end())
				return true;
		}
		return false;
	}
private:
	map<int, int> hashtable;
};

Here is C++ version of solution.
I used HashTable to store and search the node that had been created.
Running time is O(M), where M is number of relationships.
Assumption is that HashTable is real hash table.
Give the implementation I used std::map which gives O(logn) search time.

I would implement HashTable to get O(1) search time if time is allowed.
Space complexity is O(N), where N is number of nodes.

Node * buildTree(Relation * data, int len)
{
  Node * root = 0;
  map<int, Node*> nodemap;
  for (int i = 0; i < len; i++)
  {
    Node * p = 0;
    Node * c = 0;
    
    int pid = data[i].parent;
    int cid = data[i].child;

    if (pid != INT_MIN)
    {
      if (nodemap.find(pid) != nodemap.end())
      {
        p = nodemap[pid];
      } else {
        p = new Node(pid);
        nodemap[pid] = p;
      }
      
    }
    if (nodemap.find(cid) != nodemap.end())
    {
      c = nodemap[cid];
    } else { 
      c = new Node(cid);
      nodemap[cid] = c;
    }
    
    if (pid == INT_MIN)
    {
      root = c;
    }
  
    if (p) {
      if (data.isLeft)
        p->left = c;
      else
        p->right = c;
    }
  }
  return root;
}

Here is the C++ version of solution using quicksort.
Running time is O(n log n)

#include <vector>
#include <iostream>
using namespace std;
vector<int> getTriangleSides(int* inputs, int len)
{
	vector<int> result;
	quick_sort(inputs, 0, len-1);

	for (int i = 0; i<len; i++)
	{
		if (i+2 <len)
		{
			if ((inputs[i]+inputs[i+1]) > inputs[i+2])
			{
				result.push_back(inputs[i]);
				result.push_back(inputs[i+1]);
				result.push_back(inputs[i+2]);
				break;
			}
		}
	}
	return result;
}

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

#include<iostream>
using namespace std;

bool plant_flowers(int* input, int len, int target)
{
  int i = 0;
  int count = 0;
  while(i < len)
  {
    if (input[i] != 1)
    {
      if (i-1<0 ||input[i-1] != 1)
      {
        if (i+1>len||input[i+1] !=1)
        {
          input[i] = 1;
          count++;
          i+=2;
        } else {
          i += 3;
        }
      } else {
        i+=2;
      }
    } else {
      i+=2;
    }
  }
  return count >= target;
}

This is the C++ version of solution using BFS.

#include<list>
#include<iostream>
using namespace std;
struct Node {
	int value;
	Node * left;
	Node * right;
	Node(int v):value(v),left(0), right(0){}	
};

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

int main()
{
	Node * root = new Node(1);
	Node * n3 = new Node(3);
	Node * n5 = new Node(5);
	Node * n2 = new Node(2);
	Node * n4 = new Node(4);
	Node * n7 = new Node(7);
	Node * n9 = new Node(9);
	Node * n6 = new Node(6);
	Node * n8 = new Node(8);

	root->left = n3;
	root->right = n5;
	n3->left = n2;
	n3->right = n4;
	n5->left = n7;
	n2->left = n9;
	n2->right = n6;
	n4->left = n8;

	printTree(root);
	return 1;
}

Here is C++ solution.

I assume the rand() function guarantee the uniform distribution of the random numbers.

#include<time.h>
#include<iostream>
#include<chrono>
#include<random>
#include<thread>

using namespace std;

void swap(int *A, int s, int d)
{
	int tmp= A[s];
	A[s] = A[d];
	A[d] = tmp;
}

void shuffle(int* A, int len)
{
	for (int i = len-1; i >0; i--)
	{
		int next = rand()% (i+1);
		swap(A, next, i);
	}
}

int main()
{
	int A[10] = {1,2,3,4,5,6,7,8,9,10};
	srand(time(NULL));

	for (int j = 0; j < 20; j++)
	{
		shuffle(A, 10);
		for (int i = 0; i < 10; i++)
			cout<<A[i] << ", ";
		cout<<endl;
	}
	return 1;
}

Here is the C++ solution of problem.

Assumption of this algorithm is that neither of input intervals and out intervals are sorted.
If I can return the output without sorting. The following algorithm can run in O(N) time.
If output should be sorted, it would take O(N log N) due to the sorting steps.

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

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

list<itval> merge_intervals(itval* input, int len, itval target)
{
  list<itval> result;
  int start = target.start;
  int end = target.end;

  for (int i = 0; i <len; i++)
  {
    if (end >= input[i].start)
    {
      start = (start < input[i].start)? start: input[i].start;
      end = (end > input[i].end)? end: input[i].end;

    } else {
      result.push_back(input[i]);
    }
  }
  result.push_back(itval(start, end));
  return result;
}

Here is the C++ version of solution using DFS.
It is using permutation algorithm with fixed length.
I am not proud of this solution though. Will post better.

Time complexity is O(N^M) where N is # of numbers in the array and M is the fixed subset.

Any critics or suggestions are welcomed.

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

bool dfs(int left, list<int>&found, int max_depth, bool* marked, int *input, int len)
{
  if (found.size() == max_depth)
  {
    if (left == 0)
    {
      return true;
    }
    return false;
  }

  for (int i = 0; i < len; i++)
  {
    if (!marked[i] && input[i] <= left)
    {
      left -= input[i];
      marked[i] = true;
      found.push_back(input[i]);
      if (dfs(left, found, max_depth, marked, input, len))
      {
        return true;
      }
      left+= input[i];
      marked[i]= false;
      found.pop_back();
    }
  }
  return false;
}

list<int> find_sub_set(int * input, int max_size, int sum, int len)
{
  bool *marked = new bool[len];
  int left = sum;

  list<int> found;
  for (int i = 0; i < len; i++)
  {
    if (!marked[i] && input[i] <= left)
    {
      marked[i] = true;
      left -= input[i];
      found.push_back(input[i]);
      if (dfs(left, found, max_size, marked, input, len))
      {
        break;
      }
      marked[i] = false;
      left += input[i];
      found.pop_back();
    }
  }
  return found;
}

int main()
{
  int input[5] = {1,2,4,5,9};
  list<int> result = find_sub_set(input, 2, 9, 5);
  list<int>::iterator iter;
  for (iter = result.begin(); iter != result.end(); iter++)
    cout <<(*iter)<<", ";
  cout<<endl;
  return 1;
}

Here is the c++ version of solution.

I used the map to keep the dictionary and priority queue based on linked list to keep the top 3 frequent words.

Time complexity is as follows:
initialization: O(N Log N) due to the insert operation for map (it could be better O(N) if I use hash table)

search: O(N LogN) due to the search operation for std::map.

Any critics are welcomed.

#include<list>
#include<map>
#include<iostream>
#include<string>

using namespace std;

struct wordrank {
  string word;
  long rank;
  wordrank * next;
  wordrank(string s, int v):word(s), rank(v), next(0){}
};

class Dictionary{

public:

list<string> search(string key)
{
  list<string>result;
  wordrank * cur = 0;
  map<string, wordrank* >::iterator found;
  if ((found=dictionary.find(key))!= dictionary.end())
  {
    cur = found->second;
  }
  while (cur)
  {
    result.push_back(cur->word);
    cur = cur->next;
  }
  return result;
}

wordrank* add(wordrank *head, wordrank source)
{
  wordrank * new_word = new wordrank(source.word, source.rank);
  wordrank * cur = head;
  wordrank *prev = 0;
  int i = 0;
  while (cur)
  {
    if (new_word->word == cur->word)
      return head;

    if (new_word->rank > cur->rank)
	   {  
      if (prev) {
        prev->next = new_word;
      } else {
        head = new_word;
      }
      new_word->next = cur;
      break;
    }
    prev = cur;
    cur = cur->next;
  }
  if (!cur)
  {
    if (prev)  prev->next = new_word;
  }

  cur = head;
  while (cur)
  {
    if (i == 2)
    {
      cur->next = 0;
    }
    i++;
    cur = cur->next;
  }
  return head;
}

void generate_prefix(wordrank source, int len)
{
  string cur;

  for (int i = 0; i < source.word.length(); i++)
  {
    cur.push_back(source.word[i]);
    if (cur.length() == len)
    {
      if (dictionary.find(cur) != dictionary.end())
      {
        dictionary[cur] = add(dictionary[cur], source);
      }
      else {
        dictionary[cur] = new wordrank(source.word, source.rank);
      }
      cur.erase(0, 1);
 }
  }
}

void populate(wordrank source)
{
  string cur;
  for (int l = 1; l <=source.word.length(); l++)
  {
    generate_prefix(source, l);
  }

}

void initialize(wordrank * input, int len)
{
  for (int i = 0; i <len; i++)
  {
    populate(input[i]);
  }
}

private:
map<string,wordrank * > dictionary;

};

int main()
{
  wordrank input[10] = { wordrank("1231", 500), wordrank("1221", 60), wordrank("3312", 200), wordrank("5512", 1000),wordrank("6612", 102),wordrank("5121", 50),wordrank("9911", 100), wordrank("5533", 400), wordrank("987612", 800), wordrank("649320", 100)};

  Dictionary d;
  d.initialize(input, 10);
  bool exit = false;
  string in;
  while (!exit)
  {
    cout <<"enter search string (enter \"exit\" to end) : ";
    cin>> in;
    if (in == "exit")
    {
      exit = true;
      continue;
    }
    list<string> result = d.search(in);
    list<string>::iterator iter;
    for (iter = result.begin(); iter != result.end(); iter++)
      cout<< (*iter)<<endl;
    cout<<endl;
  }
  return 1;
}

Here is C++ version of solution.
DFS was used to search the relationship.

Running complexity is O(N) based on the assumption that there isn't anyone knows nobody.

#include <iostream>
using namespace std;

bool relation[5][5];


bool knows(int knower, int knowee)
{
	return relation[knower][knowee];
}

void dfs(int * visited, int pos, int len)
{
	for (int i = 0; i<len; i++)
	{
		if (pos != i && visited[i] !=1)
		{
			if (knows(pos, i))
			{
				visited[pos] = 1;
				dfs(visited, i, len);
			}
		}
	}
}
int find_celebrity(int len)
{
	int * visited = new int[len];

	for (int i = 0; i <len; i++)
	{
		visited[i] = 0;
	}

	for (int i = 0; i < len; i++)
	{ 
		if (visited[i] != 1)
			dfs(visited, i, len);
	}

	for (int i= 0; i<len; i++)
	{
		if (visited[i] ==0)
			return i;
	}
	return -1;
}



int main()
{
	relation[0][1]= true;
	relation[0][4] = true;
	relation[1][4] = true;
	relation[2][1] = true;
	relation[2][4] = true;
	relation[3][2]  = true;
	relation[3][4] = true;

	int pos = find_celebrity(5);
	cout << "celebrity is = " << pos <<endl;
}

Here is C++ version of solution.
This algorithm first search the location of the first character of the keyword within the board and start the DFS to find the keyword. DFS stops at the depth equal to the length of keyword.

#include<iostream>
using namespace std;

int x_move[8] = {-1,0,1,-1,1,-1,0,1};
int y_move[8] = {-1,-1,-1,0,0,1,1,1};


bool dfs(char** board, string keyword, string& cur, int len, int x, int y)
{
  bool found = false;
  if (cur.length() == keyword.length())
  {
    return (cur==keyword);
  }

  for (int i = 0; i < 8; i++)
  {
    int nx = x+ x_move[i];
    int ny = y+ y_move[i];
    if (nx>=0 && nx <len&& ny>=0 && ny<len&& cur.find(board[ny][nx])== string::npos)
    {
      cur.push_back(board[ny][nx]);
      found = dfs(board, keyword, cur, len, nx, ny);
      if (found)
        break;
      //back tracking
      cur.pop_back();
    }
  }
  return found;
}

bool find_word(char **board, string keyword, int len)
{
  bool found = false;
  for (int y = 0; y<len; y++)
  {
    for (int x = 0; x<len; x++)
    {
      if (board[y][x] == keyword[0])
      {
        string cur ="";
        cur.push_back(board[y][x]);
        if ((found = dfs(board, keyword, cur, len, x, y)))
            break;
      }
    }
 }
  return found;
}

Here is the solution in c++.
Running time will be O( log n)

int get_depth(node * n)
{
  int d = 0;
  node *cur = n;
  while(cur)
  {
    cur = cur->parent;
    d++;
  }
  return d;
}

node * find_cca(node * l, node * r)
{
  int ld = get_depth(l);
  int rd = get_depth(r);
  node * lparent = l;
  node * rparent = r;
  while (lparent && rparent)
  {
    if (lparent->value == rparent->value)
      return lparent;
 
    if (ld >= rd)
    {
      lparent = lparent->parent;
      ld--;
    } else {
      rparent = rparent->parent;
      rd--;
    }
  }
  return 0;
}

Here is the solution in C++.
Idea is to produce the map of partial strings in advance. It takes O(MN^2), where M is number of number strings and N is length of number strings.
Once it is done, searching is O(logn) when map is used.

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

class NumberSearch {

public:

  NumberSearch(string* input, int length)
  {
    for (int i = 0; i < length; i++)
    {
      add_partial(input[i]);
    }
  }

  void add(string newnum)
  {
    add_partial(newnum);
  }

  set<string> search(string num)
  {
    set<string> result;
    map<int, set<string> >::iterator found;
    if ((found = hash.find(atoi(num.c_str())))!= hash.end())
      return found->second;
    return result;
  }

private:
  map<int, set<string> > hash;
  void add_partial(string num)
  {
    for (int tlen = 1; tlen <= num.length(); tlen++)
    {
      string token ="";
      for (int i = 0; i < num.length(); i++)
      {
        if(num[i] == ' ')
          continue;

        token.push_back(num[i]);
        if (token.length() == tlen)
        {
          int key = atoi(token.c_str());
          if (hash.find(key)== hash.end())
          {
            set<string> l;
            hash[key] = l;
          }
          if (hash[key].find(num)== hash[key].end())
            hash[key].insert(num);
          token.erase(0, 1);
        }
      }
    }
  }
};

Here is the c++ solution of question.
I assumed I need to implement the method to find the successor for the given node in the tree.

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

Node * min(Node * n)
{
	Node * cur = n;
	while(cur->left)
	{
		cur = cur->left;	
	}
	return cur;
}

Node * successor(Node *n)
{
	if (n->right)
		return min(n->right);
	//find the parent.
	Node *cur = n;
	Node *p = n->parent;
	while(p && p->right->value == cur->value)
	{
		cur = p;
		p = cur->parent;
	}
	return p;
}

Node * find_successor(Node * root, int target)
{
	Node * cur = root;
	while(cur)
	{
		if (cur->value == target)
			return successor(cur);
		else if (cur->value > target)
			cur = cur->left;
		else 
			cur = cur->right;	
	}
	return 0;
}

Here is C++ version of Solution running in O(N), where N is the length of the sentence.

It first reverse the sentence and reverse the words.

#include<iostream>
#include<climits>
#include<string>
#include<cstdlib>

using namespace std;
void reverse(char* arr, int start, int end)
{
  int s = start, e = end;
  char temp;
  while(s < e)
  {
    temp = arr[s];
    arr[s] = arr[e];
    arr[e] = temp;
    s++;
    e--;
  }
}

void reverse_sentence(char *arr, int len)
{
  reverse(arr, 0, len-1);
  cout << arr <<endl;
  int s = INT_MIN, e;
  for(int i = 0; i < len; i++)
  {
    if (arr[i] == ' ')
    {
      if (s == INT_MIN)
      {
        cout <<"[ERROR] whitespace before the sentence"<<endl;
        return;
      }
      e = i -1;
      reverse(arr, s, e);
      s = INT_MIN;
    }else {

      if (s == INT_MIN)
        s = i;
      if (i == len-1 && s != INT_MIN)
      {
        reverse(arr, s, i);
      }
    }
  }
}

This algorithm use list to keep the longest consecutive chars.
Running time is O(N), where N is the length of the input string.

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

list<char> getlLongestConsecutiveChar(string input)
{
  list<char> found;
  char c = input[0];
  int count = 1;
  int max = INT_MIN;

  for (int i = 1; i < input.length(); i++)
  {
    if( input[i] == ' ')
      continue;
    if (c != input[i])
    {
      if (count > max)
      {
        if(found.size() >0)
          found.clear();
        found.push_back(c);
        max = count;
      } else if (count == max)
      {
        found.push_back(c);
      }
      count = 1;
      c = input[i];
    } else {
      count++;
    }
  }
  return found;
}

This is a better algorithm that is faster than the previous one.

string find_minstr(string input, set<char> seed)
{
  int min_len = INT_MAX;
  string minstr="";
  map<char, int> cmap;
  int start = 0, count = 0, len = seed.size();
  for (int i = 0 ; i < input.length(); i++)
  {
    int num_found = 0;
    char c = input[i];
    if (seed.find(c) != seed.end())
    {
      num_found = (cmap.find(c)!=cmap.end())? cmap[c]+1: 1;
      if (num_found == 1)
        count++;
      cmap[c] = num_found;
    }
    while (count == len)
    {
      char s = input[start];
      if (cmap.find(s) != cmap.end())
      {
        num_found = cmap[s];
        if (num_found == 1)
          count--;
        cmap[s] =  num_found-1;
      }

      if(i- start+1 < min_len)
      {
        minstr = input.substr(start, i-start+1);
        min_len = i - start +1;
      }
      start++;
    }
  }
  return minstr;
}

Here is C++ version of solution.
This algorithm provide running time of O(N^2) where N is the length of input string.

#include <string>
#include <iostream>
#include <climits>

using namespace std;

bool isfound(string dst, string set)
{
  int target = 0;
  int found = 0;
  int i=0, j=0;
  for (i = 0; i <set.length(); i++)
    target |= (1<<i);

  for (int i = 0; i < dst.length(); i++)
  {
    for (int j = 0; j < set.length(); j++)
    {
      if (dst[i] == set[j])
        found |= (1<<j);
    }
  }
  return (target == found);
}

string find_minstr(string input, string set)
{
  string minstr = "";
  int min = INT_MAX;
  int s = 0;
  for(s = 0; s < input.length(); s++)
  {
    string line = "";
    for (int i = s; i< input.length(); i++)
    {
      line.push_back(input[i]);
      if (isfound(line, set) == true && line.length() < min)
      {
        min = line.length();
        minstr = line;
        break;
      }
      if (line.length() > min)
        break;
    }
  }
  return minstr;
}

If no additional memory is allowed, the following algorithm can achieve the same running time of O(N).

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

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

node* head = 0;
node* tail = 0;

void inorder_tree2(node* r)
{
	if (!r)
		return;
	inorder_tree2(r->left);
	if (!head)
	{
		head = tail = r;
	} else {
		tail->right = r;
		tail = r;
	}
	inorder_tree2(r->right);
}

node * flat_tree(node *root)
{
	inorder_tree2(root);
	node * cur = head;
	node * prev = 0;
	while (cur != tail)
	{
		if (!prev)
		{
			cur->left = cur;
		} else {
			cur->left = prev;
		}
		prev = cur;
		cur = cur->right;
	}
	//do something with tail
	tail->left = prev;
	tail->right = tail;
	return head;
}

To flatten the tree, in-order search is used and queue was used to store node in order.
Running time of this algorithm is O(n).

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

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

void inorder_tree(node * r, list<node*>& queue)
{
	if (!r)
		return;
	inorder_tree(r->left, queue);
	queue.push_back(r);
	cout << r->value <<" ";
	inorder_tree(r->right, queue);
}

node * flatten_tree(node * root)
{
	list<node*> queue;
	inorder_tree(root, queue);
	node* prev=0, * cur = 0, *start = 0;
	list<node*>::iterator iter;
	for(iter= queue.begin(); iter != queue.end(); iter++)
	{
		cur = (*iter);
		if (prev == 0)
		{
			cur->left = cur;
			start = cur;
		}
		else {				
			cur->left = prev;
			prev->right = cur;
		}
		prev = cur;
	}
	prev->right = prev;
	return start;
}

I did not know the output does not have to be sorted. If that is the case, the following algorithm will give O(N) running time.

vector<Range> mergerange(vector<Range> &input, Range &newrange)
{
  int start = newrange.begin;
  int end = newrange.end;
  vector<Range> result;

  for (int i= 0; i <input.size(); i++)
  {
    if (start> input[i].end || end < input[i].begin)
    {
      result.push_back(input[i]);
    }
    else {
      start = (start< input[i].begin)? start: input[i].begin;
      end = (end > input[i].end)? end: input[i].end;
    }
  }
  result.push_back(Range(start, end));
  return result;
}

I assumed the inputs are the list of ranges and new range.

I used quicksort to sort the list of existing ranges and new range together by begin value.
After that scan the list and merge the overlapping ranges.
Running time is O(n log n), where n is the number of ranges in the list.

#include <list>
#include <string>
#include <climits>
#include <iostream>

using namespace std;

bool isNum(char c)
{
	return (c >='0' && c<='9');
}

bool isOp(char c)
{
	return (c =='+'|| c== '-'||c=='/'|| c=='*');
}

bool multiOrDiv(char c)
{
	return (c == '*' || c == '/');
}

int compute(int l, int r, char op)
{
	if (op =='+')
		return l+r;
	else if (op == '-')
		return l-r;
	else if (op == '*')
		return l*r;
	else if (op == '/')
		return l/r;
	return INT_MIN;
}

int eval_expr(string input)
{
	list<int> numbers;
	list<char> ops;
	string token;
	int result;

	for (int i = input.length()-1; i >= 0; i--)
	{
		int num;
		if (isNum(input[i]))
		{
			token.insert(0,1, input[i]);
			if (i == 0 && token.length())
			{
				num = atoi(token.c_str());
				numbers.push_back(num);			
			}		
		} else if (isOp(input[i]))
		{
			if (token.length())
			{
				num = atoi(token.c_str());
				numbers.push_back(num);
				token = "";
			}
			if (!multiOrDiv(input[i]))
			{
				char op = ops.back();
				while (multiOrDiv(op) && numbers.size() >1)
				{
					ops.pop_back();
					int l = numbers.back();
					numbers.pop_back();
					int r = numbers.back();
					numbers.pop_back();
					int result = compute(l, r, op);
					numbers.push_back(result);
					op = ops.back();
				}		
			}
			ops.push_back(input[i]);		
		}	
	}

	while (numbers.size() >1 && ops.size() >0)
	{
		char op = ops.back();
		ops.pop_back();
		int l = numbers.back();
		numbers.pop_back();
		int r = numbers.back();
		numbers.pop_back();
		result = compute(l, r, op);
		numbers.push_back(result);	
	}	
	return numbers.back();
}

This is C++ solution:

#include <list>
#include <string>
#include <climits>
#include <iostream>

using namespace std;

bool isNum(char c)
{
	return (c >='0' && c<='9');
}

bool isOp(char c)
{
	return (c =='+'|| c== '-'||c=='/'|| c=='*');
}

bool multiOrDiv(char c)
{
	return (c == '*' || c == '/');
}

int compute(int l, int r, char op)
{
	if (op =='+')
		return l+r;
	else if (op == '-')
		return l-r;
	else if (op == '*')
		return l*r;
	else if (op == '/')
		return l/r;
	return INT_MIN;
}

int eval_expr(string input)
{
	list<int> numbers;
	list<char> ops;
	string token;
	int result;

	for (int i = input.length()-1; i >= 0; i--)
	{
		int num;
		if (isNum(input[i]))
		{
			token.insert(0,1, input[i]);
			if (i == 0 && token.length())
			{
				num = atoi(token.c_str());
				numbers.push_back(num);			
			}		
		} else if (isOp(input[i]))
		{
			if (token.length())
			{
				num = atoi(token.c_str());
				numbers.push_back(num);
				token = "";
			}
			if (!multiOrDiv(input[i]))
			{
				char op = ops.back();
				while (multiOrDiv(op) && numbers.size() >1)
				{
					ops.pop_back();
					int l = numbers.back();
					numbers.pop_back();
					int r = numbers.back();
					numbers.pop_back();
					int result = compute(l, r, op);
					numbers.push_back(result);
					op = ops.back();
				}		
			}
			ops.push_back(input[i]);		
		}	
	}

	while (numbers.size() >1 && ops.size() >0)
	{
		char op = ops.back();
		ops.pop_back();
		int l = numbers.back();
		numbers.pop_back();
		int r = numbers.back();
		numbers.pop_back();
		result = compute(l, r, op);
		numbers.push_back(result);	
	}	
	return numbers.back();
}

First of all, thank you for the warm and fresh new question!!.

Here is C++ version of the solution.

This algorithm first construct the graph with each row as an edge and phone/email as a vertex.
I used DFS to find the connected graph.

Running time of this algorithm is O(N), where N is the number of distinct phone/email string.
Using the hashtable, constructing a graph takes O(N) although I did not implement hashtable in this solution. std::map will provide log(n) search time.
So, it will be O(N Log N ).

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

struct edge;
struct vertext;

struct vertex {
	string value;
	bool visited;
	vertex * parent;
	list<edge *> edges;
	map<string, edge*> merged;
	vertex(string v): value(v), parent(0), visited(false){}
};

struct edge{
	vertex *v;
	vertex *w;
	string* original;
	string value;
	edge(string v, string* o):value(v), original(o){}
};

void dfs(vertex *v, vertex *parent)
{
	list<edge *>::iterator iter;
	list<edge *>::iterator subiter;
	for (iter = v->edges.begin(); iter != v->edges.end(); iter++)
	{
		edge *e = (*iter);
		vertex* w = (e->v->value != v->value)? e->v : e->w;
		if (w->visited != true)
		{
			w->visited = true;
			w->parent = parent;
			for (subiter = w->edges.begin(); subiter != w->edges.end(); subiter++)
			{
				if (parent->merged.find((*subiter)->value) == parent->merged.end())
				{
					parent->merged[(*subiter)->value] = (*subiter);
				}
			}	
			dfs(w, parent);
		}	
	}
}


list<list<string>> merge_contact(string ** input, int len)
{
	list<list<string>>result;
	map<string, vertex *> vertices;
	map<string, vertex *>::iterator iter;

	//create the graph
	for (int i = 0; i <len; i++)
	{
		edge * e = new edge(input[i][0], input[i]);
		if ((iter = vertices.find(input[i][1])) != vertices.end())
		{
			e->v = iter->second;
			e->v->edges.push_back(e);
		} else {
			vertex * v = new vertex(input[i][1]);
			vertices[v->value] = v;
			v->edges.push_back(e);
			e->v = v;
		}

		if ((iter = vertices.find(input[i][2])) != vertices.end())
		{
			e->w = iter->second;
			e->w->edges.push_back(e);
		} else {
			vertex * w = new vertex(input[i][2]);
			vertices[w->value] = w;
			w->edges.push_back(e);
			e->w = w;
		}
	}

	for(iter = vertices.begin(); iter != vertices.end(); iter++)
	{
		if (iter->second->visited != true)
		{
			iter->second->visited = true;
			dfs(iter->second, iter->second);
		}
	}

	for (iter = vertices.begin(); iter!= vertices.end(); iter++)
	{
		vertex *v = iter->second;
		if (!v->parent)
		{
			list<string> m;
			map<string, edge*>::iterator i;
			for(i = v->merged.begin(); i != v->merged.end(); i++)
			{
				edge * e = i->second;
				m.push_back(e->original[0]);
				m.push_back(e->original[1]);
				m.push_back(e->original[2]);
			}	
			result.push_back(m);
		}
	}
	return result;
}

int main()
{
	string ** input = new string*[4];
	string s1[3] = {"John", "john@gmail.com", "john@fb.com"};
	string s2[3] = {"Dan", "dan@gmail.com", "+1234567"};
	string s3[3] = {"john123", "+5412312", "john123@skype.com"};
	string s4[3] = {"john1985", "+5412312", "john@fb.com"};
	input[0] = s1;
	input[1] = s2;
	input[2] = s3;
	input[3] = s4;
	list<list<string>>result = merge_contact(input, 4);

	list<list<string>>::iterator i;
	list<string>::iterator i2;
	for (i = result.begin(); i != result.end(); i++)
	{
		cout << "[ ";
		for (i2 = (*i).begin(); i2 != (*i).end(); i2++)
		{
			cout<<(*i2) <<", ";
		}
		cout<< " ], ";
	}

	cout<< endl;
	return 1;
}

To achieve the O(1) search time regardless of data strings, it is necessary to create the permutation of data strings with '*' in advance and store in hashtable, which gives O(1) search time.

The following is the C++ version of solution.

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

void permutate(string prev, string s, int pos, map<string, int> &m)
{
  if (m.find(prev)==m.end())
  {
    m[prev] = 1;
  }
  if (pos >= s.length())
    return;

  for (int i = pos; i < s.length(); i++)
  {
    prev.replace(i, 1, 1, '*');
    permutate(prev, s, pos+1, m);
    prev.replace(i, 1, 1, s[i]);
  }
}

void initialize(string* input, int len, map<string, int> &m)
{
  for (int i = 0; i < len; i++)
    permutate(input[i], input[i], 0, m);
}

Here is C++ version of solution. Space complexity is O(1).

#include<iostream>

using namespace std;

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

node * reverse(node * s)
{
  node *prev=0, *cur =s, *next = 0;
  while(cur)
  {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
  }

  return prev;
}

Here is C++ version of solution:

#include <string>
#include<iostream>

using namespace std;

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

bool IsSame(char s, char d)
{
  char lower_s = s -'a';
  char upper_s = s -'A';
  char lower_d = d - 'a';
  char upper_d = d - 'A';
  return ((s == d)||(lower_s == upper_d)||(upper_s == lower_d));
}


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

  while (s <e)
  {
    if (!Isdigitletter(input[s]))
    {
      s++;
      continue;
    }

    if (!Isdigitletter(input[e]))
    {
      e--;
      continue;
    }

    if (!IsSame(input[s], input[e]))
      return false;

    s++;
    e--;
  }
  return true;
}

Hi, Just wonder if this can handle [1,1,1,1,1,1,1] 20 case.
Correct me if I am wrong. This algorithm will go into infinite loop for this input since there is no boundary check for array.

Here is C++ version of solution with running time O(N), where N is the length of input array

#include <iostream>

using namespace std;

bool find_sum_seq(int* input, int target, int len)
{
  int sum = 0, start = 0;
  for (int i = 0; i <len; i++)
  {
    sum+= input[i];
    if (sum == target)
      break;
    else if (sum > target)
    {
      while(start < len && start <= i && sum > target)
      {
        sum -= input[start++];
      }
      if (sum == target)
        break;
    }
  }
  return sum == target;
}

Here is my solution using mean heap. Space complexity is O(m).

void print_matrix(int *matrix[], int h, int w)
{
  int x, y;
  heap minHeap(h, true);
  for (y = 0; y <h; y++)
    minHeap.add(node(0, y, matrix[y][0]));
  while(minHeap.size())
  {
    node min = minHeap.extract();
    cout << min.value << " ";
    if (min.x < w-1)
      minHeap.add(node(min.x+1, min.y, matrix[min.y][min.x+1]));
  }
}

Here is my solution in C++.
I used DFS to search the graph.

Running time will be O(N) for DFS.

#include<iostream>
using namespace std;

#define ATLANTIC 2
#define PACIFIC 1

int x_move[4] = {-1,0,1,0};
int y_move[4] = {-0,-1,0,1};



void dfs(int** map, int** marked, int w, int h, int x, int y, int dir)
{
  for (int m = 0; m < 4; m++)
  {
    int nx = x+x_move[m];
    int ny = y+y_move[m];
    if (nx > 0 && nx <w-1 && ny> 0 && ny <h-1&& ((marked[ny][nx] &dir) == 0) && map[y][x] <= map[ny][nx])
    {
      marked[ny][nx] |= dir;
      dfs(map, marked, w, h, nx, ny, dir);
    }
  }
}

void find_high_ground(int** map, int w, int h)
{
  int x, y;
  int** marked = new int*[h];
  for(y = 0; y < h; y++)
    marked[y] = new int[w];

  //initialize marked array
  for (x= 0; x < w; x++)
  {
    marked[0][x] = PACIFIC;
    marked[h-1][x] = ATLANTIC;
  }
  for (y = 0; y < h; y++)
  {
    if (y == 0)
    {
      marked[y][0] = PACIFIC;
    } else if (y == h-1)
    {
      marked[y][w-1] = ATLANTIC;
    } else {
      marked[y][0] = PACIFIC;
      marked[y][w-1] = ATLANTIC;
    }
  }
  //do dfs from pacific positions
  for (x = 0; x <w; x++)
    dfs(map, marked, w, h, x, 0, PACIFIC);
  for (y = 0; y <h-1; y++)
    dfs(map, marked, w, h, 0, y, PACIFIC);
  for (x = 0; x < w; x++)
    dfs(map, marked, w, h, x, h-1, ATLANTIC);
  for (y = 1; y < h; y++)
    dfs(map, marked, w, h, w-1, y, ATLANTIC);


  //print all cell with 3
  for (y = 0; y<h; y++)
  {
    for (x = 0; x <w; x++)
    { if (marked[y][x] == (PACIFIC|ATLANTIC))
        cout << "("<<map[y][x]<<") ";
      else
        cout << map[y][x] << " ";
    }
    cout<<endl;
  }
  cout<<endl;

  //print all cell with 3
  for (y = 0; y<h; y++)
    for (x = 0; x <w; x++)
      if (marked[y][x] == (PACIFIC|ATLANTIC))
        cout << "("<<x-1<<", "<<y-1<<") ";
  cout<<endl;
}

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

  int *input[7];
  for (int y = 0; y< 7; y++)
  {
    input[y] = new int[7];
  }
  for (int j =0; j <7; j++)
    for (int i = 0; i <7; i++)
      input[j][i] = array[j][i];

  find_high_ground(input, 7, 7);
  return 1;
}

This is C++ version of solution. I used DFS with backtracking.

#include<iostream>
#include<list>

using namespace std;

void permutate(int left, list<int> option, list<list<int> >&result)
{
  if (left == 0)
  {
    result.push_back(option);
    return;
  } else if ( left < 0)
  {
    return;
  }

  for (int i = 1; i <=2; i++)
  {
    left -= i;
    option.push_back(i);
    permutate(left, option, result);
    left +=i;
    option.pop_back();
  }
}

list<list<int> > list_stairs(int steps)
{
  list<list<int> >result;
  list<int>option;
  int left = 0;
  for (int i = 1; i <=2; i++)
  {
    left = steps -i;
    option.push_back(i);
    permutate(left, option, result);
    option.pop_back();
  }
  return result;
}

int main()
{
  int target = 3;
  list<list<int> > result =list_stairs(target);
  list<list<int> >::iterator iter;
  for (iter = result.begin(); iter != result.end(); iter++)
  {
  list<int>::iterator i;
    for(i =(*iter).begin(); i != (*iter).end(); i++)
      cout<< *i;
    cout<<endl;
  }
}

I would use Max heap to store the rooms.

Each room will have following variables,
- max: max capacity
- capacity: max number of guests that the room can hold given the percent value
- limit : limit percentage that each room should maintain.
- left : number of available spots left in the room
- gap: ratio of left/capacity

left is calculated by the following formula:
left =capacity - count;

gap is calculated by the following formula
gap = left/capacity

The heap will store each room in descending order of gap value.
ExtractMax() will return the room with highest gap value.

This algorithm can handle the allocation of new quest in O(logN), where N is the number of rooms.
Initial construction of heap can by achieved in O(N) using heapifiy().

If a new room is added, addition of new room will also take O(1).

The following is c++ version of solution

#include <iostream>
#include <math.h>
using namespace std;

struct room {
	int left;
	double gap;
	int max;
	int capacity;
	float limit;
	room(int c, float l):left(0), max(c), limit(l)
	{
		capacity = max*limit;
		left = capacity;
		gap = (double)left/capacity;
	}
	void add_guest(int n)
	{
		left -= n;
		gap = (double)left/capacity;
	}
};


class Heap {
public:
	Heap (bool max = true):bMax(max){}
	room * extract()
	{
		if (last < 0)
			return 0;
		room* found = list[0];
		list[0] = list[last];
		list[last--] = 0;
		heapify(0);
		return found;
	}
	void buildHeap(room** input, int length)
	{
		list = new room*[length];
		int i =0;
		for (i = 0; i <length; i++)
			list[i] = input[i];
		last = length -1;
		len = length;
		int half = floor((double)last/2);
		for (i = half; i >= 0; i--)
			heapify(i);		
	}
	bool add(room * r)
	{
		if (last < len -1)
		{
			list[++last] = r;
			bubbleUp(last);
		} else
			return false;
		return true;
	}

private:

	bool isChild(int parent, int child)
	{
		return (bMax)? list[parent]->gap > list[child]->gap  : list[parent]->gap < list[child]->gap;
	}

	void bubbleUp(int start)
	{
		if(start == 0)
			return;

		int p = parent(start);
		if (p >= 0)
		{
			if (!isChild(p, start))
			{
				swap(p, start);
				bubbleUp(p);
			}
		}	
	}	
	void swap(int src, int dst)
	{
		room *  tmp = list[src];
		list[src] = list[dst];
		list[dst] = tmp;
	}	
	void heapify(int s)
	{
		 int p = s;
    int l = left(s);
    int r = right(s);
    if (l <= last && !isChild(p, l))
    {
      p = l;
    }
    if (r <= last && !isChild(p, r))
    {
      p = r;
    }

    if (p != s)
    {
      swap(p, s);
      heapify(p);
    }

	}

	int parent (int s) { return floor((double)s/2); }
	int left (int s) { return 2*s ;}
	int right (int s) { return 2*s+1;}
	bool bMax;
	room** list;	
	int len;
	int last;
};

void  manage_rooms(room** rooms, int length, int guest_count)
{
	Heap heap;
	heap.buildHeap(rooms, length);
	for (int i = 0; i < guest_count; i ++)
	{
		room* r = 0;
		while ((r = heap.extract()))
		{
			if (r->left == 0)
				continue;
			else
			{		
				r->add_guest(1);
				heap.add(r);
			}
		}
	}
}


int main ()
{
	room *a = new room(10, 0.2);
	room *b = new room(20, 0.4);
	room *c = new room(40, 0.5);

	double i = (double)5/7;
	cout<< i <<endl;

	room* inputs[3] = { new room(10, 0.2), new room(20, 0.4), new room(40, 0.5)};
	manage_rooms(inputs, 3, 100);

	for (int i = 0; i < 3; i++)
	{
		int count = inputs[i]->capacity - inputs[i]->left;
		cout <<" room: count = " << count << "limit = "<<inputs[i]->limit << " percent = " << (double)(count*1.0/inputs[i]->max) <<endl;
	}
}

This is C++ version of solution:
I assume all the elements of php code is tokened.

#include<vector>
#include<list>
#include <map>
#include<string>
#include<iostream>
#include<fstream>

using namespace std;

map<string, list<string>* > * parse_php(vector<string> token)
{
  map <string, list<string>*> *result = new map<string, list<string>*>();
  map <string, list<string>*>::iterator found;
  bool inCode = false;
  bool inClass = false;
  int len = token.size();
  int parenthesis = 0;
  string currentClass;

  for (int i = 0; i < len; i++)
  {
    if (token[i] == "<?php" || token[i] == "<?")
      inCode = true;
    else if (token[i] == "?>")
      inCode = false;
    else if (inCode)
    {
      if (token[i] == "class")
      {
        inClass= true;
        if (i+1 < len)
        {
          currentClass = token[++i];
          list<string> *l = new list<string>();
          result->insert(pair<string, list<string>*>(currentClass, l));
          parenthesis = 0;
        }
      } else if (inClass) {
        if (token[i] == "{")
        {
          parenthesis++;
        }
        else if(token[i] == "}")
        {
          if (--parenthesis == 0)
          {
            inClass = false;
          }
        } else if (token[i] == "function")
       {
          if (i+1 <len)
          {
            found = result->find(currentClass);
            found->second->push_back(token[++i]);
          }
        }
      }
    }
  }
  return result;
}

Here is C++ version of solution, this algorithm assumes the start time and end time of meeting is given as integer. (i.e Mon 2p.m. - 4p.m. will be different from Tue 2p.m. - 4p.m.)

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

bool check_conflict(sched *input, int len)
{
  quicksort(input, 0, len-1);

  int last = -1;
  for (int i = 0; i < len; i++)
  {
    if (last !=1 && last > input[i].start)
      return true;
    last = input[i].end;
  }
  return false;
}

Here is C++ version of answer.

Running time of this algorithm is O(nlogn) due to the sorting.

#include<vector>
#include<iostream>

using namespace std;

struct Schedule{
	int start;
	int end;
	Schedule():start(-1), end(-1){}
	Schedule(int s, int e):start(s), end(e){}
};

struct Room {
	Schedule last;
	Room(){}
	Room(Schedule s):last(s){}
};
int count_meeting_rooms (Schedule* input, int len)
{
	int i = 0, r= 0;
	quicksort(input, 0, len-1);
	print_array(input, len);
	vector<Room>rooms;
	for (i = 0; i < len; i ++)
	{
		if (rooms.size() == 0)
		{
			rooms.push_back(Room());
		}

		for (r = 0; r < rooms.size(); r++)
		{				
			if (rooms[r].last.start == -1 || rooms[r].last.end <=input[i].start)
			{
				rooms[r].last = input[i];
				break;
			}
		}
		if (r >= rooms.size())
		{
			rooms.push_back(Room(input[i]));
		}
	}
	return rooms.size();
}

Here is the C++ version of solution

#include<iostream>
using namespace std;

void find_minmax(int *A, int len)
{
  if (A[0] > A[1])
  {
    if ((A[0] - (len-1)) == A[len-1])
    {
      cout<< "No local min or max exist"<<endl;
      return;
    }
    int min = (A[0]-(len-1)+ A[len-1])/2;
    cout << "Local min : "<< min <<endl;

  } else {
    if ((A[0] + (len-1)) == A[len-1])
    {
      cout<<"No local min or max exists"<<endl;
      return;
    } else {
      int max = (A[0] + (len-1) + A[len-1])/2;
      cout <<"Local max : " << max << endl;
    }
  }
}

Here is my C++ version of solution

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

using namespace std;

class PlaceQueen{

public:
    PlaceQueen(int size):N(size), answers(0)
    {
      diag1 = new bool[2*N];
      diag2 = new bool[2*N];
      row = new bool[N];
      queen = new int[N];

      int i, x, y;
      for (i = 0; i < N; i++)
      {
        row[i] = true;
        queen[i] = -1;
      }

      for (x = 0; x < N; x++)
      {
        for (y = 0; y < N; y++)
        {
          diag1[x+y] = true;
          diag2[N-y+x] = true;
        }
      }
    }

    ~PlaceQueen()
    {
      if (diag1) delete[] diag1;
      if (diag2) delete[] diag2;
      if (row) delete []row;
      if (queen) delete []queen;
    }
    void place_queens()
    {
      put_queen(0);
      cout << " result ways : " << answers << endl;
    }
private:
  int N;
  bool * diag1;
  bool *diag2;
  bool *row;
  int * queen;
  int answers;

void put_queen(int x)
{
  if (x >= N)
    answers++;
  else {
    for (int y = 0; y < N; y++)
    {
      if (row[y] && diag1[x+y] && diag2[N-y+x] && (x==0 || (x==1 && (queen[x-1]==-1 || abs(queen[x-1]-y) !=2) ) || (x > 1 && (queen[x-1]==-1 || abs(queen[x-1]-y) !=2) && (queen[x-2] ==-1 ||abs(queen[x-2]-y)!=1 )) ) )
      {
        row[y] = false;
        diag1[x+y] = false;
        diag2[N-y+x] = false;
        queen[x] = y;

        put_queen(x+1);

        row[y] = true;
        diag1[x+y] = true;
        diag2[N-y+x] = true;
        queen[x] = -1;
      }
    }

  }
}
};


int main (int argc, char *argv[])
{
  int n = atoi(argv[1]);
  PlaceQueen board(n);
  board.place_queens();
}

Here is my C++ version of answer using hashtable. Running time will be O(N)

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

bool has_sum(int* input, int len, int target)
{
	map<int, int> hashtable;
	map<int, int>::iterator iter;
	int i = 0;
	for (i = 0; i< len; i++)
		hashtable[input[i]] = input[i];

	for (i = 0; i <len; i++)
	{
		int left = target - input[i];
		iter = hashtable.find(left);
		if (iter != hashtable.end())
			return true;
	}
	return false;
}

Here is C++ version of the solution

#include<list>
using namespace std;

struct Node {
  Node * left;
  Node * right;
  Node * next;
  Node():left(0),right(0),next(0){}
};

void link_nodes(Node* s)
{
  list<Node*> queue;
  Node* last_node = nullptr;
  int nodes_to_process = 0, next_level_nodes = 0;
  queue.push_back(s);
  nodes_to_process = 1;

  while (queue.size()>0)
  {
    Node* cur = queue.front();
    queue.pop_front();
    nodes_to_process--;

    if (cur->left)
    {
      queue.push_back(cur->left);
      next_level_nodes++;
    }

    if (cur->right)
    {
      queue.push_back(cur->right);
      next_level_nodes++;
    }

    if (last_node)
      last_node->next = cur;

    if (nodes_to_process > 0)
    {// this is next level
      last_node = cur;
    } else {
      //this is next level
      nodes_to_process = next_level_nodes;
      next_level_nodes = 0;
      last_node = 0;
    }
  }
}

This algorithm makes use of minimum heap to short the non-crossing interval (here after extent).

One assumption this algorithm makes is that 00:00:00 of last day of week equals to (7*24*60*60).

This algorithm divide input intervals into two groups:
1) non-crossing intervals, where start < end
2) crossing intervals where start > end

Running Time will be O(N log N) due to the heap operations (add, extract), where N is the number of input intervals.

Any suggestions or critics are welcomed.

struct extent {
  int start;
  int end;
  extent ():start(-1), end(MAX_INT32){}
}

bool is_overlap(extent* list, int n)
{
  int c_start = -1; c_end = MAX_INT32;
  MinHeap heap;
  for(int i = 0; i < n; i++)
  {
    if (list[i].start == list[i].end)
      return true;
    else if (list[i].start < list[i].end)
      heap.add(list[i]);
    else {
      if (c_start < list[i].start)
        c_start = list[i].start;
      if (c_end > list[i].end)
        c_end = list[i].end;
    }
  }

  bool no_cross = false;
  no_cross = (c_start == -1);
  extent *min;
 
  while (heap.len() > 0)
  {
    min = heap.extract();
    if (no_cross) {
      if (c_start == -1)
      {
        c_start = min->start;
        c_end = min->end;
      } else if (c_start < min->start)
        return false;
      else
        c_end = min->end;
    } else {
      if (c_start < min.start)
        return false;
      else
        c_start = min.end;
    }
  }
  return (c_start == 0 && c_end == END_OF_WEEK) || (c_start >= c_end);
}

I am gonna assume that findMax, findMin, and findMedium all takes array A and its length as parameters and return the results in O(1) time.

If that is the case, I would use counting sort to sort the integer in O(N) time.

Any critics will be welcomed.

int* CountingSort(int* A, int len)
{
	int max = findMax(A, len);
	int min = findMin(A, len);
	int clen = max - min +1;
	int *c = new int[clen];
	int *B = new int[len];
	int i;

	for (i = 0; i <clen; i++)
		c[i] = 0;
	for(i = 0; i <len; i++)
		c[A[i]-min] += 1;
	for (i = 0; i <clen; i++)
	{
		if (i >0)
			c[i] = c[i-1]+c[i];
	}

	for (i = len-1; i >=0; i--)
	{
		B[c[A[i]-min]-1] = A[i];
		c[A[i]-min] -=1;
	}
	delete [] c;
	return B;
}

struct Point {
  int x;
  int y;
  Point(int posx, int posy):x(posx), y(posy){}
};

int x_move[4] = {1, -1, 0, 0 };
int y_move[4] = {0, 0, 1, -1};

list<Point>* get_edges(Point p, int*map[], int h, int w)
{
  list<Point>* edges = new std::list<Point>();
  int cur = map[p.y][p.x];

  for (int m = 0; m <4; m++)
  {
    int next_x = p.x+x_move[m];
    int next_y = p.y+y_move[m];
    if (next_x <=0 || next_x >= w-1 || next_y <=0 || next_y>=h-1)
      continue;
    if (cur <= map[next_y][next_x])
      edges->push_back(Point(next_x, next_y));
  }
  return edges;
}

void DFS(Point s, int*map[], int* marked[],int h, int w, int direction)
{
  list<Point>* edges = get_edges(s, map, h, w);
  list<Point>::iterator iter;
  for (iter = edges->begin(); iter != edges->end(); iter++)
  {
    if ((marked[(*iter).y][(*iter).x] & direction)==0)
    {
      marked[(*iter).y][(*iter).x] |= direction;
      DFS((*iter), map, marked, h, w, direction);
    }
  }
  delete edges;
}

void find_path(int **map, int h, int w)
{
  int EAST = 1;
  int WEST = 2;
  int **marked;
  marked = new int* [h];
  for (int i = 0; i < w; i++)
    marked[i] = new int[w];

  for (int x = 0; x < w; x++)
  {
    marked[0][x] |= EAST;
    DFS(Point(x, 0), map, marked, h, w, EAST);
  }

  for (int y = 1; y < h-1; y++)
  {
    marked[y][0] |= EAST;
    DFS(Point(0, y), map, marked, h, w, EAST);
  }

  for (int wx = 0; wx < w; wx++)
  {
    marked[h-1][wx] |= WEST;
    DFS(Point(wx, h-1), map,  marked, h, w, WEST);
  }
  for (int wy = 1; wy < h; wy++)
  {
    marked[wy][w-1] |= WEST;
    DFS(Point(w-1, wy), map,  marked, h, w, WEST);
  }
  for (int row = 0; row < w; row++)
  {
    for(int col = 0; col < h; col++)
    {
    //  if (marked[col][row] == 3) 
        cout<< marked[col][row];
    }
    cout <<endl;
  }
}