Skip to content

Instantly share code, notes, and snippets.

View coldmanck's full-sized avatar

Meng-Jiun Chiou coldmanck

View GitHub Profile
@coldmanck
coldmanck / 0063_backtrack.py
Created May 15, 2020 11:13
LeetCode 0063 combination sum (Backtrack)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def combination_sum(cur_ans, cur_sum, cand_idx):
if cur_sum >= target:
if cur_sum == target:
ans.append(cur_ans)
return
for i in range(cand_idx, len(candidates)):
combination_sum(cur_ans + [candidates[i]], cur_sum + candidates[i], i)
ans = []
combination_sum([], 0, 0)
@coldmanck
coldmanck / 0063_bfs.py
Created May 15, 2020 11:12
LeetCode 0063 combination sum (BFS)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
# BFS
from collections import deque
queue = deque() # [cur_target, cur_ans, cand_idx]
queue.append((target, [], 0))
ans = []
while queue:
cur_target, cur_ans, cand_idx = queue.popleft()
for i in range(cand_idx, len(candidates)):
new_target = cur_target - candidates[i]
@coldmanck
coldmanck / 0063_dp.py
Created May 15, 2020 11:11
LeetCode 0063 combination sum (DP)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
cache = [[] for _ in range(target + 1)]
cache[0] = [[]]
for c in candidates:
for i in range(target + 1):
if i >= c:
for temp_ans in cache[i - c]:
cache[i].append(temp_ans + [c])
return cache[-1]
def infectious_rabbit(grid):
nb_of_timestamp = 0
neighbors = [[1,0],[-1,0],[0,1],[0,-1]]
updated = True
while updated:
updated = False # assume that after this infection there's no more neighbor rabbit to infect
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1: # for each healthy rabbit see if there's infectious rabbits nearby
for nb in neighbors: # for each of its neighbors
@coldmanck
coldmanck / The Technical Interview Cheat Sheet.md
Created November 13, 2016 04:25 — forked from tsiege/The Technical Interview Cheat Sheet.md
This is my technical interview cheat sheet. Feel free to fork it or do whatever you want with it. PLEASE let me know if there are any errors or if anything crucial is missing. I will add more links soon.

Studying for a Tech Interview Sucks, so Here's a Cheat Sheet to Help

This list is meant to be a both a quick guide and reference for further research into these topics. It's basically a summary of that comp sci course you never took or forgot about, so there's no way it can cover everything in depth. It also will be available as a gist on Github for everyone to edit and add to.

Data Structure Basics

###Array ####Definition:

  • Stores data elements based on an sequential, most commonly 0 based, index.
  • Based on tuples from set theory.
@coldmanck
coldmanck / gpa_calc.py
Last active August 29, 2015 14:13 — forked from fkztw/gpa_calc.py
# -*-coding: utf-8-*-
def find_gpa(grade):
if 100 >= grade >= 90:
return [grade, 'A+', 4.3]
elif 89 >= grade >= 85:
return [grade, 'A', 4.0]
elif 84 >= grade >= 80:
return [grade, 'A-', 3.7]
elif 79 >= grade >= 77: