CareerCup

Hi ninhnnsoc,

It indeed is an interesting problem. I also doubt that this problem could be solved in polynomial time.

The guided BFS approach is great. I think it would not miss any optimal solution. I cannot prove it but I am somehow sure that it would work perfectly fine.

First of all I apologize for being late. I was out for a while.

We will use a stack for DFS instead of recursion. You can find out more about iterative DFS at Wikipedia.
Whenever we reach the target node, we stop the DFS right there, and start popping nodes out of a stack and construct the path, like in the code below:

// This code is for the stage after halting the DFS
// cur is the current node. It is the target node at the beginning
// DFSStack is our stack
// ans is the path

node * cur = DFSStack.top();
DFSStack.pop();

list <node *> ans;
ans.push_front(cur);

node *tmp;
while(!(DFSStack.empty()))
{
	tmp = DFSStack.top();
	DFSStack.pop();
	if(tmp->left == cur || tmp->right == cur)
	{
		cur = tmp;
		ans.push_front(cur);
	}
}

By randomized I mean to visit children of any node in a random order, in order to have an acceptable performance for any test case. That is, when a mean adversary queries the last leaf every time, on average, we will be searching half of the tree. By doing this, our space usage will decrease a bit for the worst case :-)

Nice one!
However, it would be better to check validity of any swap before adding to queues, because a bad swap would not be a part of a shortest path. Doing this would also give us a much smaller search space, hence a better time complexity.

We can also use A* instead of BFS to solve this a bit faster.

We can pick every n elements of the list, reverse it, and then link the tail of the previous part to the head of the current part. Note that the interviewer would probably want you to do it in-place.

This is my implementation in c++:

using namespace std;

struct node{
	node *next;
	int data;
};

void reverseList(int N, node * &head)
{
	node *prvTail = NULL;
	node *cur, *prv, *nxt, *ptr1 = head;
	while (1)
	{
		int cnt = 0;
		cur = ptr1;
		prv = NULL;

		for (cnt = 0; cnt < N && ptr1 != NULL; cnt++)
		{
			prv = ptr1;
			ptr1 = ptr1->next;
		}


		if (prvTail == NULL)
			head = (cnt<N ? cur:prv);
		else
			prvTail->next = (cnt<N ? cur:prv);
		
		if (cnt < N)
			break;

		prvTail = cur;

		
		while (cur != ptr1)
		{
			nxt = cur->next;
			cur->next = prv;
			prv = cur;
			cur = nxt;
		}
	}
}

Time complexity is O(n). Additional space used is O(1)

Client program to test validity:

void addToHead(node * &head, int val)
{
	node *cur = new node;
	cur->data = val;
	cur->next = head;
	head = cur;
}

void printList(node *head)
{
	node *cur = head;
	while (cur != NULL)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}

int main()
{
	int tmp, sz, n;
	while (cin >> sz >> n)
	{
		node *head = NULL;
		while (sz--)
		{
			cin >> tmp;
			addToHead(head, tmp);
		}
		printList(head);
		reverseList(n, head);
		printList(head);
	}
}

Inversion counting does not give the correct answer. Correct answer is 3 for the example in the statement; however, there are 4 inversions.

Ouch! You're right :-( We can do something, though. When we have computed the hash values for the pattern, discard the space used by it and replace it with the list I was talking about, we can even implement the list on the char array previously used by P. I do not really get it, even the KMP automaton would need O(P) space. How can we not use the space used previously by P?

If it was not a BST, a randomized iterative DFS would do well.

What kind of tree it was? It was not a BST, was it?

First we will calculate hash value of the pattern and keep it in a variable. Let L be the length of the pattern we are trying to find in the stream. First we will get the first L characters of the stream and store it in a linked list. Then we will take the hash value of those characters and compare it to the hash value of the pattern to find if we have a match. After that we will erase the head of the linked list and update the hash value. Then we will add the next character of the stream to the end of the list and update the hash value. Thereafter, we will compare those two hash values. We will continue this process until we reach the end of the stream.
By triple hashing I mean that we will devise three different hash functions. At any point, if all three hash values are equal to those of the pattern, we can somehow be sure that we have a match.

Topcoder tutorial explains much more and much better than my explanation. You can find how the hash values are calculated in detail. Every other thing that I said is explained thoroughly in the article.

Unfortunately, the site doesn't allow copying links in the comments, google "Rabin-Karp string matching topcoder tutorial"

Take a look at topcoder tutorial on Rabin-Karp string matching, for now.
I will explain what I mean in the next few hours ;-)

What about hashing? I think a triple hash would do the job.

No deadlocks in this case. During execution of both statements, the other object is neither locked, nor required in the statement.
However this could be DEADLY:

void test(final Object o1, final Object o2) { 
	… 
	synchronized(o1) { …  

	synchronized(o2) { … } 

	}

}

Change those [whatever]/2's with [whatever]>>1 :-P

EDIT: Nice solution BTW :-)

***EDIT: The OP HAS actually mentioned it should be a BST. Read the statement carefully. ***

Come on guys! It is trivial to construct a binary tree with only one traversal given to us. We can simply return a chain. No big deal! The OP certainly has forgotten to mention it is a BST. If you take a look at the examples, you'd know it anyway. Try to solve it for a BST. It actually is fun to try to find a way to do it in O(n)

Good idea to store the matrix as bits.
It is of course possible. During execution, you'll only need to store the length of the longest sequence and the length of the sequence for every column leading to the current row and not discard them. For the matrix, you can bring in one block at a time and update your variables and discard that block because you do not need it anymore. You'll need ~20k memory for the variables. The remaining memory could be used for bringing in the blocks.

Exactly! However, do not forget O(nlogn) normal sorting that should be done before calling this function. By the way, could you please correct the part that says A[i] = X[temp]?

