Vade Mecum

25-Feb-2015

Find what makes string not a palindrome?

Yesterday, my friend Manoj asked me this interesting question. The problem statement is as follows,
If I give you a string, say S = "madam" which is palindrome. But now, I have added few extra charater to S [You don't know how many charaters] and now S = "mPadam". I have added 'P' in this case. You have to come up with a linear time algorith i.e. O(n) and find out if I have added 1 charater or more to the original palindrome string S.

• If I have added 1 extra charater then print that extra charater
• If I have added more than one extra charater then exit the program

Following is my solution.

Give Me Answer!

19-Nov-2015

Given a real-time list of traded stocks, need to get the last N (arbitrary) unique traded stocks.
Write addTrade(string ticker) and getLastNUnique(int n) functions with efficient runtime?

This is an interesting question, I came across. Following is my solution where I use something similar to 'linkedhashmap'. If you find any bug kindly report it to my email.

class TradeTracker(object):
    def __init__(self):
        self.map = dict()
        self.first = '0'

    def addTrade(self, A):
        for a in A:
            if  self.map.has_key(a):
                if(self.map[a][0] != '0'):
                    self.map[self.map[a][0]] = [self.map[self.map[a][0]][0], self.map[a][1]]
                    self.map[a] = ['0', self.first]   
                    self.map[self.first] = [a,self.map[self.first][1]]
                    self.first = a
            else:
                if self.first != '0' :
                    self.map[self.first] = [a, self.map[self.first][1]]
                self.map[a]= ['0', self.first]
                self.first = a
        
    def giveLastN(self, n):
        cur = self.first
        while(n > 0 and cur != '0'):        
            print(cur)
            cur = self.map[cur][1]
            n-=1
            
A = ['b','a','d','b','b','b','c','a','b','a','a','k']
T = TradeTracker();
T.addTrade(A)
T.giveLastN(4)