Skip to content

Commit 594bc86

Browse files
shreyas1599shreyas1599
authored
Merge branch 'master' into master
2 parents f6164f8 + 1d4e888 commit 594bc86

25 files changed

+845
-19
lines changed

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,12 @@ The open source community has helped me a lot during my interview preparations a
1010

1111
## :file_folder: Structure of the repository
1212

13+
14+
As of now, the repository contains [**Data Structures**](data_structures), [**Algorithms**](algorithms) and [**bookmarks**](bookmarks) are the main directories.
15+
1316
As of now, the repository contains 3 main directories: **[Data Structures](data_structures)**, **[Algorithms](algorithms)** and **[Bookmarks](bookmarks)**.
1417

18+
1519
### Data Structures
1620

1721
Contains all data structure questions categorised into sub-directories like stack, queue, etc according to their type.

‎algorithms/dynamic_programming/longest_palindromic_subsequence.py‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
'''
2+
Question :
3+
Given a string consisting of English alphabets, the task is to count the alphabets in the longest palindromic subsequence.
4+
5+
For example :
6+
Input: str = "BBABCBCAB"
7+
Output: 7
8+
"BABCBAB" is the longest palindromic subseuqnce in it. "BBBBB"" and "BBCBB" are also palindromic subsequences of the given sequence, but not the longest ones.
9+
10+
Source: https://www.geeksforgeeks.org/python-program-for-longest-palindromic-subsequence-dp-12/
11+
'''
12+
13+
def lps(str):
14+
n = len(str)
15+
16+
# Create a table to store results of subproblems
17+
L = [[0 for x in range(n)] for x in range(n)]
18+
19+
# Strings of length 1 are palindrome of length 1
20+
for i in range(n):
21+
L[i][i] = 1
22+
23+
# Build the table. Note that the lower
24+
# diagonal values of table are
25+
# useless and not filled in the process.
26+
for cl in range(2, n + 1):
27+
for i in range(n-cl + 1):
28+
j = i + cl-1
29+
if str[i] == str[j] and cl == 2:
30+
L[i][j] = 2
31+
elif str[i] == str[j]:
32+
L[i][j] = L[i + 1][j-1] + 2
33+
else:
34+
L[i][j] = max(L[i][j-1], L[i + 1][j]);
35+
36+
return L[0][n-1]
37+
38+
# Test inputs
39+
seq = "BBABCBCAB"
40+
print("The length of the LPS is " + str(lps(seq)))

‎algorithms/graph/find_all_paths.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
'''
2+
find all the possible paths in a directed cyclic graph from
3+
a start point to a end point.
4+
'''
5+
6+
7+
8+
9+
def find_all_paths(graph, start, end, path=[]):
10+
path = path + [start]
11+
if start == end:
12+
return [path]
13+
if start not in graph.keys():
14+
return []
15+
paths = []
16+
for node in graph[start]:
17+
if node not in path: #to prevent cyclic rotations
18+
newpaths = find_all_paths(graph, node, end, path)
19+
#print(newpaths)
20+
for newpath in newpaths:
21+
paths.append(newpath)
22+
return paths
23+
24+
25+
graph={1:[2,4],
26+
2:[3],
27+
4:[5],
28+
3:[5]
29+
}
30+
31+
for i in graph.keys():
32+
print(i,'to 5',find_all_paths(graph,i,5))

‎algorithms/greedy/dijkstra_greedy.py‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
def dijkstra(graph, start, end):
2+
shortest_distance = {}
3+
non_visited_nodes = {}
4+
for i in graph:
5+
non_visited_nodes[i] = graph[i]
6+
7+
infinit = float('inf')
8+
9+
for no in non_visited_nodes:
10+
shortest_distance[no] = infinit
11+
shortest_distance[start] = 0
12+
13+
while non_visited_nodes != {}:
14+
shortest_extracted_node = None
15+
for i in non_visited_nodes:
16+
if shortest_extracted_node is None:
17+
shortest_extracted_node = i
18+
elif shortest_distance[i] < shortest_distance[shortest_extracted_node]:
19+
shortest_extracted_node = i
20+
21+
for no_v, Weight in graph[shortest_extracted_node]:
22+
if Weight + shortest_distance[shortest_extracted_node] < shortest_distance[no_v]:
23+
shortest_distance[no_v] = Weight + shortest_distance[shortest_extracted_node]
24+
non_visited_nodes.pop(shortest_extracted_node)
25+
return shortest_distance
26+
27+
#in this case, I made a graph within the code, but I didn't put here, you can create your graph the way you like.
28+
#this algorithm needs the start, end, and weight, but you can remove the weight as well
29+
#I will leave my example here, how I use this algorithm to solve the shortest path problem
30+
# V is vertex, u is edges and W IS WEIGHT.
31+
32+
cities, origin, destiny = map(int, input().split())
33+
graph = {i:[] for i in range(1, cities+1)}
34+
for i in range(cities-1):
35+
u, v, w = map(int, input().split())
36+
graph[v].append((u, w))
37+
graph[u].append((v, w))

‎algorithms/math/fibonacci_number.py‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,26 @@
1+
# Program that prints out the fibonacci sequence until a given number
2+
13
def calc_fib(num):
2-
while len(fib)<=num:
4+
while len(fib) <= num:
35
n = len(fib)
4-
fib.append((fib[n-1]+fib[n-2]))
6+
fib.append((fib[n-1] + fib[n-2]))
57

