Saturday, April 29, 2017

Fill in the sibling pointer in the binary tree

You are given a binary tree which has a sibling pointer in addition to left and right pointer. The tree has left and right child set correctly but sibling pointer is not yet set. Your task is to traverse the tree and fill in the sibling pointer. A sibling is defined as a node next to the given node at the same level.


In the tree above B and C, and D and E are siblings. So sibling pointer of B should point to C and sibling pointer of D should point to E. Sibling pointer of C and E should be null because they don't have any siblings to the right.

This problem is easily solved using level order traversal as shown below.

class Node {
public:
    Node *left;
    Node *right;
    // Sibling pointer that needs to be set
    Node *sibling;
    // Value stored in the node. For simplicity
    // we assume name to be the value
    std::string name;
};

// Fill in the sibling pointer of a binary tree
void fill_node_with_next_sbiling(Node *node) {
    if (!node)
        return;

    // Initialize the queue with the root node.
    std::queue<node> queue;
    queue.push(node);

    // Set count of current level in the queue to 1.
    int cur_count = 1;
    int child_count = 0;

    Node *prev = NULL;

    while (!queue.empty()) {
        Node *n = queue.front();
        queue.pop();

        // Set the sibling pointer and set previous as current node
        if (prev) {
            prev->sibling = n;
            prev = n;
        } else {
            prev = n;
        }

        cur_count--;

        if (n->left != NULL) {
            queue.push(n->left);
            child_count++;
        }

        if (n->right != NULL) {
            queue.push(n->right);
            child_count++;
        }

        // All nodes in the current level are done.
        // Set the cur_count to next level count 
        // for processing next level
        if (cur_count == 0) {
            cur_count = child_count;
            child_count = 0;
            prev = NULL;
        }

    }
}

Convert a binary search tree into doubly linked list

Converting a binary search tree into doubly linked list is a common interview question. It's a simple question as long as we know it can be solved by extending inorder tree traversal. If you are not familiar with inorder tree traversal, I have described it here. In this problem you are given a binary search tree with left and right child and you are supposed to convert left pointer to predecessor node and right pointer to the successor node. Here is the solution to the problem:

// output list
Node *list = NULL;

void convert_to_doubly_ll(Node *root) {
    if (root == NULL)
        return;

    convert_to_doubly_ll(root->left);

    if (list) {
        list->right = root;
        root->left = list;
    } 
    
    list = root;
    
    Node *right = root->right;
    root->right = NULL;

    convert_to_doubly_ll(right);
}

If you want to do this in place, then all you have to do is pass in the previous node in each recursive call. The code is given below:

void convert_to_doubly_ll_in_place(Node *root, Node **prev) {
    if (root == NULL)
        return;

    convert_to_doubly_ll_in_place(root->left, prev);

    Node *prev_node = *prev;
    Node *right = NULL;

    if (prev_node) {
        prev_node->right = root;
        root->left = prev_node;
    } 
    
    *prev = root;
    
    right = root->right;
    root->right = NULL;

    convert_to_doubly_ll_in_place(right, prev);
}

You can call the above method like this:

Node *root = ....a tree...;
Node *prev=NULL;
convert_to_doubly_ll_in_place(root, &prev);

Friday, April 28, 2017

Tree Problems

Many of the tree problems asked in the interviews can be solved by extending traversal algorithms. There are 4 popular ways a tree can be traversed. They are preorder traversal, post order traversal, inorder and level order traversal. We will look at each of these traversals and some sample interview questions that can be answered using the given traversal.

Preorder Traversal
In preorder traversal you start from root, visit left child first and then right child. The processing for that node is done before processing it's children.
void pre_order(Node *root) {
    if (!root) {
        return;
    }
    // Process the node
    std::cout << root->name << std::endl;

    // Traverse left and right children
    pre_order(root->left);
    pre_order(root->right);
}

Sample Interview Problems:
Given a root and a node in a binary tree, find the path from the root to the node.


Post Order Traversal
In post order traversal you start from root, visit left child first and then right child. The processing for the node is done after processing it's children.
void post_order(Node *root) {
    if (!root) {
        return;
    }

    // Traverse left and right children
    post_order(root->left);
    post_order(root->right);

    // Process the node.
    std::cout << root->name << std::endl;
}




Sample Interview Problems:
Given a binary tree create an in place mirror image of the tree.
Expression evaluation.


In Order Traversal
In in-order traversal you start from root, visit left subtree first and then right subtree. The processing for the node is done before you start traversing right subtree.
void in_order(Node *root) {
    if (!root) {
        return;
    }

    // Traverse left child
    post_order(root->left);

    // Process the node
    std::cout << root->name << std::end;

    // Traverse right child
    post_order(root->right);
}

