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[0] if len(nums) >= 2: self.lookup[0] = nums[0] self.lookup[1] = max(nums[0], nums[1]) for index in range(2, len(nums)): # There are two options at each […]

Read more## 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, […]

Read more## Palindrome LinkedList Recursive

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 […]

Read more## Pascal Triangle II

def getRow(self, rowIndex): “”” :type rowIndex: int :rtype: List[int] “”” if rowIndex == 0: return [1] numRows = rowIndex + 1 previous = [1] answer = None for x in range(2, numRows+1): row = [1]*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] […]

Read more## 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, […]

Read more## 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 […]

Read more## Notes on Memory Mapped Files using mmap

Introduction mmap maps a file to a process virtual address space. The file blocks are loaded as needed, in units of the system page size. Each I/O must align with the page size. A block load is handled as a page fault. mmap() can provide a private or shared mapping of a region. mmap() to […]

Read more