Interview Algorithms: August 2012

Wednesday, August 29, 2012

Swap without using 3rd variable

Swap Algorithm

A = A + B
B = A - B
A = A - B

You can not use this approach as while adding A & B (A + B), it could result in a "OVERFLOW"

Hence, we use this approach

X := X XOR Y
Y := X XOR Y
X := X XOR Y

Thursday, August 23, 2012

Design Patterns

Wednesday, August 22, 2012

[MySQL] Storage Engines

A storage engine is what stores, handles, and retrieves information from a table. There is no "perfect" or "recommended" storage engine to use, but for most applications the default MyISAM is fine. In MySQL there are 10 different storage engines, though all of them may not be available to you. To get a list of supported storage engines on your MySQL Server, you can do:

mysql -uroot -p

Password:

mysql> show engines;

This should provide a list of supported storage engines for your server. The standard engines supported by MySQL are:

MyISAM

InnoDB

MERGE

MEMORY (HEAP)

BDB (BerkeleyDB)

EXAMPLE

Tuesday, August 21, 2012

Parking Lot

Design Patterns

Chat room

Coffee Vending Machine

Elevator

Sunday, August 19, 2012

Singleton


class Singleton {
    public:
        static Singleton* GetInstance();
    private:
        Singleton();
        static Singleton* pSingleton;        // singleton instance
};

Singleton* Singleton::pSingleton= NULL;

Singleton::Singleton()
{
    // do init stuff
}

Singleton* Singleton::GetInstance()
{
    if (pSingleton== NULL) 
    {
        pSingleton = new Singleton();
    }
    return pSingleton;
}

The Singleton Pattern is one of the GoF (Gang of Four) Patterns. This particular pattern provides a method for limiting the number of instances of an object to just one. It's an easy pattern to grasp once you get past the strange syntax used.

Consider the following class:

PHP Code:

class Database

{

public function __construct() { ... }

public function connect() { ... }

public function query() { ... }

...

}

This class creates a connection to our database. Any time we need a connection we create an instance of the class, such as:

PHP Code:

$pDatabase = new Database();

$aResult = $pDatabase->query('...');

Lets say we use the above method many times during a script's lifetime, each time we create an instance we're creating a new Database object (we're also creating a new database connection, but that's irrelevant in this example) and thus using more memory. Sometimes you may intentionally want to have multiple instances of a class but in this case we don't.

The Singleton method is a solution to this common problem. To make the Database class a Singleton we first need to add a new property to the class, we'll call this $m_pInstance:

PHP Code:

class Database

{

// Store the single instance of Database

private static $m_pInstance;

...

}

As the comment states, this property will be used to store the single instance of our Database class. You should also note that this property must be static.

Next we need to change the constructor's scope to private. This is one of the strange syntaxes that usually confuse people.

PHP Code:

class Database

{

// Store the single instance of Database

private static $m_pInstance;

private function __construct() { ... }

}

By making the constructor private we have prohibited objects of the class from being instantiated from outside the class. So for example the following no longer works outside the class:

PHP Code:

$pDatabase = new Database();

We now need to add a method for creating and returning our Singleton. Add the following method to the Database class:

PHP Code:

public static function getInstance()

{

if (!self::$m_pInstance)

{

self::$m_pInstance = new Database();

}

return self::$m_pInstance;

}

This funny looking function is responsible for handling our object instance. It's relatively easy to understand, basically we check our static property $m_pInstance, if it is not valid we create a new instance of the Database class by calling the constructor. Remember, we made the __construct() method private, so an instance of the object can only be created from within the class' methods. Finally the function returns a reference to our static property. On subsequent calls to getInstance(), $m_pInstance will be valid and thus the reference will be returned - no new instances are created.

So our Database class now looks something like this

PHP Code:

class Database

