CareerCup

I propose a two step solution here:

1. Using a Depth First Traversal, push all the elements into a stack(S1) with a stub/delimiter in between each level. This can be achieved with a queue(Q) and stack(S1) as follows:

Push root element into the queue and then push a delimiter/stub value into the queue
While queue not empty:
  dequeue next element
  if(!delimiter)
	push element into stack S1
  enqueue its childern into the queue
  else //if delimiter
	push a delimiter into both stack and queue

2. Using two stacks S1 and S2, pop the levels in the spiral way i.e. pop top level from S1(level 1 of the tree), then pop remaining S1 into S2. Pop first level of S2(level n of binary tree) and pop remaining S2 into S1 and repeat till empty.

The only thing I can think of is using a multi-core / multiple processors and using multi-threaded solution.
For instance, since we have multiple processors available, divide the matrix into 2 equal parts and assign the 2 parts to 2 separate threads. Then we can have these two threads run simultaneously on multiple processors and get faster than O(nm) run time. Other than that I think the interviewer was trying a trick question

I propose a slightly better way of doing this. In worst case it will be O(N^2 log n) but in reality it will be better.

Say our original array is A = {10, 5, 3, 7, 4, 1}

Since we have to find all sub-sequences of length 3 in A which satisfy the triangle property, let us first sort the array. Complexity of this step is O(n log n)

A = {1, 3, 4, 5, 7, 10}

Now we can start going through this array and picking triplets. However, since they are already sorted, when picking up the triplets, we can quickly check if the sum of two smaller ones is less than the bigger one

So, if our triplet is a, b & c; in iterating through the above array:
a = 1 b = 3 c = 4, a+b !>(not greater than) c, this triplet does not satisfy the triangle property.
Therefore we donot need to consider any more triplets for a = 1 and b = 3,
(because our next c element will be 5, which again won't satisfy the triangle property! i.e. all the remaining elements are greater than 4)

As you see, using this algo we can skip many of the triplets outright without making necessary comparisons.

Basically, there are two way to do automatic garbage collection. First of all, only objects in the heap require garbage collection. Objects in stack are automatically cleaned once the function/program goes out of scope, objs in heap are not cleaned automatically.
1. Use reference counting i.e whenever a object is created, we also keep a count of number of pointers referring to that object called the reference count. Then, if the reference count become zero i.e. we have no pointer pointing to that object, we can safely release the memory. A good example of this is the shared/unique/weak pointers in C++ STL
2. We periodically do garbage collection i.e. after some interval a garbage collector runs and any unreferenced memory objects are freed. A good example is Java. Basically, we start from a set of base objects (say all objects in the stack), follow the references and mark any object we encounter on the way as ok. Then we sweep the entire heap again and any object found not marked is unreachable and therefore can be freed.

Which company was this for?
The aim of a Hashmap would be to store key-val pairs and allow search, insert and del operations in constant O(1) time.
A simplest implementation of a hashmap would be using a Hash Function H which gives you the index i using the key ( i = H(key) ). Using the index we will store the key-val at the appropriate place. However, if the index location is not empty, the simplest solution is to link the new key-val entry to the old one using a Linked List. Ofcourse, there are other solutions as probing and double hashing.

Some code:

A is our bool arr
i = 0
flag = false;
while (i < size of A)
    if A(i) == true
	possible starting point 
	call recusive fn with starting jump of len i
    	if the above call returns with true value, exit and return true
   else
	i++

Dynamic Programming / Recrusion should give us a natural solution.

Walk the bool array till you find a value of 1.
This represents a possible starting point for sequence of jumps.
Now make a recursive call with this position as the starting point and see if from can reach the other end.
If yes, search over.
if no continue walking the array till next true value found and similarly recurse over it.

This is the simplest solution I can think of. It can take some improvements, but the question itself is not
clear.

zr.roman: In this case the middle node would be the one containing substring "ef".

When we first walk the linked list, total number of chars = 13.
Therefore the middle element of the substring = 13/2 + 1 i.e. at index = 7 which is the char 'f'

We walk the second time, reversing the LL till we reach the node with 7th element and work from there.

I'm interested in knowing. Is question this from a Hackerrank contest?

All of the operations being O(1) looks like the interviewer is asking for a hashmap implementation.
Simplest way of implementing a hashtable/map requires two things:

1. Data structure to store key value pairs, we take array named A of size = sz
2. A hash function F.

So, our Hashtable will store key value pairs and allow Insert, Delete, Search and getRandom in O(1) time.

Insert:

Using the Hash function F, find the index(idx) where the key-val pair will be stored i.e.
idx  = F(key)
and store the key-val pair over there
H[idx] = key+val
Now, if that position is already occupied, it means we have a collision. Collisions can be handled in 
multiple ways. One simple way is to keep increasing the index till an empty space found (linear probing):
while ( H[idx] != empty && idx < size) {idx++;}. When empty cell found, insert the key-val pair.

Search and Delete are along the same lines. Just find the idx using F(key) and see if it matches the input key
For delete, just insert an special value (called tombstone) to prevent our linear probing from going wrong.

getRandom:
Bascially return any random entry from the array. Pick a random number using random number generator and use
the modulus operator to convert it into a suitable index i.e. idx = random_number % size
Now, return the key-val pair at this size.

Both prefix and postfix can be implemented using a simple strategy using a stack(LIFO). We assume the
current prefix/postfix expression is present in a queue(FIFO)
A general algo is:

Till queue empty
  Dequeue one element from queue
    if element is a number/operand or an = expression
      push it into the stack
    else //element is an operand like + - * etc
      pop top two elements from stack
      perform the operation using the operand
      push result onto stack

      if(stack becomes empty before two elements can be popped)
	error! 

At this point, your queue will contain one element i.e. the answer

I'm curious how your code will perform agains the expresssion in question i.e. * - 6 5 7 = 7?
Strting from the left, your stack will contain one 7 before = expression is encountered, when you try to remove
2 operands from the stack, you only have 1 operand -> err
Instead I would suggest also pushing in the = operator into the stack

I agree with everyone above. The question is not clear. Merging two sorted arrays to produce a sorted array can only be done in one way. If that is what we're trying to do, the merge step from mergesort is a simple algorithm to follow.

however, we will only end up with one possible array.

Data structure can be as simple as using an array to store all the strings.
Arr1[n] = {a, ab, abc, abcd, ..., abcd..xy, abcd...xyz}
Complexity will be linear ~ O(n). We will walk the array once. At each step select one string, remove last char and compare to the next string.

If the words/strings in the library are all subsets of each other, then the longest possible chain will be n.
E.g. If the words are: a, ab, abc, abcd, abcde, abcdef, .... ,abcde..xyz. You have 26 words (n = 26). Start with the last word and remove the char z, it will now be the same as the second last word. Now remove the char y, it will be same as third last word and so on till we reach the first word a. So the longest possible chain is n

Lets consider all cases:
1. If the node has a right child, then its logical descendant will be somewhere in the right tree. Therefore, find the minimum element that is bigger that the node in its right tree i.e. go right and then keep going left till you find a left node.
2. If the node has no right child, then
a) If the node is a right child of its parent, the in order traversal will end at the node, so no in order successor
b) If the node is a left child of its parent, then the parent is the in order successor.

