Algos & DS Problems

Here are some interesting problems (and their solutions) that I enjoyed solving and discussing over our class' forum.

• Loop in a List Problem
  Easy Question - Given a linked list how will you detect it contains a loop in O(n) time and using O(1) memory?
  Difficult Question - How will you remove the loop using the same constraints?
  Solution
  Analysis
  
• Code Generator Problem
  Input is an expression tree, which may contain unary, binary or ternary mathematical, logical or relational operators and operands that are integers. Your task is to design a program that creates a .C file containing a main function, which solves the particular case of the input tree. Example - Like for example

                                   +
                         ~                   *
                         4              3          -1   
                              
  which is equivalent to 
  x = ~4 + 3 * -1 ;
  
  So one possible solution can be -
  
  int main()
  {
  	int t1, t2, t3, t4, t5, t6 ;	
  	t4 = 4 ;
  	t2 = ~ t4 ;
  	t5 = 3 ;
  	t6 = -1 ;
  	t3 = t5 * t6 ;
  	t1 = t2 * t3 ;
  }
  Solution
  

• Tree List Recursion Problem
  The two data structures -- an ordered binary tree and a circular doubly linked list, store sorted elements, but they look very different. But the nodes that make up the two have the same type structure -- they each contain an element and two pointers. The only difference is that in the tree, the two pointers are labeled "small" and "large" while in the list they are labeled "previous" and "next". The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The "small" pointer should play the role of "previous" and the "large" pointer should play the role of "next". The list should be arranged so that the nodes are in increasing order. The function should be able to return the head or the tail of the list.
  Solution
  
  
• Infix Expression Problem
  We all know that traversing the expression tree in postorder and preorder will give the expression in postfix and prefix notation respectively. But the same is not true for inorder traversal. For example, Expression tree for (a+b)*c, would give postorder expression as ab+c*, preorder as *+abc and inorder as a+b*c which is wrong. This is because exp tree do not include parentheses. Your task is to traverse the tree in inorder such that it gives correct infix expression. It is very easily to obtain the infix exp in fully parenthesized form like (((a)+(b))*(c)), but this is not considered a good solution. You have to minimize the number of parentheses used only to the neccessary ones.
  Solution