Problem statement

Every column is assigned a value, A =1 , B=2 … and Z= 26. Again AA = 27, AB = 28…. and AZ = 52.
Given a string S, find out the equivalent number. For example for AAA it will be 703.

Analysis

This problem has simple solution. We just need to come up with the mathematical formula for it.
So let’s work out some examples so that we can identify some pattern and then figure out formula.
A  = 1 = 1 * (26 ^0)
AB = 2 + 26 ^1 =  28
AAB = 2 + 26^1 + 26^2 = 704
B  = 2 = 2 * (26 ^0)
BB = 2 + 2 * (26^1) =  54
ABB = 2 + 2* (26^1) + 1 *( 26^2) = 730
C = 3  = 3 * (26 ^0)
AC  = 3 * (26^0) + 1 * (26^1) = 29
ACC = 3 * (26^0) + 3 * (26^1) + 1 * (26^2)=757
Do you see some pattern?  Yes, we need to get the power of 26 based on the place the character is in string , starting from right hand side.
For example, in ABB, we took (26^2) because A is at second position from the right side, starting from zero. What else? We multiply that power to the value assigned to that character. For example, for C we multiply with 3. Value of single character can be easily found out using char -‘A’ +1 expression.
Rest is to just add each of the value to get the result. Hence our formula is

result  = result + S[i] * power(26, len-i-1) where i = 0 to len-1

It is fairly simple to code it.

Complexity Analysis

Complexity of above code is O(N) where N is size of the string

Interrupts and bottom halves

In any operating system, interrupts are very important because these provide mechanism to handle asynchronous events from various sources like keyboard, network cards, timers etc.These devices do not need CPU at all the time but when they need it, they should be able to request it. Interrupt provide that mechanism. Else we need to rely on the polling by CPU.

Let’s understand what exactly interrupts are. Going by the literal meaning of word interrupt, we can say that anything which is external to currently executing task and alters the execution paths of the task is an interrupt. New task which is executed is Interrupt Service Routine (ISR). Once ISR finishes, control goes back to the next instructions of previously executing task.

 Typical handling of an interrupt

Classification of interrupts

There are two source of interrupts :Hardware interrupts and software interrupts. As names suggest one is raised by hardware and other by the software.

Examples of hardware interrupts: Interrupts generated by the clocks external to CPU, network card interrupts etc. Software interrupts are divide by zero, illegal memory access, page faults etc.

Hardware interrupts are indicated on dedicated line to CPU and then CPU indicates the reception of such interrupt on Interrupt Acknowledgement line.

If a task or operating system wants to ignore a particular interrupt, it can mask it. Masking of an interrupt will make sure that ISR for that interrupt is not executed even if interrupt has occurred.
Non-Maskable Interrupts (NMI) are interrupts which by nature can not be masked by task or operating system. Usually non maskable interrupts are used to sense state of sub systems external to CPU, if CPU sees that there is no activity on a given line for a particular sub system, it can take action. It avoids deadlocks in overall system.
In Pentium architecture, there is a pin each for raising non maskable and maskable interrupts.

Identifying an interrupt handler

Every interrupt has an interrupt number associated with it. This number helps CPU to identify which ISR needs to be invoked when a particular interrupt occurs. operating systems sets up an Interrupt Descriptor Table (IDT) at boot time. So handler pointer is stored at IDT[intrrupt_number].

Interrupt handling

Since we have suspended normal execution of a task, it is important that we resume that task as soon as possible. So two things come up here : We need to return where we came from, so save the return address, and we need to exit ISR as soon as possible, hence no big processing here.

What else? What if other interrupt comes while are servicing an interrupt? We need to take call, what all interrupts can be serviced from this ISR, rest all are masked, so that they are ignored. Even if the same interrupt comes while in ISR, we may need to ignore it.

Since we are going to resume task we suspended, we need its register states. So save all registers states and restore it once ISR is executed.

Apart from these three basic actions, do the interrupt specific processing and return as soon as possible.

One more design issue which we need to take care is what if two interrupts occur at same time? We need to associate priority to each interrupt and based on the priority of interrupts, execution order is decided.

In next post we will discuss what are bottom halves, how interrupts is actually written in operating systems and various APIs available in Linux kernel.

Prune nodes of binary search tree

This is again a problem which can be easily solved using post order traversal of tree. It fits in to this post:  Binary Search Tree: Trick questions

Problem statement

Given a binary search tree and two integers min and max, prune all nodes of binary search tree which are not in range min and max.

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

We need to check each node with min and max and if one condition matches i.e. if root is less than min or root is greater than max, we need to remove that node. However there is a catch here. What happens to its child nodes if root node is removed? To take care of this, we need to process children node before processing the root node. What kind of traversal is that? Yes, it’s post order traversal.

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.

Complexity Analysis

Since we are visiting each node of tree at least once, complexity of code is O(N) where N is number of nodes in binary search tree.

T9 dictionary : Form words with telephone digits

Before advent of QWERTY keyboards, texts and numbers were placed on the same key.
for example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.

 T9 Keyboard

Problem statement

