Magic Words.

Magic words can be described as below.

Given a list of words L, a word is considered magical, if it can be reduced to a starting root alphabet, recursively, by stripping off one character at a time, and the newly formed word is also present in the list L.

Lets assume the root alphabet is 'A'. So 'A' should be present in the list.

[A]

Now with one word added anywhere, we can have the following magic words.

A[A..Z]
[A..Z]A

Lets pick 2 magic words for our list and extend it.

[A, AN, SA]

To our list we will add a non-magic word.

[A, AN, SA, BC]

Lets extend with some more magic words to clarify the problem.

AN -> ANT
AN -> BAN
SA -> RSA
SA -> SAS
SA -> SPA

BC (non-magic) -> ABC

So new lists looks like
[A, AN, SA, BC, ANT, BAN, RSA, SAS, SPA, ABC]

The point to note here is ABC is not a magic word, as all the sub words ( AB, AC, BC ) are non existent in the list, hence there is no way to recursively reach 'A' by reducing 'ABC' using words present in the list.

Problem : 
Given a list of words, find the longest magic word. Assume the root alphabet is always present.

Solution :
Considerations :

As we are trying to find the longest word, we can start off by arranging all the words by decreasing length and check from the longest word if it is magical or not.

Python Code.

 wordList = ["a","an","san","sans","saxds","man","said","salds","aid","axds"]
 def modifyWord(elem):
     list_of_chars = list(elem)
     if len(list_of_chars) == 1:
        return 1
     for index in range(len(list_of_chars)):
        newWordList = list_of_chars[:index] + list_of_chars[index+1:] #check for bounds
        newWord = "".join(newWordList)
        #print newWord
        if newWord in wordList:
            retVal = modifyWord(newWord)
            if retVal:
                return 1 + retVal
            else:
                return 0
     return 0

 if __name__ == '__main__':
     len_sorted_wordList = sorted(wordList, key=len, reverse=True)
     for elem in len_sorted_wordList:
        print "Elem = ", elem
        maxlen = max(0, modifyWord(elem))
        if maxlen:
            print maxlen
            break

In the above code, lets understand the function modifyWord.

The modifyWord takes as an input a word element, and converts it into a list of characters first. If the length is 1, it simply returns the length. So if we pass a root alphabet, we get a return value of '1'.
Otherwise, the code removes a character one at a time and forms the newWord. Now we check if the newWord is in the original list. If present , we call modifyWord on it again, else, we try the same on the next newWord, formed by removing the next index element. The commented print statement is there to show what the newWord looks like.

If you have better solutions please comment, I would love to know. Also other modifications can be, to create a sorted tree from the list using the root alphabet as the root element, to find magic words from a start word rather than a root alphabet, etc.

Find Decimal value from a Roman Numeral Number , iterative and recursive solutions

The problem : Given a roman value, find the corresponding decimal value.

Sample Input : XVII
Sample Output : 17

Sample Input : XIV
Sample Output : 14

Solution:

If we first look, there are certain roman values representing certain decimal values, direct mapping, cant do anything about that. So we need a map. Like the one below

map = {'I':1, 'V':5 , 'X':10, 'L':50, 'C':100}

Next gotcha, as long as the values are decreasing or constant, with index, we just keep adding the values. However, if the values increase, we need to do things differently. What needs to be done differently ? We need to subtract the lower value from higher value.

e.g.  if number is VI , index 0 has ' V ' and index 1 has ' I ' , values are decreasing, we need to add value of V + value of I , which is, 5 + 1 = 6

if number is IV, index 0 has ' I ' and index 1 has ' V ' which is increasing, we need to do value of V - value of I , which is 5 - 1 =  4

So, in general, we need to know the next Value.

Iterative Solution:

def returndec(roman):
charlist = list(roman)
num = 0
for i in range(len(charlist)):
if i+1 == len(charlist):
num += map[charlist[i]]
else:
if map[charlist[i]] >= map[charlist[i+1]]:
num += map[charlist[i]]
else:
num -= map[charlist[i]]
return num

Here, we see that indexes i and i+1 are being compared as long as i+1 is in bounds. If the order is decreasing we do  num = num - charlist[i] , which is essentially, adding up negative of lower value to higher value, which is in other words subtracting lower value from higher value.

The recursive solution gets more interesting. Here we need to track the sum as we toss it to each function as a param, but when we return , we need to return the sum, as well as value of first index. Let me demonstrate:

for roman number "XIX"

To calculate func("XIX") we need to calculate either
a)  X + func("IX")
OR
b) -X + func ("IX")

depending on whether X is greater than I or not

Recursive Solution:

def returnDecRec(roman , num):
print "roman ", roman, " num ", num
if not roman:
return (num, 0)
val = map[list(roman)[0]]
num, lastVal = returnDecRec(roman[1:], num)
if lastVal > val:
return (num - val, val)
else:
return (num + val, val)

In the above case, we return sum until the subset of string, plus value added.
Another way to recurse would be to pass the value added in the function parameter.

Something like :
def returnDecRec(roman, num, val)

Ways to import a python module with differences.

I was always confused between the subtleties of

import X

from X import *

import X as Y

__import__("X")

This (by effbot) is a nice link which explains the intricacies.

Reversing a singly linked list using recursion aka Recursively link reversal

The code to reverse a singly linked list using iteration is trivial, using the three pointer method. Lets have a look at the method to reverse a linked list recursively. Not only this is fast, but clears your pointer concepts if you think it cleanly.

Lets define the function.

It would be something like this:

Node* reverseList(Node** head)


This means we are passing the address of the pointer pointing to the head node. We do so, because this is where we want to store the return address. Every time we recurse, we do the following:


1. store the current head in a new variable called now.
2. check if we are at the end of list
3. if we are, we just return
4. if we arent, we collect the newhead from the rest of the list
5. we point the now->next->next  (now which we stored in 1) to now.
6. we make now->next = NULL.

  Node* reverseList(Node **head) {
if (*head == NULL)
return NULL;
Node *now = *head;
Node *newhead = NULL;
if((*head)->next == NULL)
return *head;
else
newhead = reverseList(&((*head)->next));
now->next->next = now;
now->next = NULL;
return newhead;
}


Lets consider an example 1->2->3->4->NULL


Call 1:
*head points to 1
saved *head into now, so now points to 1
newhead = NULL
enter the else, recurse, i.e. reverseList(2)


Call 2
*head points to 2

saved *head into now, so now points to 2

newhead = NULL

enter the else, recurse, i.e. reverseList(3)

Call 3

*head points to 3

saved *head into now, so now points to 3

newhead = NULL

enter the else, recurse, i.e. reverseList(4)

Call 4

*head points to 4

saved *head into now, so now points to 3

head->next = NULL

enter the if, return from Call 4

Return into Call 3

newhead now stores *head = 4

now = 3

now->next = 4

now->next->next = now  means we set  3 <- 4

now->next = NULL  means we set NULL <- 3 <- 4

return newhead, i.e. 4

Return into Call 2

newhead now stores  4

now = 2

now->next = 3

now->next->next = now  means we set  2 <- 3 <- 4

now->next = NULL  means we set NULL <- 2 <- 3 <- 4

Return into Call 1

newhead now stores  4

now = 1

now->next = 2

now->next->next = now  means we set  1 <- 2 <- 3 <- 4

now->next = NULL  means we set NULL <- 1 <- 2 <- 3 <- 4

we return newhead

Arrow keys not working properly on terminal

Arrow keys did not seem to be doing what they were supposed to with a few applications. With cscope it wasn't going up and down the menu items. Instead when I pressed the keys, it was giving a whole lot of control characters. With yast2, the arrow keys wouldn't simply make the cursor move. The system was a Suse Linux Enterprise Edition box. I was trying to figure out what makes it move on Ubuntu(my other box) and not on SLES.

The fix was simple. Found out that its the way different terminals handle arrow keys.

If you try echo $TERM on your shell, it showed me something like, xtermc. I replaced the value like below:

export $TERM="vt100"

This simply worked. Now my arrow keystrokes are identified properly. More on text based terminals here.

Interview Questions - 3

Google Interview Questions.

Interview Type: Telephonic
Interview Duration: 30 mins

1. What is the default signal generated by kill command ?

2. What is a sticky bit ?

3. Given a path, which system call returns the information about the inode ?

4. Given 10000 16 bit integers, and unlimited memory, what is the quickest way to count the total number of bits set in the array.

5. Given four operations
a. Read from CPU reg
b. Disk Seek
c. Context switch
d. Read from main memory

Rank them in order of speed.

6. Average case and worst case running time for quick sort.

7. What is the opposite of malloc in C.

8. Value of "a"[3 >> 1]

Interview Questions - 2

Some more questions:

Type: Data Structures
Company Type: Web, Software, e-Commerce

1. Given is a linked list, in which the Node data is the address of another node (e.g. Data of node 3 is storing address of node 5, data of node 5 is storing address of node 2, etc). How can you copy this linked list ?

Catch is when you copy memory changes, hence the data should change accordingly.

2. Given a Directed Graph, design an algorithm which can detect if there is a loop or not.

3. Given a Binary tree, where each node stores a certain value, find the average at the node.

4. Given an unsorted array, a number 'k', find how many pairs in the array sum up to the value 'k' in the most efficient way. Time complexity should be O(n).

5. Given 2 sorted arrays, and 1 array big enough to accomodate the other array [enough empty space], write a program to get the final array in O(m+n).