Longest Palindrome Substring in a String

DP based solution

class Solution(object):
    def __init__(self):
        self.lookup  = {}
        
    def isPalindrome(self, s, dp, i, k):
        j = i + k - 1
        
        if s[i] == s[j] and dp[i + 1][j - 1]:
            return True
        
        return False
        
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        if size < 2:
            return s
        
        dp = [ [False]*size for c in range(size+1) ]
        
        i = j = 0
        longest = 0
        startIndex = endIndex = 0
        
        while i < size:
            dp[i][i] = True
            
            # Handle the case of two repeated chars ('bb')
            j = i + 1
            if j < size:
                if s[i] == s[j]:
                    dp[i][j] = True
                    
                    # Always update the index for result.
                    startIndex = i
                    endIndex = j
                    longest = 2
            i += 1
        
        # Start finding substrings longer the 2.            
        k = 3
        while k <= size:
            for i in range(0, size - k + 1):
                if self.isPalindrome(s, dp, i, k):
                    dp[i][i+k-1] = True
                    strLen = k
                    
                    if strLen > longest:
                        longest = strLen
                        startIndex = i
                        endIndex = i + k - 1
            k += 1
            
        return s[startIndex: endIndex + 1]

Resources

Written with StackEdit.


Union-Find Problem

The problem is to find if a given edge (a, b) is connected in a graph with vertices {a, b, c, ...}.

Naive Solution – O(n^2)

  • Maintain a parent array of size (len of vertex array)
  • Update an edge (a, b) with the index a & b in the vertex array
ParentArray[a] = b
ParentArray[b] = b

Code

class Solution(object):
    def __init__(self, nodesCount):
        self.nodes = list(range(nodesCount + 1))

    def union(self, p, q):
        currentRoot = self.root(p)
        for index, num in enumerate(self.nodes):
            if num == currentRoot:
                self.nodes[index] = q
                
        print(self.nodes)

    def find(self, p, q):
        return self.root(p) == self.root(q)
    
    def root(self, p):
        return self.nodes[p]
    
if __name__ == "__main__":
    s = Solution(6)
    s.union(1, 2)
    s.union(2, 3)
    s.union(2, 4)
    
    print(s.find(1, 3))
    print(s.find(3, 4))
    print(s.find(3, 6))

Execution

$ python union-find.py 
[0, 2, 2, 3, 4, 5, 6]
[0, 3, 3, 3, 4, 5, 6]
[0, 4, 4, 4, 4, 5, 6]
True
True
False

Written with StackEdit.


Longest Substring without Repeating Characters

The solution uses a sliding window and uses O(n) time and O(n) space.
There are many cases to take care of.

  1. We can skip the process string less than size 2.
  2. Iterate the string, checking each char as key in the hash, adding if not present.
    If not present in hash, add each char as key and index as value.
  3. If present in hash, check if the index is more than the window start.
    Calculate the window size and update max.
  4. Check the max again at the time of return.
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) < 2:
            return len(s)
        
        wstart = wend = 0
        charMap = {}
        maxLen = 0
        currentLen = 0
        
        while wend < len(s):
            if s[wend] in charMap and charMap[s[wend]] >= wstart: #abba
                currentLen = wend - wstart
                maxLen = max(maxLen, currentLen)
                wstart = charMap[s[wend]] + 1
            
            charMap[s[wend]] = wend
            wend += 1
        
        # The expression wend - wstart gets the case of last
        # character used for len count.
        return max(maxLen, wend - wstart)

Reference

Written with StackEdit.


Rapid Learn Swagger OpenAPI

What is Swagger?

  • A standard way to document REST APIs
  • The documentation is described in a YAML or JSON document.
  • OpenAPI has syntax and tags to write an API description.

Why Use Swagger?

  • Very standard
  • It not just describes APIs but also serves as an APIs contract among teams.
  • Each API specifies the expected request, response and response codes.
  • Along with this, APIs can have examples of sample requests and responses.

Reference

Covert Swagger 2.0 to OpenAPI 3.xx

Written with StackEdit.


Pascal Triangle

def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        answer = []
        
        if numRows == 0:
            return []
            
        row = [1]
        answer.append(row)
        
        for x in range(2, numRows+1):
            # Prepare the row
            row = [1]*x
            # The first and last element on each row is 1, so skip those
            # indexes.
            for y in range(1, x-1):
                # print("x={} y={} answer={}".format(x, y, answer))
                
                # x represent row number. We need to normalize it
                # to use it as an index in the answer list.
                previousRow = answer[x-2]
                
                # In the previous row, pick an element before the current index
                # and another at the current index; sum them. 
                row[y] = previousRow[y-1]+ previousRow[y]
                
            answer.append(row)
                
        return answer

Output

