Practice Problems with Sample Solutions

----------------

1.  Consider the following class structure for (unbalanced) 
    binary trees of integers.

interface node
{
 boolean empty();
//...
}

class nil implements node
{
public boolean empty() {return true;}
//...
}

class vertex implements node
{  int item;
   node left, right;
   vertex(int h) 
     {item=h; left=right=new nil();} // usually, only one nil is needed
   vertex(int h, node l, node r)
     {item=h;  left=l;  right=r;}
    
   public boolean empty() {return false;}
   public boolean leaf() { return left.empty() && right.empty();}
...
}

// 1a Write a function to return the total number of nodes in the tree.
add it to the interface and both subclasses.  What is its average case
time complexity?

in interface, add:  int size();
in class nil, add: int size() {return 0;}
in class vertex, add: int size() {return 1+ left.size() + right.size();}

Average complexity: T(n)=2*T(n/2)+1  has O(n) solution
Worst-case complexity: T(n) = T(n-1)+1, also has O(n) solution, but
recursion shouldn't be used because worst case means tree is imbalanced.

***
NOTE THAT FOR THIS EXAM YOU WILL NOT BE REQUIRED TO USE RECURRENCE RELATIONS
IN YOUR SOLUTIONS BUT KNOWING THEM MAY WILL BE HELPFUL.  They provide the
best answers to the "explain why" parts of some questions.
***

// 1b Write a function to search for a value in a binary search tree
// Determine also its average time 
// complexity class by writing a recurrence relation

in interface node, add: boolean search(int x);
in class nil:  public boolean search(int x) {return false;}
in class vertex: 
public boolean search(int x)
{ return x==item || (x<item && left.search(x)) || (x>item && right.search(x)); 
/*
In case of a generic type T extends Comparable<T>:
int comp = head.compareTo(x);
  return comp==0 || ((comp<0 && left.search(x)) || (comp>0 && right.search(x)));

Or:

if (comp<0) return left.search(x);
else if (comp>0) return right.search(x);
else return 0;

Or:
 node current = this;
 while (!current.empty())
 {
   vertex cv = (vertex)current;
   if (x<cv.item) current=cv.left;
   else if (x>cv.item) current = cv.right;
   else return true;
 }//while
 return false; // returns false if reached nil node.
*/
}
// or: if (comp==0) return true; else if (comp<0) return left.search(x);
//     else return right.search(x);

T(n) = T(n/2) + 1 has O(log n) average complexity.  In the case of a 
worst case tree, it would be T(n)=T(n-1)+1 which is O(n).

Bonus: if we can't assume that it's a binary SEARCH tree, then we would have
to write this function recursively and search both left AND right, and the
recurrence relation would be T(n) = 2T(n/2)+1, which is O(n):

non-binary search:
public boolean nb_search(int x) {
  return x==cv.item || left.nb_search(x) || right.nb_search(x);
}

2. Given the above class for trees, consider the following code:

   node A = new vertex(6, new vertex(4), new nil());

   Explain if the following lines of code are valid, and if not valid,
   whether it will cause a compiler error or runtime error:

2a.   node i = A.left;

      compiler error: A's static type is node, not vertex

2b.   node i = ((vertex)A).right;

      this is ok because of the type cast.

2c.   int x = ((vertex)i).item;  // where i is from above

      this will compile, but since i's dynamic type is nil, there will
      be a runtime type-casting exception.

3. Show how to augment (edit) the existing interface classes to implement
   an operation on trees that determines if x is an item in the tree:

   boolean search(int x)

in node: add  boolean search(int x);
in nil: add  public boolean search(int x) { return false; }
in vertex: add  
 public boolean search(int x)
 {return x==item || (x<item && left.search(x)) || (x>item && right.search(x));}

3b. What are the average and worst case complexity classes of your program.

   Average case O(log n) because T(n)=T(n/2)+1
   Worst case O(n) because T(n)=T(n-1)+1

  Warning: for some functions such as size(), which must traverse the entire
  tree, both the average (T(n)=2T(n/2)+1) and worst (T(n)=T(n-1)+1) are
  O(n).  But you shouldn't use recursion unless the worst case is also
  T(n)=2T(n/2)+1 because T(n/2) means that the depth of recursion is log(n).

3c. Given the following tree:

      5
    /   \
   2     7
  / \   / \
 1   4 6   8
            \
             9