Hey guys, the correct solution is the original one, not the one in the comments and it is indeed O(n). I sincerely apologize to Levitan for posting a misleading comment under his original post. I screwed up terribly. :-( :-( Please please up-vote the original post so the solution gets to be seen. It is a super elegant algorithm and it does not even modify array A.

Thanks!

We can do something like what oOZz has done. Putting permuted X in array A and destroying A as we go forward. Also check Levitan's original code(not the one in comments) to see how he does not even modify A and solve this. It is super cool.

First of all, I'm really sorry for bad variable naming. Always had problems with that :-D

Let's explain those ugly variables:

1. zerocount(i,j): the number of zeroes in row "i" before and including column "j"

2. oneline(i,j): the length of the line formed in column j by ones including and immediately above the (i, j) cell. In the example below oneline(2,2) = 2, oneline(1,2) = 1, oneline(4,1) = 2, oneline(2,1) = 0, and oneline(1,4) = 1
1 1
0 1
1 0
1 1

3. fulllines(k): the number of full(all ones between column i and j) lines before and including k-th row. This variable is changed for every i and j.

4. closestzero: this variable holds the index of the nearest row above the current row that has a zero in it.

Now what happens in the for(k=1 -> n) loop:
We first check to see if the current row contains all ones between column i and j. We do this using our zerocnt table. If the number of zeroes in row k before column j is not equal to the number of zeroes before column i we know that we have a zero. We set closestzero to the current row index and go to the next row. If we have all ones in the current row, we know that it is a candidate for the bottom edge of a rectangle. We also know that any valid rectangle with this row as its edge should have a top edge that is above closestzero(so it encloses at least a zero). Another observation is that the right and the left edge can have a length of at most the minimum of two lines that extend upwards from mtrx(k,i) and mtrx(k,j). We have information about those two lines in the variable oneline. Now that we know the upper bound and the lower bound for the index of the top edge, we can simply calculate the number of full lines between those two bounds and add to our answer.

If still something is ambiguous, I'd be glad to discuss further.

Nice question! :-)

I have a solution with O(n) running time for this. We are going to traverse the array from the end. The idea is to maintain a collection of legal sub-trees to enter and to find a fit for the current element in those sub-trees. Note that, in the postorder traversal, we are always sure that all nodes in the left sub-tree of a given node appear before all nodes in the right sub-tree of that node. Knowing this, we can conclude that all sub-trees in our collection that are to the right of the current fit (for the current element), all become illegal and should be discarded. This observation tells us what data structure we should be using, and that DS is stack. The structure for the sub-trees is an implementation detail and you could get a sense of it in the following code.

My C++ implementation:

#include <iostream>
#include <stack>

using namespace std;

const int INF = (-1) ^ (1 << 31);

class TreeNode{
private:
	int data;
	TreeNode *left, *right, *par;
public:
	TreeNode()
		:left(NULL), right(NULL), par(NULL) { }
	TreeNode(TreeNode *prnt, int val)
		:data(val), left(NULL), right(NULL), par(prnt)
	{
		if (prnt == NULL)
			return;

		if (data < prnt->data)
			prnt->left = this;

		else
			prnt->right = this;
	}
	int getVal()		{ return this->data; }
	TreeNode* getRight(){ return this->right; }
	TreeNode* getLeft()	{ return this->left; }
	TreeNode* getPar()	{ return this->par; }
};

struct StackElem{
	int LB, RB;
	TreeNode *par;
	StackElem(int l, int r, TreeNode *p)
		:LB(l), RB(r), par(p){ }
};

bool fits(int b, int a, int c)
{
	return (b >= a && b <= c);
}

pair <bool, TreeNode*> solve(int *ary, int n)
{
	if (!n)
		return make_pair(true,(TreeNode *) NULL);

	TreeNode* root = new TreeNode(NULL, ary[n - 1]);

	stack <StackElem *> stk;

	stk.push(new StackElem(-INF, ary[n - 1], root));
	stk.push(new StackElem(ary[n - 1], INF, root));

	for (int i = n - 2; i >= 0; i--)
	{
		while (true)
		{
			StackElem *cur = stk.top();
			stk.pop();

			if (cur->RB < ary[i])
				return make_pair(false,(TreeNode *) NULL);

			if (fits(ary[i], cur->LB, cur->RB))
			{
				TreeNode *newNode = new TreeNode(cur->par, ary[i]);
				stk.push(new StackElem(cur->LB, ary[i], newNode));
				stk.push(new StackElem(ary[i], cur->RB, newNode));
				break;
			}
		}
	}

	return make_pair(true, root);
}

Beautiful!

Nice one!

My initial idea is to keep a counter for every column. However, this counters will utilize 5000*4 = 20 KB of main memory and we will be left with only 44 KB of memory. This means we would be able to process only two rows at a time. Although this would seem inefficient, I am not sure we could do much better. :-(

Hey buddy, I think you have misunderstood the problem. The answer is also incorrect for the given example.

Nice problem!

We have a number different approaches for solving this. I've assumed n and m to be equal for the sake of an easier analysis. Inequality of n and m has no effect on the validity of the solutions.

One is the naive approach, which picks two cells at a time and checks if those two cells can be upper left and bottom right cells of a valid rectangle. This solution has a time complexity of O(n^6).

Another approach is a dynamic programming approach. In this approach we first pre-process to calculate for every cell mx(i,j) the number of zeroes in the rectangle defined by (1,1) to (i,j). We do this with the simple formula below using the principle of inclusion and exclusion:

zeroes(i,j) = zeroes(i-1,j) + zeroes(i,j-1) - zeroes(i-1,j-1)

After that for every two cells in the matrix, we first check if those two cells define boundary of a rectangle. If they do so, we check if there is zero in between using the information we obtained previously. This approach has a running time of O(n^5).

We can do better, however. We first, pre-process the matrix to obtain the matrix of the number of zeroes like the previous approach. We have an additional pre-processing step here. We calculate for every cell that has a one in it, the number of consecutive ones immediately to the right, left, up, and down of that cell. After that for every two cell A & B we check if they define a valid boundary using the immediate ones information found previously. If they do we check if they enclose a zero similar to the previous solution. This approach runs in O(n^4).

We STILL can do better. This solution is a bit complex and my explanation of what goes in my head may not be comprehensive enough. :-)
We have two pre-processing steps. In the first step, we calculate the number of consecutive ones above every cell leading to that cell. The other pre-processing step is calculating for every cell mx(i,j), the number of zeroes in row i until column j. After that for we do the following operations on every two column i and j. We go forward one row, k, at a time and count the number of valid rectangles that have mx(k,i)---mx(k,j) as their lower edge. Feel free to check my code to get a feeling of how it is calculated. I'll be more than happy to discuss that. :-) This solution has cubic running time, and I cannot think of a better one.

My C++ implementation for the O(n^3) solution:

#include <iostream>
#include <algorithm>

using namespace std;

int zerocnt[1010][1010], oneline[1010][1010], fulllines[1010], mtrx[1010][1010];

int solve(int **mx, int n, int m)
{
	for (int i = 0; i<n; i++)
	{
		mtrx[i][0] = 0;
		oneline[i][0] = 0;
		zerocnt[i][0] = 0;
	}
	for (int j = 0; j<m; j++)
	{
		mtrx[0][j] = 0;
		oneline[0][j] = 0;
		zerocnt[0][j] = 0;
	}
	for (int i = 0; i<n; i++)
	for (int j = 0; j<m; j++)
	{
		mtrx[i + 1][j + 1] = mx[i][j];
		oneline[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 1 ? oneline[i][j + 1] + 1 : 0);
		zerocnt[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 0 ? 1 : 0) + zerocnt[i + 1][j];
	}

	int ans = 0;

	for (int i = 1; i <= m - 2; i++)
	for (int j = i + 2; j <= m; j++)
	{
		int closestzero = -1;
		fulllines[0] = 0;
		for (int k = 1; k <= n; k++)
		{
			fulllines[k] = fulllines[k - 1];
			if (zerocnt[k][j] != zerocnt[k][i])
			{
				closestzero = k;
				continue;
			}

			++fulllines[k];

			int shortline = min(oneline[k][i], oneline[k][j]);

			if (closestzero > (k - shortline) + 1)
				ans += fulllines[closestzero] - fulllines[(k - shortline)];

		}
	}

	return ans;
}

This does the trick in your code:

// make sure that Arr[wL] and Arr[wR] are positive.

Nice one!
Couldn't find a bad test case for the code.

Great job! That was beautiful :-)

