hiuhchan
BAN USER 0of 0 votes
AnswersGive a tree (any tree, can be a binary. I told the interviewer that I assume it is binary tree and he said that is fine). Print the tree content on the screen one tree level per line
 hiuhchan in United States
i.e.
if a tree is like this:
a
/ \
b c
/ /
e f
The output would be
a
bc
ef
Too bad, I was only able to make it print on one line instead of separate line. Until after the interview is over. Then I figure the final answer. Report Duplicate  Flag  PURGE
Cloudera SDET Algorithm Data Structures
Why is facebook ask such easy question? Just do inorder tree traversal and that is, everytime you traversal to it's own node, put that content into some data structure. Doesn't matter what it is. the data structure can be array, stack, queue. Then check the content in the data structure. For example, for stack, check and make sure every time you pop something from the stack, the next item you pop has to be less than or equal to the previous item it was pop. That it all.
 hiuhchan September 30, 2015void SetToInit(int * a, int i, int j, int n, int init){
int len = 1;
int k = j;
int front=j, end=j;
while (k < n){
if(a[i][k] == ‘X’)
a[i][k++] = init;
else{
end = k
break;
}
}
k = j1
while(k >=0){
if(a[i][k] == ‘X’)
a[i][k—] = init;
else{
front = k
break;
}
}
if(i + 1 < n){
for(int m= front, m <=end; ++m)
SetToInit(a, i+1, m, n, init);
}
}
int numberOfIsland(int* a, int n)
{
int init=1;
UnionFind uf(n*n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if (a[i][j] == ‘X’){
SetToInit(int *a, i, j, n, init);
init++;
}
}
}
return init;
}

hiuhchan
September 20, 2015 bool IsChar(char input){
if (input >= ‘a’ && input <= ‘z’)
return true;
else if (input >= ‘A’ && input <= ‘Z’)
return true;
else
return false;
}
bool Palindrome(char * input){
int size = 0;
char *tmp = input;
while(*tmp != ‘\0’){
size++;
tmp++;
}
int front = 0;
int back = size  1;
while (front < back){
while( !IsChar(input[front])){
front ++;
}
while( !IsChar(input[back])){
back —;
}
if (tolower(input[front]) == tolower( input[back]) ){
front ++;
back —;
}
else
return false;
}
return true;
}

hiuhchan
September 20, 2015 Untest. But I believe it is correct, (but no error handling)
bool isMatch(char* str1, char* str2)
{
while ( *str !=‘\0’ && str != ‘\0’ ){
if( *str == *str2 && *(str+1) != ‘*’ && *(str2+1) != ‘*’){
str++;
str2++;
}
else if ( *str == *str2 && *(str+1) == ‘*’ ){
while(*str2 == *str){
++str2;
}
str += 2;
}
else if ( *str == *str2 && *(str2+1) == ‘*’ ){
while(*str2 == *str){
++str;
}
str2 += 2;
}
else if (*str != *str2 && *(str+1) == ‘*’ )
str++;
else if (*str != *str2 && *(str2+1) == ‘*’ )
str2++;
else
return false;
}
if (*str != ‘\0’  *str2 != ‘\0’)
return false;
else
return true;
}

hiuhchan
September 20, 2015 removedup(char* input)
{
int a[256];
memset(a, 0, 256);
char*tmp = input;
int size = 0;
while(*tmp != ‘\0’){
a[ (int) (*tmp) ]++;
size++;
++tmp;
}
output = new char[size];
int count
while(*input != ‘\0’){
if ( a[ (int)(*input) ] > 1)
a[ (int)(*input) ] = 1;
else if (a[ (int)(*input) ] == 1){
a[ (int)(*input) ] = 0;
output[count++] = *input;
}
++input;
}
}

hiuhchan
September 20, 2015 printFirstLast(Node * node)
{
Queue<Node*> queue;
Queue<Node*> queue2;
bool printItem = true;
queue.enqueue(node);
printItem = true;
while( ! queue.IsEmpty() ){
if (queue.Count() == 1)
printItem = true;
Node *tmp = queue.dequeue();
if (printItem ){
Print(tmp);
printItem = true;
}
if ( tmp>left != null)
queue2.enqueue(tmp>left);
if ( tmp>right != null)
queue2.enqueue(tmp>right);
if(queue.IsEmpty){
while( !queue2.IsEmpty())
queue.enqueue( queue2.dequeue() );
printItem = true;
}
}
}

hiuhchan
September 20, 2015 use BFS. That is. As we put node into queue, we count the number of items. Once we remove items from queue and inserts it's child, we are reaching the next level. first level we have 1 node, second level, 2, and then 4 and so on. There should be 2^i items at each level where i is the ith level.
 hiuhchan April 29, 2015This problem can use CSP to reduce the search space
