closingtime
BAN USER'''
479
xyz
x - hundred
y - ninety, eighty, seventy, ..., twenty,
z -
nineteen, eighteen, seventeen, ..., twelve, eleven, ten
nine, eight, seven, six, ..., two, one
'''
DIGIT_MAP = {
1: 'one',
2: 'two',
3: 'three',
4: 'four',
5: 'five',
6: 'six',
7: 'seven',
8: 'eight',
9: 'nine'
}
DOUBLES_MAP = {
2: 'twenty',
3: 'thirty',
4: 'fourty',
5: 'fifty',
6: 'sixty',
7: 'seventy',
8: 'eighty',
9: 'ninety'
}
TEENS_MAP = {
10: 'ten',
11: 'eleven',
12: 'twelve',
13: 'thirteen',
14: 'fourteen',
15: 'fifteen',
16: 'sixteen',
17: 'seventeen',
18: 'eighteen',
19: 'nineteen'
}
def hundreds_group_to_words(num, groups, suffix=None):
if num == 0:
return
x = (num // 100) % 10
y = (num // 10) % 10
z = (num // 1) % 10
group = []
if x > 0:
group.append(DIGIT_MAP[x])
group.append('hundred')
if y > 0:
if y > 1:
group.append(DOUBLES_MAP[y])
if z > 1:
group.append(DIGIT_MAP[z])
else:
group.append(TEENS_MAP[y * 10 + z])
elif z > 0:
group.append(DIGIT_MAP[z])
if suffix is not None:
group.append(suffix)
groups.append(group)
def digits_to_words(s):
# 0 <= num < 1000000000000 (1 trillion)
n = len(s)
assert n > 0, f"s must be non-empty: {s}"
if s[0] == '-':
n -= 1
negative = True
else:
negative = False
assert n < 13, f"s must be less than 1000000000000: {s}"
num = -int(s) if negative else int(s)
groups = []
# Pre-thousands
pre_k = num % 1000
hundreds_group_to_words(pre_k, groups)
# Pre-millions
num //= 1000
pre_m = num % 1000
hundreds_group_to_words(pre_m, groups, 'thousand')
# Pre-billions
num //= 1000
pre_g = num % 1000
hundreds_group_to_words(pre_g, groups, 'million')
# Pre-trillions
num //= 1000
pre_t = num % 1000
hundreds_group_to_words(pre_t, groups, 'billion')
if negative:
groups.append(['negative'])
# for group in groups[::-1]:
# print(group)
# tmp = ' '.join(group)
# print(tmp.__repr__())
return ' '.join(' '.join(group) for group in groups[::-1])
print(digits_to_words('-100904'))
print(digits_to_words('1234567890'))
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
def __eq__(self, other):
return self.start == other.start and self.end == other.end
def __str__(self):
return "%s(%d, %d)" % (Interval.__name__, self.start, self.end)
def solution(intervals, val):
# Is val left of first interval?
if val < intervals[0].start:
if val + 1 == intervals[0].start:
intervals[0].start -= 1
else:
intervals.insert(0, Interval(val, val))
return intervals
for i, left_interval, right_interval in zip(range(len(intervals) - 1), intervals[:-1], intervals[1:]):
# We're guaranteed left_interval doesn't intersect right_interval
# We're guaranteed left_interval is left of right_interval
# Is val in left_interval?
if left_interval.start <= val <= left_interval.end:
return intervals
# Is val in right_interval?
elif right_interval.start <= val <= right_interval.end:
return intervals
# Is val is between left_interval and right_interval?
elif left_interval.end < val < right_interval.start:
if left_interval.end + 1 == val == right_interval.start - 1:
right_end = right_interval.end
del intervals[i + 1]
intervals[i].end = right_end
elif left_interval.end + 1 == val and val != right_interval.start - 1:
intervals[i].end += 1
elif left_interval.end + 1 != val and val == right_interval.start - 1:
intervals[i + 1].start -= 1
else:
intervals.insert(i + 1, Interval(val, val))
return intervals
else:
# continue searching
continue
# Is val right of last interval?
if val > intervals[-1].end:
if intervals[-1].end + 1 == val:
intervals[-1].end += 1
else:
intervals.append(Interval(val, val))
return intervals
intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 5)
print(attempt[0], end=' ')
print()
assert len(attempt) == 1
assert attempt[0] == Interval(1, 8)
intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 1)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(6, 8)
intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 0)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(0, 4)
assert attempt[1] == Interval(6, 8)
intervals = [Interval(1, 4), Interval(6, 8)]
attempt = solution(intervals, 10)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 3
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(6, 8)
assert attempt[2] == Interval(10, 10)
intervals = [Interval(1, 3), Interval(7, 8)]
attempt = solution(intervals, 5)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 3
assert attempt[0] == Interval(1, 3)
assert attempt[1] == Interval(5, 5)
assert attempt[2] == Interval(7, 8)
intervals = [Interval(1, 3), Interval(7, 8)]
attempt = solution(intervals, 4)
for interval in attempt:
print(interval, end=' ')
print()
assert len(attempt) == 2
assert attempt[0] == Interval(1, 4)
assert attempt[1] == Interval(7, 8)
We can slightly optimize by using binary search instead of linear search.
def solution2(intervals, val):
def binary_search(intervals, lo, hi, val):
if hi == lo + 1:
interval_lo, interval_hi = intervals[lo], intervals[hi]
if interval_lo.start <= val <= interval_lo.end:
return True, lo
elif interval_hi.start <= val <= interval_hi.end:
return True, hi
elif interval_lo.end < val < interval_hi.start:
return False, lo + 1
elif val < interval_lo.start:
return False, -1
elif interval_hi.end < val:
return False, hi + 1
mid = lo + ((hi - lo) >> 1)
interval_lo, interval_mid, interval_hi = intervals[lo], intervals[mid], intervals[hi]
if interval_mid.start <= val <= interval_mid.end:
return True, mid
elif val < interval_mid.start:
return binary_search(intervals, lo, mid, val)
elif val > interval_mid.end:
return binary_search(intervals, mid, hi, val)
n = len(intervals)
intersects, i = binary_search(intervals, 0, n - 1, val)
if not intersects:
if i == -1:
if val + 1 == intervals[0].start:
intervals[0].start = val
else:
intervals.insert(0, Interval(val, val))
elif i == n:
if intervals[-1].end + 1 == val:
intervals[-1].end = val
else:
intervals.append(Interval(val, val))
else:
interval_lo, interval_hi = intervals[i - 1], intervals[i]
if interval_lo.end + 1 == val and val == interval_hi.start - 1:
hi_end = interval_hi.end
del intervals[i]
intervals[i - 1].end = hi_end
elif interval_lo.end + 1 == val and val != interval_hi.start - 1:
intervals[i - 1].end += 1
elif interval_lo.end + 1 != val and val == interval_hi.start - 1:
intervals[i].start -= 1
else:
intervals.insert(i, Interval(val, val))
return intervals
Perform DFS with a stack that represents the simple path you're currently on.
If you visit a node that's already in the simple path, you ignore it.
When you reach a cycle, record it if its size is smaller than the current
smallest recorded cycle.
import copy
# Assuming adjacency format
def solution(node):
cycle_path = None
# Assuming the node is indeed in the graph
# Assuming there is indeed a cycle
def dfs(orig_node, node, node_stack, stack_set):
node_stack.append(node)
stack_set.add(node)
for neighbor in node.neighbors():
if neighbor == orig_node:
if cycle_path is None or len(cycle_path) > len(node_stack):
cycle_path = copy.deepcopy(node_stack)
return
if neighbor
if neighbor not in stack_set:
dfs(orig_node, neighbor, node_stack, stack_set);
node_stack.pop()
stack_set.remove(node)
node_stack = []
stack_set = set()
dfs(node, node, node_stack, stack_set);
cycle_path.append(node)
return cycle_path
Another approach is to find the strongly connected components of the graph (or at least the sub-graph that is connected to the target node).
- closingtime November 13, 2017class Node(object):
def __init__(self):
self.children = {}
class Trie(object):
def __init__(self):
self.sentinel = Node()
def add_word(self, word):
curr_node = self.sentinel
for c in word:
if c in curr_node.children:
curr_node = curr_node.children[c]
else:
new_node = Node()
curr_node.children[c] = new_node
curr_node = new_node
def _search(self, tokens, i, curr_node):
# Base case: No tokens, default True
if i == len(tokens):
return True
# Wildcard
if tokens[i][-1] == '*':
# Wildcard matches with nothing
if self._search(tokens, i + 1, curr_node):
return True
# '.*' encountered
if tokens[i][0] == '.':
# Return False if we need to match with something
# but there's nothing left in the string.
#
# Otherwise, recurse with the same token
# and the next character in the string.
return (len(curr_node.children) != 0
and any(self._search(tokens, i, child)
for child in curr_node.children.values()))
# 'w*' encountered, where w is any non-. character
else:
# Return False if we need to match with something
# but there's nothing left in the string.
#
# Otherwise, recurse with the same token
# and the next character in the string.
return (tokens[i][0] in curr_node.children
and self._search(tokens, i, curr_node.children[tokens[i][0]]))
# Single character match
else:
if tokens[i] == '.':
# Return False if we need to match with something
# but there's nothing left in the string.
#
# Otherwise, recurse with the next token
# and the next character in the string.
return (len(curr_node.children) != 0
and any(self._search(tokens, i, child)
for child in curr_node.children.values()))
else:
# Return False if we need to match with something
# but there's nothing left in the string.
#
# Otherwise, recurse with the next token
# and the next character in the string.
return (tokens[i] in curr_node.children
and self._search(tokens, i + 1, curr_node.children[tokens[i]]))
def search(self, regex):
# Assuming valid regex, tokenize
tokens = []
n = len(regex)
i = 0
while i < n:
if i == n - 1 or regex[i + 1] != '*':
tokens.append(regex[i])
i += 1
else:
tokens.append(regex[i : i + 2])
i += 2
return self._search(tokens, 0, self.sentinel)
t = Trie()
t.add_word('mad')
t.add_word('bag')
t.add_word('fad')
t.search('.*d')
'''
F(i) =
if A[i] == 0:
min(1 + F(i + 1), N1[i + 1])
else:
min(1 + N0[i + 1], F(i + 1))
F(n - 1) = 0
N0[i]: number of 0's in A[i:]
N1[i]: number of 1's in A[i:]
Bottom-up DP complexity:
Time: O(n)
Space: O(1)
'''
from itertools import accumulate, islice
def solution(binary_array):
n = len(binary_array)
if n <= 1:
return 0
N0 = accumulate([1 - bit for bit in binary_array[::-1]])
N1 = accumulate(binary_array[::-1])
f = 0
for n0, n1, i in zip(N0, N1, range(n - 1, -1, -1)):
bit = binary_array[i]
if bit == 0:
f = min(1 + f, n1)
else:
f = min(1 + n0, f)
return f
A = [1, 1, 0, 1, 0, 0, 0, 1, 0]
attempt = solution(A)
print(attempt)
assert attempt == 2
A = [0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]
attempt = solution(A)
print(attempt)
assert attempt == 5
A = [1, 0, 1, 1, 0, 0, 0]
attempt = solution(A)
print(attempt)
assert attempt == 1
'''
window:
* queue of intervals
* running count of strictly increasing subarrays
* running count of strictly decreasing subarrays
* keep track of flat subarrays too
@ every window step, we output num_incr_subarrs - num_decr_subarrs
Time complexity: O(n)
Space complexity: O(k)
'''
from collections import deque # Pythonic queue
class Interval(object):
def __init__(self, slope, x, y):
self.slope = slope
self.q = deque()
self.q.append(x)
self.q.append(y)
class Window(object):
def __init__(self):
self.queue = deque()
self.num_incr_subarrs = 0
self.num_decr_subarrs = 0
self.start_new_interval_flag = True
def insert(self, num1, num2):
# Strictly Increasing
if num1 < num2:
if (self.start_new_interval_flag
or len(self.queue) == 0
or not self.queue[-1].slope > 0):
self.queue.append(Interval(1, num1, num2))
else:
self.queue[-1].q.append(num2)
self.num_incr_subarrs += len(self.queue[-1].q) - 1
self.start_new_interval_flag = False
# Strictly Decreasing
elif num1 > num2:
if (self.start_new_interval_flag
or len(self.queue) == 0
or not self.queue[-1].slope < 0):
self.queue.append(Interval(-1, num1, num2))
else:
self.queue[-1].q.append(num2)
self.num_decr_subarrs += len(self.queue[-1].q) - 1
self.start_new_interval_flag = False
# Flat
else:
self.queue.append(Interval(0, num1, num2))
self.start_new_interval_flag = True
def cut_left(self):
if len(self.queue) == 0:
return
interval = self.queue[0]
if interval.slope > 0:
self.num_incr_subarrs -= len(interval.q) - 1
elif interval.slope < 0:
self.num_decr_subarrs -= len(interval.q) - 1
if len(interval.q) == 2:
self.queue.popleft()
else:
interval.q.popleft()
def solution(nums, k):
n = len(nums)
assert k > 1
assert n >= k
output = []
# Populate initial window
window = Window()
for i in range(k - 1):
window.insert(nums[i], nums[i + 1])
output.append(window.num_incr_subarrs - window.num_decr_subarrs)
for i in range(k - 1, n - 1):
window.cut_left()
window.insert(nums[i], nums[i + 1])
output.append(window.num_incr_subarrs - window.num_decr_subarrs)
return output
nums = [188930, 194123, 201345, 154243, 154243]
k = 3
attempt = solution(nums, k)
print(attempt)
assert attempt[0] == 3
assert attempt[1] == 0
assert attempt[2] == -1
Count each number, and put into hashmap. Dump the hashmap contents into an auxiliary array. Perform quickselect on that array. Total O(n) time and O(n) space.
- closingtime March 08, 2018