Sample Interview Problems:
Convert a binary search tree into doubly linked list.

Level Order Traversal
In level-order traversal you start from root, process the root and then move to next level. In the next level you process all the nodes from left to right and then move to next level and so on.
#include <queue>
#include <iostream>
void level_order(Node *node) {
    if (!node)
        return;

    std::queue queue;

    // Count of the nodes in current level
    int cur_count = 0; 

    // Count of the nodes in the next level
    int child_count = 0; 

    queue.push(node);

    // Start with 1 as we have root in the queue
    // to begin with
    cur_count += 1;

    while (!queue.empty()) {
        Node *n = queue.front();
        queue.pop();

        // Process the node. We will just print to 
        // indicate processing.
        std::cout << n->name << " ";
        
        // Decrement of the count of nodes remaining in the
        // queue  for current level.
        cur_count--;

        if (n->left != NULL) {
            queue.push(n->left);
            child_count++;
        }

        if (n->right != NULL) {
            queue.push(n->right);
            child_count++;
        }

        // When we hit a count of 0, we start at next level
        if (cur_count == 0) {
            cur_count = child_count;
            child_count = 0;
            std::cout << std::endl;
        }
    }
}

Sample Interview Problems:
Pretty print a binary tree.
Given a binary tree, return each level as a list.
You have a binary tree.  Lets say you add an extra sibling pointer to it. Can you fill all the sibling pointers to point to it's sibling starting  from the left to the right.


I will add more sample problems as well as provide solutions to as many I can.

Saturday, September 21, 2013

Median and Order statistics

Finding kth median in linear time

The idea is to partition the array we do in quick sort.  Assuming a 0 based index the item that you are looking for is positioned at k-1  if the array is ordered. Here is how we can find that element. First partition the array using a pivot (the pivot partitions the array into two parts; the elements on the left are smaller than the pivot element and elements on the right are greater than the pivot element).  Lets say the pivot index is i. if i equals k-1 then it is your median. Otherwise check if k-1 is less than  i. If it is  then repeat the same process for elements from 0 to i - 1 else repeat the process for elements from i + 1 to the end of partition that you are working on. As we chose the pivot randomly this algorithm would take expected linear time.

Here is the code that implements the above algorithm.

int find_kth_median(int x[],int start, int end, int k) {

 int pivot =  start + ((float)rand() - 1)/INT_MAX * (end - start +1);
 int a = x[pivot];

 int up = end, down = start;
 while(down < up) {

  while(x[down] <= a && down <= end)
   down++;
  while(x[up] > a)
   up--;
  if(down < up) {
   std::swap(x[up], x[down]);
  }
 }

 x[start] = x[up];
 x[up] = a;

 if (up == k-1)
  return x[up];
 else if (up < k-1) 
  return find_kth_median(x,up+1, end, k);
 else
  return find_kth_median(x, start, up -1, k);
}

Here are some of the questions that are similar to the above question:

Given an algorithm that finds median in linear time. How would you find kth element ?

Use the technique above. The idea is simple: find the median of the whole array ( the array will be partitioned around the media). Say the median index is i. Then if k is greater than i repeat the process on the right side of the array else repeat on the left side. Continue until you find the median.

Given a set of elements divide the set into k equal parts

The idea is to find the median of the whole set and then find median of the set at the left and right of the median and then continue so on. This requires O (n log k).

Sunday, October 24, 2010

Java Language Concepts

What's the difference between abstract classes and interface?

interface can only have method signatures on it. It can't have implementations(body of methods) but abstract classes can have implementations. A class can be labeled as abstract even if no methods in the class are abstract. Abstract classes cannot be instantiated. If all the methods in a class are abstract it behaves like interface. Is it? Then why do we need interface? Only limitation of abstract classes is that they are classes which means we cannot extend from more than one abstract class.

What is the difference between static and not static methods?

Static methods can be accessed using class name while non static method requires instance of the class to access it. Both static and non static methods have single copy in the application. So under the hood what is the difference? One important distinction is that static methods cannot be virtual. Other is that static methods don't have access to this pointer. Non static methods take the object (on which it is called as argument). Static and non static methods look like this:



class X {

public static void staticMethod() {

//do sth
}

public void nonStaticMethod() {
//do sth
}
}

Under the hood the compiler generates method like this:

public void staticMethod() {
//do sth
}

public void nonStaticMethod(X this) {
//do sth
}



What is the difference between Comparable and Comparator ?

Comparable can be implemented by any class that requires ordering. compareTo method of the Comparable interface takes another object to which the current object is compared. For example you might have Person object and you have implemented Comparable to compare those objects using the first name and last name. But later your need changes and you have to order person objects based on their address. In this case, with Comparable, you have to change the implementation. You might not want to do that because you might need sorting using first name and last name in other places.So in that case you can always use Comparator interface. The sort method of Collections class can also take Comparator as argument. This helps you sort objects based on your needs. With comparable you are stuck to one implementation.

