Crisp Reading Notes on Latest Technology Trends and Basics

Archive for the ‘Interview Questions’ Category

Iterative Post-Order Traversal of a Binary Search Tree

Overview

Background

In memory-constrained architectures, it may be necessary to work without a lot of memory. In these cases, we try to execute iterative algorithms instead of recursive algorithms.

Problem Description

To develop an Iterative algorithm to do Post-order traversal of a Binary Tree.

  • Note :- The additional storage should not be proportional to the depth of the tree.
  • In the first cut, an extra Parent pointer may be assumed

Incidentally, this is also an “Amazon Interview Question”

The Algorithm

First Node

The first node in a Post-Order traversal is derived as follows

  1. Start from the Root
  2. If a node has a left child, traverse the left link
  3. Otherwise if the node has a right link, traverse the right link.
  4. Keep repeating this till you hit a leaf
Node *first_child( Node *root ) {

Node *curr = root;

while (1) {

if( curr->left != NULL ) {

curr = curr->left;

continue;

}

if( curr->right != NULL ) {

curr = curr->right;

continue;

}

return curr;

}

}

First Child of SubTree

The above fragment of code can be used for any subtree node (not just the Root)

Next Child

Given an arbitrary node, to find the next child, there are two cases

  1. If the current node is a right sibling of its parent,
  • Both left and right subtrees of the parent have been e xamined.
  • So, next node is the parent
  1. If the current node is a left sibling of its parent
  • The right subtree has not yet been examined, and must be examined before the parent.
  • So the next node is the first post-order child of the right subtree (if it exists)

The code is therefore as follows

Node *next_child( Node *curr ) {

// If node is the right child of the parent

if ( curr->parent->right == curr ) {

return parent;

}

// If node is the left child of the parent

if ( curr->parent->left == curr ) {

if ( curr->parent->right == NULL ) {

return curr;

}

else {

return first_child( curr->parent );

}

}

}

Putting it all together

The root is the last node traversed in a post-order traversal.

The traversal is supposed to end when the child returned is the root node

// Routine to traverse all nodes of the tree

void traverse_all( Node *root ) {

Node *curr = first_child(root);

visit(curr);

while( curr != root ) {

curr = next_child(curr);

visit(curr);

}

}

Further Ideas

Incidentally, the use of the “parent” pointer is extra memory, that should well be avoided.

Unfortunately, to avoid the stack, this was deemed necessary.

We need to look at other possibilities, such as the “Threaded Pointer”, and temporary tree rotation to see if these possibilities will work.

Advertisements

Generating Permutations – An Iterative Approach

Overview

Introduction

In many applications, all permutations of a given array need to be generated. While there is a straight-forward recursive algorithm, the approach does waste a lot of stack. An iterative technique is not straight-forward, but is efficient. ( Believe it or not, this was an Amazon-Seattle interview question in 2003)

In this post, I have described the iterative algorithm, and outlined the pseudo-code. The Djikstra paper on which this is based, has a reasonably clear example. Perhaps the notes here may explain a few things that were assumed in the paper.

References

Explanation of Approach

Inversions

Let us define Inversion of a number, as a function

inv(∏,i) = count of numbers to the right of i, that are less than iEg In the permutation < 6, 3, 8, 1, 4, 7, 2, 5 >,inv(∏,4) = 1 ,

since 2 is the only number to the right of 4, less than 4

Bound on the Inversion values

Note that, for any permutation inv(∏,i) < i, for any i

  • This is obvious, since we account for only numbers 1, 2, …, i-1 , while looking to the right of i.

Inversionless Permutation

A permutation of N digits, that has no inversions is a sequence in ascending order

Eg :- The permutation <0,1,2,3> has an inversion of [0,0,0,0]

Neighboring Inversions

Two inversions are inversions differ in only one position by a value of one.

Eg :- < 0, 0, 1, 1 > and < 1, 0, 1, 2 >are considered neighboring inversions

Neighboring Inversions to Neighboring Permutations

Permutations for Neighbouring inversions can be obtained from one another by swapping exactly one item

  • For example