{

// Store the single instance of Database

private static $m_pInstance;

private function __construct() { ... }

public static function getInstance()

{

if (!self::$m_pInstance)

{

self::$m_pInstance = new Database();

}

return self::$m_pInstance;

}

You can now get an instance of the Database class from anywhere (without using globals or function arguments) in your project. Here's an example and comparison:

This is the usual way we create objects:

PHP Code:

$pDatabase = new Database();

$aResult = $pDatabase->query('...');

This is the Singleton way:

PHP Code:

$pDatabase = Database::getInstance();

$aResult = $pDatabase->query('...');

To conclude, the Singleton is an easy-to-use design pattern for limiting the number of instances of an object.

Delete a Tree


#include<stdio.h>
struct binarysearchtree
{
      int data;
      struct binarysearchtree* left;
      struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void tree_free(tree T)
{
  if (T==NULL)
     return;
  else
  {
      tree_free(T->left);
      tree_free(T->right);
      free(T);
  }
}

Count the number of leaves in a tree


#include<stdio.h>
struct binarysearchtree{
        int data;
        struct binarysearchtree* left;
        struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

int count_leaves(tree T)
{
        if(T==NULL)
            return 0;
        else if(T->left==NULL && T->right==NULL)
            return 1;
        else
            return count_leaves(T->left)+count_leaves(T->right);
}

Largest consecutive Sum


public static void main(String []args)
{
    int a[] = {-2,5,10,-3,5,-10,2,20,1};
    int result[] = new int[a.length];
    result[0] = a[0];
    
    for(int i=1;i<a.length;i++)
    {
        result[i] = (result[i-1] + a[i] > a[i]) ? result[i-1] + a[i] : a[i];
    }
    
    int max = result[0];
    for(int i=1;i<result.length;i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
}

Largest Non-Consecutive Sum


public static void main(String []args)
{
    int a[] = {1,13,10,2,5,9,15,20,8};
    int result[] = new int[a.length];
    result[0] = a[0];
    int max = 0;
    int index = 0;

    for(int i=0; i<a.length; i++)
    {
        max = 0;
        for(int j=0;j<i-1;j++)
        {
            if(result[j] > max)
                max = result[j];
        }
        result[i] = max + a[i];
    }

    for(int i=1; i<result.length; i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
    }
}

Saturday, August 18, 2012

Check whether there exists a root to leaf path sum equal to a given number


int hasSum(struct node* root, int sum)
{
    if(root == NULL)
        return (sum == 0);

    sum = sum - root->data;

    return hasSum(root->left, sum) || hasSum(root->right, sum);
}

Find if a tree is symmetric / isMirror()

A symmetric binary tree is one where if you draw a vertical line passing through the root node then the left half should be the mirror image of the right half. Here is the recursive code,


int isSymmetric(struct node* l, struct node* r)
{
    if((l == NULL) && (r == NULL))
        return 1;

    if(((l == NULL) && (r != NULL)) ||
            ((l != NULL) && (r == NULL)))
        return 0;

    return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
}

Store the sum of left and right subtrees in a node


int sum(struct node* root)
{
    if(root == NULL)
        return 0;

    int lsum = sum(root->left);
    int rsum = sum(root->right);

    root->data = lsum + rsum + root->data;

    return root->data;
}

Find the kth largest element in a Binary Search Tree

Traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element.


void printk(struct node* root, int k)
{
    if(root == NULL)
        return;

    static int index = 0;

    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }

    printk(root->left, k);
}

Calculate vertical sum of a Binary Tree

Vertical sums of a binary tree are the sum of its each vertical column. For e.g. consider the below tree,

5
/ \
3 8
/ \ / \
2 4 6 9

Vertical Sum for first column: 2
Vertical Sum for second column: 3
Vertical Sum for third column: 15 (5+4+6)
Vertical Sum for fourth column: 8
Vertical Sum for fifth column: 9

Output: 2 3 15 8 9

Algorithm:
- start from root and hash its value in a map using a key, say, 'key_col'
- recursively hash left and right children with key value 'key_col-1' and 'key_col+1'
- if the key entry is not present in the hash map then create one and set value as 'root->data'
- if the key entry is already present then just add 'root->data' to the existing value

In the end, we have vertical sum stored in the hash map. Here is the code,


void mapNode(struct node* root, map& m, int col)
{
    if(root == NULL)
        return;
 
    map::iterator it = m.find(col);

    //if column is already mapped and map already
    //has some value stored for the column then
    //add root->data to already stored value, otherwise,
    //just store root->data.
    if(it == m.end())
        m.insert(pair(col, root->data));
    else
        it->second += root->data;

    mapNode(root->left, m, col-1);
    mapNode(root->right, m, col+1);
}

int main()
{
    struct node *root=NULL;
    map m;
    map::iterator iter;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 75);

    mapNode(root, m, 0);

    for(iter = m.begin(); iter != m.end(); iter++)
        printf("%d ", iter->second);

    printf("\n");

    return 0;
}

Count total number of vertical columns in a Binary Tree

Every node in a binary tree can be considered belonging to a column. If we assume that 'root' belongs to column '0' then root->left belongs to column '-1', root->right belongs to column '+1' and root->left->right belongs to column '0' and so on. We have to find the total number of such columns.


void totalCol(struct node* root, int col, int* minC, int* maxC)
{
    if(root == NULL)
        return;

    totalCol(root->left, col-1, minC, maxC);
    totalCol(root->right, col+1, minC, maxC);

    *minC = MIN(*minC, col);
    *maxC = MAX(*maxC, col);
}

int main()
{
    struct node *root=NULL;

    int minC=0;
    int maxC=0;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 10);
    insert(&root, 5);

    totalCol(root, 0, &minC, &maxC);

    printf("Total Col: %d\n", maxC - minC + 1);

    return 0;
}

Print ancestors of a node in a Binary Tree


int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }

    return 0;
}

Serialization/Deserialization of a Binary Tree

Serialize:
to Array - (for node 'i', store left child at '2i+1' & right child at '2i+2')

Assume we have a binary tree below:

_30_
/ \
10 20
/ / \
50 45 35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out)
{
if (!p)
{
out << "# ";
}
else
{
out << p->data << " ";
writeBinaryTree(p->left, out);
writeBinaryTree(p->right, out);
}
}

Deserialize:

Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

void readBinaryTree(BinaryTree *&p, ifstream &fin)
{
int token;
bool isNumber;
if (!readNextToken(token, fin, isNumber))
return;
if (isNumber)
{
p = new BinaryTree(token);
readBinaryTree(p->left, fin);
readBinaryTree(p->right, fin);
}
}

Construct a Binary Tree, given its Inorder and preorder

Consider the following tree,

5
/ \
2 7
/ \ /
1 4 6

Inorder: 1 2 4 5 6 7
Preorder: 5 2 1 4 7 6

Algorithm:
1. Take first element from Preorder (in this case 5) and find it in Inorder.
2. Elements on the left side of '5' (1 2 4) form the left subtree of '5' and similarly elements on the right side (6 7) form right sub tree.
3. Recursively select each element from Preorder and create its left and right subtrees from Inorder.


struct node* create(int* in, int* pre, int inStrt, int inEnd)
{
    if(inStrt > inEnd)
        return NULL;

    int i;
    static int preIndex = 0;

    //create node from preOrder
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = pre[preIndex];

    //find node in inOrder
    for(i=inStrt; i<=inEnd; i++)
        if(in[i] == pre[preIndex])
            break;

    preIndex++;
   
    //recursively call create for the left and right
    //half of inOrder created by preOrder
    temp->left = create(in, pre, inStrt, i-1);
    temp->right = create(in, pre, i+1, inEnd);

    return temp;
}

Longest common subsequence problem

Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Dynamic programming to solve it in O(mn) time and space.

LCS[i, j] = LCS[i-1][j-1] + 1 ; arr1[i] == arr2[j]
= MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise


#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}


public static void main(String []args)
{
    String a = "ABCDEFGHIJKL";
    String b = "ABCD";
    int max = 0;
    int z=0; // Store the index of the last element of Substring
    int m[][] = new int[a.length()][b.length()];
    for(int i=0;i<a.length();i++)
    {
        m[i][0] = 0;
    }

    for(int i=0;i<b.length();i++)
    {
        m[0][i] = 0;
    }

    for(int i=0;i<a.length();i++)
    {
        for(int j=0;j<b.length();j++)
        {
            if(a.charAt(i) == b.charAt(j))
            {

                if(i==0 || j==0) // If first element is in the substring
                { 
                    m[i][j] = 1;
                }
                else
                {
                    m[i][j] = m[i-1][j-1] + 1;
                }

                if(m[i][j] > max)
                {
                    max = m[i][j];
                    z = j;
                }
            }
        }
    }

    System.out.println(max);
    System.out.println(z);
}