What order will the values be printed using an INORDER, PREORDER and POSTORDER
traversal.
INORDER (left-item-right): 1 2 4 5 6 7 8 9 (sorted order)
PREORDER (item-left-right): 5 2 1 4 7 6 8 9
POSTODER (right-left-item): 9 8 6 7 4 1 2 5 (inverse of PREORDER)


4. What are the *worst-case* time complexities of the following operations:

   a.  inserting into priority heap   O(log n)
   b.  searching for a value in a priority heap   O(n)
   c.  searching for a value in a hash table  O(n)
         this is the absolute worst case where every value results in
         a hash collision. usually hash tables give O(1) search time.
   d.  searching for a value in an AVL binary search tree: O(log n)
   e.  Dijkstra's algorithm in general    
       O(n*n) where n is the number of nodes, because in the worst case
       each node can have a direct edge to every other node.
   f.  removing a value from an AVL tree:  O(log n)
   g.  removing a value from the end of a cicular queue:  O(1)
   h.  an in-order traversal on an AVL tree.
       O(n).  No matter the structure, a traversal has to visit every
       node in the tree, and therefore will be at least O(n).  To be more 
       precise, the traversal function has time complexity approximated by
       the recurrence relation T(n) = 2T(n/2)+1, which has solution T(n)=2n-1.

4b. What are the (amortized) average case complexities of the following
    operations:

   a. inserting into a priority heap: O(1)
   b. inserting into an AVL tree : O(log n)
   c. inserting into a hash table: O(1)


5. Consider the following recursive function:

   int bif(int n)
   {
     if (n<2) return n;
      else return bif(n-1) * bif(n-2);
   }

 5b. Rewrite the program using a dynamic programming matrix.

This function only take one variable, so we only need a 1D array:

int bif2(int n)  // bottom-up solution
{
   int[] M = new int[n+1]; // why is it n+1?
   M[1] = 1;  // M[0] is already 0 when created
   for (int i=2;i<=n;i++)
      M[i] = M[i-1] * M[i-2];
   return M[n];
}

or:  (top-down solution, sometimes called "memoization")

 Within the same class:
   int[] M;

   public int dbif(int n)// public interface function, inits matrix
   {
     M = new int[n+1];
     M[1] = 1;
     return rbif(n);
   }

   protected int rbif(int n)  
   {
     if (n>1 && M[n]==0) M[n] = rbif(n-1) * rbif(n-2);
     return M[n];
   }
// this problem has a special case for M[0].  We're using 0 for "no value",
// but 0 is also the correct answer for bif(0), so we need to be specific
// about when this special case applies in the code.

 5c. Do the same for this:

  int k(int n, int c)
  {
     if (n<1 || c<2) return 0;
     return Math.max(k(n-1,c), k(n-1,c-2)+2);
  }

  // top down:
  int[][] M; // external, belongs to same class
  public int k(int n, int c)
  {
     M = new int[n+1][c+1];
     // initialize all values to -1, which means "no value present":
     for(int i=0;i<=n;i++) for(int k=0;k<=c;k++) M[i][k] = -1;
     return ktd(n,c);
  }
  public int ktd(int n, int c)
  {
     if (M[n][c]<0)
       {
          if (n<1 || c<2) M[n][c] = 0;
          else M[n][c] = Math.max(ktd(n-1,c), ktd(n-1,c-2)+2);
       }
     return M[n][c];
  }

// note that, unlike some other DP problems, we can't use the default
// value of 0 to represent "no answer present", so we had to initialized
// the array to -1.

// bottom-up
public int kbu(int n, int c)
{
    int[][]M = new int[n+1][c+1];
    for(int i=1;i<=n;i++)
      for(int k=2;k<=c;k+=1) // note k+=2 each time
         {
             M[i][k] = Math.max(M[i-1][k],M[i-1][k-2]+2);
         }
    return M[n][c];
}

6.  Explain the difference between nodes in the closed/interior and nodes
    on the open/frontier in Dijkstra's algorithm. 

    The interior contains all nodes that we've already found the best path to.
    The frontier are nodes we've visited, but for which better routes may 
    still exist.  The most important step of the algorithm is to select the
    minimum-cost value from the frontier.



7. Insert the following nodes into an AVL tree. show when a rotation
is required.  2 8 6 1 3 9.  Insert additional nodes (make up your numbers)
so that all 4 rotations are used.

   	    2
	     \
	      8
	     /
	    6