Can I rephrase the question? Traverse the tree and print out all the elements. That will flatten the tree into a linear array. A BST with only right children can be thought of as a linear.
For the example mentioned in the question, we can do a in-order traversal and get the desired result.

Neat solution. I think this would be the most efficient one. I propose a small change, an integer for each player to keep track of his score. The score will be +1 or -1 as per the prediction.

b?

Soln 2: If we're not allowed extra space: Sort the array.
Now iterate through the array and for each element, check its neighbors.
If a duplicate found, mark it and check the next neighbor and so on till you find a non duplicate number and repeat
Run time O(nlong n for sorting + n for subsequent iteration) = (nlongn)

Soln 1: If we're allowed extra space. Create an binary array B of size n-1 and set all elements to false. Iterate through the array.
For each element in array A, use it to index into array B. If the element at arr B is false, set it to true. If it is true, means we
have a duplicate.
E.g. for elemnt 30 at index 27 in A, if B[30] == true, this means element 30 at index 27 is duplicate
Run time O(n)

We can have two solution, one will use extra space for faster run time O(n), the other will not use extra space but take longer O(nlogn).
Say we have array A of numbers in range 0 - n-1

Ingenious solution hnatsu.
My only doubt about it is what if the numbers are not increasing linearly?
For instance: Range is 0 - 9, Numbers are {1,2,5,7,7,9} will your algorithm work?

If we're not keeping track of nodes already visited, here is a solution I propose:
Lets say the depth of tree is N i.e. number of levels is N.
1. Select a random number between 0-N-1 say P. So we will go down P levels
2. Go down P levels, one level at a time. At each level, select a random number between 0or1: if number = 0 go left else go right