Longest Increasing Subsequence problem

Given an array of integers, determine the longest increasing subsequence (not necessarily contiguous).

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]


#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}

Determine if a string has all unique characters

Solution #1:
The most simple approach will be to check each character with every other character. The time complexity will be O(n^2) with no extra space requirement.

Solution #2:
If changes are allowed, then we can sort the string in O(n log n) time and then check the adjacent elements for duplicates. Total time complexity is n log n + n ==> n log n.

Solution #3:
If the string is formed of extended ASCII characters then we can make an array of size 256 and store the occurrence of each character in this array.


int main(int argc, char** argv)
{
    int arr[256] = {0,};
    char *ptr = NULL;

    ptr = argv[1];

    while(*ptr != '\0')
    {
        if(arr[*ptr])
        {
            printf("Found Duplicate...\n");
            return 0;
        }
        else
        {
            arr[*ptr] = 1;
        }
        ptr++;
    }

    printf("No duplicates...\n");

    return 1;
}

Reverse a string

Solution #1:
If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2:
Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3:
If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4:
Approach three can also be done recursively as follows


void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

    gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

    printf("%s\n", str);

    return 1;
}

Check whether a string is a rotation of another string or not

The first thing, of course, would be to make sure that both the strings have same length.

Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego").

Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

REST API Best Practices

Base Url's
Only 2 base urls 1) collection & 2) singular
/dogs
/dog/ig

Use nouns & not verbs
/deals - Groupon
/checkins - Foursquare

// do not have getDogs / getDogById
use HTTP Methods GET, POST, PUT, DELETE to define CRUD operations

How to handle associations
Get all dogs belonging to a owner 5678
eg: GET /owners/5678/dogs

Create a new new dog for a specific owner
eg: POST /owners/5678/dogs

Additional / optional parameters
GET /owners/5678/dogs?color=red&type=pet

Errors

code : use HTTP status codes
message : have message
more_info : have url for error docs; get more context; get help

Versioning

have version at the start, do not have it in the middle
have highest level scope as much to the left as possible

eg:
/v1.2/dog/5678
Note: Do not release an API without versioning
why? FB moved from v1.2 to v1.3 and all apps supporting v1.2 broke

Partial Response

If you only want some fields out of the whole data - want only id, name, type from an entire list of data

eg:
LinkedIn -> /people:(id,first-name,last-name,industry)
Facebook -> /saumilps/friends?fields=id,name,picture

Pagination

have an offset & limit

eg:
/dogs?limit=25&offset=50

Formats
Spit more than one format

/dogs.json
/dog/1234.json
Accept: application/json (pure RESTful way / in the header)
?type=json

Authentication
OAuth

REST vs SOAP

When to use REST ?

Better performance
Better scalability
Reads can be cached
Any browser can be used because the REST approach uses the standard GET, PUT, POST, and DELETE verbs
Totally stateless operations: if an operation needs to be continued, then REST is not the best approach and SOAP may fit it better. However, if you need stateless CRUD (Create, Read, Update, and Delete) operations

When to use SOAP ?

Asynchronous processing and invocation; if your application needs a guaranteed level of reliability and security then SOAP 1.2 offers additional standards to ensure this type of operation. Things like WSRM – WS-Reliable Messaging.
Formal contracts; if both sides (provider and consumer) have to agree on the exchange format then SOAP 1.2 gives the rigid specifications for this type of interaction.
Stateful operations; if the application needs contextual information and conversational state management then SOAP 1.2 has the additional specification in the WS* structure to support those things (Security, Transactions, Coordination, etc). Comparatively, the REST approach would make the developers build this custom plumbing.

WS-Security

While SOAP supports SSL (just like REST) it also supports WS-Security which adds some enterprise security features. Supports identity through intermediaries, not just point to point (SSL). It also provides a standard implementation of data integrity and data privacy. Calling it “Enterprise” isn’t to say it’s more secure, it simply supports some security tools that typical internet services have no need for, in fact they are really only needed in a few “enterprise” scenarios.

WS-AtomicTransaction

