Thinknear Phone Interview Fulltime 09.15.2014

When I's applying summer intern last, I unintended applied a Thinknear full time position. It's really embarrassed. However it seems that they had record my information because a very nice HR got in touch with me and scheduled a phone interview.

Then I begun to have a look at this company and found that it is a really amazing company. It has a really amazing idea about the the usage of location information. By analysis customers daily data besides with geo location, they perform a refined ads method and do the ads recommendation. Based on such background, it's obvious that Thinknear is a latest technical company related to big data and the cloud. So it is unexpected fit for me.

The phone interview was pretty common. First ask me to talk about what I did in last internship. Then ask some details about how do I read paper to find the idea.
Then ask what's your most interested project and you want to continue in the further. I said is the database project. Then he asked why.

After this we built up a shared google doc and did a algorithm problem. It's a pretty common one. Check if a binary tree is a binary search tree. And asked about the time complexity.

After that it's time to ask him questions and then finished.
Quite great company and quite short an interview.


----------------------------------------------------------------------
UPDATED three days later
----------------------------------------------------------------------
I always thought that although the algorithm for binary search tree check works, it looks really ugly. When I trying to figure out a elegant way, I suddenly realized that my method was wrong. Here is my code.

class Node {

Node *left, *right;

int value;

}

bool is_bst(Node *root) {

vector<int> v;

preorder_traverse(root,v);

for(int i=1;i<v.size();i++)

if(!v[i-1]<=v[i])

return false;

return true;

}

void preorder_traverse( Node*p,vector<int>&v){

if(p==NULL)

return ;

preorder_traverse(p->left);

v.push_back(p->val);

preorder_traverse(p->right);

} 

After wrote down the code, I asked the interviewer that if it is possible to have duplicated items and it it is , is should be placed at left child or right child. The interviewer said there could be and would be placed at left child. So I updated the code like this "if(!v[i-1]<=v[i])". However it was totally wrong.
I think one solution could work.

Let the function bool is_bst ( Node *p, int min, bool min_is_equal, int max, bool max_is_equal) denote that if the subtree whose the root is p is a binary search tree that all the elements in the subtree are bigger than min and smaller then max. The min_is_equal and max_is_equal denote that if it could be equal. Do the check function recursively and update the parameter would work.