When do you have to override hashcode method?

When you will be using a hashed container to put your objects in, you need to override hashcode. If you override equals it's always good to override hashcode too. The hashcode provided by Object class in Java Language takes memory address of the object as hashcode. This is not what we want with our objects. For example consider following example:


class Person {

private String name;
private String dob;

public Person(String name, String dob) {
this.name = name;
this.dob = dob;
}
public boolean equals(Object obj) {
//implementation
}

//..


public static void main(String[] args) {

Set<Person> persons = new HashSet<Person>();
Person p1 = new Person("Person1", "12/12/2008");


persons.add(p1);

Person p2 = new Person("Person1", "12/12/2008");
if(persons.contains(p2)) {
//do sth
}

}
}



I am assuming here that person with same name and Date of Birth are equal. Do you think the condition will be true? Not necessarily. It's because the two person objects might get mapped into two different buckets in the hashset. Unless we return same hashcode for two equal objects there is no guarantee that the objects can be located in the hashed containers. So keep in mind that whenever you override equals you should override hashcode and two equal objects should always return same hashcode.

Thursday, October 21, 2010

finally in C/C++

If you have programmed in C/ C++ you know there is no such thing as finally in C/C++. If you have used Java you know how convenient it is with finally to handle resources in code that is exception prone. There is a pretty nice and clean way to simulate finally in C++ (using destructors) but C doesn't have nice and clean way to do it. I am not sure if it is the recommended approach as it utilizes goto keyword. Since I started programming, I have been told not to use goto. Even while I read books i find authors ranting about use of goto. But here is a technique in C that simulates finally using goto.




void do_sth() {

int *arr1 = 0,*arr2 = 0, * arr3 = 0;

//calling function on will return error code, 0 being success
// and other values a failure
arr1 = (int *)malloc(100 * sizeof(int));
if(!arr1)
goto finally; // u wud have free(arr1) without finally

arr2 =(int*) malloc(100 * sizeof(int));

if(!arr2)
goto finally; //u wud have free(arr1) and free(arr2) without finally

arr3 =(int*) malloc(100 * sizeof(int));

if(!arr3)
goto finally; //u wud have free(arr1) and free(arr2) and free(arr3) without finally

//do sth here

finally:
free(arr1);
free(arr2);
free(arr3);
}



This is a simple example showing how you can handle exceptions in memory allocation. This makes sure that everything is freed when function exists and makes code lot cleaner. The resource allocation used here was simple. For example if you were opening 3 files instead. How would the code ? You would probably check if the file handle is valid in finally and if it is valid you would close them. The main advantage of this approach is that your resource handling code is localized. it's not spread over places and also you would write less code with this approach.

Now how would you do same thing in C++? Well C++ has facility for destructor which can do the job for you. When the object goes out of scope, the resource is cleaned up. There are lots of examples in C++ standard library. For example, instead of using dynamic arrays as shown above in C code, you could use std::vector in C++ which takes care of freeing the resources itself. Also there is std::auto_ptr which can be used for exception prone code. Of course auto_ptr doesn't support arrays.For supporting arrays you can use equivalent of boost's scoped_array.

Producer Consumer Problem

Well this is one of the frequently asked questions. It's a good way to see how much you understand multithreading. The solution is pretty simple but it's always good to understand the subtleties. The code would look something like this:

 
public void produce() {

synchronized(queue) {

while(queue.isFull()) {
queue.wait();
}

//produce
queue.enqueue(someObj);

queue.notifyAll();
}
}




public void consume() {

synchronized(queue) {

while(queue.isEmpty()) {
queue.wait();
}

//consume
someObj = queue.dequeue();
//do something with the object

queue.notifyAll();
}

}



The code is pretty simple but even there are things where people get confused easily. First of all both the producer and consumer should synchronize on same object. Beginners tend to forget that. Also notice the use of while loop, when required conditions haven't been met threads are made to wait. A while loop is needed because we are using notifyAll here.notifyAll wakes up all the threads waiting on an object but only one thread will be able to obtain the lock. So in this case only one thread is allowed to proceed and others go back to wait. Another question arising in the context is the placement of notifyAll. Does it have to be the last statement inside synchronize block? The answer is no. It doesn't matter where you keep the notifyAll till it is inside synchronize block. The lock will only be released when synchronize block is escaped.

Recommendation

Never try to do produce consumer problem this way in production code. Always try to use the concurrent collections or facilities provided by the Java Language. For example, you could have used BlockingQueue rather than hand coding the program above.