x=3 y=1 answer=[[1], [1, 1]] 
x=4 y=1 answer=[[1], [1, 1], [1, 2, 1]] 
x=4 y=2 answer=[[1], [1, 1], [1, 2, 1]] 
x=5 y=1 answer=[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] 
x=5 y=2 answer=[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] 
x=5 y=3 answer=[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Check Two Strings are Anagrams?

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        # Keep a frequency array
        frequency = {}
        for c in s:
            if c not in frequency:
                frequency[c] = 1
            else:
                frequency[c] += 1
        
        # Go over the other string 
        for d in t:
            if d in frequency:
                frequency[d] -= 1
                if frequency[d] == 0:
                    # Just keep deleting what is not required
                    del frequency[d]
            else:
                # Anything not in dict, just say Not an Anagram.
                return False

        if len(frequency) == 0:
            return True
        
        return False

Written with StackEdit.


Top 5 VSCode Extensions for Vim Lovers

Vim Extensions

  • vscodevim: Vim emulation for Visual Studio Code
  • Better Align (: + = in visual mode)

Language Specific Extensions

C/C++

  • C/C++ IntelliSense, debugging, and code browsing.
  • Better C++: better-cpp-syntax

Golang

  • Go Microsoft
  • Go Group Imports
  • Go Critic

Python

  • Python Microsoft
  • Python Extension Pack

Ruby

  • Ruby for Visual Studio Code
  • Rubocop
  • Ruby Solargraph

Themes

  • Github Plus
  • Winter Is Coming (Light & Dark)

Python Cheatsheet – IV

Enumerate a list with index

for index, value in enumerate(mylist):
    print(index, value)

Enumerate from a different start index

mylist = [5,6,7]

for index, value in enumerate(mylist, start= 1):
    print(index, value)

1 5
2 6
3 7

Dictionary iterate

for k, v in d.items():
    print(k, v)

References

Written with StackEdit.


Simplistic API Rate Limiter in Python

The Rate Limiter is a per-minute request limiter. It allows up to 1000 events in a minute and does not roll over the underutilized capacity to the next minute.
It uses a Hashmap to keep track of per second requests. The idea is to extend the code for roll-over capacity to the next minute.

from random import seed
from random import randint
import sys

seed(1)

class RateLimit():
    def getTime(self, minute):
        if minute == 4:
            sys.exit(0)
        return minute, randint(0, 59)
    
    def __init__(self):
        self.status = {}
        self.start_minute = 1
        self.total_events = 0

    def ratelimit(self, minute, second):
        print(minute, self.start_minute, self.status, self.total_events)
        if minute != self.start_minute:
            self.start_minute = minute
            self.status.clear()
            self.total_events = 0
        
        if self.total_events > 1000:
            print("not accepting anymore")
            return -1

        hashKey = second % 60
        print("hashkey={}".format(hashKey))
        if hashKey in self.status:
            self.status[hashKey] += 1
        else:
            self.status[hashKey] = 1
        self.total_events += 1

r = RateLimit()
minute = 1    
while 1:
    m,s = r.getTime(minute)
    if r.ratelimit(m, s) == -1:
        minute += 1
        r.getTime(minute)

Sample output

hashkey=50
(3, 3, {0: 17, 1: 20, 2: 21, 3: 20, 4: 12, 5: 19, 6: 20, 7: 12, 8: 21, 9: 21, 10: 17, 11: 10, 12: 15, 13: 21, 14: 15, 15: 15, 16: 20, 17: 12, 18: 19, 19: 9, 20: 14, 21: 12, 22: 10, 23: 21, 24: 15, 25: 14, 26: 20, 27: 16, 28: 18, 29: 8, 30: 17, 31: 11, 32: 23, 33: 16, 34: 13, 35: 23, 36: 20, 37: 14, 38: 16, 39: 16, 40: 16, 41: 20, 42: 21, 43: 13, 44: 9, 45: 15, 46: 24, 47: 20, 48: 18, 49: 17, 50: 22, 51: 16, 52: 16, 53: 16, 54: 27, 55: 14, 56: 17, 57: 9, 58: 22, 59: 16}, 1001)
not accepting anymore

Written with StackEdit.


consul-vault: Fun with CLI

consul-vaulttools have a graphical and command line interfaces. I found CLI faster for development. So I’m sharing how to setup and use consul.

Steps

  1. Set consul and vault path.
    export VAULT_ADDR=https://xxxx
    export CONSUL_HTTP_ADDR=xxxx
    
  2. Login to vault
    vault login -method=github -path=github
    
  3. Install consul-template.
  4. Run the template.
    consul-template -vault-renew-token=false -template "./config.tmpl:/tmp/out.json" -log-level debug
    
  5. You can also access consul KV store from CLI. It’s much convenient to GET & PUT info.
      consul kv get -detailed database/staging/servers   
    

References