def CheckQueue(Q, ind):
if ind >= len(Q):
return True
for m in range(len(Q)):
Q[ind]=m
needCheck = True
if ind > 0:
for k in xrange(0, ind):
if Q[k] == Q[ind]:
needCheck = False
break
diff = indk
if diff < 0:
diff = diff
if Q[k]+diff == Q[ind]:
needCheck = False
break
if Q[k]diff == Q[ind]:
needCheck = False
break
if needCheck and CheckQueue(Q, ind+1):
return True
return False
N = 8
Q = [0 for i in range(0,N)]
CheckQueue(Q, 0)

hiuhchan
April 10, 2015 def assignMeetingToRoom(meeting):
list = [meeting[0]]
meeting.remove(meeting[0])
for i in meeting:
lasttime = list[len(list)1][0]
if i[1] >= lasttime:
list.append(i)
meeting.remove(i)
def NumberOfMeetingRoom(meeting):
# assuming that meeting is a list that contains a list of meeting
# where each meeting contains a list of two item, namely, ending time
# and starting time
# i.e. [[e1, s1], [e2, s2], [e3, s3]]
meeting.sort()
room = 0
while len(meeting) != 0:
assignMeetingToRoom(meeting)
room += 1
return room

hiuhchan
March 25, 2015 since time is not defined in this question, I just use integer to represent time. this should be easily convert to any time representation data type.
def IsInrange(value, range):
if value > range[1] and value < range[0]:
return True
else:
return False
def IsMeetingConflict(schedule):
#schedule = [[s1, e1], [s2, e2], [s3, e3]]
for i in schedule:
for j in schedule:
if i != j:
if not IsInrange(i[0], j) or not IsInrange(i[1], j):
return False
return True

hiuhchan
March 25, 2015 bool IsBinarySearchTree(node* n)
{
if (n == null)
return True;
if (n>left == null and n>right == null)
return True;
bool checkleft = True, checkright = True;
if (n>left != null)
if (n>content < n>left>content)
return False;
else
checkleft = IsBinarySearchTree(n>left);
if (n>right != null)
if (n>content > n>lright>content)
return False;
else
checkright = IsBinarySearchTree(n>right);
return (checkleft == checkright == True)?True:False;
}

hiuhchan
March 20, 2015 struct Point{
int x;
int y;
}Point;
Point* m_x_n_Grid(int * input, int length, int width, int test, Point pos)
{
int x = pos.x;
int y = pos.y;
if (*(input+(x*width) + y) == test){
return new Point(x, y);
}
else{
Point * p1, p2;
if (y + 1 >= length)
return null;
else if(*(input+(x*width) + y+1) > test)
p1 = m_x_n_Grid(input, length, width, test, new Point(x, y+1))
if (x + 1 >= width)
return null;
if (*(input+((x+1)*width) + y) > test)
p2 = m_x_n_Grid(input, length, width, test, new Point(x+1, y))
return (p1 == null)?p2:p1;
}
}
void main()
{
// some initialization for input, length and width of the grid
// plus the input integer
Point *p = m_x_n_Grid(input, length, width, test, new Point(0,0));
}

hiuhchan
March 02, 2015 Assuming that it is binary tree
LinkList* createLinkList(Stact<LinkList* >& s)
{
LinkList* head = null;
while(!s.IsEmpty()){
LinkList* tmp = s.pop();
tmp>next = head;
head = tmp;
}
return head;
}
void createLL(TreeNode * node)
{
Queue<TreeNode *> q;
Stact<LinkList* > s;
int tree_enqueue_count = 0;
int tmp_counter = 0;
q.enqueue(node);
tree_enqueue_count++;
while (!q.IsEmpty()){
TreeNode * tmp = q.dequeue();
if (tmp.left != null){
q.enqueue(tmp.left);
tmp_counter++;
}
if (tmp.right != null){
q.enqueue(tmp.right);
tmp_counter++;
}
LinkList * ll = new LinkList();
ll>content = tmp>content;
s.push(ll);
tree_enqueue_count;
if (tree_enqueue_count == 0){
// Don't know what to do with the head pointer of the linklist. So I just do nothing
createLinkList(&s);
tree_enqueue_count = tmp_counter;
tmp_counter = 0;
}
}
}

hiuhchan
February 27, 2015 I use hash function to solve this problem. Run time, O(n) (BTW, I did not handle the fact that there are two sequences or more with the same length)
a = [1, 2, 100, 100, 100, 3, 4, 5, 7]
hash = {}
for i in a:
if i not in hash:
hash[i] = 1
j = i  1
while j in hash:
hash[j] += 1
j = 1
max = 0
key = 0
for j in hash:
if hash[j] > max:
max = hash[j]
key = j
for k in range(0, hash[key]):
print key + k

