Software Engineering Interview Questions - 9

Q1. Compress a given string using Huffman Encoding.


Q2. Given two integers a and b, find their
       a) greatest common divisor (gcd)
       b) least common multiple (lcm)

Hint: a) Use euclidean division algorithm
                  gcd(a, 0) = a
                  gcd(a,b) = gcd (b, a mod b)

        b) Use relation lcm(a, b) = (|a*b|)/gcd(a, b)


Q3. Design an algorithm to efficiently compute binomial coefficient C(n , k).

Hint: Use recurrence formula
       C(n, k)= C(n-1, k-1) + C(n-1, k)
       C(0, k )=  0 for all integers k>0
       C(n, 0) = 1 for all integers n>=0

       Similarly, there is pascal's rule and pascal's triangle


Q4.  Design an algorithm to evaluate a fully parenthesized  infix expression/Polish Notation.
Example: (((2 * 5) - (1 * 2)) / (11 - 9))

Hint: Use a single stack data structure with operator precedence.


Q5.  Design an algorithm to evaluate a partially parenthesized infix expression.
Example:  (2 * 5 - 1 * 2) / (11 - 9)

Hint:  Use a character stack that stores the operators, a number stack for operands, and follow precedence rule.


Q6.  Design an algorithm to evaluate a prefix expression.

Example: / -  * 2 5 * 1 2 - 11 9

Hint: Read the whole expression in a stack and perform operation from last to first.


Q7.  Design an algorithm to evaluate a postfix expression/Reverse Polish Notation.
     

Q8. Design an algorithm to convert a fully parenthesized infix expression into prefix expression.


Q9. Design an algorithm to convert a fully parenthesized infix expression into postfix expression.
Hint: a) Use a character stack to store operators. Print the operands. Pop operands when we get a closing bracket.
b) Shunting-Yard  Algorithm


Q10. Given a graph G={V, E} where V is the set of vertices and E is the set of edges with unit weight and two vertices S and T, design an algorithm to find the smallest path between the nodes.

Hint: Perform a bidirectional Breadth First Search from both S and T.