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 = j-1
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;
}
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;
}
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;
}
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;
}
}
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;
}
}
}
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 = ind-k
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)
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
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
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;
}
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));
}
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;
}
}
}
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
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;
}
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;
}
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 in-place (It is possible but the implementation is very hard), Quick sort can be done in-place 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)+(k-1-p));
}
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<length-k+1; ++i){
for(int j=0; j<width-k+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;
}
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[i-1] +zero[i-2];
one[i] = one[i-1] + one[i-2];
}
printf("zero: %d, one: %d\n", zero[n], one[n]);
delete [] zero;
delete [] one;
}
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
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;
}
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[stop-i];
str[i+stop] = temp;
}
}
void reverseSentence(char* str, int size)
{
reverse(str, 0, size-1);
int start = 0;
int stop = 0; // doesn't matter actually
for(int i=0; i<size; ++i){
if(str[i] == ' '){
stop = i-1;
reverse(str, start, stop);
start = i+1;
}
}
reverse(str, start, size-1);
}
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;
}
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;
}
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
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, 2014
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