Another implementation in C++. Same idea as uuuouou.

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

using namespace std;

string strRep[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven",
"twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "ninteen" };

string lessThanaHundred[] = {"", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninenty" };

string getStrRep(long long x)
{
	if (x < 20ll)
		return (x?strRep[x]:"");
	if (x < 100ll)
		return (lessThanaHundred[x / 10] + (x % 10 ? "-"+strRep[x % 10] : ""));
	x /= 1000;
	switch (x){
	case 1:
		return "";
	case 1000:
		return " thousand";
	case 1000000:
		return " million";
	case 1000000000:
		return " billion";
	default:
		return " thrillion";
	}
}

string solve(long long ipt)
{
	if (ipt == 0)
		return "zero";
	list <string> parts;
	long long curMod = 1000;
	while (curMod / 1000ll <=ipt)
	{
		long long tmp = ipt % curMod;
		tmp /= (curMod / 1000ll);
		string curPart = "";
		if (!tmp)
		{
			curMod *= 1000ll;
			continue;
		}

		if (tmp >= 100)
		{
			curPart += getStrRep(tmp / 100) + " hundred";
			if (tmp % 100)
				curPart += " and ";
		}
		curPart += getStrRep(tmp % 100);
		curPart += getStrRep(curMod);
		parts.push_front(curPart);
		curMod *= 1000ll;
	}
	string ans = "";
	for (auto y : parts)
		ans += y + " ";
	ans.pop_back();
	return ans;
}

int main()
{
	long long ipt;
	while (cin >> ipt)
		cout << solve(ipt) << endl;
}

Nice code! Have a suggestion, though. Add long long support to be able to process the example provided by the OP.

That two-pointer idea is superb. Thanks for that.

Note that this problem is output-sensitive, that is if all elements are equal to 0 we cannot do better than O(n-cubed). Therefore, the algorithm's running time is max( O(n-squared) , O(K) ) where K denotes the output size.

A solution with quadratic running time.

1. Put negative of every number in a hash table with its index.
2. For every combination of two elements i and j (j>i) search for their sum in the hash table and print out i, j, and any index that is greater than j for their sum in the hash table.

A C++11 solution using STL vector and unordered_map (that is our hash table).

#include <iostream>
#include <unordered_map>
#include <vector>
#include <stdio.h>

using namespace std;

void solve(int *ary, int n)
{
	unordered_map <int, vector<int> > hashtable(10000);
	vector <int> tmp;
	tmp.push_back(0);
	for (int i = 0; i < n; i++)
	{
		auto x = hashtable.find(-1 * ary[i]);
		if (x != hashtable.end())
			x->second.push_back(i);
		else
		{
			tmp[0] = i;
			hashtable[-1 * ary[i]] = tmp;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			auto x = hashtable.find(ary[i] + ary[j]);
			if (x != hashtable.end())
			{
				for (auto y : x->second)
				{
					if (y>j)
						printf("%d: %d , %d: %d , %d: %d\n", i, ary[i], j, ary[j], y, ary[y]);
				}
			}
		}
	}
	
}

Love the way that auto does magic in C++11.

Correct solution! However we can have an O(n*n) solution using a hash table.

Nice!

However, we should probably ask the interviewer what is the definition of the "next nearest" here. Is it the next lucky number that is greater than the given number? Or it is the next lucky number that is greater than or equal to that number.

What if num = 8?

Great question.

No idea what to do, then :-D
Sometimes it may not even have an answer. For instance: array = {1,1} and symbols = "<"

It is O(n); however, we should first sort the array normally and then pass it to this method. So, overall, it is O(nlogn).

Thanks for the new code. :-)

I believe this one is correct.

However, the algorithm should not use any additional arrays, so we should do something about array b. The good news is, we can do what the array b does using the original array a.

Cheers!

Great job Levitan. I apologize for deleting the comment. I was constantly mixing things when trying test cases and finally got completely lost. After that, concluded that, I'd better not talk as I was starting to talk nonsense :-D
Nevertheless, we now have a superb algorithm for each of the two cases that you mentioned.
Thanks buddy!

What does it mean "just one bit extra"? Does that mean we are not allowed to iterate and not even use a counter?

Note that, this works if all numbers are distinct.

We cannot do better than O(nlogn), because if all symbols are '<', it becomes a normal sort.

Here is my solution:

1. Sort the array. 
2. After that, maintain two pointers on the array; one pointing to the first element, and the other pointing to the last one. 
3. Iterate on n-1 symbols.
3.a. If the current symbol is '<', then, add the element that the first pointer points to, to the answer and increment the first pointer.
3.b. Otherwise, add the element pointed by the second pointer to the answer and decrement the second pointer.
4. Add the remaining element (both pointers are pointing to it) to the answer

A C++ implementation using sort in STL:

#include <iostream>
#include <algorithm>

using namespace std;

int *solve(int *ary, int n, char* symbols)
{
	sort(ary, ary + n);

	int *ans = new int[n];

	int ptr1 = 0, ptr2 = n-1;

	for (int i = 0; i < n-1; ++i)
	{
		if (symbols[i] == '<')
			ans[i] = ary[ptr1++];

		else
			ans[i] = ary[ptr2--];
	}

	ans[n - 1] = ary[ptr1];

	return ans;
}

Thanks hulk for posting this problem. It refreshes some discrete math skills, which is great!

So close to the correct answer. Use the comment above as a guide to make it uniform.
Hint: An infinite loop might be needed.

Not uniform.
The ways that we can get a 0: (0, 0) , (3, 4) , (4, 3)
The ways that we can get a 4: (0, 4) , (4, 0) , (1, 3) , (3, 1) , (2, 2)

Well, we can count the number of the ways that we can obtain a given value in the range (0,6). For example, let's count the number of possible ways of obtaining 0 and 1.

For 0 we have: 1st rand == 0 and ( 2nd rand == 0 or 2 or 4 ) so we can make a 0 in three ways.

For 1 we have: [ 1st rand == 0 and ( 2nd rand == 1 or 3 ) ] + [ 1st rand == 1 and ( 2nd rand == 0 or 2 or 4 ) ] so there are five possible ways to get a 1.

That's why :-P

To anyone who knows the exact specifications of the problem:
Are we allowed to modify contents of the array A?
Thanks :-)

This would not work unfortunately. Consider the following test case:

A = {2, 1, 3}
X = {1, 2, 3}

sort(X) => X = {1, 2, 3}
first iteration of the for-loop: X = {2, 1, 3}
second iteration: X = {1, 2, 3}
third iteration: X = {1, 2, 3}

Not uniform.

Nice explanation.