hiuhchan
February 26, 2015 This one use recursion. I know I know. just for the fun of it (untested)
node* reverse(node** head)
{
if (head == null  head>next == null)
return head;
node* current = head;
node* rest = head>next;
second = reverse(&rest);
current>next>next = current;
current>next = null;
&head = rest;
return current;
}

hiuhchan
February 25, 2015 Just being lazy, I did not convert upper case to lower case. so something like 'AAa' will not work in my case, but just to present idea.
bool isletter(char a)
{
if (a >= 'a' && a <= 'z')
return true;
else if (a >= 'A' && a <= 'Z')
return true;
else if (a >= '0' && a <= '9')
return true;
else
return false;
}
bool ispalindrome(char* input, int size)
{
int begin = 0;
int end = size  1;
while(begin < end){
while( ! isletter(input[begin]) ){
begin++;
}
while( ! isletter(input[end]) ){
end;
}
if (input[begin] != input[end])
return false;
}
return true;
}

hiuhchan
February 25, 2015 Merge sort always run at O(n log(n)). Quick sort can be O(n^2) in worst case scenario.
Merge sort cannot be done inplace (It is possible but the implementation is very hard), Quick sort can be done inplace a lot easier.
Which one is better? Quick sort, as long as we use randomize algorithm to randomize the quick sort pivot selection so that we can make the worst case runtime of O(n^2) virtually disappear.
yes of course, for example, greedy algorithms. you find the maximum value in the matrix, then search for the maximum possible products that contains that maximum value you just found. But since it is greedy algorithms, the answer may not be the best.
another solution, if you know there are at least one row, or column that contains at least k continuous positive number, you can just skip calculate the cell that contains 0 or negative one.
May not be the best implementation. but it works. Sorry that I am not good at 2D array algorithms.
The idea is basically use a smaller matrix to mask inside a bigger matrix and then get all the products
int getMax(int *input, int k)
{
int product = 999999;
for(int p=0; p<k; ++p){
int prod = 1;
for (int q=0; q<k; ++q){
prod *= *(input+(p*k)+q);
}
product = (prod > product) ? prod : product;
}
for(int p=0; p<k; ++p){
int prod = 1;
for (int q=0; q<k; ++q){
prod *= *(input+(q*k)+p);
}
product = (prod > product) ? prod : product;
}
int prod = 1;
for(int p=0; p<k; ++p){
prod *= *(input+(p*k)+p);
}
product = (prod > product) ? prod : product;
prod = 1;
for(int p=0; p<k; ++p){
prod *= *(input+(p*k)+(k1p));
}
product = (prod > product) ? prod : product;
}
int GetbiggestProduct(int *input, int length, int width, int k)
{
int max = 999999;
int product = 1;
int *test = new int[k*k];
for(int i=0; i<lengthk+1; ++i){
for(int j=0; j<widthk+1; ++j){
for(int s=0; s<k*k; ++s)
*(test+s) = 1;
for(int p=0; p<k; ++p){
for (int q=0; q<k; ++q){
*(test+p*k+q) *= *(input+length*(i+p)+j+q);
}
}
int tmp = getMax(test, k);
max = (tmp>max) ? tmp : max;
}
}
return max;
}
int main()
{
int matrix[] = {1, 2, 0, 1, 4,
3, 1, 2, 4, 6,
0, 2, 3, 1, 4,
1, 3, 2, 0, 7,
2, 1, 3, 2, 9};
cout<<GetbiggestProduct(matrix, 5, 5, 4)<<endl;
}

hiuhchan
February 13, 2015 fib_Zero_And_One_Count(int n){
int *zero = new int[n+1];
int *one = new int[n+1];
zero[0] = 1;
zero[1] = 0;
one[0] = 0;
one[1] = 1;
for(int i = 2; i<=n; ++i){
zero[i] = zero[i1] +zero[i2];
one[i] = one[i1] + one[i2];
}
printf("zero: %d, one: %d\n", zero[n], one[n]);
delete [] zero;
delete [] one;
}

hiuhchan
February 12, 2015 My solution in python in a different approach without sorting.
def PointInLine(line, point):
if point >= line[0] and point <= line[1]:
return True
else:
return False
def OverlapLineHelper(line1, line2):
check1 = PointInLine(line1, line2[0])
check2 = PointInLine(line1, line2[1])
if check1 and check2:
return line1
elif check1:
return [line1[0], line2[1]]
elif check2:
return [line2[0], line1[1]]
else:
return None
def OverlapLine(line1, line2):
line = OverlapLineHelper(line1, line2)
if line == None:
return OverlapLineHelper(line2, line1)
else:
return line
set = [[4,8], [3,5], [1,2], [10,12]]
newset = []
while len(set) != 0:
test = set.pop()
removeset = []
for i, k in enumerate(set):
check = OverlapLine(k, test)
if check != None:
test = check
removeset.append(i)
for i in reversed(removeset):
del set[i]
newset.append(test)
print newset