Each node will have equal probability of being selected.

Why do we need to keep track of the nodes we've already visited?
If I'm selecting a random number between 1-5 and I select #3 the first time, I can select #3 the second time or the third time too(since probability of number being selected is equal). So why would I keep track of numbers/nodes already selected?

Coming back to the discussion, I'm not sure if sorting the string after concatenation will be all that useful?
Consider 4 strings A < B < C < D (in that sorted order)
# of operations to concatenate without sorting:
A,B,C,D join A&B -> A+B,C,D join A&B with C -> 2A+2B+C,D
join A&B&C with D -> 3A+3B+2C+D
# of operations to concat with sorting:
A,B,C,D join A&B -> A+B,C,D sort -> C,D,A+B -> join C+D -> C+D, A+B
sort -> A+B, C+D join the two -> 2A+2B+2C+2D
Without sorting might be faster?

Thank you! If there is one thing I hate with a passion, its people hiding behind anonymity. I mean, if you're down-voting it, give me a reason, say something, don't just hide behind your computer.
That being said, I'm pretty sure someone will be down-voting this comment too :-)

Here is a solution I propose. Not sure if it is the fastest, I'd like to see others thoughts on it.
Start by concatenating the smallest strings and concatenate with a bigger string and so on.
Say we have three strings A, B & C with lengths L1 > L2 > L3.
If we concatenate largest to smallest (A with B and then with C),
# of operations = (L1 + L2)(For A&B) + (L1+L2 + L3 (For A&B with C)= 2L1 + 2L2 + L3
If however, we concatenate smallest to largest (C & B and then with A)
# of operations = L1 + 2L2 + 2L3 which would be less than the above case.

So, first sort the strings according to increasing length and then use concatenate function on them, from smallest to largest.

Nicely done!

So, in essence, find all the rectangles enclosing the point. The find the rectangle with minimum area among those rectangles.

This might sound silly, but can anyone help me understand
how the original question found 5 sets of anagrams:

Set: <abc,cab,dac,beed,deb,few,acd>
Anagrams:
abc, cab
dac, acd
deb, beed
So 3 sets of anagrams, not 5?

I like your idea of using a STL Map. The one obvious advantage I see is while in graph to start with node A, you would have to traverse the graph to find the actual node A; in Map you can directly start with node A.
However, beyond this both would be an ~O(n) solution since we would have to examine each node in turn.
The space complexity might be a little less in a graph since we're not storing each node and its children individually.

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

bool findRotationIdx(int *A, int length)
{
	printf("length of array is %d \n", length);
	if(length == 0)
	{
		printf("Empty array \n");
		return false;
	}
	if(length == 1)
	{
		printf("Index is %d", length-1);
		return true;
	}

	int l = 0;
	int h = length-1;
	int m = 0;

	while(l<=h)
	{
		m = (l+h)/2;
		if(l==h)
		{
			//match
			printf("Rotation index is %d \n",l);
			return true;
		}
		else if (A[l] < A[m])
		{
			//pivot is in upper half
			l = m+1;
		}
		else
		{
			h = m-1;
		}
	}

	return true;
}


int main()
{
	int A[10] = {6,7,8,9,10,11,1,2,3,4};
	int B[7] = {6,7,1,2,3,4,5};
	bool retVal = findRotationIdx(B, (sizeof(B)/sizeof(int)));
	if (!retVal)
	{
		printf("Error in array, kindly check \n");
	}
	return 0;
}

As others have already suggested, we can use a modified binary search to find the pivot point. Here is a sample working code in C. Its self explanatory so I'm not going into the details.

Complexity analysis:
Initially creating a graph out of the text file ~ O(n ^ 2)
BFS search ~ O(n). So we can produce linear time results if we spend initial time and create a graph.

A sample run would look like this:
Q1: A D,C,B C,D D F,E G,F G NULL
Q2: 0 1,1,1 1,1 1 2,2 3,2 3 NULL

o/p by level of association:
level 0: A
level 1: B,C,D
level 2: E,F
level 3: G

With our data in place, we will perform a BFS on the graph.
Since we want level (of association), we will use two queues:
Q1: to hold graph nodes
Q2: to hold association levels

I cannot draw the graph here, so I will leave the drawing of the graph to your imagination. To traverse the graph:

Start with A:
Enqueue it to Q1 and enqueue level of association 0 into Q2
Then repeat the following till Q1 is empty:

