Month: April 2014
Interrupts and bottom halves
Typical handling of an interrupt 
Classification of interrupts
Interrupt Masking
Identifying an interrupt handler
Interrupt handling
Prune nodes of binary search tree
Problem statement
That is to say remove all nodes from BST which are either less than min or greater than max.
For example, if for following input tree min = 22 and max = 40 are given
Output will be like output tree.
Input tree 
Output tree 
Analysis
When we are processing a node, there are two cases:
1. Node is less than min.
In this case we two things for sure. First all nodes in left sub tree are less than this node and hence less than min. These nodes would have been already deleted when we processes left child. So e don’t care about left child of node.
Second, right sub tree may or may not contain nodes which are less than min, which would have been already pruned and only valid nodes will be remaining. Hence we need to pass the reference of remaining right sub tree to parent of this node.
2. Node is greater than max.
Again in this case too, two things are clear. All nodes on right sub tree are greater than node and hence greater than max, so ignore them. They are already processed anyway.
However, nodes on left sub tree may or may not be greater than max, so return reference to left sub tree of node to its parent before deleting the node.
So we process the left child first.Then right child and at last the current node. With above two conditions we can decide what has to be returned to parent node of current node.
Code
Complexity Analysis
T9 dictionary : Form words with telephone digits
T9 Keyboard 
Problem statement
Analysis
Code
Complexity Analysis
Reference:
Programming interviews exposed
Next smallest number with same number of bits set
Next smallest number with same number of bits set
Analysis
Number

Bit representation

Next number

Bit representation

3

00000011

5

00000101

7

00000111

11

00001011

13

00001101

14

00001110

6

00000110

9

00001001

11

00001011

13

00001101

Code
Next smallest number with same digits
Next smallest number with same digits
Analysis
 Scan through digits of number from left to right till they are monotonically increasing. Once we find a digit which is less than the digit at left, we stop. That number let’s say y will be our pivot. Now search in right part of the number, digit is which is least greater than pivot. Swap pivot and that number.
 Second part involves sorting of all digits on the right hand side of the pivot. This will give us the result.
Code
Complexity Analysis
Dynamic programming :Longest Arithmetic Progression
Problem statement
Analysis
Code
Complexity Analysis
Reference
http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf