# Basic: Useful Code Templates For Code Test

Common code templates for typical problems.

Get all codetemplate problems: #codetemplate.

1. code structure
2. variable/functions definitions

Templates:

```## 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?
# @param version, an integer
# @return a bool
class Solution(object):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left < right:
mid = left + (right-left)/2
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([])
if '0000' in dead_set: return -1
if '0000' == target: return 0

level = 0
queue.append('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)
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
```

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

Share It, If You Like It.