CareerCup

@cobra : yeah exactly we just need to pass the height ....

it would be O(1) extra space in each recursion call ...

check my implementation below.... have submitted it ...

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(leftHeight-rightHeight) > 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;
}

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)

hey thanks for pointing that out....

i can make out from ur account that you had an Amazon interview recently ....

can u please share the experience on the following link

www(dot)careercup(dot)com/forumpost?id=14186679

@cobra : yeah thanks for pointing that out....
the statement went down the wrong way...
have editted it in the main post...

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)

can sort the list and do it without using extra space in O(nlogn) time

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)

here 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;
        
}

this will only check if the midpoint is balanced index or not ...

eg
in array [10 4 3 2 5] 1st position is the balanced inxdex since leftsum = rightsum = 10

@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....

hey thanks for posting... have prepared DS and algo and am working on OS right now.....

we 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 = x-1;
        }
        else
        {
                *(ptr+i)=(char)r+'A'-1;
                i++;
        }
 
   }
   *(ptr+i)='\0';
for(i=i-1;i>=0;i--)
   printf("%c",*(ptr+i));
return 0;
}

hey thanks for pointing that out.... will correct it

hey can you please explain how the following requirement is met in ur code....

"One additional consideration here is, the user is free to provide any length of integer (bigint long int etc), no restriction there."

is template has any role in that???

the code there gives wrong answer
try BC

@anonymous : hey thanks for sharing it....

i would also like to know if they had any written test at you campus for both the companies.... also what was the test pattern and how would you rate the difficulty level....

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;
}

BITS ..

@anonymous : still erroneous .....just test is for BC

works fine till AZ but then goes wrong
try BA should give 53
BB should give 54
BC should give 55
and so on.....

--> 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 = length-1;
        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 mid-2 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,mid-2);
 
        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

also where all this ques in written test or interview....

hey your ques are coming couple of times .... please remove the duplicate ones.... thanks a lot

that is the simplest of the solution we can give for the problem with time complexity O(n^2) or O(mn)....

any idea how we can improve it

@sb : was this in written test or interview ???

@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

@zprogd : hey thanks for pointing out the error... will modify it and try to come up with correct solution.....

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 12-4-1 , 12-4-2, 12-4-3..... since 1,2,3 are leaf nodes ... if suppose node 1 had a child X then we would have pushed to stack and printed 12-4-1-X 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+n-1) // (ptr+n) is '\0';
.. compare 2nd node with * (ptr+n-2)
.. compare 3rd node with * (ptr+n-3)

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=(arrSize-1);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;
}

hey can u please show how is it O(nlogn) , i mean isn't it O(logn)

please explain the algo

someone please do some commenting or explain the algo...

not able to make out anything out of it

please test it and if it fails then please share the test case

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=(arrSize-1);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;
}

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=(arrSize-1);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;
}

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)

@curious : can u please explain what is the difference between a substring and a subsequence??

wont we be required to check the nodes which we are directly skipping .... what if they are merging at the first node itself

@aravind and dheeraj sharma : can u share more questions which were asked to you!!!!