Skip to content

Commit e94cf89

Browse files
srbhrsrbhr
authored
Merge pull request prabhupant#1 from prabhupant/master
Sync
2 parents 769b199 + 7682c2a commit e94cf89

40 files changed

Lines changed: 687 additions & 72 deletions

‎README.md‎

Lines changed: 37 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
1-
# <img src="logo\logo.png" style="zoom:50%;"/> Python Data Structures
1+
![logo](logo/logo.png)
22

3-
This repository contains data structures and algorithms questions in Python.
3+
# Python Data Structures and Algorithms
4+
5+
This repository contains data structures and algorithms concepts and questions in Python.
46

57
## :dart: Objective
68

@@ -14,27 +16,44 @@ As of now, the repository contains a file called [`useful_links.md`](useful_link
1416

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

17-
1. Array
18-
2. Dictionary
19-
3. Binary Search Tree
20-
4. Linked List
21-
5. Stack
22-
6. Graphs
23-
7. Circular Linked List
19+
1. Array
20+
2. Dictionary
21+
3. Binary Search Tree
22+
4. Linked List
23+
5. Stack
24+
6. Graphs
25+
7. Circular Linked List
2426

2527
### Algorithms
2628

27-
Contains algorithm-based questions like dynamic programming, greedy etc.
29+
This directory contains various types of algorithm questions like Dynamic Programming, Sorting, Greedy, etc. The current structure of this directory is like -
30+
31+
1. Dynamic Programming
32+
2. Math
33+
3. Sorting
34+
35+
### Bookmarks
36+
37+
You can find useful links in this repository in the different markdown files. Below is a table of contents.
38+
39+
| Category | Link |
40+
| :-- | :--: |
41+
| Articles | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/articles.md) |
42+
| Books | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/books.md) |
43+
| Topics | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/topics.md) |
44+
| Tutorials | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/tutorials.md) |
45+
| Videos | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/videos.md) |
46+
| Misc. | [Click Here](https://github.com/prabhupant/python-ds/blob/master/bookmarks/misc.md) |
2847

2948
## :clipboard: Things need to be done
3049

3150
As you can see, the repo is still in its infancy. Here are some key things in the to-do.
3251

33-
1. Queue questions
34-
2. Algorithms
35-
2.1. Dynamic Programming
36-
2.2. Greedy
37-
3. More questions in data structures, especially for graph, circular linked list, tries, heaps and hash.
52+
1. Queue questions
53+
2. Algorithms
54+
2.1. Dynamic Programming
55+
2.2. Greedy
56+
3. More questions in data structures, especially for graph, circular linked list, tries, heaps and hash.
3857

3958
## :raised_hand: Contributing
4059

@@ -43,6 +62,6 @@ Feel free to raise new issues, file new PRs and star and fork this repo! :wink:
4362

4463
Here are some guidelines:
4564

46-
1. Clone the repo to your local machine
47-
2. Make the new branch and name it accordingly
48-
3. File the PR and wait for the review :)
65+
1. Clone the repo to your local machine
66+
2. Make the new branch and name it accordingly
67+
3. File the PR and wait for the review :)

‎algorithms/dynamic_programming/climbing_stairs.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
"""
2+
High Level Description:
3+
You are climbing a stair case. It takes n steps to reach to the top.
4+
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
5+
6+
Time Complexity:
7+
O(n)
8+
"""
9+
10+
def climb_stairs(n):
11+
if n==0 or n==1:
12+
return 1
13+
first= 1
14+
second= 1
15+
ans= 0
16+
17+
for i in range(2, n+1):
18+
ans = first + second
19+
second = first
20+
first = ans
21+
return ans

‎algorithms/dynamic_programming/edit_distance.py‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
"""
2+
High Level Description:
3+
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
4+
You have the following 3 operations permitted on a word:
5+
Insert a character
6+
Delete a character
7+
Replace a character
8+
9+
Time Complexity:
10+
O(m*n)
11+
"""
12+
def edit_dist(str1, str2, m, n):
13+
dp = [[0 for x in range(n+1)] for x in range(m+1)]
14+
15+
for i in range(m+1):
16+
for j in range(n+1):
17+
if i == 0:
18+
dp[i][j] = j
19+
elif j == 0:
20+
dp[i][j] = i
21+
elif str1[i-1] == str2[j-1]:
22+
dp[i][j] = dp[i-1][j-1]
23+
else:
24+
dp[i][j] = 1 + min(dp[i][j-1], # Insert
25+
dp[i-1][j], # Remove
26+
dp[i-1][j-1]) # Replace
27+
28+
return dp[m][n]

‎algorithms/dynamic_programming/index.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# Index of dynamic_programming
2+
3+
* longest_common_subsequence.py
4+
* rod_cutting.py

‎algorithms/dynamic_programming/max_subarray.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
"""
2+
High Level Description:
3+
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
4+
5+
Time Complexity:
6+
O(n)
7+
"""
8+
# Iterative Solution
9+
def max_sub_array(self, arr):
10+
if not arr:
11+
return 0
12+
13+
cur_sum = max_sum = arr[0]
14+
for num in arr[1:]:
15+
cur_sum = max(num, cur_sum + num)
16+
max_sum = max(max_sum, cur_sum)
17+
18+
return max_sum

‎algorithms/dynamic_programming/unique_grid_paths.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
"""
2+
High Level Description:
3+
A preson is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
4+
The preson can only move either down or right at any point in time.
5+
The preson is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
6+
How many possible unique paths are there?
7+
8+
Time Complexity:
9+
O(m*n)
10+
"""
11+
def number_of_paths(m, n):
12+
count = [[0 for x in range(m)] for y in range(n)]
13+
14+
for i in range(m):
15+
count[i][0] = 1;
16+
17+
for j in range(n):
18+
count[0][j] = 1;
19+
20+
for i in range(1, m):
21+
for j in range(n):
22+
count[i][j] = count[i-1][j] + count[i][j-1]
23+
return count[m-1][n-1]

‎algorithms/greedy/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+

‎algorithms/math/fibonacci_number.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
def calc_fib(num):
2+
while len(fib)<=num:
3+
n = len(fib)
4+
fib.append((fib[n-1]+fib[n-2]))
5+
6+
def main():
7+
print("Enter the Position of the Number in the Sequence or \'0\' to Quit: ")
8+
num = 0
9+
fib = list()
10+
fib.append(0)
11+
fib.append(1)
12+
while True:
13+
num = int(input())
14+
if(num<=0):
15+
break
16+
17+
if len(fib)<=num:
18+
calc_fib(num)
19+
20+
print('Fibonacci Number at Position '+str(num)+' is: '+str(fib[num]))
21+
22+
if __name__ == '__main__':
23+
main()

‎algorithms/math/index.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
# Index of math
2+
3+
* greatest_common_divisor.py

‎algorithms/math/prime.py‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
def prime(limit):
2+
3+
count = 1
4+
while(count<limit):
5+
6+
flag = 0
7+
for i in range(3,count,2):
8+
if (count%i==0):
9+
flag = 1
10+
11+
if (flag==0):
12+
print(count)
13+
14+
count+=2
15+
16+
prime(100)

0 commit comments

Comments
 (0)