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

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

## Covert Swagger 2.0 to OpenAPI 3.xx

Written with StackEdit.

# Pascal Triangle

``````def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""

if numRows == 0:
return []

row = 

for x in range(2, numRows+1):
# Prepare the row
row = *x
# The first and last element on each row is 1, so skip those
# indexes.
for y in range(1, x-1):

# x represent row number. We need to normalize it
# to use it as an index in the answer list.

# 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]

``````

Output

``````x=3 y=1 answer=[, [1, 1]]
x=4 y=1 answer=[, [1, 1], [1, 2, 1]]
x=4 y=2 answer=[, [1, 1], [1, 2, 1]]
x=5 y=1 answer=[, [1, 1], [1, 2, 1], [1, 3, 3, 1]]
x=5 y=2 answer=[, [1, 1], [1, 2, 1], [1, 3, 3, 1]]
x=5 y=3 answer=[, [1, 1], [1, 2, 1], [1, 3, 3, 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)
``````

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-vault`tools 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
``````vault login -method=github -path=github
3. Install `consul-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