Need ACID Transactions over a service, you’re going to need SOAP. While REST supports transactions, it isn’t as comprehensive and isn’t ACID compliant. Fortunately ACID transactions almost never make sense over the internet. REST is limited by HTTP itself which can’t provide two-phase commit across distributed transactional resources, but SOAP can. Internet apps generally don’t need this level of transactional reliability, enterprise apps sometimes do.

WS-ReliableMessaging

Rest doesn’t have a standard messaging system and expects clients to deal with communication failures by retrying. SOAP has successful/retry logic built in and provides end-to-end reliability even through SOAP intermediaries.

Summary

In Summary, SOAP is clearly useful, and important. For instance, if I was writing an iPhone application to interface with my bank I would definitely need to use SOAP. All three features above are required for banking transactions. For example, if I was transferring money from one account to the other, I would need to be certain that it completed. Retrying it could be catastrophic if it succeed the first time, but the response failed.

Thursday, August 16, 2012

Anagrams

Find whether two words are anagrams (cafe / face)

Go to first word in hash table, add 1 in hash table then see whether all letters of 2nd word also in hash table, if it reaches end of 2nd word it means it is a anagram. Issue: 2 same letters in the word
Increment values in the hash table instead of storing 1 for the first word & then for the 2nd word, decrement values, if all values 0 at the end of 2nd word - it means anagram Complexity = 3n (parse 1st word, parse 2nd word, parse the array)

Create sets of anagrams from a word list (cafe, face, fdga, dgfa - you you will have 2 lists => cafe/face & fdga/dgfa)

Go to first word, see if any lists, if a list take a word from that list & run the above function for that two words, if return true then add to that list, if false do this for all the lists, create a new list with that word is still that word not in any list Complexity = l * 3n * x (l-no of words, x-no of unique lists)
sort each word & sort list & then group

aefc, aefc, adfg, adfg
Complexity =>
sorting = nlogn
sorting each word = nlogn * size of each word
sorting list = l*log l * total no of words
total complexity = sorting each word + sorting list + grouping

Diameter of a Binary Tree

         /      \
       2         9
     /    \      /
    1    4    7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)


int height(struct node* root)
{
    if(root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

int diameter(struct node* root)
{
    if(root == NULL)
        return 0;

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}

Wednesday, August 15, 2012

Detecting a Loop in a Singly Linked List

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

Hint:
The best approach uses only O(N) time and O(1) space.

Solution:

The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.


bool hasLoop(Node *head) 
{
    Node *slow = head, *fast = head;

    while (slow && fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;    
        
        if (slow == fast)
            return true;
    }
    return false;
}

Longest Palindromic Substring

Easy but invalid solution:

Reverse S and become S’.

This seemed to work, let’s see some examples below.

For example,

S = “caba”, S’ = “abac”.

The longest common substring between S and S’ is “aba”, which is the answer.

Let’s try another example:

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.

The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us a O(N²) DP solution which uses O(N²) space.

Correct Solution

Print Edge Nodes (Boundary) of a Binary Tree

_30_

   /    \
  10    20
 /     /  \
50    45  35

The correct solution should print 30, 10, 50, 45, 35, 20.

        ______30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /
 5  15      28          41

The correct solution should print 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.

   _______________28_______________
  /                                \
  4____                        ____69
       \                      /
      __8__                __56__
     /     \              /      \
   __7     12__        __34    __27__
  /            \      /       /      \
  5_          _13    _2      _3      39
    \        /      /       /
     6      11     10       9

correct output of: 28, 4, 8, 7, 5, 6, 11, 10, 9, 39, 27, 56, 69.

Hint:
To solve this problem, you first need to pay attention to these three key areas:

Printing the leftmost edges from top to bottom. When a node is a leftmost edge, its left child must also be a leftmost edge.
Printing the leaves from left to right. Remember depth-first traversal?
Printing the rightmost edges. You would need to print from bottom to top. The key is printing in the opposite order. Easy if you know how to manipulate recursion into a stack-based solution. Remember post-order traversal?

Solution:
We could divide the tree into two subtrees. One is the left subtree, and the other is the right subtree.

For the left subtree, we print the leftmost edges from top to bottom. Then we print its leaves from left to right.

For the right subtree, we print its leaves from left to right, then its rightmost edges from bottom to top.

Printing the leaves from left to right order is a classic example of depth-first traversal. How do you know if a node is a leaf? Easy, if the node does not have both left and right children.

Printing the leftmost edges is just a trivial addition to the depth-first traversal. When a node is a leftmost edge, then its left child must also be a leftmost edge. We could use a variable to pass this information down the tree. Please note that you must add the condition to avoid printing the node twice (a node could be a leftmost edge as well as a leaf node).

Printing the rightmost edges from bottom to top is easy if you realize the trick of manipulating recursion as a stack. Try relate this with how post-order traversal works. When calling recursive functions, function calls are pushed onto a stack, and therefore you could use the implicit stack to your advantage. This trick is especially handy when applied in situation where you need to reverse the order of operations.


#include<stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node *right;
    int data;
};

struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}

void printLeftBoundary(node *root) {

    if(root==NULL) return;
    if(root->left) {
       printf("%d ",root->data);
       printLeftBoundary(root->left);
    }
    else if(root->right) {
       printf("%d ",root->data);
       printLeftBoundary(root->right);
    }
}

void printLeafBoundary(node *root) {

    if(root) {
   
       printLeafBoundary(root->left);
      
       if(root->left==NULL && root->right==NULL)
          printf("%d ",root->data);
         
       printLeafBoundary(root->right);
    }
}

void printRightBoundary(node *root)
{
    if(root==NULL) return;
    if(root->right) {
       printRightBoundary(root->right);
       printf("%d ",root->data);
    }
    else if(root->left) {
       printRightBoundary(root->left);
       printf("%d ",root->data);
    }
}

void printBoundary(node *root)
{
if(root)
    {
        printf("%d ", root->data);
       
        printLeftBoundary(root->left);
       
        printLeafBoundary(root);
       
        printRightBoundary(root->right);
    }
}

int main()
{
    struct node *root=newnode(1000);
    root->left=newnode(500);
    root->right=newnode(1500);
    root->left->right=newnode(510);
    root->left->right->right=newnode(600);   
    root->left->left=newnode(240);
    root->left->left->left=newnode(120);
    root->left->left->right=newnode(300);   
    root->right->left=newnode(1300);
    root->right->left->right=newnode(1320);   
   
    printBoundary(root);
   

    return 0;
}

Time Complexity
PrintLeftBoundary - O(h), where h is height of tree, log(n) nodes on left are visited once
PrintLeafBoundary - O(n), as each node is visited once
PrintRightBoundary - O(h), where h is height of tree, log(n) nodes on right are visited once.

O(n+2h) total time complexity

Lowest Common Ancestor of a Binary Search Tree (BST)

_______6______

       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. LCA of nodes 2 and 4 is 2

Hint:

A top-down walk from the root of the tree is enough.

Solution:

There’s only three cases you need to consider.

Both nodes are to the left of the tree.
Both nodes are to the right of the tree.
One node is on the left while the other is on the right.

For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.

Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.

A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add another case number ):

4. When the current node equals to either of the two nodes, this node must be the LCA too.

The run time complexity is O(h), where h is the height of the BST. Translating this idea to code is straightforward (Note that we handle case 3) and 4) in the else statement to save us some extra typing


Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (max(p->data, q->data) < root->data)
    return LCA(root->left, p, q);
  else if (min(p->data, q->data) > root->data)
    return LCA(root->right, p, q);
  else
    return root;
}

Lowest Common Ancestor of a Binary Tree "WITHOUT" Parent pointers

_______3______

       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Hint:

Top-down or bottom-up? Consider both approaches and see which one is more efficient.

A Top-Down Approach (Worst case O(n²) ):

Let’s try the top-down approach where we traverse the nodes from the top to the bottom. First, if the current node is one of the two nodes, it must be the LCA of the two nodes. If not, we count the number of nodes that matches either p or q in the left subtree (which we call totalMatches). If totalMatches equals 1, then we know the right subtree will contain the other node. Therefore, the current node must be the LCA. If totalMatches equals 2, we know that both nodes are contained in the left subtree, so we traverse to its left child. Similar with the case where totalMatches equals 0 where we traverse to its right child.


// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}

What is the run time complexity of this top-down approach?

First, just for fun, we assume that the tree contains n nodes and is balanced (with its height equals to log(n) ). In this case, the run time complexity would be O(n). Most people would guess a higher ordered complexity than O(n) due to the function countMatchesPQ() traverses the same nodes over and over again. Notice that the tree is balanced, you cut off half of the nodes you need to traverse in each recursive call of LCA() function. The proof that the complexity is indeed O(n) is left as an exercise to the reader.

What if the tree is not necessarily balanced? Then in the worst case the complexity could go up to O(n²). Why? Could you come up with such case? (Hint: The tree might be a degenerate tree).

A Bottom-up Approach (Worst case O(n) ):Using a bottom-up approach, we can improve over the top-down approach by avoiding traversing the same nodes over and over again.

We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Sounds complicated? Surprisingly the code appears to be much simpler than the top-down one.


Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Interview Websites

http://formatmysourcecode.blogspot.com/

Maximum Height (Depth) of a Binary Tree

The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.

Recursive Solution:
We can solve this easily using recursion. Why? Because each of the leftChild and rightChild of a node is a sub-tree itself. We first compute the max height of left sub-tree, then compute the max height of right sub-tree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.


int maxHeight(BinaryTree *p)
{
     if (!p) return 0;

     int left_height = maxHeight(p->left);
     int right_height = maxHeight(p->right);

     return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

Pop in Linked List

Extract the data from the head node, delete the node, advance the head pointer to point at the next node in line. Uses a reference parameter since it changes the head pointer.


int Pop(struct node** headRef) 
{
    struct node* head;
    int result;
    head = *headRef;
    
    assert(head != NULL);
    
    result = head->data; // pull out the data before the node is deleted
    *headRef = head->next; // unlink the head node for the caller
    
    // Note the * -- uses a reference-pointer
    //  just like Push() and DeleteList().
    
    free(head); // free the head node
    return(result); // don't forget to return the data from the link
}

Delete Linked List

Delete the whole list and set the head pointer to NULL. There is a slight complication

inside the loop, since we need extract the .next pointer before we delete the node, since
after the delete it will be technically unavailable.


void DeleteList(struct node** headRef)
{
    struct node* current = *headRef; // deref headRef to get the real head
    struct node* next;

    while (current != NULL)
    {
        next = current->next; // note the next pointer
        free(current); // delete the node
        current = next; // advance to the next node
    }

    *headRef = NULL; // Again, deref headRef to affect the real head back in the caller.
}

GetNth() in a Linked List


int GetNth(struct node* head, int index)
{
    struct node* current = head;
    int count = 0; // the index of the node we're currently looking at
    while (current != NULL)
    {
        if (count == index) return(current->data);
        count++;
        current = current->next;
    }

    assert(0); // if we get to this line, the caller was asking
    // for a non-existent element so we assert fail.
}

Count number of times a value repeated in Linked List


int Count(struct node* head, int searchFor)
{
    struct node* current = head;
    int count = 0;
    while (current != NULL)
    {
        if (current->data == searchFor) count++;
        current = current->next;
    }
    return count;
}

Length of Linked List


// Return the number of nodes in a list (while-loop version)
int Length(struct node* head)
{
    int count = 0;
    struct node* current = head;
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return(count);
}

Insert in a BST

Insert()

Insert() -- given a binary search tree and a number, insert a new node with the given number into the tree in the correct place. The insert() code is similar to lookup(), but with the complication that it modifies the tree structure. As described above, insert() returns the new tree pointer to use to its caller. Calling insert() with the number 5 on this tree...
2
/ \
1 10

returns the tree...

2
/ \
1 10
/
5

The solution shown here introduces a newNode() helper function that builds a single node. The base-case/recursion structure is similar to the structure in lookup() -- each call checks for the NULL case, looks at the node at hand, and then recurs down the left or right subtree if needed.


/*
 Helper function that allocates a new node
 with the given data and NULL left and right
 pointers.
*/
struct node* NewNode(int data) {
  struct node* node = new(struct node);    // "new" is like "malloc"
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
} 

/*
 Give a binary search tree and a number, inserts a new node
 with the given number in the correct place in the tree.
 Returns the new root pointer which the caller should
 then use (the standard trick to avoid using reference
 parameters).
*/
struct node* insert(struct node* node, int data) {
  // 1. If the tree is empty, return a new, single node
  if (node == NULL) {
    return(newNode(data));
  }
  else {
    // 2. Otherwise, recur down the tree
    if (data <= node->data) node->left = insert(node->left, data);
    else node->right = insert(node->right, data);

    return(node); // return the (unchanged) node pointer
  }
}

Check whether two trees are structurally identical


/*
 Given two trees, return true if they are
 structurally identical.
*/
int sameTree(struct node* a, struct node* b) {
  // 1. both empty -> true
  if (a==NULL && b==NULL) return(true);
  // 2. both non-empty -> compare them
  else if (a!=NULL && b!=NULL) {
    return(
      a->data == b->data &&
      sameTree(a->left, b->left) &&
      sameTree(a->right, b->right)
    );
  }
  // 3. one empty, one not -> false
  else return(false);
}

Check whether a given tree is a BST


/*
 Returns true if a binary tree is a binary search tree.
*/
int isBST(struct node* node) {
  if (node==NULL) return(true);
  // false if the max of the left is > than us

  // (bug -- an earlier version had min/max backwards here)
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false);

  // false if the min of the right is <= than us
  if (node->right!=NULL && minValue(node->right) <= node->data)
    return(false);

  // false if, recursively, the left or right is not a BST
  if (!isBST(node->left) || !isBST(node->right))
    return(false);

  // passing all that, it's a BST
  return(true);
}


