development

## Python Solution: House Robber Problem

class Solution(object): def __init__(self): self.maxVal = 0 self.lookup = {} def rob(self, nums): “”” :type nums: List[int] :rtype: int “”” if len(nums) == 0: return 0 if len(nums) == 1: return nums if len(nums) >= 2: self.lookup = nums self.lookup = max(nums, nums) for index in range(2, len(nums)): # There are two options at each […]

development

## Palindrome Linked Lists O(1) Space Solution

There are three isolated steps: Find the mid of the list Reverse half of the list and create a new head Compare two heads class Solution(object): def findMiddle(self, head): slow = fast = head # find the mid node while fast and fast.next: fast = fast.next.next slow = slow.next if fast is None: return slow, […]

development

Details Send the pointer to head(phead) and head itself. Recurse till next of head is not NULL. Start popping the frames. If *phead == *head, good to move to next frame-up. Before moving up, move phead to next // Recursive function to check if linked list is palindrome or not int checkPalindrome(struct Node** left, struct […]

development

## Pascal Triangle II

def getRow(self, rowIndex): “”” :type rowIndex: int :rtype: List[int] “”” if rowIndex == 0: return  numRows = rowIndex + 1 previous =  answer = None for x in range(2, numRows+1): row = *x # Mutate the row for y in range(1, x-1): #print(“x={} y={} row={} prev={}”.format(x, y, row, previous)) row[y] = previous[y-1]+ previous[y] […]

development

## Pascal Triangle

def generate(self, numRows): “”” :type numRows: int :rtype: List[List[int]] “”” answer = [] if numRows == 0: return [] row =  answer.append(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, […]

development

## Why Use Python Ordered Dictionary?

The ordered dictionary offers same time complexity as the standard dict. The implementation is simple: Keep two dictionaries and a doubly-linked list of keys. The DLL maintains order. One dict maps key => DLL node Other dict maps key => value Implementation details https://github.com/python/cpython/blob/3.7/Lib/collections/init.py#L129 Example Problem: Find the first non-repeating char in a string. def […]