need RL rotation:

         6
       /   \
      2     8

then:

         6
       /   \
      2     8
     / \     \
    1   3     9

now insert:

         6
       /   \
      2     8
     / \     \
    1   3     9
               \
                10
  
this requires a RR rotation on the 8

         6
       /   \
      2     9
     / \   / \
    1   3 8   10


As a general hint: whatever tree you construct, ALWAYS make sure that it's
still a binary search tree.


8. If I ask this, it would be considered one of the harder questions.
Give a specific example of deleting from an AVL tree where more
than one rotation is required to balance the tree. There are four
distinct rotations: LL, RR, RL and LR, the rotations "RL" and "LR"
should be counted as ONE rotation, not two.

                        8
                    /      \
                   /        \
                  5          15
                 / \       /    \
                3   6    10     18
               /        /  \   /  \
              1        9   12 16  20
                            \
                             13

This is an AVL tree as the balance property is satisfied at every node
But removing the 6 will first cause a LL rotation on the left subtree,
which will then decrease the height of left subtree by one, causing
a new imbalance to be detected at the root node, An RL rotation centered
on 8 is then needed to balance the tree.

REMEMBER: when sketching an AVL tree, make sure it's still a binary search tree!


9. What's wrong with the following code. Pinpoint where the error is and
   explain why it's an error (don't say how to fix the error).

   public abstract class shape implements Comparable<shape> {
     public int x, y; // position of shape
     public abstract int area();
     public int compareTo(shape other) {
        return this.area() - other.area();
     }
     public shape(int x0, int y0) { x=x0;  y=y0;}
   }
   //... in some other class:
   public static void main(String[] args) {
      shape[] A = new shape[10];
      for(int i=0;i<10;i++) A[i] = new shape(i,i*2);
   }

The only thing wrong is on the last line in main, which tries to
call the contructor of the abstract class.  You can only call an
abstract class constructor from a subclass.  You can't create instances
of an abstract class.  NOTHING else is wrong and pointing out other things
that are wrong would result in a point deduction.


10.  Assume that you want to represent a SET of integers (these
integers can, for example, index some values in an array).  You want
to be able to insert, delete and search for values in the set with
maximum efficiency. Furthermore, you also want to be able to determine
quickly both the smallest and the largest index of the "set".  For
example, if the set consists of {3,2,6,1,8,7}, you want to be able to
determine quickly that the smallest value of the set is 1 and that the
largest is 8, as well as be able to search/insert/delete other values.
What kind of data structure would you use and WHY?

Use a balanced binary search tree such as an AVL tree (or "red-black"
tree, java.util.TreeSet).
All described operations are worst-case log(n) time.  Search
for the smallest (largest) value by following the left (right) branch
to the end.  Because we're representing a SET, there need not be
duplicates, which is one problem for balanced binary search trees.

11.  Determine the output of the following program:

class A {
    int f() { return 1; }
}

public class B extends A {
    @Override
    int f() { return 2; }
    
    int g(A x) { return 10; }
    int g(B x) { return 20; }    

    public static void main(String[] args) {
        A a = new B();
        B b = new B();
        System.out.println( a.f() );
        System.out.println( b.g(a) );
    }    
}

prints 2, then 10.  This problem distinguishes "overriding" from
"overloading".  When functions such as g share a name but take
different types of arguments, it's called overloading.  Overloading is
resovled at COMPILE time.  The compiler only knows that the type of a
is A, and so it will call int g(A x), not int g(B x).  Overriding uses
"dynamic dispatch": the function to be called is based on the dynamic
type that's known at runtime, so a.f() will call the version of f in
B, which is the type of the runtime object.


12. Given the following local variables inside some function:

     Optional<String> Aopt;
     String A;

  a. Write code to print the string inside the optional if it exists

     Aopt.ifPresent(x -> System.out.print(x));

  b. Assign A to the string inside Aopt if it exists, and to "" if it doesn't
     Under no circumstances can your code throw an exception.

  The no exceptions requirement implies that you can't call .get().
     
     A = Aopt.orElse("");

  Note: don't try to do it this way:

  String A = "";
  Aopt.ifPresent(s -> A = s);

  because Java does not allow you to change a local variable inside a
  lambda.  It would only work if dna is defined as an INSTANCE variable
  inside a class:  Aopt.ifPresent(s -> this.A = s) would be ok.
  

13. Assume:

class A
{
   public void f() {}
}