/*
 Returns true if the given tree is a binary search tree
 (efficient version).
*/
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
 Returns true if the given tree is a BST and its
 values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively,
  // tightening the min or max constraint
  return
    isBSTUtil(node->left, min, node->data) &&
    isBSTUtil(node->right, node->data+1, max)
  );
}

Create a new duplicate node for each node in a BST

 For each node in a binary search tree,
 create a new duplicate node, and insert
 the duplicate as the left child of the original node.
 The resulting tree should still be a binary search tree.
 So the tree...
    2
   / \
  1   3

 Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1

*/


void doubleTree(struct node* node) {
  struct node* oldLeft;

  if (node==NULL) return;

  // do the subtrees
  doubleTree(node->left);
  doubleTree(node->right);

  // duplicate this node to its left
  oldLeft = node->left;
  node->left = newNode(node->data);
  node->left->left = oldLeft;
}

Mirror a BST

 Change a tree so that the roles of the
 left and right pointers are swapped at every node.
 So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/


void mirror(struct node* node) {
  if (node==NULL) {
    return;
  }
  else {
    struct node* temp;

    // do the subtrees
    mirror(node->left);
    mirror(node->right);

    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}

Print out all root-to-leaf paths


/*
 Given a binary tree, print out all of its root-to-leaf
 paths, one per line. Uses a recursive helper to do the work.
*/
void printPaths(struct node* node) {
  int path[1000];
  printPathsRecur(node, path, 0);
}

/*
 Recursive helper function -- given a node, and an array containing
 the path from the root node up to but not including this node,
 print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
  if (node==NULL) return;

  // append this node to the path array
  path[pathLen] = node->data;
  pathLen++;

  // it's a leaf, so print the path that led to here
  if (node->left==NULL && node->right==NULL) {
    printArray(path, pathLen);
  }
  else {
  // otherwise try both subtrees
    printPathsRecur(node->left, path, pathLen);
    printPathsRecur(node->right, path, pathLen);
  }
}

// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
  int i;
  for (i=0; i<len; i++) {
    printf("%d ", ints[i]);
  }
  printf("\n");
}

Find path from root to leaf with a given sum


/*
 Given a tree and a sum, return true if there is a path from the root
 down to a leaf, such that adding up all the values along the path
 equals the given sum.
 Strategy: subtract the node value from the sum when recurring down,
 and check to see if the sum is 0 when you run out of tree.
*/
int hasPathSum(struct node* node, int sum) {
  // return true if we run out of tree and sum==0
  if (node == NULL) {
    return(sum == 0);
  }
  else {
  // otherwise check both subtrees
    int subSum = sum - node->data;
    return(hasPathSum(node->left, subSum) ||
           hasPathSum(node->right, subSum));
  }
}