Skip to content

Commit feece1b

Browse files
author
Ankit Thakur
committed
adding more problems
1 parent 6c74baa commit feece1b

75 files changed

Lines changed: 2145 additions & 44 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎algoexpert/sorting/__init__.py‎

Whitespace-only changes.

‎algoexpert/sorting/bubble_sort.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
"""
2+
Implement bubble sort
3+
Perform adjacent swaps
4+
T: O(N^2)
5+
S: O(1)
6+
"""
7+
8+
9+
def bubble_sort(array):
10+
is_sorted = False
11+
counter = 0
12+
while not is_sorted:
13+
is_sorted = True
14+
for i in range(1, len(array) - counter):
15+
if array[i-1] > array[i]:
16+
array[i], array[i-1] = array[i-1], array[i]
17+
is_sorted = False
18+
counter += 1
19+
return array
20+
21+
22+
if __name__ == '__main__':
23+
print(bubble_sort([8, 5, 2, 9, 5, 6, 3]))

‎algoexpert/sorting/insertion_sort.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
"""
2+
Implement insertion sort
3+
T: O(N^2)
4+
S: O(1)
5+
"""
6+
7+
8+
def insertion_sort(array):
9+
for i in range(1, len(array)):
10+
j = i
11+
while j > 0 and array[j] < array[j-1]:
12+
array[j], array[j-1] = array[j-1], array[j]
13+
j -= 1
14+
return array
15+
16+
17+
if __name__ == '__main__':
18+
print(insertion_sort([8, 5, 2, 9, 5, 6, 3]))

‎algoexpert/sorting/selection_sort.py‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
"""
2+
Implement selection sort(Least Used)
3+
Algorithm: Maintain two list, unsorted and sorted
4+
T: O(N^2)
5+
S: O(1)
6+
"""
7+
8+
9+
def insertion_sort(array):
10+
current_index = 0
11+
while current_index < len(array) - 1:
12+
smallest_index = current_index
13+

‎algoexpert/tries/__init__.py‎

Whitespace-only changes.

‎algoexpert/tries/multi_string_search.py‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
class Trie:
2+
def __init__(self, string):
3+
self.root = {}
4+
self.__construct_trie(string)
5+
6+
# Time: O(b^2); Space: O(b^2)
7+
def __construct_trie(self, string):
8+
for i in range(len(string)):
9+
self.__insert_substring_starting_at(i, string)
10+
11+
def __insert_substring_starting_at(self, current_index, string):
12+
node = self.root
13+
for j in range(current_index, len(string)):
14+
letter = string[j]
15+
if letter not in node:
16+
node[letter] = {}
17+
node = node[letter]
18+
19+
# Time: O(m); Space: O(1)
20+
def contains(self, string):
21+
node = self.root
22+
for letter in string:
23+
if letter not in node:
24+
return False
25+
node = node[letter]
26+
return True
27+
28+
29+
def multiStringSearch(bigString, smallStrings):
30+
result = [False] * len(smallStrings)
31+
if not smallStrings or not bigString:
32+
return result
33+
trie = Trie(bigString.strip())
34+
for idx, string in enumerate(smallStrings):
35+
if trie.contains(string):
36+
result[idx] = True
37+
else:
38+
result[idx] = False
39+
return result
40+
41+
42+
def multi_string_search(big_string, small_strings):
43+
return [is_in_big_string(big_string, small_string) for small_string in small_strings]
44+
45+
46+
def is_in_big_string(big_string, small_string):
47+
for i in range(len(big_string)):
48+
if i + len(small_string) > len(big_string):
49+
break
50+
if is_in_big_string_helper(big_string, small_string, i):
51+
return True
52+
return False
53+
54+
55+
def is_in_big_string_helper(big_string, small_string, current_index):
56+
left_big_idx = current_index
57+
right_big_idx = current_index + len(small_string) - 1
58+
left_small_idx = 0
59+
right_small_idx = len(small_string) - 1
60+
while left_big_idx <= right_big_idx:
61+
if big_string[left_big_idx] != small_string[left_small_idx] or \
62+
small_string[right_small_idx] != big_string[right_big_idx]:
63+
return False
64+
left_small_idx += 1
65+
right_small_idx -= 1
66+
left_big_idx += 1
67+
left_small_idx -= 1
68+
return True
69+
70+
71+
class ModifiedTrie:
72+
def __init__(self):
73+
self.root = {}
74+
self.end_symbol = '*'
75+
76+
def insert(self, string):
77+
current_node = self.root
78+
for i in range(len(string)):
79+
80+
if __name__ == '__main__':
81+
print(multiStringSearch('this is a big string', ['this', 'yo', 'is', 'a', 'bigger', 'string', 'kappa']))

‎algoexpert/tries/suffix_trie_construction.py‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
"""
2+
Trie will be represented as a dictionary of dictionary starting at an empty node
3+
"""
4+
5+
6+
class Trie:
7+
def __init__(self, input_string):
8+
self.root = {}
9+
self.end_symbol = '*'
10+
self.__construct_trie(input_string)
11+
12+
# Time: O(n^2), Space: O(n^2)
13+
def __construct_trie(self, input_string):
14+
for i in range(len(input_string)):
15+
self.__populate_trie(i, input_string)
16+
17+
def __populate_trie(self, current_idx, input_string):
18+
node = self.root
19+
for j in range(current_idx, len(input_string)):
20+
current_letter = input_string[j]
21+
if current_letter not in node:
22+
node[current_letter] = {}
23+
node = node[current_letter]
24+
node[self.end_symbol] = True
25+
26+
# Time: O(m) where m is the length of the string; Space: O(1)
27+
def contains(self, string):
28+
if not self.root:
29+
return False
30+
node = self.root
31+
for letter in string:
32+
if letter not in node:
33+
return False
34+
node = node[letter]
35+
return self.end_symbol in node
36+
37+
38+
if __name__ == '__main__':
39+
trie = Trie('babbc')
40+
print(trie.contains('abbc'))

‎algorithmic_patterns/dynamic_programming/0_1_knapsack.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
"""
2+
* 0/1 Knapsack Problem - Given items of certain weights/values and maximum allowed weight
3+
* how to pick items to pick items from this set to maximize sum of value of items such that
4+
* sum of weights is less than or equal to maximum allowed weight.
5+
"""
6+
7+
8+
def max_value(values, weights, total_weight):
9+
dp = [[0 for _ in range(total_weight+1)] for _ in range(len(values)+1)]
10+
11+
for i in range(len(values)+1):
12+
for j in range(total_weight+1):
13+
if i == 0 or j == 0:
14+
dp[i][j] = 0
15+
continue
16+
if j - weights[i-1] >= 0:
17+
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
18+
else:
19+
dp[i][j] = dp[i-1][j]
20+
return dp[len(values)][total_weight]
21+
22+
23+
if __name__ == '__main__':
24+
print(max_value([22, 20, 15, 30, 24, 54, 21, 32, 18, 25], [4, 2, 3, 5, 5, 6, 9, 7, 8, 10], 30))
25+
print(max_value([60, 100, 120], [10, 20, 30], 50))

‎algorithmic_patterns/dynamic_programming/__init__.py‎

Whitespace-only changes.

‎algorithmic_patterns/dynamic_programming/length_of_longest_bitonic_subsequence.py‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
"""
2+
Find the length of longest bitonic subsequence
3+
"""
4+
5+
6+
def find_LBS(nums):
7+
n = len(nums)
8+
lds = [0 for _ in range(n)]
9+
lds_reverse = [0 for _ in range(n)]
10+
11+
for i in range(n):
12+
lds[i] = 1
13+
for j in range(i-1, -1, -1):
14+
if nums[j] < nums[i]:
15+
lds[i] = max(lds[i], 1 + lds[j])
16+
17+
for i in range(n-1, -1, -1):
18+
lds_reverse[i] = 1
19+
for j in range(i+1, n):
20+
if nums[j] < nums[i]:
21+
lds_reverse[i] = max(lds_reverse[i], 1 + lds_reverse[j])
22+
23+
max_length = 0
24+
for i in range(n):
25+
max_length = max(max_length, lds[i] + lds_reverse[i] - 1)
26+
return max_length

0 commit comments

Comments
 (0)