Some Microsoft Interview Problem Solution-2

Problem:FindReverse of a tree.

/* Linked List Node structure
  struct Node  {
     int data;
     struct Node *next;
  }
*/

// Should reverse list and return new head.
struct Node* reverse(struct Node *head)
{
  // Your code here
  Node *curr=head;
  Node *prev=NULL;
  Node *nxt;
  while(curr!=NULL)
  {
      nxt=curr->next;
      curr->next=prev;
      prev=curr;
      curr=nxt;
  }
  head=prev;
  return head;
}

Problem:Balance check of a binary tree.

A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree.

/* A binary tree node structure
struct Node {
    int data;
    struct Node* left, * right;
}; */

int mx(int a,int b)
{
    if(a>b)
    return a;
    return b;
}
int height(Node *a)
{
    if(a==NULL)
    return 0;
    return 1+mx(height(a->left),height(a->right));
}
// This function should return tree if passed  tree
// is balanced, else false.  Time complexity should
//  be O(n) where n is number of nodes in tree
bool isBalanced(struct Node *root)
{
    //  Your Code here
    if(root==NULL)
    return 1;
    int lh=0,rh=0;
    lh=height(root->left);
    rh=height(root->right);
    if(lh==rh)
    return 1;
    else if(lh-rh==1 || lh-rh==-1)
    return 1;
    return 0;
}

Problem:Find Maximum Width of Tree.
Maximum width is maximum number of nodes in any level. The problem also given in Flipkartinterview.

Problem Link

/*  Structure of a Binary Tree
struct Node
{
    int data;
    struct Node* left, *right;
}; */

/* Function to get the maximum width of a binary tree*/
int getMaxWidth(Node* root)
{
   // Your code here
   if(root==NULL)
   return 0;
   int mxWidth;
   int levelOfNode[1005];
   int level[105];
   queue<Node*> cue;
   Node *tmp=root,*a;
   for(int i=0;i<1005;i++)
   levelOfNode[i]=-1;
   for(int i=0;i<105;i++)
   level[i]=0;
   levelOfNode[root->data]=0;
   cue.push(root);
   level[0]=1;
   mxWidth=1;
   while(cue.size())
   {
       tmp=cue.front();
       cue.pop();
       if(tmp->left)
       {
           a=tmp->left;
           levelOfNode[a->data]=levelOfNode[tmp->data]+1;
           level[levelOfNode[a->data]]+=1;
           mxWidth=(mxWidth>level[levelOfNode[a->data]]?mxWidth:level[levelOfNode[a->data]]);
           cue.push(a);
       }
       if(tmp->right)
       {
           a=tmp->right;
           levelOfNode[a->data]=levelOfNode[tmp->data]+1;
           level[levelOfNode[a->data]]+=1;
           mxWidth=(mxWidth>level[levelOfNode[a->data]]?mxWidth:level[levelOfNode[a->data]]);
           cue.push(a);
       }
   }
   return mxWidth;
}

Problem:Find nodes of K distance from root
Print all nodes that are at distance k from root (root is considered at distance 0 from itself).It was given as question in Amazon interview.

Problem Link

/* A binary tree node has data, pointer to left child
   and a pointer to right child /
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}; */

// Recursive function to print right view of a binary tree.
void printKdistance(struct Node *root, int k)
{
  // Your code here
  if(root==NULL)
  return;
  Node *tmp=root,*a;
  queue<Node*> cue;
  int levelOfNode[1005];
  int nodeCountPerLevel[105];
  for(int i=0;i<1005;i++)
    levelOfNode[i]=-1;

  for(int i=0;i<105;i++)
    nodeCountPerLevel[i]=0;

    levelOfNode[root->data]=0;
    nodeCountPerLevel[0]=1;
    cue.push(root);
    while(cue.size())
    {
        tmp=cue.front();
        cue.pop();
        if(levelOfNode[tmp->data]==k)
        printf("%d ",tmp->data);
        if(tmp->left)
        {
            a=tmp->left;
            cue.push(a);
            levelOfNode[a->data]=levelOfNode[tmp->data]+1;
            nodeCountPerLevel[levelOfNode[a->data]]+=1;
        }
        if(tmp->right)
        {
            a=tmp->right;
            cue.push(a);
            levelOfNode[a->data]=levelOfNode[tmp->data]+1;
            nodeCountPerLevel[levelOfNode[a->data]]+=1;
        }
    }
}

 

Problem:Print the words of a given sentence reverse order separated by (.). Sentence will contain words and fullstops(.).

C++ Solution:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int t,len;
    string str="",prev="",cur="";
    cin>>t;
    t+=1;
    while(t--)
    {
        getline(cin,str);
        len=str.size()-1;
        if(str[len]=='.')
        len-=1;
        for(int i=len;i>=0;i--)
        {
            if(str[i]=='.')
            {
                cout<<prev<<".";
                cur="";
                prev="";
            }
            else
            {
                cur.append(1u,str[i]);
                cur.append(prev);
                prev=cur;
                cur="";
            }
        }
        if(prev.size())
        cout<<prev<<"\n";
        prev="";
    }
    return 0;
}

python Solution:

t=int(raw_input())
for i in range(t):
    line=raw_input()
    mylist = line.split('.')
    mylist.reverse()
    print '.'.join(mylist).strip()