Consider a permutation of the digits 0, 1, 2, 3The permutations corresponding to the Inversion areInversion                          Permutation

i[0]  i[1]  i[2] i[3]

[   0,    0,    1,    1 ] corresponds to   < 0, 2, 3, 1 >

and

[   0,    0,    1,    2 ] corresponds to   < 0, 3, 2, 1 >

  • There is also a very simple rule to obtain the second permutation from the first
Since the second inversion is formed by increasing i[3] by 1,the second permutation is formed from the first by– moving the number 3 right by one digit.
  • Note that getting a neighboring permutation is a O(1) operation, that involves swapping one number.

Gray Codes

Gray Codes are a way to cycle through a set of available values, so that the adjacent rows differ in at-most one digit. (It is used mostly in Boolean Algebra).

  • Here, we cycle through the inversions as [ ii, i2, …, ij ] , where ijisthe inversion for number j,
    • and hence varies from 0 through (j-1)
  • For the example of Inversions of size 3
    • The inversion sequence according to Gray-Code sequence is as shown below
    • Also shown is the permutation corresponding to these inversions
  Inversion             Permutation[ 0, 0, 0, 0 ]        < 0, 1, 2, 3 >[ 0, 0, 0, 1 ]        < 0, 1, 3, 2 >

[ 0, 0, 0, 2 ]        < 0, 3, 1, 2 >

[ 0, 0, 0, 3 ]        < 3, 0, 1, 2 >

[ 0, 0, 1, 3 ]        < 3, 0, 2, 1 >

[ 0, 0, 1, 2 ]        < 0, 3, 2, 1 >

[ 0, 0, 1, 1 ]        < 0, 2, 3, 1 >

[ 0, 0, 1, 0 ]        < 0, 2, 1, 3 >

[ 0, 0, 2, 0 ]        < 2, 0, 1, 3 >

…                    …

  • Observe carefully how the above permutations obey the rules
  • The Gray-Code generation algorithm is described below
  • The algorithm needs to distinguish between an increasing sequence of values, and a decreasing sequence of values.
    • To encode this, we use positive values when the sequence of values is increasing, and a decreasing set of values, when it is decreasing
    • Also, there needs to be a clear distinction between +0 and -0.
    • To accommodate this, we add one to all the positive values, and decrement one from the negative values. So, the range becomes –N to -1 ( versus –N+1 to 0 ), and N to 1 ( versus N-1 to 0 )

The Algorithm

Gray-Code Generation

So, a sequence of values< 0, 1, 2, 3,  3,  2,  1,  0, 0, 1, 2, 3 >would be encoded as

< 1, 2, 3, 4, -4, -3, -2, -1, 1, 2, 3, 4 >

  • With this encoding, the pseudo-code becomes, as shown above
<next,pos> := get_next_inv(curr,N);// Function to iterate over all digitsfunc get_next_inv( curr:Array, size:int ) : <next:Array,pos:int>

{

int  pos  = size-1;

while(pos > 0) {

<next,cont> = iter(curr,pos,size);

if (!cont) return <next,pos>;

pos–;

}

return <next,pos>;

}

// Function to iterate for a single digit

func iter( curr:Array, i:pos, size:int )

: tuple<next: Array, carry: bool>

if (curr[i] == size ) { curr[i] = -size; return <curr, false>; }

curr[i]++;

if ( curr[i] == -1 ) { return <curr,true>; }

return <curr,false>;

}

Getting the next Permutation

  • Getting the next Permutation involves the following steps
  1. Compute the inversion array from the current permutation
  2. Compute the next inversion and the change using the next_gray_code routine mentioned above
  3. Execute the change on the original permutation, and return the new one.
func next_perm(curr:Array, cinv:Array, size:int): <next:Array, ninv:Array>{

<ninv,pos> = get_next_inv( cinv, size );

next = move_item( curr, pos );

return <next,ninv>;

}

func move_item( curr:Array, pos:int ): <next:Array>

{

next = curr;

exchange( next, pos, pos + sign(curr[pos]) );

return next;

}

Tag Cloud