- Dequeue a node(N) from Q1 and the level(L) from Q2
- Enqueue all unvisited childern of N into Q1 with association level of L+1 and mark them visited

We'll use the example in the question:
A: B,C,D
D: B,E,F
E: C,F,G

Start with element A. Insert it into the graph
node * A = new node("A"); //Data of a node is the character A
Insert B,C & D as its childern
A->addChild(B); A->addChild(C); ...

Then we will repeat the process for A's childern.
Take the next child(say D).
Search the entire file for D. Since file is not sorted its a linear time operation O(n)
Insert D into graph and repeat for its childern.

Since its linear search time for every node:
Complexity would be ~ O(n + n + n ....n times) ~ O(n ^2)

Sample node of a graph:
struct node{
	int data;
	vector <node *>childern; //A Linked List would be equally fine
	bool isVisited; //during BFS, check if the node has been visited
};

Oookay I think BFS traversal will work. However for that we would need to convert the file into a graph and then perform the BFS on it.

So the solution would broadly comprise  of:
A) Convert the file into a graph. Its a one time operation, once done we won't need to do it again.
B) Starting with the appropriate node in the graph, perform a BFS(using queues)

Here is a sample code:

void findSeq(node *n, int sum, vector<int>V)
{
	if(n->lt == NULL && n->rt == NULL)
	{
		//leaf node
		if(n->data == sum)
		{
			//match
			V.push_back(n->data);
			cout << endl << "=================" << endl;
			printVec(V);
			cout << "=================" << endl;
		}
		else
		{
			//no match
			return;
		}
	}
	else
	{
		V.push_back(n->data);
		//cout<< "Not a leaf node" << endl;
		if(n->data == sum)
		{
			//match
			cout << endl << "=================" << endl;
			printVec(V);
			cout << "=================" << endl;
		}
		//recurse on child nodes
		if(n->lt != NULL)
			findSeq(n->lt, (sum - n->data), V);
		if(n->rt != NULL)
			findSeq(n->rt, (sum - n->data), V);
	}

}

So unless its a binary search tree, we will have to examine all possible paths.
We cannot stop if we find a matching sequence (E.g. 2,5). We will still need to keep going till we
reach the leaf node. (E.g. 2,5,-2,2 would be a match, 2,3,4 would not be a match)

So here is a O(n^2) algorithm.

Start at root
For any node, check if there is a match till here and print it.
If its a leaf node, we return.
Else, we pass in the remaining sum (number to be found - previous node) to its children and recurse

// Main functions:

void findElement(int *Arr, int size, int element)
{
	if(size == 0)
	{
		cout << "err" << endl;
		return;
	}
	if(size == 1)
	{
		if (Arr[0] == element)
		{
			cout << "Found element at idx 0" << endl;
			return;
		}
		else
		{
			cout << "Not found" << endl;
			return;
		}
	}
	int peak = findPeak(Arr, size);
	int l1 = 0; int h1 = peak;
	int l2 = peak+1; int h2 = size;
	
	if (binarySearch(Arr, l1, h1, element) || invertedBinarySearch(Arr, l2, h2, element))
	{
		cout << "element found" << endl;
	}
	else
	{
		cout << "element not found" << endl;
	}
	return;
}

int main()
{
	int A[9] = {1,2,3,5,7,9,11};
	int B[9] = {11,9,7,5,3,2,1};
	int C[9] = {1,2,5,8,13,9,3,-1};
	findElement(C, 7, 3);
	return 0;
}

//Supporting functions:

int findPeak(int * myArr, int mySize)
{
//Find Peak Element
	if (mySize  == 0 || mySize == 1)
	{
		return 0;
	}

	int h = mySize - 1;
	int l = 0;
	int m = (l + h)/2;

	while(l <= h)
	{
		
		if (l == h)
		{
			cout << "Peak element idx is " << l << endl;
			return l;
		}
		m = (l+h)/2;
		//cout << "low" << myArr[l] << " med" << myArr[m] << " high" << myArr[h] << endl;
		if (myArr[m] > myArr[m-1] && myArr[m] > myArr[m+1])
		{
			cout << "Peak element is at idx" << m << endl;
			return m;
		}
		if(myArr[m] > myArr[m-1])
		{
			//cout << "peak in upper half" << endl;
			l = m+1;
			cout << " l:" << l << endl;
		}
		else
		{
			//cout << "peak in lower half" << endl;
			h = m-1;
			cout << " h: " << h << endl; 
		}
	}
	return 0;
}


