iroodaz
BAN USERFirst 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 :)
 iroodaz May 14, 2014Nice 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 inplace.
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);
}
}

iroodaz
May 14, 2014 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?
 iroodaz May 02, 2014First 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 "RabinKarp string matching topcoder tutorial"
***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.
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 upvote 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!
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 kth 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 subtrees to enter and to find a fit for the current element in those subtrees. Note that, in the postorder traversal, we are always sure that all nodes in the left subtree of a given node appear before all nodes in the right subtree of that node. Knowing this, we can conclude that all subtrees 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 subtrees 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);
}

iroodaz
April 22, 2014 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. :(
 iroodaz April 22, 2014Nice 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 preprocess 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(i1,j) + zeroes(i,j1)  zeroes(i1,j1)
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, preprocess the matrix to obtain the matrix of the number of zeroes like the previous approach. We have an additional preprocessing 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 preprocessing steps. In the first step, we calculate the number of consecutive ones above every cell leading to that cell. The other preprocessing 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;
}

iroodaz
April 21, 2014 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;
}

iroodaz
April 19, 2014 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.
 iroodaz April 19, 2014Great 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!
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 n1 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 = n1;
for (int i = 0; i < n1; ++i)
{
if (symbols[i] == '<')
ans[i] = ary[ptr1++];
else
ans[i] = ary[ptr2];
}
ans[n  1] = ary[ptr1];
return ans;
}

iroodaz
April 18, 2014 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
Hi ninhnnsoc,
 iroodaz May 18, 2014It 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.