Vassili Gorshkov
BAN USERI have not looked at all the solutions in this thread, but the ones I did look at had O(N**2) complexity metric. Below I offer 2 solutions: one naive O(N**2) and one that executes in O(N) time.
# input [2,3,1,4]
# output [12,8,24,6]
#
# Multiply all fields except it's own position.
#
# Restrictions:
# 1. no use of division
# 2. complexity in O(n)
#
# O(N**2) solution
def multiply_list_O_nn(l: list) -> list:
res = [1] * len(l)
for i in range(len(l)):
for j in range(len(l)):
res[i] *= l[j] if i != j else 1
return res
# O(N) solution
def multiply_list_O_n(l: list) -> list:
tree_mul_children = []
tree_mul_others = []
# First compute tree_mul_children
last_row = l
tree_mul_children.append(l)
while len(last_row) > 1:
new_row = []
for i in range(0, len(last_row), 2):
if i + 1 < len(last_row):
s = last_row[i] * last_row[i + 1]
else:
s = last_row[i]
new_row.append(s)
tree_mul_children.append(new_row)
last_row = new_row
tree_mul_children.reverse()
# Now compute tree_mul_others
tree_mul_others.append([1])
for i in range(1, len(tree_mul_children)):
row = tree_mul_children[i]
new_row = []
for j in range(len(row)):
mul_others = tree_mul_others[i - 1][j // 2] * row[(j % 2 + 1) % 2 + j // 2 * 2]
new_row.append(mul_others)
tree_mul_others.append(new_row)
return tree_mul_others[-1]
print(multiply_list_O_nn([2, 3, 1, 4]))
print(multiply_list_O_n([2, 3, 1, 4]))
# A k-palindrome is a string which transforms into a palindrome on removing at most k characters.
#
# Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".
# Constraints:
# S has at most 20,000 characters.
# 0<=k<=30
#
# Sample Test Case#1:
# Input - abxa 1
# Output - YES
# Sample Test Case#2:
# Input - abdxa 1
# Output - No
import string
import random
def lev_distance_modified(a: list, b: list, max_dist: int, dist: int) -> int:
# See if we can terminate early
if dist > max_dist:
res = dist
elif len(a) == 0:
res = len(b)
elif len(b) == 0:
res = len(a)
elif a[0] == b[0]:
res = lev_distance_modified(a[1:], b[1:], max_dist, dist)
else:
res = min([
lev_distance_modified(a, b[1:], max_dist, dist + 1), # 1 delete from b
lev_distance_modified(b, a[1:], max_dist, dist + 1), # 1 delete from a
lev_distance_modified(a[1:], b[1:], max_dist, dist + 2)]) # 2 deletes one for each side
return res
def num_palindrome_deletes(s: str, max_dist: int) -> str:
l = list(s)
r = list(reversed(l))
return lev_distance_modified(l, r, max_dist, 0)
def is_k_palindrome(s: str, k: int) -> str:
return num_palindrome_deletes(s, k * 2) <= k * 2
print(is_k_palindrome("abxa", 1))
print(is_k_palindrome("abdxa", 1))
s = "".join(random.choices(string.ascii_letters, k=20000))
print(is_k_palindrome(s, 6))
# Given a length n, count the number of strings of length n that can be made
# using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.
def num_strings(n: int) -> int:
case_all_a = 1
case_c = n
case_b = n
case_cc = n * (n - 1) / 2 # divide by 2 since the order doesn't matter
case_cb = n * (n - 1)
case_ccb = n * (n - 1) * (n - 2) / 2
res = case_all_a
if n > 0:
res += case_c + case_b
if n > 1:
res += case_cc + case_cb
if n > 2:
res += case_ccb
return res
for i in range(5):
print(f"num_strings({i}) => {num_strings(i)}")
add_rules = {
('0', '0', '0'): ('0', '0'),
('0', '0', '1'): ('0', '1'),
('0', '1', '0'): ('0', '1'),
('0', '1', '1'): ('1', '0'),
('1', '0', '0'): ('0', '1'),
('1', '0', '1'): ('1', '0'),
('1', '1', '0'): ('1', '0'),
('1', '1', '1'): ('1', '1'),
}
def add_binary_strings(l: str, r: str) -> str:
result = []
c = '0'
l1 = list(reversed(list(l)))
r1 = r[::-1]
# Pad both list with '0' to the same length
while len(l1) < len(r1):
l1.append('0'),
while len(r1) < len(l1):
r1.append('0')
for a, b in zip(l1, r1):
c, v = add_rules[(c, a, b)]
result.append(v)
if c == '1':
result.append(c)
result.reverse()
return "".join(result)
print(add_binary_strings("101101", "1101010") == "10010111")
# Given an integer array and an integer K, find the number of sub array in
# which all elements are less than K.
#
# Follow up -
# Given an integer array and an integer K, find the number of non
# overlapping unordered pairs of sub array in which all elements are less
# than K.
from itertools import combinations
K = 10
a = [1, 2, 3, 11, 4, 5, 12, 13, 7]
def get_sub_array_sizes(a: [int], k: int):
sub_size = 0
for v in a:
if v < k:
sub_size += 1
else:
if sub_size > 0:
yield sub_size
sub_size = 0
if sub_size > 0:
yield sub_size
# Count the number of max size sub array with all elements less than K
# For the example above, sub array are: [1,2,3], [4, 5], [7]. num = 3
def num_sub_arrays(a: [int], k: int) -> int:
return sum(1 for i in get_sub_array_sizes(a, k))
# number of non overlapping interval pairs in a range(n)
# e.g. range(1,3) can produce the following pairs:
# [[1,(2,3)], [1, 2], [1,3], [(1,2), 3], [2,3]
# for the total of 5 pairs
def num_range_interval_pairs(n: int) -> int:
return sum((i + 1) * (n - i - 1) * (n - i) / 2 for i in range(n))
# Number of non overlapping subarray pairs size > 0 with all elements < K
def num_outer_sub_array_pairs(a: [int], k: int) -> int:
return sum(a * (a+1)/2 * b * (b+1)/2
for a, b in combinations(get_sub_array_sizes(a, k), 2))
def num_inner_sub_array_pairs(a: [int], k: int) -> int:
return sum(num_range_interval_pairs(a) for a in get_sub_array_sizes(a, k))
def num_sub_array_pairs(a: [int], k: int) -> int:
return num_inner_sub_array_pairs(a, k) + num_outer_sub_array_pairs(a, k)
print(num_sub_arrays(a, K))
print(num_sub_array_pairs(a, K))
[]
- Vassili Gorshkov April 10, 2021[[2, 3, 1, 2, 1, 3], [3, 1, 2, 1, 3, 2]]
[[2, 3, 4, 2, 1, 3, 1, 4], [4, 1, 3, 1, 2, 4, 3, 2]]
[]
[]
[[1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7], [1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5], [1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7], [1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7], [1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3], [1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6], [1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7], [1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3], [1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4], [1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5], [2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5], [2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4], [2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5], [2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7], [2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7], [2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5], [2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3], [2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6], [3, 4, 5, 7, 3, 6, 4, 1, 5, 1, 2, 7, 6, 2], [3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5], [3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4], [3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1], [3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5], [3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1], [4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5], [4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5], [4, 5, 6, 7, 1, 4, 1, 5, 3, 6, 2, 7, 3, 2], [4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5], [4, 6, 1, 7, 1, 4, 5, 2, 6, 3, 2, 7, 5, 3], [4, 6, 3, 5, 7, 4, 3, 2, 6, 5, 2, 1, 7, 1], [5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3], [5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7], [5, 2, 4, 7, 2, 6, 5, 4, 1, 3, 1, 7, 6, 3], [5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7], [5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4], [5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1], [5, 3, 6, 7, 2, 3, 5, 2, 4, 6, 1, 7, 1, 4], [5, 6, 1, 7, 1, 3, 5, 4, 6, 3, 2, 7, 4, 2], [5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2], [5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4], [5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1], [5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2], [6, 1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2], [6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1], [7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5], [7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2], [7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1], [7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1], [7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1], [7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5], [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1], [7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2]]