deque-blog’s gists

deque-blog / drop_egg.py

Created March 3, 2020 16:12

	def drop_egg(n: int) -> int:
	return math.ceil(math.sqrt(2 * n + 0.25) - 0.5)

deque-blog / find_guilty_commit.py

Created March 3, 2020 14:35

	def find_guilty_commit(commits: List[CommitId]) -> Optional[CommitId]:
	lo = 0
	hi = len(commits) - 1
	while lo <= hi:
	mid = lo + (hi - lo) // 2
	if is_test_failing(commits[mid]):
	hi = mid - 1
	else:
	lo = mid + 1
	return commits[lo] if lo < len(commits) else None

deque-blog / poor_pigs.py

Created March 1, 2020 18:43

	def poor_pigs(buckets: int, iterations: int):
	pigs = math.log(buckets, iterations + 1)
	return math.ceil(pigs)

deque-blog / guess_mapping_full.py

Created February 27, 2020 15:53

	def topological_sort(graph: Dict[Any, Iterable[Any]]) -> List[Any]:
	ordered = []
	discovered = set()

	def dfs(node):
	for children in graph.get(node, []):
	if children not in discovered:
	discovered.add(children)
	dfs(children)
	ordered.append(node)

deque-blog / guess_mapping.py

Created February 27, 2020 15:51

	def guess_mapping(words: List[str]) -> Dict[str, str]:
	ordering_constraints : Dict[str, Set[str]] = find_constraints(words)
	ordered_letters: List[str] = topological_sort(ordering_constraints)
	return {dst: src for src, dst in zip(string.ascii_lowercase, ordered_letters)}

deque-blog / longestValidParentheses_linear.py

Created February 27, 2020 14:07

	def longestValidParentheses(s: str) -> int:
	def scan(s: str, opening_char: str) -> int:
	longest = 0
	opened = 0
	start = 0
	for i in range(len(s)):
	if s[i] == opening_char:
	opened += 1
	elif opened > 0:
	opened -= 1

deque-blog / longestValidParentheses_better.py

Created February 27, 2020 13:41

	def longestValidParentheses(s: str) -> int:
	def longest_from(i: int) -> int:
	longest = 0
	opened = 0
	for j in range(i, len(s)):
	if s[j] == '(':
	opened += 1
	elif opened > 0:
	opened -= 1
	if opened == 0:

deque-blog / longestValidParentheses_naive.py

Last active February 27, 2020 13:33

	def longestValidParentheses(s: str) -> int:
	def is_valid(i: int, j: int) -> bool:
	opened = 0
	for c in s[i:j+1]:
	if c == '(':
	opened += 1
	elif opened > 0:
	opened -= 1
	else:
	return False

deque-blog / maxArea_last.py

Created February 26, 2020 17:18

	def maxArea(heights: List[int]) -> int:
	i = 0
	j = len(heights) - 1
	max_area = 0
	while i < j:
	width = j - i
	if heights[i] < heights[j]:
	max_area = max(max_area, width * heights[i])
	i += 1
	else:

deque-blog / maxArea_linear.py

Created February 26, 2020 17:14

	def maxArea(heights: List[int]) -> int:
	i = 0
	j = len(heights) - 1
	max_area = 0
	while i < j:
	width = j - i
	height = min(heights[i], heights[j])
	max_area = max(max_area, width * height)
	if heights[i] < heights[j]:
	i += 1