Basic: Useful Code Templates For Code Test

Common code templates for typical problems.



Get all codetemplate problems: #codetemplate.

Please Leave Me Comments For Suggestions.

About templates, get familiar with:

  1. code structure
  2. variable/functions definitions

Templates:

First Bad Version

## Blog link: https://code.dennyzhang.com/first-bad-version
## Basic Ideas: Binary search
##         Find the first False
##         F F F F T T
##         T T
##      Hint: how to update index, if mid is F?
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = left + (right-left)/2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        # left == right
        return left if isBadVersion(left) else None

Find Minimum in Rotated Sorted Array

## Blog link: https://code.dennyzhang.com/find-minimum-in-rotated-sorted-array
class Solution:
    ## Basic Ideas: Binary Search
    ##   Check current node with the right node of the range
    ##   If it's smaller, check left half(included). Check the right half(excluded)
    ##
    ##   Notice: Here we can't compare it with the left node of the range.
    ##      Why? (0+1)/2 == 0. We might run into dead loop with left == mid.
    ##
    ## Complexity: Time O(log(n)), Space O(1)
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 0: return None
        # 4 5 6 7 0 1 2
        left, right = 0, length-1
        while left<right:
            mid = left + (int)((right-left)/2)
            if nums[mid] < nums[right]:
                # check the left half(included)
                right = mid
            else:
                # check the right half(excluded)
                left = mid + 1
        return nums[left]

Search Insert Position


## Blog link: https://code.dennyzhang.com/open-the-lock
dead_set, seen, queue = set([]), set([]), collections.deque([])
for dead in deadends: dead_set.add(dead)
if '0000' in dead_set: return -1
if '0000' == target: return 0

level = 0
queue.append('0000')
seen.add('0000')
while len(queue) != 0:
    level += 1
    for k in xrange(len(queue)):
        node = queue.popleft()
        # find next neighbors
        for i in xrange(4):
            for offset in [1, -1]:
                ascii = (ord(node[i]) - ord('0') + offset + 10) % 10 + ord('0')
                ch = chr(ascii)
                neighbor = node[0:i]+ch+node[i+1:]
                if (neighbor in seen) or (neighbor in dead_set):
                    continue
                # If found, stop immediately
                if neighbor == target:
                    # print node, neighbor
                    return level
                queue.append(neighbor)
                seen.add(neighbor)
return -1

## Blog link: https://code.dennyzhang.com/number-of-islands
        res = 0
        for i in xrange(self.row_count):
            for j in xrange(self.col_count):
                if grid[i][j] == '1':
                    res += 1
                    self.DFSMark(grid, i, j)
        return res

    def DFSMark(self, grid, i, j):
        if i < 0 or i >= self.row_count \
            or j < 0 or j >= self.col_count:
            return

        # stop digging, if not '1'
        if grid[i][j] != '1': return

        grid[i][j] = 'X'
        # mark four positions in a recursive way
        self.DFSMark(grid, i-1, j)
        self.DFSMark(grid, i+1, j)
        self.DFSMark(grid, i, j-1)
        self.DFSMark(grid, i, j+1)

## Blog link: https://code.dennyzhang.com/longest-word-in-dictionary
## Basic Ideas: trie tree
## Complexity: Time O(n), Space O(n). n the count of characters involved
class TrieNode(object):
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        # Build TrieNode
        root = TrieNode()
        # check each word, and insert if missing
        for word in words:
            # always check from the top
            node = root
            for ch in word:
                node = node.children[ch]
            node.is_word = True

        return self.foundLongestWord(root)

    def foundLongestWord(self, node):
        """
        :rtype: (length, str)
        """
        # BFS:
        # How to check:
        #    Candidates should be: 
        #             1. is_word as true for all nodes in the path. 
        #             2. Has no children
        # How to move to next:
        #   Only check nodes with is_word as True
        #   When node has no children, we 
        max_length, max_str = 0, ''
        queue = []
        # initialize queue
        # Since we have sorted the keys, we will get smallest lexicographical match
        for ch in sorted(node.children):
            child = node.children[ch]
            if child.is_word:
                queue.append((child, ch, 1))

        while len(queue) != 0:
            (node, str, length) = queue[0]
            del queue[0]
            if length > max_length:
                max_length, max_str = length, str
            for ch in sorted(node.children):
                child = node.children[ch]
                if child.is_word:
                    queue.append((child, '%s%s' % (str, ch), length+1))
        return max_str

Revert a linked list: Reverse Linked List II










## Blog link: https://code.dennyzhang.com/number-of-1-bits
res = 0
while n != 0:
    n = n & (n-1)
    res += 1
return res

## Blog link: https://code.dennyzhang.com/kth-largest-element-in-an-array
q = []
for num in nums: heapq.heappush(q, num)
return heapq.nlargest(k, q)[-1]

## Blog link: https://code.dennyzhang.com/daily-temperatures
## Basic Ideas: Monotonous stack can help us find first largest element in O(n) time complexity.
##
##              Descending stack: find the next bigger nubmer for each element
##
##              For any given number, if we haven't met the bigger number. We push it to the stack
##              If we pop out one element, we do find a bigger number than this element.
##
## Complexity: Time O(n), Space O(n)
class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        length = len(temperatures)
        res = [0]*length
        stack = []
        for i in xrange(length):
            # If current number is bigger, we solved the previous puzzles
            while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                k = stack.pop()
                # t[i] is the next bigger number than t[k]
                res[k] = i-k
            stack.append(i)
        return res

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.