Skip to content

Commit 660f5a0

Browse files
seba3cseba3c
committed
Added new coding challenges
1 parent ba77733 commit 660f5a0

File tree

6 files changed

+364
-1
lines changed

6 files changed

+364
-1
lines changed

‎src/adr_books.py‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@
1111
E.g. Searching for "My" or "book" would match a book containing "My book", but searching for "My b" or "boo" would *not* match.
1212
'''
1313
import re
14+
from sre_constants import SRE_FLAG_DOTALL
1415

1516

1617
LIBRARY_DATA = """
@@ -71,7 +72,7 @@ def __init__(self, data):
7172
if not t:
7273
continue
7374

74-
m = re.search('.*TITLE:(.*)AUTHOR:(.*)DESCRIPTION:(.*)', t, re.DOTALL)
75+
m = re.search('.*TITLE:(.*)AUTHOR:(.*)DESCRIPTION:(.*)', t, SRE_FLAG_DOTALL)
7576

7677
title = m.group(1)
7778
author = m.group(2)

‎src/binary_tree_max_distinct_values.py‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
# -*- coding: utf-8 -*-
2+
import timeit
3+
"""
4+
Find the maximum number of distinct values that appear on a path starting at the root of the
5+
Tree.
6+
"""
7+
8+
9+
class Tree:
10+
11+
def __init__(self, x, l=None, r=None):
12+
self.x = x
13+
self.l = l
14+
self.r = r
15+
16+
17+
def max_distinct_numbers_1(T, values):
18+
if T is None:
19+
return len(set(values))
20+
else:
21+
values.append(T.x)
22+
value = max(max_distinct_numbers_1(T.l, values), max_distinct_numbers_1(T.r, values))
23+
values.remove(T.x)
24+
return value
25+
26+
27+
def solution_1(T):
28+
values = []
29+
return max_distinct_numbers_1(T, values)
30+
31+
32+
def max_distinct_numbers_2(T, count, values):
33+
if T is None:
34+
return count
35+
else:
36+
c = count
37+
if T.x not in values:
38+
values.add(T.x)
39+
c += 1
40+
value = max(max_distinct_numbers_2(T.l, c, values), max_distinct_numbers_2(T.r, c, values))
41+
values.discard(T.x)
42+
return value
43+
44+
45+
def solution_2(T):
46+
values = set()
47+
return max_distinct_numbers_2(T, 0, values)
48+
49+
50+
def build_T1():
51+
G = Tree(5)
52+
D = Tree(4, G)
53+
B = Tree(5, D)
54+
55+
E = Tree(1)
56+
F = Tree(6)
57+
C = Tree(6, E, F)
58+
59+
A = Tree(4, B, C)
60+
return A
61+
62+
63+
def build_T2():
64+
G = Tree(9)
65+
D = Tree(8, G)
66+
B = Tree(5, D)
67+
68+
E = Tree(1)
69+
F = Tree(6)
70+
C = Tree(6, E, F)
71+
72+
A = Tree(4, B, C)
73+
return A
74+
75+
76+
if __name__ == '__main__':
77+
assert solution_1(build_T1()) == 3
78+
assert solution_1(None) == 0
79+
assert solution_1(build_T2()) == 4
80+
81+
assert solution_2(build_T1()) == 3
82+
assert solution_2(None) == 0
83+
assert solution_2(build_T2()) == 4
84+
85+
T = build_T1()
86+
g = {"solution_1": solution_1, "solution_2": solution_2, "T": T}
87+
n = 100000
88+
t = timeit.timeit("solution_1(T)", number=n, globals=g)
89+
print("Time for solution 1: ", t)
90+
91+
t = timeit.timeit("solution_2(T)", number=n, globals=g)
92+
print("Time for solution 2: ", t)

‎src/capitalize_string.py‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
# -*- coding: utf-8 -*-
2+
3+
# Write a program that will correct an input string to use proper capitalization and spacing.
4+
# Allowed punctuation are the period ( . ), question mark ( ? ), and exclamation ( ! ).
5+
# Make sure that single space always follows commas ( , ), colons ( : ), semicolons ( ; )
6+
# and all other punctuation.
7+
# The input string will be a valid English
8+
# sentence.capitalizeString("first, solve the problem.then, write the code.")
9+
# // "First, solve the problem. Then, write the code."
10+
# capitalizeString("this is a test... and another test.")
11+
# // "This is a test... And another test."
12+
import re
13+
14+
15+
def capitalizeString(S):
16+
17+
def upper_after_dot(m):
18+
return m[1] + " " + m[2].strip().capitalize()
19+
20+
if S is not None:
21+
ss = S.strip()
22+
# first letter
23+
ss = ss.capitalize()
24+
# replace more than one space by one space
25+
ss = re.sub("\s+", " ", ss)
26+
# fix . spacing
27+
ss = re.sub(r"([.])(\s{2,*})", r". \2", ss)
28+
ss = re.sub(r"([.])(\w+)", r". \2", ss)
29+
# fix , spacing
30+
ss = re.sub(r"(\,)(\s{2,*})", r", \2", ss)
31+
ss = re.sub(r"(\,)(\w+)", r", \2", ss)
32+
# fix ; spacing
33+
ss = re.sub(r"(\;)(\s{2,*})", r"; \2", ss)
34+
ss = re.sub(r"(\;)(\w+)", r"; \2", ss)
35+
# fix : spacing
36+
ss = re.sub(r"(\:)(\s{2,*})", r": \2", ss)
37+
ss = re.sub(r"(\:)(\w+)", r": \2", ss)
38+
# fix ? spacing
39+
ss = re.sub(r"(\?)(\s{2,*})", r"? \2", ss)
40+
ss = re.sub(r"(\?)(\w+)", r"? \2", ss)
41+
# fix ! spacing
42+
ss = re.sub(r"(\!)(\s{2,*})", r"! \2", ss)
43+
ss = re.sub(r"(\!)(\w+)", r"! \2", ss)
44+
# upper case after .
45+
ss = re.sub(r"([.])(\s[a-z]*)", upper_after_dot, ss)
46+
47+
return ss
48+
return None
49+
50+
51+
if __name__ == '__main__':
52+
53+
print(capitalizeString("first, solve the problem.then, write the code."))
54+
assert capitalizeString("first, solve the problem.then, write the code.") \
55+
== "First, solve the problem. Then, write the code."
56+
57+
print(capitalizeString("this is a test... and another test."))
58+
assert capitalizeString("this is a test... and another test.") \
59+
== "This is a test... And another test."
60+
61+
print(capitalizeString("aaaaa bbbbb,ccccc; ddddd.eeeee"))
62+
assert capitalizeString("aaaaa bbbbb,ccccc; ddddd.eeeee") \
63+
== "Aaaaa bbbbb, ccccc; ddddd. Eeeee"

‎src/domino.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
# -*- coding: utf-8 -*-
2+
3+
# "Domino": We are given an S string, representing a domino tile chain.
4+
# Each tile has an L-R format, where L and R are numbers from the 1..6 range.
5+
# The tiles are separated by a comma. Some examples of a valid S chain are:1.
6+
# "6-3"2. "4-3,5-1,2-2,1-3,4-4"3. "1-1,3-5,5-2,2-3,2-4"
7+
# Devise a function that given an S string, returns the number of tiles in the longest
8+
# matching group within S. A matching group is a set of tiles that match and that are subsequent in S.
9+
# Domino tiles match, if the right side of a tile is the same as the left side of the following tile.
10+
# "2-4,4-1" are matching tiles, but "5-2,1-6" are not.domino("1-1,3-5,5-2,2-3,2-4") //
11+
# should return 3.
12+
13+
14+
def solution(S):
15+
max_count = 0
16+
if S is not None:
17+
tiles = S.split(",")
18+
ccount = 0
19+
for i in range(0, len(tiles)):
20+
cur_tile = tiles[i].split("-")
21+
if (i < len(tiles) - 1):
22+
next_tile = tiles[i + 1].split("-")
23+
if cur_tile[1] == next_tile[0]:
24+
ccount += 1
25+
else:
26+
ccount = 0
27+
if ccount > max_count:
28+
max_count = ccount
29+
max_count = max_count + 1
30+
return max_count
31+
32+
33+
if __name__ == '__main__':
34+
35+
print(solution("2-4,4-1"))
36+
assert solution("2-4,4-1") == 2
37+
print(solution("1-1,3-5,5-2,2-3,2-4"))
38+
assert solution("1-1,3-5,5-2,2-3,2-4") == 3
39+
40+
assert solution("1-1") == 1
41+
assert solution("1-2,1-2") == 2
42+
assert solution("3-2,2-1,1-4,4-4,5-4,4-2,2-1") == 4
43+
assert solution("5-5,5-5,4-4,5-5,5-5,5-5,5-5,5-5,5-5,5-5") == 7
44+
assert solution("1-1,3-5,5-5,5-4,4-2,1-3") == 4
45+
assert solution("1-2,2-2,3-3,3-4,4-5,1-1,1-2") == 3

‎src/proper_prefixes_suffixes.py‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
# -*- coding: utf-8 -*-
2+
import random
3+
import string
4+
import timeit
5+
6+
from concurrent.futures.thread import ThreadPoolExecutor
7+
8+
"""
9+
Get a proper suffix and prefix with the maximum length
10+
"""
11+
12+
13+
def proper_prefixes(S):
14+
prefixs = set([""])
15+
cc = ""
16+
for c in S[0:len(S) - 1]:
17+
cc += c
18+
prefixs.add(cc)
19+
return prefixs
20+
21+
22+
def proper_suffixes(S):
23+
prefixs = set([""])
24+
cc = ""
25+
for c in S[::-1][0:len(S) - 1]:
26+
cc = c + cc
27+
prefixs.add(cc)
28+
return prefixs
29+
30+
31+
def solution_1(S):
32+
"""
33+
Submitted
34+
"""
35+
s1 = proper_prefixes(S) # O(len(S))
36+
s2 = proper_suffixes(S) # O(len(S))
37+
s1.intersection_update(s2) # O(len(s1) * len(s2))
38+
s1 = sorted(s1, reverse=True) # O(len(s1) log len(s1))
39+
return len(s1[0]) # O(1)
40+
41+
42+
def solution_2(S):
43+
"""
44+
Using threads
45+
"""
46+
t = ThreadPoolExecutor(2)
47+
t1 = t.submit(proper_prefixes, S)
48+
t2 = t.submit(proper_suffixes, S)
49+
s1 = t1.result()
50+
s2 = t2.result()
51+
s1.intersection_update(s2)
52+
s1 = sorted(s1, reverse=True)
53+
return len(s1[0])
54+
55+
56+
def solution_3(S):
57+
current = ""
58+
start = 0
59+
end = len(S) - 1
60+
prefix = ""
61+
suffix = ""
62+
for i in range(start, end): # O(N - 1)
63+
prefix += S[i] # ##
64+
suffix = S[end - i] + suffix # O(1)
65+
if prefix == suffix: #
66+
current = prefix # ##
67+
return len(current) # O(1)
68+
69+
70+
def build_input(N):
71+
return ''.join(random.choices(string.ascii_lowercase, k=N))
72+
73+
74+
if __name__ == '__main__':
75+
76+
assert solution_1("codibility") == 0
77+
assert solution_1("abbabba") == 4
78+
79+
assert solution_2("codibility") == 0
80+
assert solution_2("abbabba") == 4
81+
82+
assert solution_3("codibility") == 0
83+
assert solution_3("abbabba") == 4
84+
85+
S = build_input(1000)
86+
assert solution_1(S) == solution_3(S)
87+
88+
S = build_input(10000)
89+
g = {"solution_1": solution_1, "solution_2": solution_2, "solution_3": solution_3, "S": S}
90+
n = 100
91+
t = timeit.timeit("solution_1(S)", number=n, globals=g)
92+
print("Time for solution 1: ", t)
93+
94+
t = timeit.timeit("solution_2(S)", number=n, globals=g)
95+
print("Time for solution 2: ", t)
96+
97+
t = timeit.timeit("solution_3(S)", number=n, globals=g)
98+
print("Time for solution 3: ", t)

‎src/unique_permutations.py‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# -*- coding: utf-8 -*-
2+
import random
3+
import timeit
4+
import itertools
5+
6+
7+
def solution_1(N):
8+
n = str(N)
9+
# https://docs.python.org/2/library/itertools.html#itertools.permutations
10+
p = itertools.permutations(n, len(n))
11+
p = set(p)
12+
p = list(itertools.filterfalse(lambda x: len(x) > 1 and x[0] == '0', p))
13+
return len(p)
14+
15+
16+
def solution_2(N):
17+
"""
18+
Submitted
19+
"""
20+
n = str(N)
21+
ps = itertools.permutations(n, len(n))
22+
result = set()
23+
for p in ps:
24+
if (len(p) > 1 and p[0] != '0' or len(p) == 1) and p not in result:
25+
result.add(p)
26+
return len(result)
27+
28+
29+
def solution_3(N):
30+
n = str(N)
31+
p = itertools.permutations(n, len(n))
32+
p = set(p)
33+
p = list(itertools.filterfalse(lambda x: x[0] == '0' and len(x) > 1, p))
34+
return len(p)
35+
36+
37+
if __name__ == '__main__':
38+
39+
assert solution_1(0) == 1
40+
assert solution_1(1213) == 12
41+
assert solution_1(123) == 6
42+
assert solution_1(100) == 1
43+
44+
assert solution_2(0) == 1
45+
assert solution_2(1213) == 12
46+
assert solution_2(123) == 6
47+
assert solution_2(100) == 1
48+
49+
assert solution_3(0) == 1
50+
assert solution_3(1213) == 12
51+
assert solution_3(123) == 6
52+
assert solution_3(100) == 1
53+
54+
N = random.randint(100000000, 999999999)
55+
g = {"solution_1": solution_1, "solution_2": solution_2, "solution_3": solution_3, "N": N}
56+
n = 1000
57+
t = timeit.timeit("solution_1(N)", number=n, globals=g)
58+
print("Time for solution 1: ", t)
59+
60+
t = timeit.timeit("solution_2(N)", number=n, globals=g)
61+
print("Time for solution 2: ", t)
62+
63+
t = timeit.timeit("solution_3(N)", number=n, globals=g)
64+
print("Time for solution 3: ", t)

0 commit comments

Comments
 (0)