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).

Interview Questions - 1

Interview Month: February
Interview Position: Software Engineer
Interview Duration: About 30 minutes
Interview Company Type: Networking

1. Whats the library used for threading in C on Unix based systems ?

2. What is the pthread library call used to create a new thread and the parameters to the call?

3. How do you think the pthread_lock() is implemented ?

4. Will this work for multi processor/core systems also ? {This question asked in many interviews}
Dont know a proper answer to this question yet. Any links would be helpful.

5. What is malloc? System call or Library Call? Why?

6. At what times does malloc invoke a system call? Does it always invoke?
Answer is something regarding maintaining buckets. Check out malloc implementation details

7. What is a hash-map data structure? How does it store data?

8. Advantages and disadvantages of using a hashmap. Give examples of systems where you would not use 1.