CareerCup

Based on ChrisK's idea :

bool isRectangle( const vector<vector<int>>&  matrix )
{
	int rows = matrix.size();
	if(rows == 0 ) return false;
	int columns = matrix[0].size();
	
	unordered_map<int, unordered_set<int>> table;
	
	for( int i=0; i<rows; ++i)
	{
		
		for( int j=0; j<columns-1; ++j)
		{
			for(int k=j+1; k<columns; ++k)
			{
				if( matrix[i][j]==1 && matrix[i][k]==1)
				{
					if( table.find(j) != table.end() && table[j].find(k) != table[j].end() )
					{
						return true;
					}
					if( table.find(k) != table.end() && table[k].find(j) != table[k].end() )
					{
						return true;
					}
					table[j].insert(k);
					table[k].insert(j);
				}
			}
		}
	}
	return false;
}

class node
{
public:
	int val;
	node* left;
	node* right;
	node( int v): val(v), left( nullptr), right(nullptr)
	{}
};

node* eraseNodes(node* root, vector<node*>& result, function< bool(node*) >& shouldBeErased )
{
	if(!root) return nullptr;
	
	// check if leaf node
	if( !root->left && !root->right )
	{
		if( shouldBeErased(root) )
		{
			delete root;
			return nullptr;
		}
		else
		{
			return root;
		}
	}
	
	root->left = eraseNodes( root->left, result, shouldBeErased );;
	root->right = eraseNodes(root->right, result, shouldBeErased);;
	
	if( shouldBeErased(root) )
	{
		if( root->left ) result.push_back(root->left);
		if( root->right ) result.push_back( root->right);
		return nullptr;
	}
	return root;
}

Since we are not allowed to create a dummy node, we need to adjust the newHead first.

class node
{
public:
	int val;
	node* next;
	node( int v ):val(v), next(nullptr)
	{}
};

node* mergeTwoSortedList( node* first, node* second )
{
	if( first == nullptr ) return second;
	if( second == nullptr ) return first;
	
	if(  first == second ) return first;
	
	node* newHead = nullptr;
	node* tail = nullptr;
	
	// Initialize newHead and tail first.
	if( first->val < second->val )
	{
		newHead = tail = first;
		first = first->next;
	}
	else
	{
		newHead = tail = second;
		second = second->next;		
	}
	
	// Go over both list at same time and update new list 
	while( first && second )
	{
		if( first->val < second->val )
		{
			tail->next = first;
			first = first->next;
		}
		else
		{
			tail->next = second;
			second = second->next;
		}
		tail = tail->next;
	}
	
	// Append unfinished list to end of new list
	tail->next = first ? first : second;
	return newHead;
}

Posting simple trie solution:
+ Replace '*' with all possible valid characters in trie.

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int TOTAL_LENGTH = 26;
class trieNode
{
public:
	bool isKey;
	vector<trieNode*> children;
	trieNode():isKey(false), children( vector<trieNode*>( TOTAL_LENGTH, nullptr))
	{}
};

class wordDict
{
private:
	trieNode* root;
	
	bool findWordHelper( trieNode* curr, const string& word )
	{
		if( word.size() == 0 ) return false;
		
		for( size_t i=0; i<word.size();  ++i)
		{
			// either a regualer character
			if( curr && word[i] != '*')
			{
				curr = curr->children[ word[i]-'a'];
			}
			else if( curr && word[i] == '*')
			{				
				// Go over all the characters
				for( int j=0; j< TOTAL_LENGTH; ++j)
				{
					if( curr->children[j] != NULL &&
					    findWordHelper( curr->children[j], word.substr(i)) )
					{
						return true;
					}
				}
			}
			else
			{
				break;
			}
		}
		return curr && curr->isKey;
	}
	
public:
	wordDict(): root( new trieNode() )
	{}
	
	void addWord( const string& word )
	{
		if( word.size() == 0) return;
		
		trieNode* curr = root;
		for( size_t i=0; i< word.size(); ++i )
		{
			if( curr->children[ word[i]-'a'] == NULL)
			{
				curr->children[ word[i]-'a'] = new trieNode();
			}
			curr = curr->children[ word[i]-'a'];
		}
		
		//after loop set the flag to indicate valid word
		
		curr->isKey = true;
	}
	
	// Word could contain a '*' charactrer to map to any charcter 
	bool findWord( const string& word )
	{
		return findWordHelper( root, word );
	}
	
	
};

int main()
{
	
	wordDict dict;
	
	dict.addWord("hello");
	dict.addWord("one");
	dict.addWord("two");

	cout << dict.findWord("one") << endl;
	cout << dict.findWord("two") << endl;
 	cout << dict.findWord("****e") << endl;

	return 0;
}

Simple BruteForce using Backtracking.
+ This is not an optimal solution, but very intuitive to reach during interview.
+ Pick one color at a time ( loop over K value ) and recurse for next one.
+ If last 3 colors were the same as this color, dont pick this color and continue.
+ when we reach n colors, count that solution as 1 valid result.

int helper( int n, int k, vector<int>& result )
{
	int size = result.size();
	if( size == n )
	{
		return 1;
	}	
	int count = 0;
	for( int i=0; i<k; ++i )
	{
		if( size >=3 && result[size-1] == i 
		             && result[size-2] == i 
		             && result[size-3] == i )
		{
			continue;
		}
		result.push_back( i );
		count += helper(n,k, result);
		result.pop_back();	
	}
	return count;
}

void getCount(int n, int k )
{
	vector<int> result;
	int count = helper(n,k, result);	
	cout << " Count is " << count;
}

This seems like a "Reservoir sampling" problem. Select K sample from a stream of samples.
+ Fill a buffer of size K with first K samples from stream.
+ Continue processing stream, and create a random number from 0 to current index for stream.
+ If number is in range [0,K] then overwrite current sample at this random index with current item from stream.

vector<int> reservoirSampling( const vector<int>& stream, int k )
{
	vector<int> result(k);
	
	// copy first k elements from stream as it is
	for( int i=0; i<k; ++i)
	{
		result[i] = stream[i];
	}
	
	srand( time(0) );
	
	for(; i<stream.size(); ++i )
	{
		// pick a random index from 0 to i inclusive
		int index = rand() % (i+1);
		
		// overwrite sample is randomly chosen index is between 0 and k.
		if( index < k)
		{
			result[index] = stream[i];
		}
	}
	
	return result;
}

Recursive solution with look-up table :
+ Going over input string and split it into two parts ( left + right ) of different length.
+ If left is a valid string in dictionary then we recurse over right part.
+ Every recursive call, we use look-up table to avoid duplicate calls.
+ After all combination for a given string, save "minimum cuts" into lookup table.

#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<limits.h>

using namespace std;

unordered_map<string, int> table;

int minCut( const string str, 
            const unordered_set<string>& dict )
{
    // look up return
    if( table.find( str) != table.end() )
    {
        return table[str];
    }
    
    // find it in dict
    if( dict.find( str) != dict.end())
    {
        table[str] = 0;
        return table[str];
    }
    
    int minCount = INT_MAX;
    for( int i=1; i<str.size(); ++i )
    {
        int count = 0;
        string left = str.substr(0,i);
        if( dict.find(left) != dict.end() )
        {
            string right = str.substr(i);
            count += minCut( right, dict);
            
            // INT_MAX means right substring is not breakable into valid combination
            if( count != INT_MAX )
            {
                ++count;
                minCount = min( count, minCount);
                
            }
        }
    }
    table[str] = minCount;
    return table[str];
}

int main()
{
    string str = "CatMatYY";
    unordered_set<string> dict = { "Cat", "Mat", "Ca", "tM", "at", "C", "M", "Y"};
    
    
    cout << minCut( str, dict );
    return 0;
}

Different from ChrisK's solution.
+ Insert a new node at alternate locationin the original list that we are trying to copy.
exapmle, original list 1->2->3. Make it 1->1->2->2->3->3
+ Go over the list again to adjust random pointers at even location nodes.
+ go over the list again to separate odd/even location list.
+ return pointer to even location list.

Advantage here is we dont need o(n) space for lookup table. But at the same time, we are modifying the original list, so in real world this entire operation has to be atomic.

In ChrisK's solution we are not modifying the original list.

class node
{
public:
	int val;
	node* next;
	node* random;
	
	node( int k ): val(k), next(nullptr), random(nullptr)
	{}
};


node* deepCopy( node* head )
{
	if( head == nullptr ) return nullptr;
	
	node* curr = head;
	node* origNext = nullptr;
	
	// [1] create new nodes link them with current list
	// After this step, we will have 2 lists combined into 1
	while( curr )
	{
		origNext = curr->next;
		curr->next = new node( curr->val );
		curr->next->next = origNext;
		curr = origNext;
	}
	
	// [2] Go over the entire list again and adjust random ptr
	// If original list has x nodes, then new list has 2x nodes
	curr = head;
	while( curr )
	{
		// current's next is copy of current
		// only do this if random is valid
		if( curr->random )
		{
			curr->next->random = curr->random->next;
		}
		curr = curr->next->next;		
	}
	
	// [3] Go over the list again and de-link the new list
	
	node* dummy = new node(-1);
	curr = head;
	node* newCurr = dummy;
	while( curr )
	{
		origNext = curr->next->next;
		newCurr->next = curr->next;
		curr->next = origNext;
		newCurr = newCurr->next;
		curr = curr->next;
	}
	
	return dummy->next;
	
}

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

using namespace std;

bool isOverlap( const pair<int,int>& p1,
                const pair<int,int>& p2 )
{
	if( p1 == p2 )
	{
		return true;
	}
	else if( p1 < p2 )
	{
		return ( p1.second >= p2.first ) ? true : false;
	}
	else
	{
		return ( p2.second >= p1.first ) ? true :false;
	}	
}