Given a keypad as above, and a three digit number, list all words which are possible by pressing these numbers.

For example if my number is 234, possible words which can be formed are (Alphabetical order):

cdg,cdh,cdi,ceg,ceh,cei,cfg,cfh,cfi

Analysis

Let’s do some calculations first. How many words are possible with seven digits with each digit representing 3 letters?
For first digit we have three choices, and for each choice for first letter, we have three choices for second digit and so on. So it’s simple maths it will be 3x3x3 = 3^3. So any solution which gives us these many words is correct one. Since keys  0 and 1 don’t have any corresponding alphabet, 3^3 would be the upper bound of number of words and not the minimum words.

Now let’s do some examples.
For number above  234. Do you see any pattern?
Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed.
Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end.
Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.

Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case.
When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.

Complexity Analysis

Complexity of above code is 3^N where N is number of digits in telephone number.

Reference:

Programming interviews exposed

Next smallest number with same number of bits set

Given a number, find next smallest number which as same number of bits set.
For example, if given number is 3  (011) then result should be 5 (101). Both have 2 bits set and 5 >3

Analysis

Let do some examples first and see if some pattern emerges from there.

 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

From above table, we can observe following things
1. First zero encountered after encountering one is changed to 1 and one before this zero is made to be zero.
2. All rest ones moved to the right most bits.

So in case 6 (0000 0110), we change the fourth bit as 1 and third bit to 0. Also 1 at bit position two is moved to right most bit and space is filled with zeros. Result is 9 (00001001)

We know the trick to find the right most bit set, which is given by

rightmost =  x & ~(x-1)

rightmost  = 00000110 & 0000010 = 00000010 = 2

Now if we add this rightmost number to original number, there is ripple effect created which will make all ones ahead of rightmost one as zero and first zero after those consecutive ones as 1.

swapped  = x + rightmost

Swapped  = 00000110 + 00000010 = 00001000 = 8

Now if we XOR the number x with swapped we get all bits sets which are set in one of them.

xor  = x^ swapped.
xor =  00000110 ^ 00001000 = 00001110 = 14

adjusted  = (00001110 >>2 ) / 2 = 3/2 =1 = 00000001

Final answer is swapped | adjusted  = 00001000 | 00000001 = 00001001

Code is fairly simple now.

Next smallest number with same digits

Given a number, find out the next smallest number which can be formed using same digits.

Analysis

Using brute force algorithm, we can generate all permutations of the given number and sort them. After sorting search for the given number and then return the number next to it.
This requires generation of log N! permutation which itself is very high followed by sorting and searching.
Let us look for optimized solution.Take some examples:
Number = 12543
What is the next smallest number? Its 13245.
Number = 123
What is the next smallest number? It’s 132.
Number = 1234554321
Next smallest number will be 1234123455.

There are two steps to get next smallest number.
1. 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.
2. Second part involves sorting of all digits on the right hand side of the pivot. This will give us the result.
Apply this algorithm on number 12543.
We start scanning from 4 as there is no right digit for 3. Since 4 is greater than 3, we move on.
Now our current digit becomes 5. 5 is also greater than 4 , hence we are good. Move on.
Current digit is 2, which is less than 5 and hence our pivot.
Now search for the number which is least greater than 2. In this case it would be 3. Swap 2 and 3
Number becomes 13542.

Now second part of algorithm. Sort all digits on right of pivot that is 2.  So final number becomes 13245.

Sorting and searching can be easily done using an array of size 10 as digits will be from 0 to 9.

Complexity Analysis

Complexity of above algorithm will be Log N where N is number. Log N gives us number of digits in that number.

Dynamic programming :Longest Arithmetic Progression

Arithmetic progression is set of numbers in which difference between two consecutive numbers is constant. For example, 1,4,7,10,13 form a arithmetic progression.

Problem statement

Given a set of integers in sorted order, find the length of longest arithmetic progression.

Analysis

This problem can be easily solved using hash.We need to consider each possible pair of elements in array and add that pair to the hash table entry corresponding to that difference. There are n*(n-1)/2 such pairs. So our complexity becomes O(N^2) with extra space for hash size of which is proportional to the maximum difference between any two elements.

Let’s simplify the problem first. What if we need to check if there are three numbers in set which form AP? Two numbers always form an AP Why?

A[i], A[j] and A[k] form an AP if 2* A[j] = A[i] + A[k] where k>j and i<j.

So we need to check of each j in array and if we find i and k satisfying above condition, we return true.

How can we apply this to find length of longest arithmetic progression?
As I mentioned above, two numbers always from an arithmetic progression, any number from set will always from AP of length 2 with last element of set.
If formulate a table where Table[i][j] is set to length of AP with  first and second element as A[i] and A[j]. When j = N, value is set to 2 as per above statement.
Now we move up from N-1 to 0 and fill Table [i][j].
We search for i j such that A[i], A[j] and A[k] form an AP. Then,

Table[i][j] = Table[j][k] +1

Since we are filling table bottom up and k>j Table[j][k] would have been already calculated.

Complexity Analysis

Complexity of above code is O(N^2) with O(N^2) extra space.

Reference

http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf