student
BAN USER 2 Answers Dynamic Programming questions in MS and Amazon interviews
Am preparing for MS and Amazon interviews...
 student July 18, 2012
is anyone having any clue how the questions on dynamic programming are ????
and any good link from where we can study it..
please share it if you have any good source or material...
thanks a tonne... Flag  PURGE  10 Answers Upcoming test and interview for Microsoft and Amazon
hello people...
 student July 02, 2012
i would be having campus interview in a month;s time and Microsoft and Amazon would be the first couple of companies to be visiting .... can some one who has recently attended interview process of any of this company please share your experiecne...
also would like to know what would be the patter of the test and how should we prepare for it...
also is it fully technical or do we need to prepare some aptitude also??/
thanks a lot in advance... please be generous and do share your experience as I guess the topic would be helpful to lot of students as campus interviews in India would be starting in month of august .....
thanks a lot Flag  PURGE
you first need to ask the interviewer what should be the height difference between left subtree and right subtree for tree to be imbalance
(this is just to show the interviewer that you are not directly assuming anything in questions)
here I am assuming that if difference between height of left subtree and right subtree is more than 1 then out tree is imbalanced
i.e.if(abs (leftHeight  rightHeight ) > 1)
return FALSE;
here is the full code
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node* Node;
Node newNode(int data)
{
Node temp = (Node)malloc(sizeof(Node));
temp>data = data;
temp>left = temp>right = NULL;
return temp;
}
void insert(Node *head , int data) //Passing address of node because its data is being editted
{
if(*head == NULL)
*head= newNode(data);
else
{
if(data <= (*head)>data)
insert(&((*head)>left),data);
else
insert(&((*head)>right),data);
}
}
int returnMax(int a, int b)
{
return a>b?a : b;
}
int util_isBalanced(Node head,int *height)
{
if(head == NULL)
{
*height = 0;
return TRUE;
}
int leftHeight,rightHeight=0;
int leftTree,rightTree;
leftTree = util_isBalanced(head>left,&leftHeight);
rightTree = util_isBalanced(head>right,&rightHeight);
if(abs(leftHeightrightHeight) > 1)
return FALSE;
//if left Subtree and right subTree are balanced
if(leftTree == TRUE && rightTree ==TRUE)
{
*height = returnMax(leftHeight,rightHeight)+1;
return TRUE;
}
return FALSE;
}
int isBalanced(Node head)
{
int height = 0;
return util_isBalanced(head,&height);
}
int main()
{
Node head = NULL;
insert(&head,4);
insert(&head,3);
insert(&head,6);
insert(&head,5);
insert(&head,7);
insert(&head,12);
int isBalancedTree = isBalanced(head);
isBalancedTree==TRUE?printf("Balanced") : printf("Not balanced");
return 0;
}

student
July 19, 2012 see here height of the tree would be calculated multiple times for the same set of nodes
so the time complexity become O(n^2)
we need to use the fact that to calculate the height of a tree we are calculating height of subtree and so there should not be need to again calculate height of sub tree which would done in this case when you are doing
balanced_tree(tree>left)&&balanced_tree(tree>right)
1.) travel both the link lists and find out their length... (since after they merge the length would be same from point of merging ....)
so if both the lengths are same then traverse through both the lists one node at a time and go on comparing them....
if lengths are different then calculate the difference abs(length of A  length of B)
 suppose the difference in length is X...
then travel X nodes in the longer linked list first....
and now travel 1 node at a time from both the list .... for shorter list from the starting and for longer list from the point after X nodes...
if the list is merging then you would get the point of merge
Time complexity O(n)
Well I could think of 3 solutions by which we can solve this...
1) Using two loops to traverse the array and count the number of times each digit is
encountered...... Time Complexity O(n^2) Space Complexity O(1)
2) Using hash table
Time ComplexityO(n) Space ComplexityO(n)
3)Sorting the list and then checking the number at position i with i+1 and i+2
Time Complexity O(nlogn) Space Complexity O(1)
i want to know if its possible to solve it in Time complexity O(N) and space complexity O(1)
 student July 17, 2012here first we traverse the array once to find total sum of array....
then we again start from 0th position and start subtracting value from total sum and go on adding it to leftsum and then compare leftsum and total remaining sum
#include<stdio.h>
int equil(int arr[],int size)
{
int i=0,arrsum=0;
int leftsum=0;
for(i=0;i<size;i++)
arrsum+=arr[i];
for(i=0;i<size;i++)
{
arrsum= arr[i];
if(leftsum == arrsum)
return i;
leftsum+=arr[i];
}
return 1;
}
int main()
{
int arr[] = {7, 1, 5, 2, 4, 3, 0};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Equilibrium index is : %d",equil(arr,size));
return 0;
}

student
July 15, 2012 @anonymous : am sure that test would be there ..... about the test pattern I wanted to know type of questions : like last year in our campus there was a coding ques , a design ques and one in which we had to write test cases and another half where there was MCQs....
 student July 11, 2012we need to do %26 but need to take care that 0 has no representation over here....
i.e. when we do % 8 out values are from 0 to 7
but here 0 has no representation ... so every time remainder is 0 we take it as 26 and print 'Z' and subtract 1 from Quotient ....
#include<stdio.h>
#include<math.h>
int main()
{
long long int x = 704;
char *ptr = (char *)malloc(sizeof(char));
// we are skipping any of the decimal points
//from input... i.e. error handling is not there
//right now
int i=0;
while(x > 0)
{
int r = x%26;
x = x/26;
if(r==0)
{
*(ptr+i)='Z';
i++;
x = x1;
}
else
{
*(ptr+i)=(char)r+'A'1;
i++;
}
}
*(ptr+i)='\0';
for(i=i1;i>=0;i)
printf("%c",*(ptr+i));
return 0;
}

student
July 11, 2012 there is no need to put two stacks...
we can do it one stack itself....
what I have done is crated a struct forTraversal where I can mark whether I have visited the node's left or right child...
if left child is not visited then first visit left child and then right child and then print value of node..
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node* Node;
struct forTraversal
{
Node node;
int vleft;
int vright;
};
Node newNode(int data)
{
Node temp = (Node)malloc(sizeof(Node));
temp>data = data;
temp>left = temp>right = NULL;
return temp;
}
void insert(Node *head , int data) //Passing address of node because its data is being editted
{
if(*head == NULL)
*head= newNode(data);
else
{
if(data <= (*head)>data)
insert(&((*head)>left),data);
else
insert(&((*head)>right),data);
}
}
void iterativePostOrder(Node root, int noOfNodes)
{
if(root == NULL)
return;
struct forTraversal *stack = (struct forTraversal *)malloc(sizeof(struct forTraversal)*noOfNodes);
int i=0;
for(i=0;i<noOfNodes;i++)
stack[i].vleft = stack[i].vright = 0;
int top = 1;
stack[++top].node = root;
while(top!=1)
{
if(root>left != NULL && stack[top].vleft == 0)
{
stack[top].vleft = 1;
stack[++top].node = root>left;
root = root>left;
continue;
}
if(root>right!=NULL && stack[top].vright == 0)
{
stack[top].vright = 1;
stack[++top].node = root>right;
root = root>right;
continue;
}
printf("\n%d" , root>data);
stack[top].vleft = stack[top].vright = 0;
root = stack[top].node;
}
}
int main()
{
Node head = NULL;
insert(&head,4);
insert(&head,3);
insert(&head,6);
insert(&head,5);
insert(&head,7);
insert(&head,8);
insert(&head,1);
printf("\nIterative Post order \n");
iterativePostOrder(head,7);
return 0;
}

