listEntries10({"version":"1.0","encoding":"UTF-8","feed":{"xmlns":"http://www.w3.org/2005/Atom","xmlns$openSearch":"http://a9.com/-/spec/opensearchrss/1.0/","id":{"$t":"tag:blogger.com,1999:blog-32064785"},"updated":{"$t":"2008-02-23T10:02:30.597-08:00"},"title":{"type":"text","$t":"Placements For Freshers"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/search/label/Solutions"},{"rel":"next","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/-/Solutions?alt\u003djson-in-script\u0026start-index\u003d26\u0026max-results\u003d25"},{"rel":"http://schemas.google.com/g/2005#feed","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/-/Solutions?alt\u003djson-in-script"}],"author":[{"name":{"$t":"chaitanya"}}],"generator":{"version":"7.00","uri":"http://www.blogger.com","$t":"Blogger"},"openSearch$totalResults":{"$t":"28"},"openSearch$startIndex":{"$t":"1"},"openSearch$itemsPerPage":{"$t":"25"},"entry":[{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-3685901237581180464"},"published":{"$t":"2007-12-25T03:18:00.000-08:00"},"updated":{"$t":"2007-12-25T03:30:45.682-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C-program to count the leaves in  a  tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e12. Write a C program to count the number of leaves in a tree\u003c/span\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e        int data;\u003cbr /\u003e        struct binarysearchtree* left;\u003cbr /\u003e        struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003eint count_leaves(tree T)\u003cbr /\u003e{\u003cbr /\u003e        if(T\u003d\u003dNULL)\u003cbr /\u003e         return 0;\u003cbr /\u003e         else if(T-\u0026gt;left\u003d\u003dNULL \u0026amp;\u0026amp; T-\u0026gt;right\u003d\u003dNULL)\u003cbr /\u003e         {\u003cbr /\u003e                return 1;\u003cbr /\u003e         }\u003cbr /\u003e         else\u003cbr /\u003e         return count_leaves(T-\u0026gt;left)+count_leaves(T-\u0026gt;right);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/c-program-to-count-leaves-in-tree.html","title":"C-program to count the leaves in  a  tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d3685901237581180464\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/3685901237581180464/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/3685901237581180464"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/3685901237581180464"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-1902976402399051617"},"published":{"$t":"2007-12-22T04:36:00.000-08:00"},"updated":{"$t":"2007-12-22T04:38:55.419-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Search On a Binary Search Tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e11. Write a C program to search for a value in a binary search tree (BST).\u003c/span\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003e#include\u0026lt;stdbool.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e        int data;\u003cbr /\u003e        struct binarysearchtree* left;\u003cbr /\u003e        struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003etree search_node(tree T,int num)\u003cbr /\u003e{\u003cbr /\u003e        if(T\u003d\u003dNULL)\u003cbr /\u003e        {\u003cbr /\u003e                return NULL;\u003cbr /\u003e        }\u003cbr /\u003e        else\u003cbr /\u003e        {\u003cbr /\u003e                if(T-\u0026gt;data\u0026gt;num)\u003cbr /\u003e                        search_node(T-\u0026gt;left,num);\u003cbr /\u003e                else if(T-\u0026gt;data\u0026lt;num)\u003cbr /\u003e                     search_node(T-\u0026gt;right,num);\u003cbr /\u003ereturn T;\u003cbr /\u003e        }\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick  Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/search-on-binary-search-tree.html","title":"Search On a Binary Search Tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d1902976402399051617\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/1902976402399051617/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/1902976402399051617"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/1902976402399051617"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-5706908571936859771"},"published":{"$t":"2007-12-22T04:04:00.000-08:00"},"updated":{"$t":"2007-12-22T04:13:30.583-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C-program to delete  a node from  a tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e10. Write a C program to delete a node from a Binary Search Tree?\u003c/span\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e        int data;\u003cbr /\u003e        struct binarysearchtree* left;\u003cbr /\u003e        struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003etree delete_node(tree T,int num)\u003cbr /\u003e{\u003cbr /\u003e        tree temp;\u003cbr /\u003e        if (T\u003d\u003dNULL)\u003cbr /\u003e                exit(0);\u003cbr /\u003e                //return NULL;\u003cbr /\u003e        else if(num\u0026lt;T-\u0026gt;data)\u003cbr /\u003e                T-\u0026gt;left\u003ddelete_node(T-\u0026gt;left,num);\u003cbr /\u003e        else if(num\u0026gt;T-\u0026gt;data)\u003cbr /\u003e                T-\u0026gt;right\u003ddelete_node(T-\u0026gt;right,num);\u003cbr /\u003e        else\u003cbr /\u003e        {\u003cbr /\u003e                if(T-\u0026gt;left!\u003dNULL\u0026amp;\u0026amp;T-\u0026gt;right!\u003dNULL)\u003cbr /\u003e                {\u003cbr /\u003e                        temp\u003dmin(T-\u0026gt;right);\u003cbr /\u003e                        T-\u0026gt;data\u003dtemp-\u0026gt;data;\u003cbr /\u003e                        T-\u0026gt;right\u003ddelete_node(T-\u0026gt;right,T-\u0026gt;data);\u003cbr /\u003e                }\u003cbr /\u003e                else if(T-\u0026gt;left\u003d\u003dNULL)\u003cbr /\u003e                {\u003cbr /\u003e                        temp\u003dT;\u003cbr /\u003e                        T\u003dT-\u0026gt;right;\u003cbr /\u003e                }\u003cbr /\u003e                else if(T-\u0026gt;right\u003d\u003dNULL)\u003cbr /\u003e                {\u003cbr /\u003e                        temp\u003dT;\u003cbr /\u003e                        T\u003dT-\u0026gt;left;\u003cbr /\u003e                }\u003cbr /\u003e                        free(temp);\u003cbr /\u003e        }\u003cbr /\u003e        return T;\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/c-program-to-delete-node-from-tree.html","title":"C-program to delete  a node from  a tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d5706908571936859771\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/5706908571936859771/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/5706908571936859771"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/5706908571936859771"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-2549819093822351020"},"published":{"$t":"2007-12-22T03:57:00.000-08:00"},"updated":{"$t":"2007-12-22T04:02:00.406-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C-program to check whether a binary tree is a Binary search tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e8. Write a C program to check if a given binary tree is a binary search tree or not?\u003c/span\u003e\u003cbr /\u003eSolution:\u003cbr /\u003eIf the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003ebool flag\u003dtrue;\u003cbr /\u003evoid inorder(tree T,int *lastprinted)\u003cbr /\u003e{\u003cbr /\u003eif(T\u003d\u003dNULL)\u003cbr /\u003e  {\u003cbr /\u003e   printf(\u0026quot;the tree is empty .Hence, it is a BST\\n\u0026quot;);\u003cbr /\u003e  }\u003cbr /\u003eelse\u003cbr /\u003e{\u003cbr /\u003e  if(T-\u0026gt;left!\u003dNULL)\u003cbr /\u003e  {\u003cbr /\u003e      inorder(T-\u0026gt;left,lastprinted);\u003cbr /\u003e  }\u003cbr /\u003e  if(T-\u0026gt;data \u0026gt; *lastprinted)\u003cbr /\u003e  {\u003cbr /\u003e     *lastprinted\u003dT-\u0026gt;data;\u003cbr /\u003e  }\u003cbr /\u003e  else\u003cbr /\u003e  {\u003cbr /\u003e     printf(\u0026quot;the given binary tree is not a BST\\n\u0026quot;);\u003cbr /\u003e     flag\u003dfalse;\u003cbr /\u003e     exit(0);\u003cbr /\u003e  }\u003cbr /\u003e  inorder(T-\u0026gt;right,lastprinted);\u003cbr /\u003e  }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003eNow check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/c-program-to-check-whether-binary-tree.html","title":"C-program to check whether a binary tree is a Binary search tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d2549819093822351020\u0026isPopup\u003dtrue","title":"1 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/2549819093822351020/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/2549819093822351020"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/2549819093822351020"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-7755892788694475185"},"published":{"$t":"2007-12-22T03:36:00.000-08:00"},"updated":{"$t":"2007-12-22T03:47:43.835-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C-program to make a copy of a tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e7.Write a C program to create \u003cbr /\u003ea copy of a tree\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e      int data;\u003cbr /\u003e      struct binarysearchtree* left;\u003cbr /\u003e      struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003etree copy(tree T)\u003cbr /\u003e{\u003cbr /\u003e if(T\u003d\u003d NULL)\u003cbr /\u003e        return NULL;\u003cbr /\u003eelse\u003cbr /\u003e {\u003cbr /\u003e        tree *newtree\u003d(tree*)malloc(sizeof(tree));\u003cbr /\u003e        newtree-\u0026gt;data\u003dtree-\u0026gt;data;\u003cbr /\u003e        newtree-\u0026gt;left\u003dcopy(T-\u0026gt;left);\u003cbr /\u003e        newtree-\u0026gt;right\u003dcopy(T-\u0026gt;right);\u003cbr /\u003e        return newtree;\u003cbr /\u003e }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e  \u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/c-program-to-make-copy-of-tree.html","title":"C-program to make a copy of a tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d7755892788694475185\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/7755892788694475185/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/7755892788694475185"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/7755892788694475185"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-3804164725832266354"},"published":{"$t":"2007-12-04T07:06:00.000-08:00"},"updated":{"$t":"2008-02-12T06:46:35.383-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solution1"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eThere is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].\u003cbr /\u003e\u003cbr /\u003eSolve it without division operator and in O(n).\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:At each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting \u003cspan style\u003d\u0022font-style: italic;\u0022\u003eA[i]\u003c/span\u003e\u003d\u003cspan style\u003d\u0022font-style: italic;\u0022\u003ea*b\u003c/span\u003e,where \u003cspan style\u003d\u0022font-style: italic;\u0022\u003ea\u003c/span\u003e\u003dcumulative product of all those elements to the left of A[i] and \u003cspan style\u003d\u0022font-style: italic;\u0022\u003eb\u003c/span\u003e\u003dcumulative product of all those elements to the right of A[i].\u003cbr /\u003e\u003cbr /\u003eWe can put this simply by storing the result in a separate array  and by traversing the input array twice.\u003cbr /\u003e\u003cbr /\u003eIn the first iteration, we traverse the input array left to right  and   assign Output[i]\u003da (where  a is the product of all the numbers preceding A[i]).\u003cbr /\u003e\u003cbr /\u003eNow we traverse the input array again ,but in reverse direction and this time we find \u003cbr /\u003eb(here  b is the product of all the numbers following A[i]) and Assign\u003cbr /\u003e\u003cbr /\u003eOutput[i]\u003dOutput[i]*b; which amounts to putting  Output[i]\u003da*b\u003cbr /\u003e\u003cbr /\u003eHence Each Output[i] contains the product of all the elements in A except A[i].\u003cbr /\u003e\u003cbr /\u003eBelow is a C function to do the same.\u003cbr /\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eint* function(int  input[],int size,int output[])\u003cbr /\u003e{\u003cbr /\u003e long int result\u003d1;\u003cbr /\u003e for(int i\u003d0;i\u0026lt;size;i++)\u003cbr /\u003e {\u003cbr /\u003e  output[i]\u003dresult;\u003cbr /\u003e  result*\u003dinput[i];\u003cbr /\u003e }\u003cbr /\u003e result\u003d1;\u003cbr /\u003e for(int i\u003dsize-1;i\u0026gt;\u003d0;i--)\u003cbr /\u003e {\u003cbr /\u003e output[i]*\u003dresult;\u003cbr /\u003e result*\u003dinput[i];\u003cbr /\u003e }\u003cbr /\u003e return output;\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/solution1.html","title":"Solution1"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d3804164725832266354\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/3804164725832266354/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/3804164725832266354"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/3804164725832266354"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-1232942248846670554"},"published":{"$t":"2007-12-04T04:27:00.000-08:00"},"updated":{"$t":"2007-12-04T23:47:31.823-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to problems in recursion analysis"},"content":{"type":"html","$t":"\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/11/recursion-analysis.html\u0022\u003eClick here for the questions\u003c/a\u003e\u003cbr /\u003e\u003col\u003e\u003cbr /\u003e\u003cli\u003eUsing the substitution method, we substitute the function recursively till we arrive at T(1).\u003cbr /\u003ei.e T(n)\u003dT(n/2) + 1 \u003d T(n/4) + 1 + 1 \u003d ....\u003cbr /\u003e\u003cbr /\u003eWe get a total of lg(n) iterations\u003cbr /\u003ei.e T(n)\u003dT(1) +lg(n)\u003cbr /\u003e\u003cbr /\u003eThus the complexity is O(lg n).\u003cbr /\u003e\u003c/li\u003e\u003cbr /\u003e\u003cli\u003eSimilar to the 1st problem, it takes lg(n) iterations to reach T(1).After final iteration:\u003cbr /\u003e\u003cbr /\u003eT(n)\u003d(2^lg(n))*(T(1) + lg(n)*17)\u003cbr /\u003e\u003cbr /\u003eThus the complexity is (2^lg(n))*(lg n) \u003d n*lg(n)\u003cbr /\u003e\u003c/li\u003e\u003cbr /\u003e\u003cli\u003eLet n\u003d2^m,then T(2^m)\u003d2*T(2^m/2) + 1\u003cbr /\u003eNow let S(m)\u003dT(2^m).\u003cbr /\u003e\u003d\u003eS(m)\u003d2*S(m/2) +1\u003cbr /\u003e\u003cbr /\u003eThis is the same as 2nd problem.\u003cbr /\u003eThus the complexity is O(m*lg(m)),but m\u003dlg(n)\u003cbr /\u003e\u003cbr /\u003eThus the final complexity is O(lg(n)*lg(lg(n)))\u003cbr /\u003e\u003c/li\u003e\u003cbr /\u003e\u003c/ol\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/solutions-to-problems-in-recursion.html","title":"Solutions to problems in recursion analysis"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d1232942248846670554\u0026isPopup\u003dtrue","title":"1 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/1232942248846670554/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/1232942248846670554"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/1232942248846670554"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-5011867184806503328"},"published":{"$t":"2007-12-04T03:57:00.000-08:00"},"updated":{"$t":"2007-12-20T07:48:14.875-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Google Top Interview Puzzles"},"content":{"type":"html","$t":"To start with,we are posting solutions to some of the questions.In due course of time ,all the questions shall be solved.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].\u003cbr /\u003e\u003cbr /\u003eSolve it without division operator and in O(n).\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eAt each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eA[i]\u003c/span\u003e\u003d\u003cspan style\u003d\u0022font-style:italic;\u0022\u003ea*b\u003c/span\u003e,where \u003cspan style\u003d\u0022font-style:italic;\u0022\u003ea\u003c/span\u003e\u003dcumulative product of all those elements to the left of A[i] and \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eb\u003c/span\u003e\u003dcumulative product of all those elements to the right of A[i].\u003cbr /\u003e\u003cbr /\u003eWe can put this simply by storing the result in a separate array  and by traversing the input array twice.\u003cbr /\u003e\u003cbr /\u003eIn the first iteration, we traverse the input array left to right  and   assign Output[i]\u003da (where  a is the product of all the numbers preceding A[i]).\u003cbr /\u003e\u003cbr /\u003eNow we traverse the input array again ,but in reverse direction and this time we find  \u003cbr /\u003eb(here  b is the product of all the numbers following A[i]) and Assign \u003cbr /\u003e\u003cbr /\u003eOutput[i]\u003dOutput[i]*b; which amounts to putting  Output[i]\u003da*b\u003cbr /\u003e\u003cbr /\u003eHence Each Output[i] contains the product of all the elements in A except A[i].\u003cbr /\u003e\u003cbr /\u003eBelow is a C function to do the same.\u003cbr /\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eint* function(int  input[],int size,int output[])\u003cbr /\u003e{\u003cbr /\u003e  long int result\u003d1;\u003cbr /\u003e  for(int i\u003d0;i\u0026lt;size;i++)\u003cbr /\u003e  {\u003cbr /\u003e   output[i]\u003dresult;\u003cbr /\u003e   result*\u003dinput[i];\u003cbr /\u003e  }\u003cbr /\u003e  result\u003d1;\u003cbr /\u003e  for(int i\u003dsize-1;i\u0026gt;\u003d0;i--)\u003cbr /\u003e  {\u003cbr /\u003e  output[i]*\u003dresult;\u003cbr /\u003e  result*\u003dinput[i];\u003cbr /\u003e  }\u003cbr /\u003e  return output;\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e2.There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.\u003cbr /\u003e\u003cbr /\u003eHint:\u003cbr /\u003e\u003cbr /\u003e1. Use random function rand() (returns a number between 0 and 1) and irand()\u003cbr /\u003e(return either 0 or 1)\u003cbr /\u003e2. It should be done in O(n).\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eTraverse the list, generating a new random number for each entry. Keep a ‘top k’ chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.\u003cbr /\u003e\u003cbr /\u003eThis random number generated for each element can be defined as a function f\u003dabsolute(irand()-rand()),which is random enough.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e3 Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M \u003e\u003e N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThis problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for \u0027n\u0027 can be found as follows:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003ebase \u003d n/8; (base is the char whose certain bit needs to be set)\u003cbr /\u003e\u003cbr /\u003eoffset \u003d 1 \u003c\u003c (n mod 8); (offset is the bit to be set)\u003cbr /\u003e\u003cbr /\u003eb_array[base] |\u003d offset; (I set the particular bit)\u003cbr /\u003e\u003cbr /\u003eOnce this is done of all N numbers, given a number m,\u003cbr /\u003ewe can first find corresponding  bit offset and check whether it is one.\u003cbr /\u003e\u003cbr /\u003ebase \u003d m/8; (base is the char whose certain bit needs to be set)\u003cbr /\u003e\u003cbr /\u003eoffset \u003d 1 \u003c\u003c (m mod 8); (offset is the bit to be set)\u003cbr /\u003e\u003cbr /\u003eif (b_array[base] \u0026 offset)\u003cbr /\u003e    // found the number\u003cbr /\u003eelse\u003cbr /\u003e    //number could not be found\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e*Any other solutions will be appreciated.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e5)You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi \u003d a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003eSolution:Please refer to Question1.This question is identical to the first one,except that it is made to look much harder.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e6 How do you put a Binary Search Tree in an array in a efficient manner.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003eHint :: If the node is stored at the ith position and its children are at\u003cbr /\u003e2i and 2i+1(I mean level order wise)Its not the most efficient way.\u003cbr /\u003e\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThe method of construction given in Hint though looks good at a mere glance,it has too many shortcomings.Exponential memory is required at the worst case.\u003cbr /\u003e\u003cbr /\u003eThe solution is maintain inorder and one of the other 2 traversals of the tree.These 2 are sufficient to construct back the tree.So the space requirement now is \u003cspan style\u003d\u0022font-style:italic;\u0022\u003e2N\u003c/span\u003e i.e \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO(N)\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e7. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.\u003cbr /\u003eNote :: You should not use use any extra space. i.e sorting Binary Search Tree\u003cbr /\u003eand storing the results in an array and listing out the fifth element.\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eint num\u003d0;\u003cbr /\u003evoid max(tree*t)\u003cbr /\u003e{\u003cbr /\u003e        if(t\u003d\u003dNULL)\u003cbr /\u003e                return;\u003cbr /\u003e        max(t-\u003eright);\u003cbr /\u003e        num++;\u003cbr /\u003e        if(num\u003d\u003d5)\u003cbr /\u003e                printf(\u0022%d\\n\u0022,t-\u003eno);\u003cbr /\u003e        max(t-\u003eleft);\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e8.Given a Data Structure having first n integers and next n chars. A \u003d i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A \u003d i1 c1 i2 c2 ... in cn\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:we divide the array in four sections:[X,Y|A,B]\u003cbr /\u003eIt is easy to see that with swaps we can modify it to the form [X,A|Y,B].\u003cbr /\u003eNow do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.[as given in comments section]\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e9.Given two sequences of items, find the items whose \u003cbr /\u003eabsolute number increases or decreases the most when comparing \u003cbr /\u003eone sequence with the other by reading the sequence only once.\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003eSolution:Well, this question requires some reading and understanding \u003cbr /\u003eof data streams.The stress is upon the algorithmic challenges in web search engines.It wouldn\u0027t be appropriate to quote a short piece of text\u003cbr /\u003eas the answer.So please go through the paper\u003ca href\u003d\u0022http://www.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf\u0022\u003e\u003cu\u003eFinding Frequent Items in Data Streams\u003c/u\u003e\u003c/a\u003e  to have a thorough understanding of the problem \u003cbr /\u003eas well as its applications.\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e11.How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThe three non-collinear points form a triangle. There will be 3 lines which are equidistant from all the three points. \u003cbr /\u003eDraw altitudes from each point to the line joining the other two points.We get 3 altitudes.Now draw a line passing through the mid point of the altitude line and parallel to line onto which the altitude is drawn.This line is equidistant from all the 3 points.Thus we get 3 lines.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e13.Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThis solution has been framed on the assumption that all the occurances of a  string in the large string of length N are to be reported.\u003cbr /\u003eSo one can just sort the M strings in \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO(l*Mlog(M))\u003c/span\u003e.An additional l figures because comparison function of strings of length l is of complexity O(l).\u003cbr /\u003eOnce these M strings are sorted,we can simply do a binary search on them for each of the N-l+1 continuous substrings of big string.The complexity of this search for each such substring is \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO(l*logM)\u003c/span\u003e.\u003cbr /\u003eSo the complexity of this procedure is \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO(l*MlogM)+O((N-l+1)*(l*logM)).\u003c/span\u003e\u003cbr /\u003eFor N\u003e\u003el this reduces to \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO(l*MlogM)+O(N*l*log(M)\u003c/span\u003e.\u003cbr /\u003eThis can be reduced to \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eO((M+N)*l*log(M))\u003c/span\u003e.\u003cbr /\u003e\u003cbr /\u003eIf you find a better solution than this,please post it in the comments section.\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e\u003cbr /\u003e14.Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree\u003cbr /\u003eHint: Some kind of pointer handling with In Order Traversal - anybody in for\u003cbr /\u003ewriting some code.\u003c/span\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eIf the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003ebool flag\u003dtrue;\u003cbr /\u003evoid inorder(tree T,int *lastprinted)\u003cbr /\u003e{\u003cbr /\u003eif(T\u003d\u003dNULL)\u003cbr /\u003e  {\u003cbr /\u003e   printf(\u0026quot;the tree is empty .Hence, it is a BST\\n\u0026quot;);\u003cbr /\u003e  }\u003cbr /\u003eelse\u003cbr /\u003e{\u003cbr /\u003e  if(T-\u0026gt;left!\u003dNULL)\u003cbr /\u003e  {\u003cbr /\u003e      inorder(T-\u0026gt;left,lastprinted);\u003cbr /\u003e  }\u003cbr /\u003e  if(T-\u0026gt;data \u0026gt; *lastprinted)\u003cbr /\u003e  {\u003cbr /\u003e     *lastprinted\u003dT-\u0026gt;data;\u003cbr /\u003e  }\u003cbr /\u003e  else\u003cbr /\u003e  {\u003cbr /\u003e     printf(\u0026quot;the given binary tree is not a BST\\n\u0026quot;);\u003cbr /\u003e     flag\u003dfalse;\u003cbr /\u003e     exit(0);\u003cbr /\u003e  }\u003cbr /\u003e  inorder(T-\u0026gt;right,lastprinted);\u003cbr /\u003e  }\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003eNow check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e15.You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003eSolution:For each chunk of sorted list which occupies a block,make a note of the first and last elements.Thus we have lookup table giving the first and last elements of each of the blocks.Now associate  an empty list  with each of the blocks.\u003cbr /\u003eNow try to find the block which might contain the first entry A[1]of the small sorted list(say)A given.Since we knew the first and last elements of all the blocks,we can identify the block \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eBi\u003c/span\u003e ,which only can contain the desired number.Now add A[1] to the empty list associated with \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eBi\u003c/span\u003e.Now we need to identify the candidate block for A[2].As A is also sorted,A[2] should lie either in \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eBi\u003c/span\u003e or its successors.So we simultaneously traverse \u003cbr /\u003eA as well as lookup table.When we are done with finding the probable blocks of all the numbers in A,we have also finished the look up table. We also have in the lists associated with each block,all those entries of A to search for, in that particular block.Now for each block \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eBi\u003c/span\u003e,search for all the entries in its list using binary search.This way we have minimized the number of disk block accesses,which is the bottleneck .\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eDifferent solutions exist for this problem,depending on how once perceives the question.\u003cbr /\u003eIf all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eNc2\u003c/span\u003e ways.Now in the second iteration  we can merge 2 companies among the remaining N-1 in \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eN-1c2\u003c/span\u003e.\u003cbr /\u003eWe go on merging like this until we have a single union of all the companies.\u003cbr /\u003eHence the number of ways of doing this is \u003cspan style\u003d\u0022font-style:italic;\u0022\u003e(Nc2)*(N-1c2)*(N-2c2)*........*(2c2)\u003d(N!*(N-1)!)/2^(N-1) .\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eOne more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be  merged.\u003cbr /\u003e\u003cbr /\u003eWe could have merged companies 1\u00262 in the first iteration and 3\u00264 in the 2nd iteration.Likewise we could have also merged 3\u00264 in the first iteration and then 1\u00262 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn\u0027t even consider that.\u003cbr /\u003eIf we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are  identical .Then this problem reduces to parenthesis problem,i.e  number of ways of putting N pairs of parenthesis.The answer then would be N-1 th \u003ca href\u003d\u0022http://en.wikipedia.org/wiki/Catalan_number\u0022\u003eCatalan Number\u003c/a\u003e,\u003cbr /\u003ei.e (2N-2)!/N!(N-1)!.\u003cbr /\u003e\u003cbr /\u003eIf the companies aren\u0027t identical ,with some permutations also getting into the picture, then the solution isn\u0027t straightforward and we couldn\u0027t figure it out.\u003cbr /\u003e\u003cbr /\u003eSo if anyone has a solution to this,please post it in the comments section.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e\u003cbr /\u003e17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThe maximum size of int is 2,147,483,647 in case of 32-bit integers. Thus we need declare an array of long long int.\u003cbr /\u003eThen we can do a merge sort and in doing so we can find the integers which appear atleast twice in the merge step.Thus we can solve the problem in \u003cbr /\u003enlogn time.\u003cbr /\u003eIf you have any better solution then please comment.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e18 Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003eSolution:This question is similar to question 9 in the context which it appears and\u003cbr /\u003eanswer lies in the same paper \u003ca href\u003d\u0022http://www.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf\u0022\u003e\u003cu\u003eFinding Frequent Items in Data Streams\u003c/u\u003e\u003c/a\u003e.\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e\u003cbr /\u003e19.Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.\u003c/span\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eUse 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.\u003cbr /\u003eWhen one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .\u003cbr /\u003eWhen one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.\u003cbr /\u003e\u003cbr /\u003eHence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e20.Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThis is a flavour of coin change problem ,for which sufficient material is available at \u003ca href\u003d\u0022http://www.algorithmist.com/index.php/Coin_Change\u0022\u003e\u003cu\u003eCoin Change Problem\u003c/u\u003e\u003c/a\u003e.\u003cbr /\u003eIf you have gone through the above link,please refer below to the minor changes we make to the pseudo code of one given in the above link.\u003cbr /\u003e\u003cbr /\u003eLet p[n][m] denote the minimum no of coins of various denomination required to give change for n cents from coins of m different denominations.\u003cbr /\u003e\u003cbr /\u003eP[n][m]\u003dmin((1+p[n-S[m]][m]),p[n][m-1])// these notations will be clear only if you go through the above link thoroughly.\u003cbr /\u003e\u003cbr /\u003eThen it isn\u0027t much difficult to write the conditions for base cases as well.\u003cbr /\u003eThis is only a suggested solution to this problem and we have clues here and there as to how to proceed.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e21.Given an array,\u003cbr /\u003e\u003cbr /\u003ei) find the longest continuous increasing subsequence.\u003cbr /\u003e\u003cbr /\u003eii) find the longest increasing subsequence.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003ea)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.\u003cbr /\u003e\u003cbr /\u003eb)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.\u003cbr /\u003eThe following is a function which returns the length of the longest increasing subsequence in a.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eint lis(int*a,int n)\u003cbr /\u003e{\u003cbr /\u003e int length[n],path[n],i,j,max\u003d0;\u003cbr /\u003e\u003cbr /\u003e for(i\u003d0;i \u003c N;i++)\u003cbr /\u003e  length[i]\u003d1,path[i]\u003di; //path contains the longest subsequence.\u003cbr /\u003e\u003cbr /\u003e for(i\u003d1;i \u003c N;i++)\u003cbr /\u003e  for(j\u003d0;j \u003c i;j++)\u003cbr /\u003e   if(a[i] \u003e a[j] \u0026\u0026 length[i] \u003c length[j]+1)\u003cbr /\u003e    length[i]\u003dlength[j]+1,path[i]\u003dj;\u003cbr /\u003e\u003cbr /\u003e for(i\u003d0;i \u003c N;i++)\u003cbr /\u003e  if(max \u003c length[i])\u003cbr /\u003e   max\u003dlength[i];\u003cbr /\u003e\u003cbr /\u003e return max;\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e22.Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThis is a repeated question, same as the 16th. So please refer to the 16th answer.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e23.Write a function to find the middle node of a single link list.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003e\u003cpre\u003e\u003cbr /\u003etypedef struct linklist\u003cbr /\u003e{\u003cbr /\u003e        int no;\u003cbr /\u003e        struct linklist*next;\u003cbr /\u003e}list;\u003cbr /\u003e\u003cbr /\u003evoid midvalue(list*start)\u003cbr /\u003e{\u003cbr /\u003elist*head;\u003cbr /\u003ehead\u003dstart;\u003cbr /\u003ewhile(1)\u003cbr /\u003e{\u003cbr /\u003e   if(start-\u003enext\u003d\u003dNULL)\u003cbr /\u003e   {\u003cbr /\u003e    if(head-\u003enext\u003d\u003dNULL)\u003cbr /\u003e     {\u003cbr /\u003e       printf(\u0022Only one node in the list which is %d\\n\u0022,head-\u003eno);\u003cbr /\u003e     }\u003cbr /\u003e   else\u003cbr /\u003e   {\u003cbr /\u003e       printf(\u0022Middle node is %d\\n\u0022,head-\u003enext-\u003eno);\u003cbr /\u003e   }\u003cbr /\u003e   break;\u003cbr /\u003e  }\u003cbr /\u003e  if(start-\u003enext-\u003enext\u003d\u003dNULL)\u003cbr /\u003e  {\u003cbr /\u003e     printf(\u0022Middle nodes are %d and %d\\n\u0022,head-\u003eno,head-\u003enext-\u003eno);\u003cbr /\u003e  }\u003cbr /\u003e     start\u003dstart-\u003enext-\u003enext;\u003cbr /\u003e     head\u003dhead-\u003enext;\u003cbr /\u003e  }\u003cbr /\u003e        return;\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003eThis algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e24.Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eThe following is a function to check if the two trees are similar or not.It returns true if they are similar else false.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eint compareTree(struct node* a, struct node* b) {\u003cbr /\u003e    if (a\u003d\u003dNULL \u0026\u0026 b\u003d\u003dNULL) \u003cbr /\u003e  return(true);\u003cbr /\u003e    else if (a!\u003dNULL \u0026\u0026 b!\u003dNULL) {\u003cbr /\u003e    return(\u003cbr /\u003e      a-\u003edata \u003d\u003d b-\u003edata \u0026\u0026\u003cbr /\u003e      compareTree(a-\u003eleft, b-\u003eleft) \u0026\u0026\u003cbr /\u003e      compareTree(a-\u003eright, b-\u003eright)\u003cbr /\u003e    );\u003cbr /\u003e  }\u003cbr /\u003e    else return(false);\u003cbr /\u003e} \u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e25.Implement put/get methods of a fixed size cache with LRU replacement algorithm.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eEach cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.\u003cbr /\u003eGetting some data is just a search for the data thereby incrementing it age and resorting the cache units.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003eget(id)\u003cbr /\u003e{\u003cbr /\u003e z\u003dsearch(id);\u003cbr /\u003e data\u003dcache[z].data;\u003cbr /\u003e cache[z].age++;\u003cbr /\u003e sort(cache);\u003cbr /\u003e return(x);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003eput(id,x)\u003cbr /\u003e{\u003cbr /\u003e if(top\u003d\u003dcachesize)  //if cache is full\u003cbr /\u003e  top--\u003cbr /\u003e cache[top].id\u003did;   \u003cbr /\u003e cache[top].data\u003dx;\u003cbr /\u003e cache[top].age\u003d0;\u003cbr /\u003e top++;\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e26 You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.\u003cbr /\u003e\u003cbr /\u003eDistance is defined like this :\u003cbr /\u003e\u003cbr /\u003eIf a[i], b[j] and c[k] are three elements then\u003cbr /\u003e\u003cbr /\u003edistance\u003dmax(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))\u0022\u003cbr /\u003e\u003cbr /\u003ePlease give a solution in O(n) time complexity\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003ePoint to the first elements of the three arrays, namely a[0],b[0],c[0].\u003cbr /\u003eFind the smallest and second smallest of the three.Let us say that a[0] is the smallest and b[0] is the second smallest. Increment the pointer of a until you find a[i]\u003eb[0]. Calculate the difference between a[i-1] and c[0] and store it as current min. Now,again find the smallest and second smallest between a[i], b[0], and c[0] and repeat the above process. If the new difference is smaller than current min,update the value of current min.\u003cbr /\u003eRepeat the above process until one of the arrays are finished.\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e27.Classic - Egg Problem\u003cbr /\u003e\u003cbr /\u003eYou are given 2 eggs.You have access to a 100-storey building.\u003cbr /\u003e\u003cbr /\u003eEggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.\u003cbr /\u003e\u003cbr /\u003eNow the question is how many drops you need to make. You are allowed to break 2 eggs in the process.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003eSolution:\u003c/span\u003eLet d be the number of drops required.\u003cbr /\u003eNow we need to find an optimal solution no matter at which floor the egg breaks.\u003cbr /\u003eSo we find d such that it doesn\u0027t depend on the floor number.\u003cbr /\u003e\u003cbr /\u003eLet us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.\u003cbr /\u003eIf the egg doesn\u0027t break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.\u003cbr /\u003eWe proceed in this fashion,till we reach the 100th floor.\u003cbr /\u003e\u003cbr /\u003eThus we break at d,2*d-1,3*d-2,....\u003cbr /\u003e\u003cbr /\u003ethus d+(d-1)+(d-2)+.... 1 \u003c\u003d100\u003cbr /\u003e\u003d\u003ed\u003d14\u003cbr /\u003eThus we need atmax of 14 attempts for any case.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003eSolutions to the remaining puzzles will be posted soon. If we have a solution then please comment it.\u003c/span\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html","title":"Solutions to Google Top Interview Puzzles"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d5011867184806503328\u0026isPopup\u003dtrue","title":"2 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/5011867184806503328/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/5011867184806503328"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/5011867184806503328"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-6143663084590037569"},"published":{"$t":"2007-12-03T03:20:00.000-08:00"},"updated":{"$t":"2007-12-03T06:28:55.969-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Traversals of a Binary Tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eWrite C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities?\u003c/span\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e      int data;\u003cbr /\u003e      struct binarysearchtree* left;\u003cbr /\u003e      struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003evoid inorder_print(tree T)\u003cbr /\u003e{\u003cbr /\u003e      if (T!\u003dNULL)\u003cbr /\u003e      {\u003cbr /\u003e              printf(\u0022%d\\n\u0022,T-\u0026gt;data);\u003cbr /\u003e              inorder_print(T-\u0026gt;left);\u003cbr /\u003e              inorder_print(T-\u0026gt;right);\u003cbr /\u003e      }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003evoid postorder_print(tree T)\u003cbr /\u003e{\u003cbr /\u003e if (T\u003d\u003dNULL)\u003cbr /\u003e {\u003cbr /\u003e    return;\u003cbr /\u003e }\u003cbr /\u003e postorder_print(T-\u0026gt;left);\u003cbr /\u003e postorder_print(T-\u0026gt;right);\u003cbr /\u003e printf(\u0022%d\\n\u0022,T-\u0026gt;data);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003evoid preorder_print(tree T)\u003cbr /\u003e{\u003cbr /\u003e if (T\u003d\u003dNULL)\u003cbr /\u003e {\u003cbr /\u003e    return;\u003cbr /\u003e }\u003cbr /\u003e printf(\u0022%d\\n\u0022,T-\u0026gt;data);\u003cbr /\u003e preorder_print(T-\u0026gt;left);\u003cbr /\u003e preorder_print(T-\u0026gt;right);\u003cbr /\u003e\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003eEach of them traverse all the nodes.\u003cbr /\u003eSo the complexity is O(N).\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/traversals-of-binary-tree.html","title":"Traversals of a Binary Tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d6143663084590037569\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/6143663084590037569/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/6143663084590037569"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/6143663084590037569"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-2630056406353343849"},"published":{"$t":"2007-12-01T09:49:00.000-08:00"},"updated":{"$t":"2007-12-20T13:24:35.735-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Amazon Intern Interview Questions"},"content":{"type":"html","$t":"\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/11/amazon-intern-interview-questions.html\u003eClick here for the questions\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e1)Place a red ball in a urn and all the further balls in the other urn.The probability for picking out the red ball is now greater than 0.5.\u003cbr /\u003e\u003cbr /\u003e2)If v\u003c\u003d2V then the position is (v*L)/(2*V) from the starting point else it is 2*L -(v*L)/(2*V) from the starting point.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e4)If we know the process then we can kill it by killall -9 \u0022process name\u0022 else we can kill it using its process id obtained by the command ps -x by kill -9 \u0022processid\u0022 .\u003cbr /\u003e\u003cbr /\u003e5)Top command displays all the Linux tasks running at that particular time.It provides their running time and the resources used.\u003cbr /\u003e\u003cbr /\u003e6)The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n).\u003cbr /\u003eFor floating numbers multiply it with 100 and proceed."},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/12/solutions-to-amazon-intern-interview.html","title":"Solutions to Amazon Intern Interview Questions"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d2630056406353343849\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/2630056406353343849/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/2630056406353343849"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/2630056406353343849"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-1391555008509272385"},"published":{"$t":"2007-11-29T07:51:00.000-08:00"},"updated":{"$t":"2007-11-29T21:10:59.030-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C program to create mirror copy of a tree"},"content":{"type":"html","$t":"Question:\u003cb\u003eWrite a C program to create a mirror copy of a tree left nodes become right and right nodes become left)\u003c/b\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree{\u003cbr /\u003e       int data;\u003cbr /\u003e       struct binarysearchtree* left;\u003cbr /\u003e       struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003etree mirror_copy(tree T)\u003cbr /\u003e{\u003cbr /\u003e if(T\u003d\u003dNULL)\u003cbr /\u003e return T;\u003cbr /\u003e else\u003cbr /\u003e {\u003cbr /\u003e    tree temp1\u003dmirror_copy(T-\u0026gt;left);\u003cbr /\u003e    tree temp2\u003dmirror_copy(T-\u0026gt;right);\u003cbr /\u003e    T-\u0026gt;left\u003dtemp2;\u003cbr /\u003e    T-\u0026gt;right\u003dtemp1;\u003cbr /\u003e    return T;\u003cbr /\u003e }\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/c-program-to-create-mirror-copy-of-tree.html","title":"C program to create mirror copy of a tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d1391555008509272385\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/1391555008509272385/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/1391555008509272385"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/1391555008509272385"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-7274857883340341063"},"published":{"$t":"2007-11-28T06:58:00.000-08:00"},"updated":{"$t":"2007-12-04T02:28:58.718-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Questions on recursion"},"content":{"type":"html","$t":"\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/11/some-questions-on-recursion.html\u0022\u003e\u003cu\u003eClick here for the questions\u003c/u\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e1)\u003cbr /\u003eint Fibinocci(int n)\u003cbr /\u003e{\u003cbr /\u003e   if(n\u003d\u003d1)\u003cbr /\u003e       return 1;\u003cbr /\u003e   else\u003cbr /\u003e       n+Fibinocci(n-1);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e2)\u003cbr /\u003evoid reverse(char*str)\u003cbr /\u003e{\u003cbr /\u003e   if(*str !\u003d \u0027\\0\u0027)\u003cbr /\u003e               reverse(str+1);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e3)\u003cbr /\u003eint Factorial(int n)\u003cbr /\u003e{\u003cbr /\u003e   if(n\u003d\u003d1)\u003cbr /\u003e        return 1;\u003cbr /\u003e   else\u003cbr /\u003e       return(n*Factorial(n-1);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e4)\u003cbr /\u003evoid MoveTower(int disk, int source, int dest, int spare):\u003cbr /\u003e{\u003cbr /\u003e   if(disk \u003d\u003d 1)\u003cbr /\u003e       printf(\u0022Move top disc from %d to %d\\n\u0022,source,desc);\u003cbr /\u003e   else\u003cbr /\u003e   {\u003cbr /\u003e       MoveTower(disk - 1, source, spare, dest); \u003cbr /\u003e       printf(\u0022Move top disc from %d to %d\\n\u0022,source,desc);            \u003cbr /\u003e                   // Step 2\u003cbr /\u003e       MoveTower(disk - 1, spare, dest, source);\u003cbr /\u003e   }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e5)\u003cbr /\u003eint gcd(int a,int b)\u003cbr /\u003e{\u003cbr /\u003e   if(b\u003d\u003d0)\u003cbr /\u003e       return(a);\u003cbr /\u003e   else\u003cbr /\u003e       return(gcd(b,a(mod)b);\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e6)\u003cbr /\u003earr is an array containing N integers.You can also change the program by keeping characters.k is initially 0.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003evoid permutation(int *arr, int N, int k)\u003cbr /\u003e{\u003cbr /\u003e   static level \u003d -1;\u003cbr /\u003e   level \u003d level+1;\u003cbr /\u003e   arr[k] \u003d level;\u003cbr /\u003e\u003cbr /\u003e    if (level \u003d\u003d N)\u003cbr /\u003e   {\u003cbr /\u003e       if(arr!\u003d0)\u003cbr /\u003e       for(int i\u003d0; i \u003c N;i++)\u003cbr /\u003e         printf(\u0022%d\u0022,arr[i]);     \u003cbr /\u003e   }\u003cbr /\u003e   else\u003cbr /\u003e     for (int i \u003d 0; i \u003c N; i++)\u003cbr /\u003e         if (arr[i] \u003d\u003d 0)\u003cbr /\u003e             permutation(arr, N, i);\u003cbr /\u003e  level \u003d level-1;\u003cbr /\u003e  arr[k] \u003d 0;\u003cbr /\u003e}   \u003cbr /\u003e\u003cbr /\u003e7)void combinations(char*str,int no)\u003cbr /\u003e{\u003cbr /\u003e        int temp1\u003d0;\u003cbr /\u003e        int i,count,n\u003d1,num,len;\u003cbr /\u003e        \u003cbr /\u003e   for(i\u003d0;*(str+i)!\u003d\u0027\\0\u0027;i++);\u003cbr /\u003e   len\u003di;\u003cbr /\u003e   \u003cbr /\u003e   for(i\u003d0;i \u003c len;i++)\u003cbr /\u003e                n\u003d2*n;\u003cbr /\u003e        temp\u003d(int*)malloc(len*sizeof(int));\u003cbr /\u003e        for(i\u003d0;i \u003c len;i++)\u003cbr /\u003e                *(temp+i)\u003d0;\u003cbr /\u003e        for(num\u003d0;num \u003c\u003d n;num\u003dnum+1)\u003cbr /\u003e        {\u003cbr /\u003e                temp1\u003dnum;\u003cbr /\u003e                for(i\u003d0;i \u003c len;i++)\u003cbr /\u003e                {\u003cbr /\u003e                        *(temp+i) \u003d temp1%2;\u003cbr /\u003e                        temp1\u003dtemp1/2;\u003cbr /\u003e                }\u003cbr /\u003e                count\u003d0;\u003cbr /\u003e                for(i\u003d0;i \u003c len;i++)\u003cbr /\u003e                {\u003cbr /\u003e                        if(*(temp+i)\u003d\u003d1)\u003cbr /\u003e                                count++;\u003cbr /\u003e                }\u003cbr /\u003e                if(count\u003d\u003dno)\u003cbr /\u003e      { \u003cbr /\u003e      for(i\u003d0;i \u003c len;i++)\u003cbr /\u003e             {\u003cbr /\u003e                 if(*(temp+i)\u003d\u003d1)\u003cbr /\u003e                        printf(\u0022%c\u0022,*(str+i));\u003cbr /\u003e             }\u003cbr /\u003e          printf(\u0022\\n\u0022);\u003cbr /\u003e                        \u003cbr /\u003e   \u003cbr /\u003e        }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e8)\u003cbr /\u003e\u003cb\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/09/sorting-mergesort.html\u0022\u003eMergesort\u003c/a\u003e\u003c/b\u003e:a is an array of n intergers,temp is just a temporary array.low is initially 0 and high is n-1.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003evoid mergesort(int *a,int *temp,int low,int hi)\u003cbr /\u003e{\u003cbr /\u003e   int mid;\u003cbr /\u003e   if(hi\u003d\u003dlow)\u003cbr /\u003e   {\u003cbr /\u003e       return;\u003cbr /\u003e   }\u003cbr /\u003e   else\u003cbr /\u003e   {\u003cbr /\u003e       mid\u003d(low+hi)/2;\u003cbr /\u003e       mergesort(a,temp,low,mid);\u003cbr /\u003e       printf(\u00221\\n\u0022);\u003cbr /\u003e       mergesort(a,temp,mid+1,hi);\u003cbr /\u003e       printf(\u00222\\n\u0022);\u003cbr /\u003e       merge(a,temp,low,mid+1,hi);\u003cbr /\u003e    }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003evoid merge(int a[],int temp[],int left,int rig,int r)\u003cbr /\u003e{\u003cbr /\u003e   printf(\u0022%d %d %d\\n\u0022,left,rig,r);\u003cbr /\u003e   int i,l,n,k;\u003cbr /\u003e   l\u003drig-1;\u003cbr /\u003e   k\u003dleft;\u003cbr /\u003e   n\u003dr-left+1;\u003cbr /\u003e   while(left\u003c\u003dl\u0026amp;\u0026amp;rig\u003c\u003dr)             \u003cbr /\u003e   {\u003cbr /\u003e        if(a[left]\u003c\u003da[rig])\u003cbr /\u003e            temp[k++]\u003da[left++];\u003cbr /\u003e        else\u003cbr /\u003e            temp[k++]\u003da[rig++];\u003cbr /\u003e   }\u003cbr /\u003e   while(left\u003c\u003dl)\u003cbr /\u003e        temp[k++]\u003da[left++];\u003cbr /\u003e   while(rig\u003c\u003dr)                \u003cbr /\u003e        temp[k++]\u003da[rig++];         \u003cbr /\u003e   for(i\u003d0;i \u003c n;i++,r--)                \u003cbr /\u003e        a[r]\u003dtemp[r];\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cb\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/sorting-quick-sort.html\u0022\u003eQuicksort\u003c/a\u003e\u003c/b\u003e:a is an array of n integers.left is initially 0 and right is n-1.\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003evoid quick(int *a, int left, int right)\u003cbr /\u003e{\u003cbr /\u003e   int temp,i,k;\u003cbr /\u003e   temp\u003dleft;\u003cbr /\u003e   if (left\u003e\u003dright)\u003cbr /\u003e   {      \u003cbr /\u003e       return;\u003cbr /\u003e   }\u003cbr /\u003e \u003cbr /\u003e   k\u003d(left+right)/2;\u003cbr /\u003e   swap(a,left,k);\u003cbr /\u003e   for (i\u003dleft+1;i\u003c\u003dright;i++)\u003cbr /\u003e   {\u003cbr /\u003e        if (a[i] \u003c a[left])\u003cbr /\u003e        {\u003cbr /\u003e            swap(a,++temp,i);\u003cbr /\u003e        }\u003cbr /\u003e    }\u003cbr /\u003e\u003cbr /\u003e    swap(a,left,temp); //swap a[left] and a[temp]\u003cbr /\u003e    quick(a,left,temp-1);\u003cbr /\u003e    quick(a,temp+1,right);\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/solutions-to-questions-on-recursion.html","title":"Solutions to Questions on recursion"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d7274857883340341063\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/7274857883340341063/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/7274857883340341063"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/7274857883340341063"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-4693712771154292482"},"published":{"$t":"2007-11-27T10:10:00.000-08:00"},"updated":{"$t":"2007-11-29T08:10:14.104-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Minimum Value of  a Binary Search Tree"},"content":{"type":"html","$t":"Question:\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eWrite a C program to find the minimum value in a binary search tree.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree\u003cbr /\u003e{\u003cbr /\u003e       int data;\u003cbr /\u003e       struct binarysearchtree* left;\u003cbr /\u003e       struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003etree min(tree T)\u003cbr /\u003e{\u003cbr /\u003e if (T\u003d\u003dNULL)\u003cbr /\u003e    return NULL;\u003cbr /\u003e else\u003cbr /\u003e {\u003cbr /\u003e    if(T-\u0026gt;left\u003d\u003dNULL)\u003cbr /\u003e        return T;\u003cbr /\u003e    else\u003cbr /\u003e      return min(T-\u0026gt;left);\u003cbr /\u003e }\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/minimum-value-of-binary-search-tree.html","title":"Minimum Value of  a Binary Search Tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d4693712771154292482\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/4693712771154292482/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/4693712771154292482"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/4693712771154292482"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-5026865349729429365"},"published":{"$t":"2007-11-27T08:58:00.000-08:00"},"updated":{"$t":"2007-11-27T23:40:05.706-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C program to delete a tree"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eWrite a C program to delete a tree\u003c/span\u003e(i.e, free up its nodes)\u003cbr /\u003e\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree\u003cbr /\u003e{\u003cbr /\u003e      int data;\u003cbr /\u003e      struct binarysearchtree* left;\u003cbr /\u003e      struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003evoid tree_free(tree T)\u003cbr /\u003e{\u003cbr /\u003e  if (T\u003d\u003dNULL)\u003cbr /\u003e     return;\u003cbr /\u003e  else\u003cbr /\u003e  {\u003cbr /\u003e      tree_free(T-\u0026gt;left);\u003cbr /\u003e      tree_free(T-\u0026gt;right);\u003cbr /\u003e      free(T);\u003cbr /\u003e  }\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick  Here For Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/c-program-to-delete-tree.html","title":"C program to delete a tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d5026865349729429365\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/5026865349729429365/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/5026865349729429365"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/5026865349729429365"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-5789212924950322782"},"published":{"$t":"2007-11-27T08:36:00.000-08:00"},"updated":{"$t":"2007-11-29T08:05:00.749-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C program to determine the number of nodes in a binary tree"},"content":{"type":"html","$t":"Question:\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eWrite a C program to determine the number of elements(or size) in a binary tree?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e\u003cpre\u003e\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003estruct binarysearchtree\u003cbr /\u003e{\u003cbr /\u003e      int data;\u003cbr /\u003e      struct binarysearchtree* left;\u003cbr /\u003e      struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003eint tree_size(tree  T)\u003cbr /\u003e{\u003cbr /\u003e  if(T\u003d\u003dNULL)\u003cbr /\u003e     return 0;\u003cbr /\u003e  else\u003cbr /\u003e  {\u003cbr /\u003e     return 1+tree_size(T-\u0026gt;left)+tree_size(T-\u0026gt;right);\u003cbr /\u003e  }\u003cbr /\u003e}\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/c-program-to-determine-number-of-nodes.html","title":"C program to determine the number of nodes in a binary tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d5789212924950322782\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/5789212924950322782/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/5789212924950322782"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/5789212924950322782"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-5933929877702581758"},"published":{"$t":"2007-11-27T08:24:00.000-08:00"},"updated":{"$t":"2007-11-29T08:06:09.569-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"C program to find the height of a binary search tree"},"content":{"type":"html","$t":"Question:\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eWrite a C program to find the depth or height of a binary tree\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e#include\u0026lt;stdio.h\u0026gt;\u003cbr /\u003e\u003cpre\u003estruct binarysearchtree\u003cbr /\u003e{\u003cbr /\u003e       int data;\u003cbr /\u003e       struct binarysearchtree* left;\u003cbr /\u003e       struct binarysearchtree* right;\u003cbr /\u003e};\u003cbr /\u003etypedef struct binarysearchtree* tree;\u003cbr /\u003e\u003cbr /\u003eint max(int a,int b)\u003cbr /\u003e{\u003cbr /\u003e       if(a \u0026gt;\u003db)\u003cbr /\u003e               return a;\u003cbr /\u003e       else\u003cbr /\u003e               return b;\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003eint height(tree T)\u003cbr /\u003e{\u003cbr /\u003e  if(T\u003d\u003dNULL)\u003cbr /\u003e       return 0;\u003cbr /\u003e  else\u003cbr /\u003e  {\u003cbr /\u003e       int h1\u003dheight(T-\u0026gt;left);\u003cbr /\u003e       int h2\u003dheight(T-\u0026gt;right);\u003cbr /\u003e       return 1+max(h1,h2);\u003cbr /\u003e  }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/trees-programming-interview-questions.html\u0022\u003e\u003cu\u003eClick Here For More Questions\u003c/u\u003e \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/c-code-to-find-height-of-binary-search.html","title":"C program to find the height of a binary search tree"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d5933929877702581758\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/5933929877702581758/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/5933929877702581758"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/5933929877702581758"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-8459773068205114310"},"published":{"$t":"2007-11-26T21:19:00.000-08:00"},"updated":{"$t":"2007-11-27T07:55:59.634-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Logical Puzzles-3"},"content":{"type":"html","$t":"\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/11/logical-puzzles-3.html\u003eClick here for the questions \u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e1)\u003cbr /\u003e\u003cbr /\u003e2)3,\u003cbr /\u003e The number obtained by dividing 48 with 4 is 12 which is even while all the others get odd number for the same.\u003cbr /\u003e\u003cbr /\u003e3)4,\u003cbr /\u003e The sequence has to be AON,EWR,IEV,MMZ\u003cbr /\u003e\u003cbr /\u003e4)2\u003cbr /\u003e The remaining 3 are input devices.\u003cbr /\u003e\u003cbr /\u003e5)2\u003cbr /\u003e The remaining 3 represent an image.\u003cbr /\u003e\u003cbr /\u003e6)3\u003cbr /\u003e Trousers can only take a plural form while others can also take a singular form.\u003cbr /\u003e\u003cbr /\u003e7)\u003cbr /\u003e\u003cbr /\u003e8)\u003cbr /\u003e\u003cbr /\u003e9)4\u003cbr /\u003e All the other three lie inside a cell.   \u003cbr /\u003e\u003cbr /\u003e10)\u003cbr /\u003e\u003cbr /\u003e11)4\u003cbr /\u003e\u003cbr /\u003e12)3\u003cbr /\u003e\u003cbr /\u003e13)1\u003cbr /\u003e\u003cbr /\u003e14)2\u003cbr /\u003e\u003cbr /\u003e15)3\u003cbr /\u003e\u003cbr /\u003e16)3\u003cbr /\u003e\u003cbr /\u003e17)1\u003cbr /\u003e\u003cbr /\u003e18)3\u003cbr /\u003e\u003cbr /\u003e19)3\u003cbr /\u003e\u003cbr /\u003e20)4"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/solutions-to-logical-puzzles-3.html","title":"Solutions to Logical Puzzles-3"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d8459773068205114310\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/8459773068205114310/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/8459773068205114310"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/8459773068205114310"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-3194526689693726095"},"published":{"$t":"2007-11-26T08:05:00.000-08:00"},"updated":{"$t":"2007-11-27T07:52:41.953-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Logical Puzzles-1"},"content":{"type":"html","$t":"\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/10/logical-puzzles-1.html\u003eClick here for the questions\u003c/a\u003e \u003cbr /\u003e\u003cbr /\u003eWe need 3 cuts to cut a cube into 6 equal pieces,with one cut in each dimension.Maximum identical pieces obtained with n cuts[if n is a factor of 3] \u003d (n/3 + 1)^3, with n/3 cuts, we form n/3 + 1 equal pieces.If we need to get maximum number of identical cubes with some number of cuts then the number of cuts in all the dimensions should be equal if possible or almost equal. \u003cbr /\u003eThe number of identical pieces formed with l,n,m cuts in the 3 demensions are (l+1)*(n+1)*(m+1).\u003cbr /\u003e\u003cbr /\u003e1)3,Here there are 6,7,8 cuts in each dimension\u003cbr /\u003e\u003cbr /\u003e2)2\u003cbr /\u003e\u003cbr /\u003e3)4,Here the number of cuts are 7,7,6 in the 3 dimensions.\u003cbr /\u003e\u003cbr /\u003e4)1\u003cbr /\u003e\u003cbr /\u003e5)3\u003cbr /\u003e\u003cbr /\u003eAll the problems from 6-18 are based mostly on imagination.Note that 27 identical pieces have no color at all i.e they are inner pieces.\u003cbr /\u003e\u003cbr /\u003e6)3\u003cbr /\u003e\u003cbr /\u003e7)4\u003cbr /\u003e\u003cbr /\u003e8)1\u003cbr /\u003e\u003cbr /\u003e9)3\u003cbr /\u003e\u003cbr /\u003e10)2\u003cbr /\u003e\u003cbr /\u003e11)2\u003cbr /\u003e\u003cbr /\u003e12)4\u003cbr /\u003e\u003cbr /\u003e13)1\u003cbr /\u003e\u003cbr /\u003e14)4\u003cbr /\u003e\u003cbr /\u003e15)3\u003cbr /\u003e\u003cbr /\u003e16)1\u003cbr /\u003e\u003cbr /\u003e17)4\u003cbr /\u003e\u003cbr /\u003e18)1\u003cbr /\u003e\u003cbr /\u003e19)2\u003cbr /\u003e\u003cbr /\u003e20)4"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/solutions-to-logical-puzzles-1.html","title":"Solutions to Logical Puzzles-1"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d3194526689693726095\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/3194526689693726095/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/3194526689693726095"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/3194526689693726095"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-6830097426352504721"},"published":{"$t":"2007-11-25T21:32:00.000-08:00"},"updated":{"$t":"2007-11-27T16:22:29.359-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Basic C Interview Questions"},"content":{"type":"html","$t":"\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/10/basic-c-interview-questions.html\u003eClick here for the questions\u003e\u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e1)To check for it, create two pointers,and set each to the start of the list. Update each as follows:\u003cbr /\u003e\u003cbr /\u003ewhile (pointer1) {\u003cbr /\u003e pointer1 \u003d pointer1-\u003enext;\u003cbr /\u003e pointer2 \u003d pointer2-\u003enext;\u003cbr /\u003e if (pointer2) pointer2\u003dpointer2-\u003enext;\u003cbr /\u003e if (pointer1 \u003d\u003d pointer2) {\u003cbr /\u003e   print (\u0022circular linked list\\n\u0022);\u003cbr /\u003e }\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e2)Union x : 1101791232  21.500000\u003cbr /\u003eUnion y : 100 d 0.000000\u003cbr /\u003e\u003cbr /\u003e3)It is an object of some class whose purpose is to indicate that a real object of that class does not exist. One common use for a null object is a return value from a member function that is supposed to return an object with some specified properties but cannot find such an object.\u003cbr /\u003e\u003cbr /\u003e4) Java,Smalltalk,Eiffel,Sather.\u003cbr /\u003e\u003cbr /\u003e5)A container class is a class that is used to hold objects in memory or\u003cbr /\u003eexternal storage. A container class acts as a generic holder. A\u003cbr /\u003econtainer class has a predefined behavior and a well-known interface. A\u003cbr /\u003econtainer class is a supporting class whose purpose is to hide the\u003cbr /\u003etopology used for maintaining the list of objects in memory. When a\u003cbr /\u003econtainer class contains a group of mixed objects, the container is\u003cbr /\u003ecalled a heterogeneous container; when the container is holding a group\u003cbr /\u003eof objects that are all the same, the container is called a homogeneous\u003cbr /\u003econtainer.\u003cbr /\u003e\u003cbr /\u003e6)fffffff0\u003cbr /\u003e\u003cbr /\u003e7)C was the C++ predecessor. As it\u0027s name implies, a lot of C remains in C++. Although not actually being more powerful than C, C++ allows the programmer to more easily manage and operate with Objects, using an OOP (Object Oriented Programming) concept.\u003cbr /\u003e\u003cbr /\u003eC++ allows the programmer to create classes, which are somewhat similar to C structures. However, to a class can be assigned methods, functions associated to it, of various prototypes, which can access and operate within the class, somewhat like C functions often operate on a supplied handler pointer.\u003cbr /\u003e\u003cbr /\u003eAlthough it is possible to implement anything  which C++ could implement in C, C++ aids to standarize a way in which objects are created and managed, whereas the C programmer who implements the same system has a lot of liberty on how to actually implement the internals, and style among programmers will vary a lot on the design choices made.\u003cbr /\u003e\u003cbr /\u003eIn C, some will prefer the handler-type, where a main function initializes a handler, and that handler can be supplied to other functions of the library as an object to operate on/through. Others will even want to have that handler link all the related function pointers within it which then must be called using a convention closer to C++.\u003cbr /\u003e\u003cbr /\u003eTo finish this discussion, C++ applications are generally slower at runtime, and are much slower to compile than C programs. The low-level infrastructure for C++ binary execution is also larger. For these reasons C is always commonly used even if C++ has alot of popularity, and will probably continue to be used in projects where size and speed are primary concerns, and portable code still required (assembly would be unsuitable then).\u003cbr /\u003e\u003cbr /\u003e8)Incomplete types\u003cbr /\u003erefers to pointers in which there is non availability of the\u003cbr /\u003eimplementation of the referenced location or it points to some location\u003cbr /\u003ewhose value is not available for modification.\u003cbr /\u003e\u003cbr /\u003e        int *i\u003d0x400  // i points to address 400\u003cbr /\u003e        *i\u003d0;        //set the value of memory location pointed by i.\u003cbr /\u003e\u003cbr /\u003e9)Printf : Call by value\u003cbr /\u003e  Scanf : Call by reference\u003cbr /\u003e\u003cbr /\u003e10)a const pointer means the pointer which represents the address of one value. so if you declare a pointer inside the function, it doesn\u0027t have scope outside the function. if it is also available to the outside function whenever we declare a pointer as const.\u003cbr /\u003e\u003cbr /\u003e11)Type casting must be done wheneever the data type of the variable to which u r gonna assign some values is diff from the data type of the variable on the right side.\u003cbr /\u003e\u003cbr /\u003efor instance;\u003cbr /\u003e\u003cbr /\u003efloat f;\u003cbr /\u003eint i \u003d 10 , j \u003d 5 ;\u003cbr /\u003e\u003cbr /\u003ef \u003d (float) ( i / j ) ;\u003cbr /\u003e\u003cbr /\u003ef -------\u003e left side variable.\u003cbr /\u003ei -------\u003e right side variable.\u003cbr /\u003e\u003cbr /\u003ebut always make sure that the size of the var on the left is greater than that of the right. else there will be data loss.\u003cbr /\u003e\u003cbr /\u003eA type cast should not be used to override a const or volatile declaration. Overriding these type modifiers can cause the program to fail to run correctly.\u003cbr /\u003eA type cast should not be used to turn a pointer to one type of structure or data type into another. In the\u003cbr /\u003erare events in which this action is beneficial, using a union to hold the values makes the programmer.s\u003cbr /\u003eintentions clearer.\u003cbr /\u003e \u003cbr /\u003e12)he answer is the standard library function qsort(). It.s the easiest sort by far for several reasons:\u003cbr /\u003eIt is already written.\u003cbr /\u003eIt is already debugged.\u003cbr /\u003eIt has been optimized as much as possible (usually).\u003cbr /\u003eVoid qsort(void *buf, size_t num, size_t size, int (*comp)(const void *ele1, const void *ele2));\u003cbr /\u003e \u003cbr /\u003e13)The answer depends on what you mean by quickest. For most sorting problems, it just doesn\u0027t matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one answer. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.\u003cbr /\u003eThere are three sorting methods in this author.s .toolbox. that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.\u003cbr /\u003e \u003cbr /\u003eThe Quick Sort\u003cbr /\u003eThe quick sort algorithm is of the .divide and conquer. type. That means it works by reducing a sorting\u003cbr /\u003eproblem into several easier sorting problems and solving each of them. A .dividing. value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets.the algorithm will still work properly.\u003cbr /\u003e \u003cbr /\u003eThe Merge Sort\u003cbr /\u003eThe merge sort is a .divide and conquer. sort as well. It works by considering the data to be sorted as a\u003cbr /\u003esequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don.t fit into memory. It also can be implemented as a stable sort.\u003cbr /\u003e \u003cbr /\u003eThe Radix Sort\u003cbr /\u003eThe radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.\u003cbr /\u003e \u003cbr /\u003e14)Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.\u003cbr /\u003e\u003cbr /\u003e15)The preprocessor is used to modify your program according to the preprocessor directives in your source code. Preprocessor directives (such as #define) give the preprocessor specific instructions on how to modify your source code. The preprocessor reads in all of your include files and the source code you are compiling and creates a preprocessed version of your source code. This preprocessed version has all of its macros and constant symbols replaced by their corresponding code and value assignments. If your source code contains any conditional preprocessor directives (such as #if), the preprocessor evaluates the condition and modifies your source code accordingly.\u003cbr /\u003e The C preprocessor is used to modify your program according to the preprocessor directives in your source code. A preprocessor directive is a statement (such as #define) that gives the preprocessor specific instructions on how to modify your source code. The preprocessor is invoked as the first part of your compiler program.s compilation step. It is usually hidden from the programmer because it is run automatically by the compiler.\u003cbr /\u003e\u003cbr /\u003e16)The standard C library provides several functions for converting strings to numbers of all formats (integers, longs, floats, and so on) and vice versa.\u003cbr /\u003e \u003cbr /\u003eThe following functions can be used to convert strings to numbers:\u003cbr /\u003eFunction Name Purpose\u003cbr /\u003eatof() Converts a string to a double-precision floating-point value.\u003cbr /\u003eatoi() Converts a string to an integer.\u003cbr /\u003eatol() Converts a string to a long integer.\u003cbr /\u003estrtod() Converts a string to a double-precision floating-point value and reports any .leftover. numbers that could not be converted.\u003cbr /\u003estrtol() Converts a string to a long integer and reports any .leftover. numbers that could not be converted.\u003cbr /\u003estrtoul() Converts a string to an unsigned long integer and reports any .leftover. numbers that could not be converted. \u003cbr /\u003e\u003cbr /\u003e17)\u003cbr /\u003eThe standard C library provides several functions for converting numbers of all formats (integers, longs, floats, and so on) to strings and vice versa\u003cbr /\u003e \u003cbr /\u003eThe following functions can be used to convert integers to strings:\u003cbr /\u003eFunction Name Purpose\u003cbr /\u003eitoa() Converts an integer value to a string.\u003cbr /\u003eltoa() Converts a long integer value to a string.\u003cbr /\u003eultoa() Converts an unsigned long integer value to a string.\u003cbr /\u003e \u003cbr /\u003eThe following functions can be used to convert floating-point values to strings:\u003cbr /\u003eFunction Name Purpose\u003cbr /\u003eecvt() Converts a double-precision floating-point value to a string without an embedded decimal point.\u003cbr /\u003efcvt() Same as ecvt(), but forces the precision to a specified number of digits.\u003cbr /\u003egcvt() Converts a double-precision floating-point value to a string with an embedded decimal point.\u003cbr /\u003e \u003cbr /\u003e18)The heap is where malloc(), calloc(), and realloc() get memory.\u003cbr /\u003eGetting memory from the heap is much slower than getting it from the stack. On the other hand, the heap\u003cbr /\u003eis much more flexible than the stack. Memory can be allocated at any time and deallocated in any order. Such\u003cbr /\u003ememory isn\u0027t deallocated automatically; you have to call free().\u003cbr /\u003eRecursive data structures are almost always implemented with memory from the heap. Strings often come\u003cbr /\u003efrom there too, especially strings that could be very long at runtime. If you can keep data in a local variable (and allocate it from the stack), your code will run faster than if you put the data on the heap. Sometimes you can use a better algorithm if you use the heap.faster, or more robust, or more flexible. It\u0027s a tradeoff.\u003cbr /\u003eIf memory is allocated from the heap, it.s available until the program ends. That\u0027s great if you remember to deallocate it when you.re done. \u003cbr /\u003e\u003cbr /\u003e19)n++ takes more than one instruction, ++n is faster. n++ has to store n, increment the variable and return n, while ++n increment n and return without storing the previous value of n.\u003cbr /\u003e\u003cbr /\u003e20) If a program is large, it is subdivided into a number of smaller programs that  are called modules or subprograms. If a complex problem is solved using more modules, this approach is known as modular programming. \u003cbr /\u003e\u003cbr /\u003e21)expression if (a\u003d0) always return false\u003cbr /\u003e      expression if (a\u003d1) always return true\u003cbr /\u003e\u003cbr /\u003e22)Malloc is dynamic memory allocation,it  allocates the memory and initialize garbage value.Calloc is similar to malloc but only difference is initialize zero\u003cbr /\u003e\u003cbr /\u003e23)A middle level language\u003cbr /\u003e\u003cbr /\u003e24)Overloading is polymorphism which is one of the characteristics of Object oriented programming. C is not and object oriented language like C++ or Java. Therefore, no overloading, inheritance, etc.\u003cbr /\u003e\u003cbr /\u003e25)Static int variable are accessed only inside the file where it is defined. Thus we can have same variable name  in 2 files if the variable is defined as static. The scope of the variable is limited to the file in which it is defined.\u003cbr /\u003e\u003cbr /\u003eOn the other hand if the variable is not defined as static and defined globally then it can be accessed across the files. To access the variable which is global variable and declared and defined in file A, keyword \u0022extern\u0022 is used in front of the variable in file B. This indicated to compiler while compiling that the variable is defined in some other file other than B and continues compiling and while linking the variable it search for the actual definition and links."},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/solutions-to-basic-c-interview.html","title":"Solutions to Basic C Interview Questions"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d6830097426352504721\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/6830097426352504721/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/6830097426352504721"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/6830097426352504721"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-7235800711729024157"},"published":{"$t":"2007-11-25T21:27:00.000-08:00"},"updated":{"$t":"2007-11-27T06:20:24.754-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Combinations"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion:Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.So given 5\u003c\u003dN\u003c\u003d100 5\u003c\u003dM\u003c\u003d100 and M\u003c\u003dN.Compute the EXACT value of: N!/(M!*(N-M)!) The final value of C will fit in a 32-bit Pascal LongInt or a C long. So deduce an approach based on this assumption given.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:At a mere glance,this problem may seem to have a direct solution,though it isn\u0027t upon a long thought.The naive approach to calculate combination of N things taken M at a time is obtained by mere application of formula,which mean finding N! ,M! and (N-M)! and the putting them in the expression.But as N and M are independently large enough for overflows to occur in N! and M! calculations.\u003cbr /\u003eOne of the approaches to solve this problem,based on prime factorization can be formulated in the following manner.\u003cbr /\u003e\u003cbr /\u003eConsider a prime P whose exponents in N!,M! and (N-M)! are p1,p2 and p3 respectively.\u003cbr /\u003e\u003cbr /\u003etherefore the exponent of P in N!/M!*(N-M)! is p1+p2-p3.\u003cbr /\u003e\u003cbr /\u003eThis way we can store the exponents of all primes \u0026lt;\u003d the largest prime which divides N.\u003cbr /\u003e\u003cbr /\u003eOne this is done ,we can merely multiply all these  primes each raised to its exponent to get the required answer.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003eNow getting on to the tricky part of finding the exponent of a prime P in N!\u003cbr /\u003e\u003cbr /\u003eIn general ,if P is any prime,then the no of P\u0027s in N! is given by\u003cbr /\u003eSum (floor(n/P^i)) for P^i \u003c\u003d N   This apparently weird formula can be explained with ease!!  consider the numbers 1,2,3,.........,,N.Every Pth number is divisible by P.So all those multiples of P put together contribute floor(N/P) to the power of P.  Similarly every P^2th number is divisible by P^2.And each of them have already contributed 1 to power of P in previous iteration,as each of them are divisible by P.So each of them contribute an additional 1, which means they all together contribute floor(N/P^2) to the already sum.  These terms of contribution go on till we have P^i \u003c\u003d N,hence the summation Sum (floor(N/P^i)) for P^i \u003c\u003d N   The Cpp implementation of above task is given below    \u003cpre\u003e\u003cbr /\u003e#include\u0026lt;iostream\u0026gt;\u003cbr /\u003eusing namespace std;\u003cbr /\u003e#include\u0026lt;cmath\u0026gt;\u003cbr /\u003e#include\u0026lt;cstdlib\u0026gt;\u003cbr /\u003e#include\u0026lt;cstdio\u0026gt;\u003cbr /\u003e#include\u0026lt;vector\u0026gt;\u003cbr /\u003etypedef vector\u0026lt;int\u0026gt; powers;\u003cbr /\u003evoid insert(vector\u0026lt;powers\u0026gt; \u0026amp;P,int i,vector\u0026lt;int\u0026gt; V,int size)\u003cbr /\u003e{\u003cbr /\u003e       vector\u0026lt;int\u0026gt; temp\u003dP[i-1];\u003cbr /\u003e        //calculation of exponent of each prime\u003cbr /\u003e       for(int j\u003d0;j \u0026lt;size \u0026amp;\u0026amp; i!\u003d1;j++)\u003cbr /\u003e       {\u003cbr /\u003e               while(i%V[j]\u003d\u003d0)\u003cbr /\u003e               {\u003cbr /\u003e                       temp[j]++;\u003cbr /\u003e                       i/\u003dV[j];\u003cbr /\u003e               }\u003cbr /\u003e       }\u003cbr /\u003e       P.push_back(temp);\u003cbr /\u003e}\u003cbr /\u003eint main()\u003cbr /\u003e{\u003cbr /\u003e       vector\u0026lt;int\u0026gt; V;\u003cbr /\u003e       vector\u0026lt;powers\u0026gt; P;\u003cbr /\u003e       V.push_back(2);\u003cbr /\u003e       bool flag;\u003cbr /\u003e       int N,R;\u003cbr /\u003e       for(int i\u003d3;i\u0026lt;100;i+\u003d2)\u003cbr /\u003e       {\u003cbr /\u003e               flag\u003dtrue;\u003cbr /\u003e               for(int j\u003d0;V[j]*V[j] \u0026lt;\u003di;j++)\u003cbr /\u003e               {\u003cbr /\u003e                       if(i%V[j]\u003d\u003d0)\u003cbr /\u003e                       {\u003cbr /\u003e                               flag\u003dfalse;\u003cbr /\u003e                               break;\u003cbr /\u003e                       }\u003cbr /\u003e               }\u003cbr /\u003e               if(flag)\u003cbr /\u003e               {\u003cbr /\u003e                       V.push_back(i);\u003cbr /\u003e               }\u003cbr /\u003e       }\u003cbr /\u003e       int size\u003dV.size();\u003cbr /\u003e       vector\u0026lt;int\u0026gt; temp(size,0);\u003cbr /\u003e       P.push_back(temp);\u003cbr /\u003e       P.push_back(temp);\u003cbr /\u003e       for(int i\u003d2;i\u0026lt;\u003d100;i++)\u003cbr /\u003e       {\u003cbr /\u003e               insert(P,i,V,size);\u003cbr /\u003e       }\u003cbr /\u003e       while(cin \u0026gt;\u0026gt; N \u0026gt;\u0026gt;R)\u003cbr /\u003e       {\u003cbr /\u003e               if(N\u003d\u003d0 \u0026amp;\u0026amp; R\u003d\u003d0)\u003cbr /\u003e               {\u003cbr /\u003e                       return(0);\u003cbr /\u003e               }\u003cbr /\u003e               else\u003cbr /\u003e               {\u003cbr /\u003e                       long sol\u003d1;\u003cbr /\u003e                       for(int i\u003d0;i\u0026lt;size;i++)\u003cbr /\u003e                       {\u003cbr /\u003e\u003cpre\u003e               sol*\u003d(long)pow((double)V[i],P[N][i]-P[R][i]\u003cbr /\u003e                    -P[N-R][i]); //P\u003cspan style\u003d\u0022font-style: italic;\u0022\u003ei\u003c/span\u003e^(p1-p2-p3)\u003cbr /\u003e                       }\u003cbr /\u003e                       cout\u0026lt;\u0026lt;N\u0026lt;\u0026lt;\u0022 things taken \u003cbr /\u003e                       \u0022\u0026lt;\u0026lt;R\u0026lt;\u0026lt;\u0022 at a time is \u003cbr /\u003e                       \u0022\u0026lt;\u0026lt;sol\u0026lt;\u0026lt;\u0022 exactly.\u0022\u0026lt;\u0026lt;\u0027\\n\u0027;\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e               }\u003cbr /\u003e\u003cbr /\u003e       }\u003cbr /\u003e       return(0);\u003cbr /\u003e}\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/interesting-aspects-of-factorisation.html\u0022\u003eClick Here for More questions\u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/combinations.html","title":"Combinations"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d7235800711729024157\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/7235800711729024157/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/7235800711729024157"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/7235800711729024157"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-3620806722925720598"},"published":{"$t":"2007-11-25T12:03:00.000-08:00"},"updated":{"$t":"2007-11-27T16:20:37.651-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Solutions to Logical Puzzles-2"},"content":{"type":"html","$t":"\u003ca href\u003dhttp://placementsindia.blogspot.com/2007/11/logical-puzzles-2.html\u003eClick here for the questions \u003c/a\u003e\u003cbr /\u003e\u003cbr /\u003e1)3 \u003cbr /\u003eIt is of the form 0^2+2,1^2+2,3^2+2,6^2+2,10^2+2,.....\u003cbr /\u003eThe sequence of n is 0,1,3,6,10,... so the next n is 15 \u003d\u003e 15^2+2\u003cbr /\u003e\u003cbr /\u003e2)2\u003cbr /\u003eThe function is S(n)\u003dS(n-1)*(n+2) + 3 ,n\u003e1\u003cbr /\u003e                    \u003d6  ,n\u003d1\u003cbr /\u003e\u003cbr /\u003e3)1\u003cbr /\u003eIt is of the form S(n)*3+2 for even and S(n)*2-3 for odd where S(n) is the nth element.\u003cbr /\u003eSo 7th element \u003d 239*2-3\u003d475\u003cbr /\u003e\u003cbr /\u003e4)2\u003cbr /\u003eThe function is S(n)\u003d(n+2)^3 -2\u003cbr /\u003e\u003cbr /\u003e5)1\u003cbr /\u003eThe numbers in the sequence is a combination of n^2 and n^3 and n is odd.\u003cbr /\u003e\u003cbr /\u003e6)2\u003cbr /\u003eThe function is S(n)\u003dS(n-1)*n-n n\u003e1\u003cbr /\u003e                    \u003d3 n\u003d1\u003cbr /\u003e\u003cbr /\u003e7)\u003cbr /\u003e\u003cbr /\u003e8)1\u003cbr /\u003eThe function is S(n)\u003d(S(n-1)-1)*(n-1) n\u003e1\u003cbr /\u003e     \u003d8    n\u003d1\u003cbr /\u003e\u003cbr /\u003e9)\u003cbr /\u003e\u003cbr /\u003e10)"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/solutions-to-logical-puzzles-2.html","title":"Solutions to Logical Puzzles-2"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d3620806722925720598\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/3620806722925720598/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/3620806722925720598"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/3620806722925720598"}],"author":[{"name":{"$t":"Bapineedu"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-3070323370486904944"},"published":{"$t":"2007-11-25T10:28:00.000-08:00"},"updated":{"$t":"2007-11-27T07:54:40.422-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Number of  ways to express a number as summation of consecutive numbers"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion.All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer ,you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:\u003cbr /\u003e2+3+4\u003d(1+2+3+4)-(1)\u003cbr /\u003e     \u003d(1+2+3+4+5)-(1+2+3)\u003cbr /\u003e     \u003d(1+2+3+4+5+6+7+8+9)-(1+2+3+4+5+6+7+8)\u003cbr /\u003e\u003cbr /\u003eThis shows that the no of solutions to this problem is the no of tuples (n,m) such that\u003cbr /\u003egiven number K can be expressed as K\u003d(1+2+..........+n)-(1+2+3+...........+m) \u003cbr /\u003eand n \u0026gt; m\u003cbr /\u003e\u003cbr /\u003ei.e K\u003dn*(n+1)/2 -m*(m+1)/2\u003cbr /\u003e    \u003d(n-m)(n+m+1)/2\u003cbr /\u003e   2*k\u003d(n-m)*(n+m+1)\u003cbr /\u003eIf we put the factor n-m\u003dp and (n+m+1)\u003dq,we get S\u003d2*k\u003dp*q\u003cbr /\u003eAs p+q\u003d2*n+1 is odd and S is even either n-m is odd otherwise n+m+1 is odd.\u003cbr /\u003eThis leaves out with finding out the no of odd divisors of S,which can be easily done using prime factorization.\u003cbr /\u003eif S\u003d(2^p)*(3^q)*(5^r)*(7^s)......\u003cbr /\u003e\u003cbr /\u003ethen the solution is (q+1)*(r+1)*(s+1)*..  i.e the no of odd divisors of S.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/interesting-aspects-of-factorisation.html\u0022\u003e\u003cb\u003e\u003cu\u003eclick here for more questions\u003c/u\u003e\u003c/b\u003e \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/number-of-ways-to-express-number-as.html","title":"Number of  ways to express a number as summation of consecutive numbers"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d3070323370486904944\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/3070323370486904944/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/3070323370486904944"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/3070323370486904944"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-8775333578018473209"},"published":{"$t":"2007-11-25T08:41:00.000-08:00"},"updated":{"$t":"2007-11-27T02:13:41.716-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Tree Arithmetic"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e1)If a tree has N nodes, then how many are the edges?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:Every node has a parent except the root.Each edge associates a node with its child.So the number of edges are N-1.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e2)Prove that there exists only a single path from each node to the root?\u003c/span\u003e\u003cbr /\u003eSolution:If there are more than 1 paths from a node to the root,it means there are more than 1 parents for one of the ancestors of the node concerned, which is impossible in a tree.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e3)Prove that the depth of a tree is always equal to the height of the tree?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution: Height of a tree is the height of the root.Depth of a tree is the depth of the deepest node, which is the number of edges from root to it.This should also be the node which defines the height of the root,otherwise we end up with a contradiction.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e4)The structure of a typical tree is to have in each node ,besides it data, a pointer to each of its children.But this might be infeasible if there aren’t fixed number of children at each node.So how do modify this data structure to accommodate variable no of children at each node?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:Well the answer to this is child sibling relationship.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e5)What are the maximum and minimum depths of a binary search tree?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:In a binary tree of N nodes,the maximum depth is N-1   when it develops only on 1 side and the minimum is floor(log(N)).\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e6)How many are the no of null pointers for a binary tree of N nodes?\u003c/span\u003e\u003cbr /\u003e \u003cbr /\u003eSolution: Total no of pointer\u003d2*N. And each edge is associated with 1 pointer.\u003cbr /\u003eSo the no of null pointer is 2*N-(N-1)\u003dN+1 .\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e7)Distinguish inorder , preorder and postorder traversals properly?\u003c/span\u003e\u003cbr /\u003eSolution: \u003cspan style\u003d\u0022font-style:italic;\u0022\u003eInorder traversal\u003c/span\u003e:Left subtree is first processed ,followed by root and then by right subtree.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-style:italic;\u0022\u003ePreorder\u003c/span\u003e: root is first processed followed by left and right subtrees.There is no order defined between left and right children.Essentially left and right subtrees are traversed only after the root is traversed.\u003cbr /\u003e   \u003cbr /\u003e\u003cspan style\u003d\u0022font-style:italic;\u0022\u003ePostorder\u003c/span\u003e:Left  and right children are traversed before traversing root.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e8)How is a binary tree different from binary search tree?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:In Binary search tree, all the elements in the left subtree are \u0026lt;\u003d root and all the elements in the right subtree are \u0026gt;\u003d root,which is not the case with all the binary trees.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e9)Recursive calls have always been employed in the case of trees because of their recursive structural property.But linked lists aren’t that different .But why recursion is not that advisable in the case of lists?(A little theoretical …. Think in terms of limited stack size of your machine)\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003eSolution:The depth of a well built tree of N nodes  is log(N).So recursive calls are affordable most of the times as stack overflow is seldom possible.But if recursive calls are employed for lists, then the order of recursive call stack size is N which \u003cbr /\u003eis not feasible for large N.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e10)What are the complexities of insertion,deletion on a binary search tree?\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:Insertion in a well built binary search tree is O(logN) and so is the deletion.This is under assumption that depth of tree is O(logN).\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight:bold;\u0022\u003e11)Show that the maximum number of nodes in a binary tree of height H is 2^(H+1) -1\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:In a binary tree of height H ,with maximum number of nodes,all the levels should be completely filled.At depth d, the number of nodes should be 2^d.\u003cbr /\u003eTherefore, the total number of nodes \u003d1+2+4+....+2^H\u003d2^(H+1)-1."},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/10/tree-arithmetic.html","title":"Tree Arithmetic"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d8775333578018473209\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/8775333578018473209/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/8775333578018473209"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/8775333578018473209"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-9117263081959706421"},"published":{"$t":"2007-11-25T05:26:00.000-08:00"},"updated":{"$t":"2007-11-27T02:11:06.656-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Run time Analysis of QuickSort ,Nature of Input,Pivot strategies"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion Determine the running time of QuickSort for\u003cbr /\u003e\u003cbr /\u003ea.Sorted input\u003cbr /\u003eb.reverse -ordered input\u003cbr /\u003ec.random input\u003cbr /\u003ed. When all the elements are equal\u003cbr /\u003e\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:This solution is being written with the assumption that middle element of the array is chosen as the pivot.The answers differ based on the pivot selection as well.\u003cbr /\u003e\u003cspan style\u003d\u0022font-style: italic;\u0022\u003ea.Sorted input\u003c/span\u003e\u003cbr /\u003e   In the case of sorted input,the left and right pointers of the sub arrays pass each other with out a single swap in all the iterations.The problem is divided in to 2 equal problems in all but the base case of unit size array.Hence the recurrence relation for this case is \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eT(N)\u003d2*T(N/2)+O(N)\u003c/span\u003e.Hence the complexity in this case is \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN)\u003c/span\u003e.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-style: italic;\u0022\u003eb.reverse-ordered input\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eThis case is identical to the previous case except that we have so many swaps in each iteration.The left and right pointers swap the content on each increment in their directions.This effects only the O(N) part of the recurrence relation that we have in the previous case.But as the swap is of complexity O(1), the complexity of each iteration remains the same.And the division of the array is still even.So the complexity doesn\u0027t change.Hence it is still \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN)\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-style: italic;\u0022\u003ec.Random Input\u003c/span\u003e\u003cbr /\u003eWell there are theorems asserting that the complexity of quicksort on a random input is \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN)\u003c/span\u003e.We will prove it by considering evenly the chances of even and worst splits.\u003cbr /\u003elet\u0027s consider that good and bad splits alternate in   the iterations, with good splits in the best case (N/2) and bad ones in  the worst (N-1).\u003cbr /\u003eSo every two levels, the array\u0027s been cut in half,which means, it\u0027s still exponential reduction -- \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN )\u003c/span\u003e.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-style: italic;\u0022\u003ed. When all the elements are equal\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eIt is as good as the sorted array.So the complexity is \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN).\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion The ones who are familiar with QuickSort might  also  be well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:Choosing the middle element never makes it unlikey that the QuickSort will require quadratic time.One might encounter an input in which the middle element is always the maximum in all iterations.Then the complexity will be quadratic.\u003cbr /\u003e\u003cbr /\u003eexample:a\u003d{1,3,2} choosing 3 as pivot produces 2 subproblems , one of size 0 and other of size 2.In the next iteration,with out loss of generality take 2 as the pivot.It produces a sub array of size 1 and another of size 0.Thus an input can always be generated in such a way that QuickSort routine always gives rise to 2 subarrays,one of them being  of size 0.Hence quadratic time is not always avoidable.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion What is the worst-case behavior (number of comparisons) for quick sort?\u003c/span\u003e\u003cbr /\u003eSolution:As we have seen in the previous question,because of a bad pivot selection we might at the worst run in to quadratic time complexity.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:\u003cbr /\u003ea.The first element of the array\u003cbr /\u003eb.The last element of the array\u003cbr /\u003ec.The middle element of the array\u003cbr /\u003ed.The largest element of the array\u003cbr /\u003ee.The median of the array\u003cbr /\u003ef.Any of the above\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:while the choices a,b,c will always not guarantee \u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eO(NlogN)\u003c/span\u003e complexity,choice d always gives quadratic run time.choice e guarantees even partition of the array.Hence it is the optimal partition.\u003cbr /\u003ehence the sol is e.\u003cbr /\u003e\u003cbr /\u003e\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion In its worst case QuickSort behaves like:\u003cbr /\u003ea.Bubble sort\u003cbr /\u003eb.Selection sort\u003cbr /\u003ec.Insertion sort\u003cbr /\u003ed.Bin sort\u003cbr /\u003e\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:In the worst ,the pivot selected will always be the maximum element leading to quadratic time complexity.In this case as it depicts the behaviour of bubble sort,where in maximum element always bubbles to the end.\u003cbr /\u003e\u003cbr /\u003efor more questions \u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/sorting-quick-sort.html\u0022\u003eclick here \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/11/interview-questions-on-sorting-quick.html","title":"Run time Analysis of QuickSort ,Nature of Input,Pivot strategies"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d9117263081959706421\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/9117263081959706421/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/9117263081959706421"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/9117263081959706421"}],"author":[{"name":{"$t":"Rajiv"}}]},{"id":{"$t":"tag:blogger.com,1999:blog-32064785.post-4639919839024894583"},"published":{"$t":"2007-11-25T05:21:00.000-08:00"},"updated":{"$t":"2007-11-27T08:08:27.838-08:00"},"category":[{"scheme":"http://www.blogger.com/atom/ns#","term":"Solutions"}],"title":{"type":"text","$t":"Quick Sort routine to find the kth smallest element in an array"},"content":{"type":"html","$t":"\u003cspan style\u003d\u0022font-weight: bold;\u0022\u003eQuestion Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.\u003c/span\u003e\u003cbr /\u003e\u003cbr /\u003eSolution:We make slight modifications to the quicksort routine to find the \u003cspan style\u003d\u0022font-style: italic;\u0022\u003ek\u003c/span\u003eth smallest element.Like in normal quicksort,we choose a pivot and partition the remaining array in to 2 sub arrays.At this stage,we have 3 possibilities.\u003cbr /\u003e\u003cbr /\u003e1)the size of the first sub array is k-1 ,in which case pivot itself is the \u003cspan style\u003d\u0022font-style: italic;\u0022\u003ek\u003c/span\u003eth smallest.\u003cbr /\u003e2)the size of the first sub array is greater than k ,in which case \u003cspan style\u003d\u0022font-style: italic;\u0022\u003ek\u003c/span\u003eth smallest element is to be recursively searched in the first sub-array.\u003cbr /\u003e\u003cbr /\u003e3)the size of the first sub array is less than k-1 ,in which case reuired  element is to be recursively searched in the second sub-array.\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003eHence unlike quicksort where each problem gives rise to 2 subproblems,here each problem gives rise to only 1 sub problem.\u003cbr /\u003e\u003cbr /\u003ePseudo Code:\u003cbr /\u003e\u003cbr /\u003eQuickSelect(Array A, n, k)\u003cbr /\u003epivot \u003d A [Random(1, n)]\u003cbr /\u003eX\u003d{x | x belongs to A and x \u0026lt;\u003dpivot}\u003cbr /\u003eY\u003d{x | x belongs to A and x \u0026gt;\u003dpivot}\u003cbr /\u003eif size(X) \u003d k\u003cbr /\u003e      return pivot;\u003cbr /\u003eelse if size(X) \u0026lt; k\u003cbr /\u003e    return QuickSelect(Y,n-size(X)-1,k-size(X)-1);\u003cbr /\u003eelse\u003cbr /\u003e    return QuickSelect(X,size(X),k); \u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\u003ca href\u003d\u0022http://placementsindia.blogspot.com/2007/10/sorting-quick-sort.html\u0022\u003eclick here \u003c/a\u003e"},"link":[{"rel":"alternate","type":"text/html","href":"http://placementsindia.blogspot.com/2007/10/quick-sort-routine-to-find-kth-smallest.html","title":"Quick Sort routine to find the kth smallest element in an array"},{"rel":"replies","type":"text/html","href":"http://www.blogger.com/comment.g?blogID\u003d32064785\u0026postID\u003d4639919839024894583\u0026isPopup\u003dtrue","title":"0 Comments"},{"rel":"replies","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/4639919839024894583/comments/default","title":"Post Comments"},{"rel":"self","type":"application/atom+xml","href":"http://placementsindia.blogspot.com/feeds/posts/default/4639919839024894583"},{"rel":"edit","type":"application/atom+xml","href":"http://www.blogger.com/feeds/32064785/posts/default/4639919839024894583"}],"author":[{"name":{"$t":"Rajiv"}}]}]}});