vector< pair<int,int>> getRange( const vector< pair<int,int> >& arr1,
                                 const vector< pair<int,int> >& arr2)
{
	vector< pair<int,int> > result;
	
	// get intersection of timestamps
	size_t i=0;
	size_t j=0;
	
	while( i< arr1.size() && j<arr2.size() )
	{
		// If they dont overlap then advance smaller pair index
		if( !isOverlap( arr1[i], arr2[j]))
		{
			( arr1[i] < arr2[j] )? ++i : ++j;
			continue;
		}
		
		if( arr1[i] == arr2[j])
		{
			result.push_back( arr1[i]);
			++i;
			++j;
		}
		else 
		{
			int left = max( arr1[i].first, arr2[j].first );
			int right = min( arr1[i].second, arr2[j].second );
				
			result.push_back( make_pair( left, right));
			(right == arr1[i].second) ? ++i : ++j;
		}
	}
	
	return result;
}

int main()
{
	vector< pair<int,int> > ip1 = { {2,4}, {9,11}, {14,18}, {20,22}};
	vector< pair<int,int> > ip2 = { {3,5}, {9,10}, {15,17}, {22,25}};

	vector< pair<int,int> > result = getRange( ip1, ip2 );
	for( auto item : result )
	{
		cout << item.first << " : " << item.second << endl;
	}
	return 0;
}

Using C++ STL "Set" as balanced tree and keeping track of intervals.
+ Deleting intervals when we insert new overlapping intervals.
+ Intervals expected in [start,end) format.

#include<iostream>
#include<vector>
#include<stack>
#include<utility>
#include<set>

using namespace std;

class intervalTracker
{
public:
	int total;
	set< pair<int,int> > tree;
	
	intervalTracker(): total(0)
	{}
	
	void insert( pair<int,int> range )
	{
		if( tree.empty() )
		{
			tree.insert(range);
			total += (range.second - range.first);
		}
		
		// This is not the first node, so now we find a correct place to install this
		pair<int,int> tmp = { range.first, INT_MAX };
		auto it = tree.upper_bound( tmp );
		
		// update previous neighbor 
		if( it != tree.begin() )
		{
			if( (--it)->second < range.first )
			{
				++it;
			}
			else
			{
				range.first = it->first;
				range.second = max( it->second, range.second );
				total -= ( it->second - it->first );
				it = tree.erase(it);
			}
		}
		
		// itertor still points to upper bound, regardless erased node or not
		// check next neighbor for overlapping intervals
		while( it != tree.end() && range.second >= it->first )
		{
			total -= ( it->second - it->first);
			range.second = max( it->second, range.second );
			it = tree.erase( it);
		}
		
		total += ( range.second - range.first );
		tree.insert(range);		
	}
	
	vector<int> addIntervals( const vector<pair<int,int>>& intervals)
	{
		vector<int> result;
		for( auto x : intervals )
		{
			insert(x);
			result.push_back( total );
		}
		return result;
	}
};
int main()
{
	vector< pair<int,int> > intervals = {{1,3},{4,7},{5,8},{3,6},{9,12}};
	intervalTracker iTrack;
	vector<int> result = iTrack.addIntervals( intervals );
	
	for(int i=0; i<result.size(); ++i)
	{
		cout << result[i] << " ";
	}
	return 0;
}

@PenChief

Small correction here:
this->value = this->left && this->right;
This line will set value = 1 as long as we have valid left and right child. We actually need to read the value of left and right child in order to set the value of parent to Logical AND.

Please correct me if I'm wrong here.

Simple trick.
[1] Do a binary search to find lowest value index in array.
[2] Then just a regular binary search to look for target value, but use index from [1] to accommodate for rotation.

#include<iostream>
#include<vector>

using namespace std;
const int notFoundError = -1;
int findElement( const vector<int>& input, const int target )
{
	// Do a binary search and find lowest element in array
	int lo=0;
	int hi = input.size()-1;
	
	while( lo < hi)
	{
		int mid = lo + (hi- lo)/2;
		if( input[mid] > input[hi] )
		{
			lo = mid+1;
		}
		else
		{
			hi = mid;
		}
	}
	
	//  save index of minimum value
	int minIndex = lo;
	
	// reset lo and hi
	lo = 0;
	hi = input.size()-1;
	
	// we do binary search for original element
	while( lo <= hi)
	{
		int mid = lo + (hi- lo)/2;
		int realMid = ( mid+ minIndex) % input.size();
		if( target == input[realMid] ) 
		{
			return realMid;
		}
		else if( target > input[realMid] )
		{
			lo = mid+1;
		}
		else{
			hi = mid-1;
		}
	}
	return notFoundError;
}
int main()
{
	vector<int> input({7,8,2,4,5, 6});
	cout << findElement(input, 5);	
	return 0;
}

#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>

using namespace std;
const int deckSize = 52;
void fisherYatesShuffler( vector<int>& cards )
{
	srand(time(0));
	for( int i=cards.size()-1; i>=0; --i)
	{
		int randomIndex = rand() % (i+1);
		swap( cards[i], cards[randomIndex] );
	}
	
}
int main()
{
	vector<int> cards( deckSize );
	for( int i=0; i<cards.size(); ++i)
	{
		cards[i] = i+1;
	}
	
	fisherYatesShuffler( cards );
	return 0;
}