68
def main():
79
print("Enter the Position of the Number in the Sequence or \'0\' to Quit: ")
810
num = 0
911
fib = list()
1012
fib.append(0)
1113
fib.append(1)
14+
1215
while True:
1316
num = int(input())
14-
if(num<=0):
17+
if(num <= 0):
1518
break
1619

17-
if len(fib)<=num:
20+
if len(fib) <= num:
1821
calc_fib(num)
1922

20-
print('Fibonacci Number at Position '+str(num)+' is: '+str(fib[num]))
23+
print('Fibonacci Number at Position ' + str(num) + ' is: ' + str(fib[num]))
2124

2225
if __name__ == '__main__':
2326
main()

‎algorithms/math/greatest_common_divisor.py‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -7,23 +7,23 @@
77
"""
88
# Iterative Solution
99
def gcd(x, y):
10-
if x==0:
10+
if x == 0:
1111
return y
12-
if y==0:
12+
if y == 0:
1313
return x
1414

15-
while x%y != 0:
16-
rem = x%y;
15+
while x % y != 0:
16+
rem = x % y;
1717
x = y
1818
y = rem
1919

2020
return y
2121

2222
# Recursive Solution
2323
def gcd(x, y):
24-
if x==0:
24+
if x == 0:
2525
return y
26-
if y==0:
26+
if y == 0:
2727
return x
2828

29-
return gcd(y, x%y)
29+
return gcd(y, x % y)

‎algorithms/math/modular_exponentiation.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# to compute modular power
2+
3+
# Iterative Function to calculate
4+
# (x^y)%p in O(log y)
5+
6+
def power(x, y, p) :
7+
res = 1 # Initialize result
8+
9+
# Update x if it is more
10+
# than or equal to p
11+
x = x % p
12+
13+
while (y > 0) :
14+
15+
# If y is odd, multiply
16+
# x with result
17+
if ((y & 1) == 1) :
18+
res = (res * x) % p
19+
20+
# y must be even now
21+
y = y >> 1 # y = y/2
22+
x = (x * x) % p
23+
24+
return res

‎algorithms/math/prime.py‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,16 @@
11
def prime(limit):
22

33
count = 1
4-
while(count<limit):
4+
while (count < limit):
55

66
flag = 0
7-
for i in range(3,count,2):
8-
if (count%i==0):
7+
for i in range(3, count, 2):
8+
if (count % i == 0):
99
flag = 1
1010

11-
if (flag==0):
11+
if (flag == 0):
1212
print(count)
1313

14-
count+=2
14+
count += 2
1515

1616
prime(100)

‎algorithms/math/recursive_fibonacci.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
"""
2+
Recursivly compute the Fibonacci sequence
3+
"""
4+
5+
def rec_fib(n):
6+
if n == 1:
7+
return 1
8+
elif n == 0:
9+
return 0
10+
else:
11+
return rec_fib(n-1)+rec_fib(n-2)
12+
13+
def main():
14+
n : int = int(input("n := "))
15+
for i in range(0, n):
16+
print(rec_fib(i))
17+
18+
if __name__ == "__main__":
19+
main()

‎algorithms/sorting/heap_sort.py‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
'''
2+
High Level Description:
3+
This algorithm segments the list into sorted and unsorted parts.
4+
It converts the unsorted segment of the list to a Heap data structure, so that we can efficiently determine the largest element.
5+
Time Complexity:
6+
The overall time complexity is O(nlog(n)).
7+
'''
8+
9+
def heapify(nums, heap_size, root_index):
10+
# Assume the index of the largest element is the root index
11+
largest = root_index
12+
left_child = (2 * root_index) + 1
13+
right_child = (2 * root_index) + 2
14+
15+
# If the left child of the root is a valid index, and the element is greater
16+
# than the current largest element, then update the largest element
17+
if left_child < heap_size and nums[left_child] > nums[largest]:
18+
largest = left_child
19+
20+
# Do the same for the right child of the root
21+
if right_child < heap_size and nums[right_child] > nums[largest]:
22+
largest = right_child
23+
24+
# If the largest element is no longer the root element, swap them
25+
if largest != root_index:
26+
nums[root_index], nums[largest] = nums[largest], nums[root_index]
27+
# Heapify the new root element to ensure it's the largest
28+
heapify(nums, heap_size, largest)
29+
30+
31+
def heap_sort(nums):
32+
n = len(nums)
33+
34+
# Create a Max Heap from the list
35+
# The 2nd argument of range means we stop at the element before -1 i.e.
36+
# the first element of the list.
37+
# The 3rd argument of range means we iterate backwards, reducing the count
38+
# of i by 1
39+
for i in range(n, -1, -1):
40+
heapify(nums, n, i)
41+
42+
# Move the root of the max heap to the end of
43+
for i in range(n - 1, 0, -1):
44+
nums[i], nums[0] = nums[0], nums[i]
45+
heapify(nums, i, 0)
46+
47+
48+
# Verify it works
49+
random_list_of_nums = [35, 12, 43, 8, 51]
50+
heap_sort(random_list_of_nums)
51+
print(random_list_of_nums)

0 commit comments

Comments
 (0)