Merge branch 'master' into restructure-index

shreyas1599 · web-flow · commit 3b8b1b9fa8d1 · 2019-10-12T12:51:02.000+05:30
diff --git a/.github/pull_request_template.md b/.github/pull_request_template.md
@@ -0,0 +1,23 @@
+# Description
+
+Please include a summary of the change and which issue is fixed or what question/feature you have added.
+
+Fixes # (issue)
+
+## Type of change
+
+Please delete options that are not relevant.
+
+- [ ] Bug fix (non-breaking change which fixes an issue)
+- [ ] New feature/question
+- [ ] This change requires a documentation update
+- [ ] Bookmark link
+
+# Checklist:
+
+- [ ] My code follows the style guidelines of this project i.e. [Pep8](https://www.python.org/dev/peps/pep-0008/)
+- [ ] I have performed a self-review of my own code
+- [ ] I have commented my code, particularly in hard-to-understand areas
+- [ ] I have made corresponding changes to the documentation
+- [ ] Any dependent changes have been merged and published in downstream modules
+- [ ] I have squashed unnecessary commits
diff --git a/README.md b/README.md
@@ -31,6 +31,8 @@ This directory contains various types of algorithm questions like Dynamic Progra
 1. Dynamic Programming
 2. Math
 3. Sorting
+4. Greedy
+5. Misc
 
 ### Bookmarks
 
@@ -65,4 +67,4 @@ To follow the guidelines, refer to [Contributing.md](CONTRIBUTING.md)
 
 ## :page_facing_up: License
 
-MIT @ Prabhu Pant
+MIT @ Prabhu Pant
diff --git a/algorithms/dynamic_programming/climbing_stairs.py b/algorithms/dynamic_programming/climbing_stairs.py
@@ -1,7 +1,8 @@
 """
 High Level Description:
 You are climbing a stair case. It takes n steps to reach to the top.
-Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
+Each time you can either climb 1 or 2 steps. In how many distinct ways can you
+climb to the top?
 
 Time Complexity:
 O(n)
diff --git a/algorithms/dynamic_programming/edit_distance.py b/algorithms/dynamic_programming/edit_distance.py
@@ -1,28 +1,31 @@
 """
 High Level Description:
-Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
-You have the following 3 operations permitted on a word:
+Given two words word1 and word2, find the minimum number of operations
+required to convert word1 to word2. You have the following 3 operations
+permitted on a word:
 Insert a character
 Delete a character
 Replace a character
 
 Time Complexity:
 O(m*n)
 """
+
+
 def edit_dist(str1, str2, m, n):
-    dp = [[0 for x in range(n+1)] for x in range(m+1)] 
-  
-    for i in range(m+1): 
-        for j in range(n+1):  
-            if i == 0: 
-                dp[i][j] = j   
-            elif j == 0: 
-                dp[i][j] = i    
-            elif str1[i-1] == str2[j-1]: 
-                dp[i][j] = dp[i-1][j-1] 
-            else: 
-                dp[i][j] = 1 + min(dp[i][j-1],        # Insert 
-                                   dp[i-1][j],        # Remove 
-                                   dp[i-1][j-1])    # Replace 
-  
-    return dp[m][n]
+    dp = [[0 for x in range(n+1)] for x in range(m+1)]
+
+    for i in range(m+1):
+        for j in range(n+1):
+            if i == 0:
+                dp[i][j] = j
+            elif j == 0:
+                dp[i][j] = i
+            elif str1[i-1] == str2[j-1]:
+                dp[i][j] = dp[i-1][j-1]
+            else:
+                dp[i][j] = 1 + min(dp[i][j-1],        # Insert
+                                   dp[i-1][j],        # Remove
+                                   dp[i-1][j-1])    # Replace
+
+    return dp[m][n]
diff --git a/algorithms/dynamic_programming/longest_common_subsequence.py b/algorithms/dynamic_programming/longest_common_subsequence.py
@@ -4,6 +4,7 @@
 longest common subsequence
 '''
 
+
 def lcs(S1, S2):
     m = len(S1)
     n = len(S2)
@@ -12,7 +13,7 @@ def lcs(S1, S2):
 
     for i in range(m + 1):
         for j in range(n + 1):
-            if i == 0 or j == 0 :
+            if i == 0 or j == 0:
                 LCS[i][j] = 0
             elif S1[i-1] == S2[j-1]:
                 LCS[i][j] = LCS[i-1][j-1]+1
diff --git a/algorithms/dynamic_programming/max_subarray.py b/algorithms/dynamic_programming/max_subarray.py
@@ -1,10 +1,13 @@
 """
 High Level Description:
-Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
+Given an integer array nums, find the contiguous subarray (containing at least
+one number) which has the largest sum and return its sum.
 
 Time Complexity:
 O(n)
 """
+
+
 # Iterative Solution
 def max_sub_array(self, arr):
     if not arr:
@@ -15,4 +18,4 @@ def max_sub_array(self, arr):
         cur_sum = max(num, cur_sum + num)
         max_sum = max(max_sum, cur_sum)
 
-    return max_sum
+    return max_sum
diff --git a/algorithms/dynamic_programming/rod_cutting.py b/algorithms/dynamic_programming/rod_cutting.py
@@ -4,18 +4,19 @@
 of all pieces of size less than n. We
 need to find the maximum maximum price
 obtainable by cutting the rod and
-selling it.  
+selling it.
 '''
 INT_MIN = -32767
 
+
 def cutRod(price, n):
     values = [0 for i in range(n+1)]
     values[0] = 0
 
     for i in range(1, n+1):
         max_value = INT_MIN
         for j in range(i):
-             max_value = max(max_value, price[j] + values[i-j-1])
+            max_value = max(max_value, price[j] + values[i-j-1])
         values[i] = max_value
 
     return values[n]
diff --git a/algorithms/dynamic_programming/unique_grid_paths.py b/algorithms/dynamic_programming/unique_grid_paths.py
@@ -1,23 +1,26 @@
 """
 High Level Description:
-A preson is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
-The preson can only move either down or right at any point in time. 
-The preson is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
+A preson is located at the top-left corner of a m x n grid (marked 'Start' in
+the diagram below). The preson can only move either down or right at any point
+in time. The preson is trying to reach the bottom-right corner of the grid
+(marked 'Finish' in the diagram below).
 How many possible unique paths are there?
 
 Time Complexity:
 O(m*n)
 """
-def number_of_paths(m, n): 
-    count = [[0 for x in range(m)] for y in range(n)] 
 
-    for i in range(m): 
-        count[i][0] = 1; 
 
-    for j in range(n): 
-        count[0][j] = 1; 
+def number_of_paths(m, n):
+    count = [[0 for x in range(m)] for y in range(n)]
 
-    for i in range(1, m): 
-        for j in range(n):              
-            count[i][j] = count[i-1][j] + count[i][j-1] 
-    return count[m-1][n-1] 
+    for i in range(m):
+        count[i][0] = 1
+
+    for j in range(n):
+        count[0][j] = 1
+
+    for i in range(1, m):
+        for j in range(n):
+            count[i][j] = count[i-1][j] + count[i][j-1]
+    return count[m-1][n-1]
diff --git a/algorithms/math/index.md b/algorithms/math/index.md
@@ -4,3 +4,4 @@
 * [Fibonacci Number](https://github.com/prabhupant/python-ds/blob/master/algorithms/math/fibonacci_number.py)
 * [Nth Prime Number](https://github.com/prabhupant/python-ds/blob/master/algorithms/math/prime.py)
 * [Sieve of Erastothenes](https://github.com/prabhupant/python-ds/blob/master/algorithms/math/sieve_of_eratosthenes.py)
+
diff --git a/algorithms/math/sieve_of_eratosthenes.py b/algorithms/math/sieve_of_eratosthenes.py
@@ -0,0 +1,18 @@
+"""
+Description:
+Sieve of Eratosthenes is a very fast method (loglog(n)) of finding primes upto a given number.
+"""
+
+
+def sieve(n):
+    prime_list = []
+    for i in range(2, n+1):
+        if i not in prime_list:
+            print(i)
+            for j in range(i*i, n+1, i):
+                prime_list.append(j)
+
+
+if __name__ == '__main__':
+    input_number = int(input("Provide a number upto which primes are to be found :"))
+    sieve(input_number)
diff --git a/data_structures/array/matrix_layer_rotation.py b/data_structures/array/matrix_layer_rotation.py
@@ -0,0 +1,88 @@
+"""
+Description:
+
+Matrix Layer Rotation
+
+You are given a 2D matrix of dimension mxn and a positive integer r. You have to rotate the
+matrix r times and print the resultant matrix. Rotation should be in anti-clockwise direction.
+Rotation of a 4x5 matrix is represented by the following figure. Note that in one rotation,
+you have to shift elements by one step only. This is shifting the elemment.
+Note:- Minimum of m and n will be even.
+
+Start         First           Second
+ 1 2 3 4        2  3  4  5      3  4  5  6
+12 1 2 5  ->   1  2  3  6 ->   2  3  4  7
+11 4 3 6      12  1  4  7       1  2  1  8
+10 9 8 7      11 10  9  8     12 11 10  9
+"""
+
+
+# Function to rotate the sides of the matrix in place.
+def matrix_rotate(matrix, m, n, i=0, j=0):
+    if (m, n) == (1, 1):
+        return matrix
+    if (m, n) == (2, 2):
+        temp = matrix[i][j]
+        matrix[i][j] = matrix[i + 1][j]
+        matrix[i + 1][j] = matrix[i + 1][j + 1]
+        matrix[i + 1][j + 1] = matrix[i + 1][j]
+        matrix[i + 1][j] = temp
+        return matrix
+    else:
+        temp = matrix[i][j]
+        # top
+        for a in range(j, n - j - 1):
+            matrix[i][a] = matrix[i][a + 1]
+        matrix[i][n - j - 1] = matrix[i + 1][n - j - 1]
+        # right
+        for a in range(i + 1, m - i - 2):
+            matrix[a][n - 1 - j] = matrix[a + 1][n - 1 - j]
+        matrix[m - j - 2][n - j - 1] = matrix[m - j - 1][n - j - 1]
+        # bottom
+        for a in range(n - j - 1, j, -1):
+            matrix[m - j - 1][a] = matrix[m - j - 1][a - 1]
+        matrix[m - j - 1][j] = matrix[m - j - 2][j]
+        # left
+        for a in range(m - i - 2, i, -1):
+            matrix[a][i] = matrix[a - 1][i]
+        matrix[i + 1][j] = temp
+        return matrix
+
+
+def driver_code(matrix, r):
+    m = len(matrix)
+    n = len(matrix[0])
+    i, j = 0, 0
+    s = 0
+    while (i, j) < (m // 2, n // 2):  # Checking for the maximum values of i, j.
+        for _ in range(r):
+            s = matrix_rotate(matrix, m, n, i, j)
+        i += 1
+        j += 1
+    print_matrix(s)
+
+
+def print_matrix(matrix):
+    m = len(matrix)
+    n = len(matrix[0])
+    print('\n'.join([' '.join(['{:n}'.format(item) for item in row])
+                     for row in matrix]))
+
+
+if __name__ == '__main__':
+    mnr = input().rstrip().split()
+
+    m = int(mnr[0])
+
+    n = int(mnr[1])
+
+    r = int(mnr[2])
+
+    matrix2d = []
+
+    for _ in range(m):
+        matrix2d.append(list(map(int, input().rstrip().split())))
+
+    driver_code(matrix2d, r)
+
+
diff --git a/data_structures/linked_list/merge_list_of_linked_lists.py b/data_structures/linked_list/merge_list_of_linked_lists.py
@@ -0,0 +1,37 @@
+class Node:
+
+    def __init__(self, x):
+        self.val = x
+        self.next = None
+
+        
+def merge_two_lists(l1, l2):
+    if not l1 and not l2:
+        return
+    elif not l2:
+        return l1
+    elif not l1:
+        return l2
+
+    if (l1.val < l2.val):
+        l1.next = merge_two_lists(l1.next, l2)
+        return l1
+    l2.next = merge_two_lists(l1, l2.next)
+    return l2
+
+
+def merge_k_lists(lists):
+    length = len(lists)
+    if length == 0:
+        return;
+    elif length == 1:
+        return lists[0]
+    elif length == 2:
+        return merge_two_lists(lists[0], lists[1])
+
+    mid = length // 2
+
+    left_half = lists[:mid]
+    right_half = lists[mid:]
+
+    return merge_two_lists(merge_k_lists(left_half), merge_k_lists(right_half))
diff --git a/data_structures/strings/adjacent_vowel_pairs.py b/data_structures/strings/adjacent_vowel_pairs.py
@@ -0,0 +1,34 @@
+'''
+Question :
+Given a string consisting of English alphabets, the task is to count the number of adjacent pairs of vowels.
+For example :
+Input: str = “abaebio”
+Output: 2
+(a, e) and (i, o) are the only valid pairs.
+Source:A very Common Interview Question.
+
+Time Complexity : The goal is to complete this question in O(n).
+'''
+
+#function to check whether a character is vowel or not
+def is_vowel(character):
+    if character.lower() in ['a', 'e', 'i', 'o', 'u']: 
+        return True
+    else:  
+        return False
+  
+
+#function to find the number of adjacent vowel pairs.
+def adjacent_pairs(string):
+    string=string.lower()
+    n=len(string)
+    count = 0
+    for i in range(0,n):
+        if ((is_vowel(string[i]) and is_vowel(string[i + 1]))): 
+            count += 1
+    return count
+
+#driver code
+string=input("enter string")
+print (adjacent_pairs(string),"is the number of adjacent pairs of vowels")
+  
diff --git a/data_structures/strings/toggle_string.py b/data_structures/strings/toggle_string.py