hiuhchan
February 12, 2015 int max_num_one(int [][] matrix, int row, int col)
{
int maxrow = 0;
int num_one = col;
for(int i=0; i<row;++i){
for (int j = 0; j < col; ++j){
if(matrix[i][j] == 1){
if (j == 0)
return i;
else{
if(j < num_one){
max_row = i;
num_one = j;
}
break;
}
}
}
}
return maxrow;
}

hiuhchan
January 29, 2015 Here is my code. Of course it will not work if I have two white space or more.
void reverse(char* str, int start, int stop)
{
int len = stop  start + 1;
for(int i = 0, i < len/2 + start; ++i)
{
char temp = str[i+start];
str[i+start] = str[stopi];
str[i+stop] = temp;
}
}
void reverseSentence(char* str, int size)
{
reverse(str, 0, size1);
int start = 0;
int stop = 0; // doesn't matter actually
for(int i=0; i<size; ++i){
if(str[i] == ' '){
stop = i1;
reverse(str, start, stop);
start = i+1;
}
}
reverse(str, start, size1);
}

hiuhchan
January 23, 2015 Look like most of you do inorder tree traversal. I guess I do the same
bool BST2List(Node* node, Node** front, Node ** back, Node ** head)
{
if (node == null)
return False;
if (BST2List(node>left, &front, &back, &head)){
back>right = node;
node>left = back;
}
else{
if (head == null)
head = node;
front = node;
node>left = null;
}
if(BST2List(node>right, &front, &back, &head)){
front>left = node;
node>right = front;
}
else{
back = node;
node>right = null;
}
return True;
}

hiuhchan
January 07, 2015 We start by building the double linklist by always getting the minimum of the tree and delete the minimum node in the tree.
Node* GetMinNode(Node** node)
{
if (node == null)
return null;
Node* tmp = node;
if (node>left == null){
node = node>right;
return tmp;
}
while(node>left != null){
tmp = node;
node = node>left;
}
tmp>left = null;
return tmp;
}
Node* BST_to_DLL(Node* tree)
{
Node * head;
head = GetMinNode(&tree);
if (head == null)
return null;
Node * tmp = head;
Node * tmp2;
head>left = null;
tmp2 = GetMinNode(&tree);
while(tmp2 != null){
tmp>right = tmp2;
tmp2>left = tmp;
tmp = tmp2;
tmp2 = GetMinNode(&tree);
}
tmp>right = null;
return head;
}

hiuhchan
January 07, 2015 Assuming that it is binary tree
struct TreeNode{
char content;
TreeNode *left;
TreeNode *right;
}
void printTree(TreeNode* root)
{
Queue<TreeNode*> q, temp_q;
q.enqueue(root);
while(!q.IsEmpty()){
while(!q.IsEmpty()){
TreeNode *node = q.dequeue();
if (node>left != null)
temp_q.enqueue(node>left);
if (node>right != null)
temp_q.enqueue(node>right);
cout<< node>content;
}
cout<<endl;
while(!temp_q.IsEmpty())
q.enqueue(temp_q.dequeue);
}
}
This question is same as the one I was being asked few weeks ago.
careercup . com /question ? id=5169384622391296 (remove the space and paste onto your browser)
def sortChar(str):
output = ''
for u in sorted(str):
output += u
return output
test = ["trees", "bike", "cars", "steer", "arcs"]
long = 0
dict = {}
for i in test:
if len(i) > long:
long = len(i)
tmp = sortChar(i)
if tmp not in dict.keys():
list = [i]
dict[tmp] = list
else:
dict[tmp].append(i)
finallist = []
for i in dict:
finallist.append(dict[i])
print finallist
print long

hiuhchan
December 15, 2014 This is not a very good question because it is not clear. By that I mean the function that gives you all the positions that the horse can reach, it is not clear the cost to a particular position. Is it always going to be 1 or it can be something else? If it is always 1, then all you need to do is use BFS. And once you reach the ending point, you are done. If it give you the associate cost for the reachable position and they are always positive cost, then you can use Dijkstra algorithms. Otherwise, it is going to be too hard for an interview question to think and code. Especially this is only SDE1 position
 hiuhchan December 12, 2014Open Chat in New Window
N order statistic with modified version of Quick sort. Run time O(n).
 hiuhchan November 19, 2015algorithms:
pivot=partition array()
if pivot index is medium
return
else if pivot index is less then medium
recursively call the first half of array before the pivot
else
recursively call the second half of array after the pivot