bool binarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
	if (start_Idx > end_Idx)
	{
		cout << "err" << endl;
		return false;
	}
	if (start_Idx == end_Idx)
	{
		if (Arr[0] == element)
		{
			cout << "binarySearch found element at idx 0" << endl;
			return true;
		}
		else
		{
			cout << "binarySearch Not found" << endl;
			return false;
		}	
	}
	int l = start_Idx;
	int h = end_Idx;
	int m = 0;

	while (l <= h)
	{
		m = (l+h)/2;
		//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
		
		if (Arr[m] == element)
		{
			cout << "binarySearch Found element at idx" << m << endl; 
			return true; 
		}
		else if (Arr[m] > element)
		{
			//cout << "binarySearch Element in lower half" << endl;
			h = m-1;
		}
		else
		{
			//cout << "binarySearch Element in upper half" << endl;
			l = m+1;
		}
	}
	cout << "binarySearch Element not found" << endl; 	
	return false;
}

bool invertedBinarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
//Binary search for a decreasing array. E.g. {9, 8, 7, 6}
	if (start_Idx > end_Idx)
	{
		cout << "err" << endl;
		return false;
	}
	if (start_Idx == end_Idx)
	{
		if (Arr[0] == element)
		{
			cout << "invertedBinarySearch found element at idx 0" << endl;
			return true;
		}
		else
		{
			cout << "invertedBinarySearch Not found" << endl;
			return false;
		}	
	}
	int l = start_Idx;
	int h = end_Idx;
	int m = 0;

	while (l <= h)
	{
		m = (l+h)/2;
		//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
		
		if (Arr[m] == element)
		{
			cout << "invertedBinarySearch Found element at idx" << m << endl; 
			return true; 
		}
		else if (Arr[m] > element)
		{
			//cout << "binarySearch Element in lower half" << endl;
			l= m+1;
		}
		else
		{
			//cout << "binarySearch Element in upper half" << endl;
			h = m-1;
		}
	}
	cout << "invertedBinarySearch Element not found" << endl; 	
	return false;
}

As other have already suggested.
1. Do a binary search to find the peak or largest element. O(log n) operation
2. Split the original array at the peak element, say at element p
3. Do a binary search on the lower array. O(log p)
4. Do a binary search on the higher array. O(log n-p)

Complexity = O(log n) + O(log p) + O(log n-p) ~ O(log n).
I'm including some code.

Nice approach. However, I don't think the time calculation is correct since the max element will not always be in the center.

It will happen whenever you try to dereference a pointer that is set to NULL.
In stdio.h, NULL is defined as zero
so if you have a pointer which is set to NULL, it will point to the memory location 0, which is reserved by the OS for its own use.
Therefore you would get this error.

class node 
{
//each node has 3 childers
//to indicate leaf node, its first child is NULL
public:
	node();
	node(int _data);
	int data;
	node * childern[3];
};

bool isSumProp(node * input_node)
{
	node * parent = input_node;
	//check if leaf node 
	if(parent->childern[0] == NULL)
	{
		cout << "tis but a leaf node" << endl;
	}

	int sum_P = parent->data;
	cout << "Parent sum: " << sum_P << endl;
	int sum_C = 0;
	int i = 0;

	node * child = parent->childern[i];

	while( (i < 3) && (sum_P > sum_C) )
	{
		sum_C += child->data;
		if(sum_P == sum_C)
		{
			cout << "This node follows Sum Property "<< endl;
			return true;
		}
		i++;
		child = parent->childern[i];
	}
	cout << "This node DOES NOT follows Sum Property "<< endl;
	return false;

}

bool findSumProp(node *current)
{
	if(current->childern[0] == NULL)
	{
		cout << "Leaf node" << endl;
		return false;
	}
	node *curr = current;
	if( !isSumProp(curr) )
	{
		cout << "array does not follow Sum Property" << endl;
		return false;
	}
	findSumProp(curr->childern[0]);
	findSumProp(curr->childern[1]);
	findSumProp(curr->childern[2]);
	return true;
}

For every node N, you will check if the sum of its children. If the sum matches the parent, this node follows the Sum Property. Apply a recursive solution on all its children. Where ever we find that the Sum Property is not followed, we checking and return false.

Can you clarify on the question.
What does intersection of Linked Lists mean? Two or more common elements in the same order?

Lazy alert! The above code still needs to handle some special cases (array length 0 or 1 or 2 and maybe array with all 1's), I was too lazy to do it :D