student
July 09, 2012 > we are calling binary search two times , first on elements at even position and then for elements at odd position
> we can also merge both the conditions in one call but that was getting complex and wouldn;t improve performance anyway....
Time complexity here is O(logn) , Space complexity O(1)
#include<stdio.h>
#include<stdlib.h>
int search(int arr[],int element,int start,int end);
int main()
{
int arr[] = {12,2,16,5,18,32,33,38,34,39};
int length = sizeof(arr)/sizeof(int);
//suppose we are searching for 16;
int element = 39;
printf("\n Search Trace \n");
// We will apply binary search seperately on list of elements at even position
//and then at list of elements at odd position
int evenStart = 0; //start of list of even elements
int oddStart = 1; //start of list of odd elements
int end = length1;
int evenEnd; //end of list of even elements
int oddEnd; //end of list of odd elements
if(end%2==0)
{
evenEnd = end;
oddEnd = end  1;
}
else
{
oddEnd = end;
evenEnd = end  1;
}
int pos;
pos = search(arr,element,evenStart ,evenEnd );
if(pos == 1)
pos = search(arr,element,oddStart,oddEnd );
if(pos == 1)
printf("\n\nElement not in list ");
else
printf("\n\nPositio of element : %d in list is %d",element,pos );
return 0;
}
//basic binary search
int search(int arr[],int element,int start,int end)
{
printf("Start : %d \t End : %d\n\t\t",start,end);
if(start > end)
return 1;
int mid = (start + end)/2;
if(start%2 == 0) //if start is even then making sure that middle element is also at even position
{
if(mid%2 != 0)
mid++;
}
else //if start is odd then making sure that middle element is also at odd position
{
if(mid%2 == 0)
mid++;
}
if(element == arr[mid])
return mid;
int pos;
//since we have odd and even elements we do mid+2 and mid2 to make
//sure start and end are always odd or even
if(element > arr[mid])
pos = search(arr,element,mid+2,end);
else
pos = search(arr,element,start,mid2);
return pos;
}
Ouput :
Search Trace
Start : 0 End : 8
Start : 6 End : 8
Start : 10 End : 8
Start : 1 End : 9
Start : 7 End : 9
Positio of element : 39 in list is 9
@spider : this might help u understand
*parse the string from right to left
* when doing so keep track of the number of zeros(am using countZero variable for that)
* when you encounter a 1, add the current count of zeros to total counts (am doing it using for loop in else condition )
At the end of the loop, total counts will have the minimum number of swaps needed
1... Travel the tree in DFS while adding the node in a stack......
2... When you reach the leaf node.. print out of the elements in stack from 0 to top of stack + leaf node
3... No need to add the leaf element in the stack...
4... then keep popping out elements from stack and go on performing DFS on them...
eg.. for the given problem
push 12
push 4
then print 1241 , 1242, 1243..... since 1,2,3 are leaf nodes ... if suppose node 1 had a child X then we would have pushed to stack and printed 1241X and then pop out 1
1. create a char pointer
char *ptr;
2. traver the linked list and keep adding element to ptr to form a string
eg.
if our linked list is
c>a>t>a>c
then do as
*ptr = c;
*(ptr+1) = a;
*(ptr+2)=t;
...
.
.
*(ptr+5)='\0'; // ofcourse this would be a for loop
//so *(ptr+i) till node!=NULL
3. then again traverse linked list from starting and compare element from end of string ..
eg.. compare 1st node with * (ptr+n1) // (ptr+n) is '\0';
.. compare 2nd node with * (ptr+n2)
.. compare 3rd node with * (ptr+n3)
and so on...
time complexity O(n)
space complexity o(1);
parse the string from right to left
* when doing so keep track of the number of zeros
* when you encounter a 1, add the current count of zeros to total counts
At the end of the loop, total counts will have the minimum number of swaps needed
what i think is there would be swaps amongs 1s also... which i guess we can avoid.... we dont need to perform swap among adjacent 1's
correct me if i am wrong
this is the implementation of above logic
#include<stdio.h>
int main()
{
int arr[]={0,0,0,1,0,1,1,0,1};
int countZero = 0;
int arrSize = 9,i,j,temp,k=0;
int swap=0;
for(i=(arrSize1);i>=0;i)
{
if(arr[i] == 0)
{
countZero++;
}else
{
for(j=i,k=0;k<countZero;j++,k++)
{
swap++;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(i=0;i<arrSize;i++)
printf("\t%d",arr[i]);
printf("\nSwaps = %d",swap);
return 0;
}

student
June 04, 2012 this is the implementation of above logic
#include<stdio.h>
int main()
{
int arr[]={0,0,0,1,0,1,1,0,1};
int countZero = 0;
int arrSize = 9,i,j,temp,k=0;
int swap=0;
for(i=(arrSize1);i>=0;i)
{
if(arr[i] == 0)
{
countZero++;
}else
{
for(j=i,k=0;k<countZero;j++,k++)
{
swap++;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(i=0;i<arrSize;i++)
printf("\t%d",arr[i]);
printf("\nSwaps = %d",swap);
return 0;
}

student
June 02, 2012 what i think is there would be swaps amongs 1s also... which i guess we can avoid.... we dont need to perform swap among adjacent 1's
correct me if i am wrong
this is the implementation of above logic
#include<stdio.h>
int main()
{
int arr[]={0,0,0,1,0,1,1,0,1};
int countZero = 0;
int arrSize = 9,i,j,temp,k=0;
int swap=0;
for(i=(arrSize1);i>=0;i)
{
if(arr[i] == 0)
{
countZero++;
}else
{
for(j=i,k=0;k<countZero;j++,k++)
{
swap++;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(i=0;i<arrSize;i++)
printf("\t%d",arr[i]);
printf("\nSwaps = %d",swap);
return 0;
}

student
June 02, 2012 algorithm seems to be O(n) but can you please explain the reason for taking visited array of size 256.... i think we can work out by only taking it of size 26 if we assume that only alphabets will be entered ...
or of size 52 if we consider upper and lower case as different
also someone do correct me if you think that algorithm is not O(n)
@cobra : yeah exactly we just need to pass the height ....
 student July 20, 2012it would be O(1) extra space in each recursion call ...
check my implementation below.... have submitted it ...