class B extends A
{
  public void g() {}
}

...

A m = new A();
A n = new B();


// determine if there's an error in the following code, and whether
// it's a compiler or runtime error:

a.  n = m;
    This is fine. the static types of n and m are both A. The pointer to
    the B object is changed to a pointer to the A object.
b.  n.f();
    This calls the f() inherited from A by B
c.  n.g();
    this is a compiler error: the static type of n is A, which doesn't have g
d.  ((B)n).g();
    this is OK.  The type cast is legal at compile-time and runtime
e.  ((B)m).g();
    This is a runtime error. The type cast is legal at compile time but
    not at runtime.

f. (extra)  ((String)n).length());  This will not compile because String
   and A are unrelated classes (neither is a subclass of the other).



14. Given a Trie with strings as keys, what advantages would a trie have
    over a hashmap?

    a key can be a prefix of an entire subtree of related keys and values,
    for example, all phone numbers under "516-463".

   14a. explain why not all "nodes" in a trie contain values.
   (hint: this is best answered by an example)
   
: intermediate nodes may have to be created in order for keys with values
  to exist:

        c
        |
        a
        |
        t : value


   14b. Assume that the trie contains n nodes and m values, what is
   the worst case time complexity of searching, inserting or removing a
   value from the trie?

   This is a bit of a trick question but if you understood how tries work
   it's not really that hard:   O(length of longest key).


15. Explain how Dijkstra's algorithm avoids cycles.

: by ignoring nodes already on the interior.

15b. What is the absolute worst case time complexity of Dijkstra's
algorithm in terms of the number of possible nodes (vertices) in
graph.

: O(n*n)  (n-squared), because in the worst case there could be a direct
edge from every node to every other node: the inner loop of the algorithm
"for each neighbor" will therefore also run O(n) times.

15c.  Given the following weighted graph

  A ----4----> B ----1----> F
  |            |            |
  8            2            3
  |            |            |
  |            |            |
  v            v            v
  C <----3---- D ----3----> E

Apply Dijkstra' single-source shortest path algorithm to source node A

Apply Dijkstra' single-source shortest path algorithm to source node B


For A, order of nodes in interior

  Interior | Frontier    order taken from frontier
  -------------------
  (A,0,_)  | (A,0,_)       1
  (B,4,A)  | (B,4,A)       2
           | (C,9,A)       * (replaced by better node)
           | (D,6,B)       4
  (F,5,B)  | (F,5,B)       3
           | (E,8,F)       5
  (D,6,B   | (C,8,D)       6
  (E,8,F)
  (C,8,D)

16. Apply the Needle-Wunsch algorithm to the following sequences:

A=    .ATGACTG
B=    .TGATGC

with the following scoring scheme:

  int score(int i, int k) {
     if (A.charAt(i)==B.charAt(k)) return 1; else return 0;
  }
  int w() {return 0;}

Show the matrix generated by the algorithm.
Display one optimal alignment (traceback) (without the . at the front)


ATGACTG-
 ||| ||
-TGA-TGC
Alignment score: 5
      .   T   G   A   T   G   C
   .  0   0   0   0   0   0   0
   A  0   0   0   1   1   1   1
   T  0   1   1   1   2   2   2
   G  0   1   2   2   2   3   3
   A  0   1   2   3   3   3   3
   C  0   1   2   3   3   3   4
   T  0   1   2   3   4   4   4
   G  0   1   2   3   4   5   5

How about under the following Scheme:

   int score(int i, int k) {
        if (A.charAt(i) == B.charAt(k)) return 2;
        else return -1;
   }
   int W() { return -1; }

ATGACTG-
 ||| ||
-TGA-TGC
Alignment score: 7
      .   T   G   A   T   G   C
   .  0  -1  -2  -3  -4  -5  -6
   A -1  -1  -2   0  -1  -2  -3
   T -2   1   0  -1   2   1   0
   G -3   0   3   2   1   4   3
   A -4  -1   2   5   4   3   3 
   C -5  -2   1   4   4   3   5
   T -6  -3   0   3   6   5   4
   G -7  -4  -1   2   5   8   7



17.  java.util.function.Function is an interface equivalent to:

interface Function<A,B> {
  B apply(A x);
}

Explain what's wrong with the following declaration:

Function<? extends A, ? super B> myfunction;

:? super can only be applied to the domain and ? extends can only be applied
to the codomain (return value).  This declaration does the opposite and
would not compile.