Print BST "Postorder"

[sourcecode]
/*
 Given a binary tree, print its
 nodes according to the "bottom-up"
 postorder traversal.
*/
void printPostorder(struct node* node) {
  if (node == NULL) return;
  // first recur on both subtrees
  printTree(node->left);
  printTree(node->right);

  // then deal with the node
  printf("%d ", node->data);
}
[/sourcecode]

Print BST "Inorder"

[sourcecode]
/*
 Given a binary search tree, print out
 its data elements in increasing
 sorted order.
*/
void printTree(struct node* node) {
  if (node == NULL) return;
  printTree(node->left);
  printf("%d ", node->data);
  printTree(node->right);
}
[/sourcecode]

minValue() of BST

[sourcecode]
/*
 Given a non-empty binary search tree,
 return the minimum data value found in that tree.
 Note that the entire tree does not need to be searched.
*/
int minValue(struct node* node) {
  struct node* current = node;
  // loop down to find the leftmost leaf
  while (current->left != NULL) {
    current = current->left;
  }

  return(current->data);
}
[/sourcecode]

maxDepth() of BST

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.

[sourcecode]
/*
 Compute the "maxDepth" of a tree -- the number of nodes along
 the longest path from the root node down to the farthest leaf node.
*/
int maxDepth(struct node* node) {
  if (node==NULL) {
    return(0);
  }
  else {
    // compute the depth of each subtree
    int lDepth = maxDepth(node->left);
    int rDepth = maxDepth(node->right);
    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
} 

[/sourcecode]

SQL Joins

The "Persons" table:

P_Id LastName FirstName Address         City
1 Hansen     Ola        Timoteivn 10  Sandnes
2 Svendson   Tove       Borgvn 23     Sandnes
3 Pettersen  Kari       Storgt 20     Stavanger

The "Orders" table:

O_Id OrderNo P_Id
1 77895 3
2 44678 3
3 22456 1
4 24562 1
5 34764 15

INNER JOIN
"List all the persons with any orders"

SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo
FROM Persons
INNER JOIN Orders
ON Persons.P_Id=Orders.P_Id
ORDER BY Persons.LastName

The result-set will look like this:

LastName FirstName OrderNo
Hansen     Ola     22456
Hansen     Ola     24562
Pettersen  Kari    77895
Pettersen  Kari    44678

LEFT JOIN / LEFT OUTER JOIN
The LEFT JOIN keyword returns all the rows from the left table (table_name1), even if there are no matches in the right table (table_name2)

"List all the persons and their orders - if any"

SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo
FROM Persons
LEFT JOIN Orders
ON Persons.P_Id=Orders.P_Id
ORDER BY Persons.LastName

The result-set will look like this:

LastName FirstName OrderNo
Hansen     Ola     22456
Hansen     Ola     24562
Pettersen  Kari    77895
Pettersen  Kari    44678
Svendson Tove      (null)

The LEFT JOIN keyword returns all the rows from the left table (Persons), even if there are no matches in the right table (Orders).

RIGHT JOIN / RIGHT OUTER JOIN
The RIGHT JOIN keyword returns all the rows from the right table (table_name2), even if there are no matches in the left table (table_name1)

"List all the orders with containing persons - if any"

SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo
FROM Persons
RIGHT JOIN Orders
ON Persons.P_Id=Orders.P_Id
ORDER BY Persons.LastName

The result-set will look like this:

LastName FirstName OrderNo
Hansen     Ola     22456
Hansen     Ola     24562
Pettersen  Kari    77895
Pettersen  Kari    44678
(null)    (null)   34764

The RIGHT JOIN keyword returns all the rows from the right table (Orders), even if there are no matches in the left table (Persons).

Print all permutations of a string

permute("123", 0, 3);

function permute($str, $start, $strLength) {
  if ($start === $strLength) {
    var_dump($str);
    return;
  }
  for ($i=$start; $i<$strLength; $i++) {
    swap($str, $i, $start);
    permute($str, $start+1, $strLength);
    swap($str, $start, $i);
  }
}
 
function swap(&$str, $pos1, $pos2) { 
  $tmp = $str[$pos1]; 
  $str[$pos1] = $str[$pos2]; 
  $str[$pos2] = $tmp; 
}

Print all possible combinations of strings that can be made using a keypad given a number

telKeys("2133004655", "2133004655", 0, 10);

$keypad = array("ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ");
function telKeys($original, $new, $start, $strLength) {
  global $keypad;
  if ($start === $strLength) {
    var_dump($new);
    return;
  }

    $new[$start] = $keypad[$original[$start]][0];
    telKeys($original, $new, $start+1, $strLength);
    
    $new[$start] = $keypad[($original[$start])][1];
    telKeys($original, $new, $start+1, $strLength);
    
    if(($original[$start]) < 8) {
        $new[$start] = $keypad[($original[$start])][2];
        telKeys($original, $new, $start+1, $strLength);
    }
}

Print given string in all combinations of uppercase and lowercasecharacters

Given a string we need to print the string with all possible combinations of the uppercase and lowercase characters in the string.

So given a string "abc", we need to print the following:
ABC
ABc
AbC
Abc
aBC
aBc
abC
abc

Solution is a simple recursive approach where we call the function again and again once with a character in lower case and another time with the same character in upper case. The code is similar to what we would write for all permutations of a string.

lowerUpper("abc", 0, 3);

function lowerUpper($str, $start, $strLength) {
  if ($start === $strLength) {
    var_dump($str);
    return;
  }
    
  $str[$start] = strtoupper($str[$start]);
  lowerUpper($str, $start+1, $strLength);
    
  $str[$start] = strtolower($str[$start]);
  lowerUpper($str, $start+1, $strLength);
}

ACID properties

Atomic
• Any database Transaction is all or nothing
• If one part of the transaction fails it all fails
• An incomplete transaction cannot exist
• eg: Order & Shipment - Mark order as complete & mark as shipped at the same time.
Consistent
• Any transaction will take the data from one consistent state to another
• Only consistent data is allowed to be written
Isolated
• No transaction should be able to interfere with another transaction
• The same field cannot be updated by two sources at the exact same time
Durable
• Once  a transaction is committed it will stay that way
• Save it once, read it forever unless modified / deleted

Print each level's data in a Binary Tree in a separate line

[sourcecode]
    3
   /  \
  9   20
     /  \
    15    7

For example, the level order output of the tree above is:

3
9 20
15 7
[/sourcecode]

1. Implemented using a "Queue".
2. First we enter root in the queue.
3. As root is the only node at its level, we enter a dummy node after it to signal end of level.
4. Remove a node from queue,
5. If it is a normal node, we enter all its children in the queue.
6. If it is a dummy node, we enter another dummy node in the queue (this signals that we have encountered all nodes in previous level and entered their children in the queue, so this level ends here).
7. As we need to print each level in new line, we enter a new line when we see a dummy node

[sourcecode]
void printLevel(Node* root)
{
    queue<Node*> q;
    Node *dummy = NULL;
    if(root == NULL)
        return;
    //Enter root in the queue
    else
    {
        q.push(root);
        q.push(dummy);
    }
    //If queue is empty then we are done.
    while(!q.empty())
    {
        Node* temp = q.front();
        q.pop();
        //If its a dummy node
        if(temp == NULL)
        {
            cout<<endl;
            q.push(dummy);
        }
        //Else enter node's children in the queue
        if(temp->left!=NULL)
            q.push(temp->left);
        if(temp->right!=NULL)
            q.push(temp->right);
        //Print out node's data.
        cout<<temp->data<<" ";
    }
}
[/sourcecode]

Closures

Classic "last value" problem, when function declared within loop ends up using last value of an incrementing variable:

for (var i = 0; i < 10; i++)

{
    document.getElementById('box' + i).onclick = function()
    {
        alert('You clicked on box #' + i);
    };
}

This assigns 10 functions as event handlers to corresponding elements.Our intention is to have different `i` values in each of the event handlers. But this is not at all what happens in reality.

If you look closer, it's easy to see what's really going on. Each of the functions assigned to `onclick` has access to `i` variable. Since `i` variable is bound to the entire enclosing scope—just like any other variable declared with `var` or as function declaration—each of the functions have access to the same `i` variable. Once this snippet is executed, `i` variable keeps its last value—the one that was set when loop ended.

So how do we fix it? By taking advantage of closures, of course. The solution is simple: scope each of the `i` values to the level of event handler. Let's see how this is done:

for (var i = 0; i < 10; i++)
{
    document.getElementById('box' + i).onclick = (function(index) {
        return function() {
            alert('You clicked on box #' + index);
        };
    })(i);
}

OR

function makeHandler(index) 
{
    return function() 
    {
        alert('You clicked on box #' + index);
    };
}
for (var i = 0; i < 10; i++) 
{
    document.getElementById('box' + i).onclick = makeHandler(i);
}

Print every word that is an anagram of another word in the dictionary

An anagram is any word that rearranges the letters of another word to form itself. For example, “act” and “cat” are anagrams of each other, as well as “admirer” and “married”.

Easy Solution

Compare each word against every other word in the dictionary, checking if they are anagrams of each other by sorting by character and testing for equality. This requires O(n^2) and is a working solution.

Efficient Solution

Example dictionary: {cat, dog, sad, act, cab, mat, god }
--- Sort each word only once, saving it into a temporary copy of the dictionary
Copy dictionary and sort by character: { act, dgo, ads, act, abc, amt, dgo }

Flow 1:

Use a Hashtable with hash(eachWord) as key & count as value, if count > 1 it means there is an anagram creation of the hashtable is n*mLogm (m is the average number of letters in a word and n is the total number of words in the dictionary)

Flow 2: 

We can take it one step further and gain real savings from sorting the temporary copy as well, which only costs O(n log n). It then allows you to find anagrams in O(n) time by going down the list and checking neighbors for equality. However, you’ll have to store the index into the original dictionary of the word as well since they’ll get rearranged.

Example dictionary: {cat, dog, sad, act, cab, mat, god }
Copy dictionary along with index and sort by character:
{ (act 0), (dgo 1), (ads 2), (act 3), (abc 4), (amt 5), (dgo 6) }
Sort dictionary: { (abc 4), (act 0), (act 3), (ads 2), (amt 5), (dgo 1), (dgo 6) }
Go through and find matching neighbors, extracting their indices and printing the corresponding word in the dictionary: 0, 3, 1, 6 -> cat act dog god

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

[sourcecode]
          ___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.

[/sourcecode]

An easy solution:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

[sourcecode]
Node *LCA(Node *root, Node *p, Node *q)
{
    hash_set <Node *> visited;
    while (p || q)
    {
        if (p)
        {
            if (!visited.insert(p).second)
            return p; // insert p failed (p exists in the table)
            p = p->parent;
        }
        if (q)
        {
            if (!visited.insert(p).second)
            return q; // insert q failed (q exists in the table)
            q = q->parent;
        }
    }
    return NULL;
}
[/sourcecode]

The run time complexity of this approach is O(h), where h is the tree’s height. The space complexity is also O(h), since it can mark at most 2h nodes.

The best solution:
A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is always dh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?

The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes. If not, one of the node would eventually reach NULL (root’s parent), which we conclude that both nodes are not in the same tree. However, that part of code shouldn’t be reached, since the problem statement assumed that both nodes are in the same tree.

[sourcecode]
int getHeight(Node *p) 
{
    int height = 0;
    while (p) 
    {
        height++;
        p = p->parent;
    }
    return height;
}

// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) 
{
    int h1 = getHeight(p);
    int h2 = getHeight(q);
    // swap both nodes in case p is deeper than q.
    if (h1 > h2) 
    {
        swap(h1, h2);
        swap(p, q);
    }
    // invariant: h1 <= h2.
    int dh = h2 - h1;
    for (int h = 0; h < dh; h++)
    q = q->parent;
    while (p && q) 
    {
        if (p == q) return p;
        p = p->parent;
        q = q->parent;
    }
    return NULL; // p and q are not in the same tree
}
[/sourcecode]