Data Structures and Algorithms (Python)
Full set of flashcards for learning Data structures and algorithms, as well as the key patterns that often come up in DSA interview questions.
25 flashcards · Computer Science · by JTH1999
Average of conitiguous subarray Given an array, find the average of all contiguous subarrays of size ‘K’ in it. (result should be an array of the averages of the subarrays).
Create empty array for storing results Sliding window approach, get first window of length k Append average of the first array of length k to results shift sliding window def average_of_subarrays(k, arr): result = [] windowSum, windowStart = 0.0, 0 for windowEnd in range(len(arr)): windowSum += arr[windowEnd] # add the next element to the sum # slide the array - not needed until at kth element if windowEnd >= k - 1: result.append(windowSum / k) # calculate the average windowSum -= arr[windowSta…
Maximum subarray of size K Given an array of positive numbers and a positive number ‘k’, find the maximum sum of any contiguous subarray of size ‘k’. Example 1 Input: [2, 1, 5, 1, 3, 2], k=3 Output: 9 Explanation: Subarray with maximum sum is [5, 1, 3]. Example 2 Input: [2, 3, 4, 1, 5], k=2 Output: 7 Explanation: Subarray with maximum sum is [3, 4]. Time and space complexity?
def max_sub_array_of_size_k(k,arr): maxSum, windowSum, windowStart = 0, 0, 0 for windowEnd in range(len(arr)): windowSum += arr[windowEnd] if windowEnd >= k - 1: maxSum = max(maxSum, windowSum) windowSum -= arr[windowStart] windowStart += 1 return maxSum # Time complexity O(N) # Space complexity O(1)
Smallest subarray with given sum Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists. Example 1: Input: [2, 1, 5, 2, 3, 2], S=7 Output: 2 Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2]. Example 2: Input: [2, 1, 5, 2, 8], S=7 Output: 1 Explanation: The smallest subarray with a sum greater than or equal to '7' is [8]. Tim…
def smallest_sub_array_with_given_sum(s, arr): smallestLength = len(arr) + 1 windowStart, windowSum = 0, 0 for windowEnd in range(len(arr)): windowSum += arr[windowEnd] while windowSum >= s: smallestLength = min(smallestLength, windowEnd + 1 - windowStart) windowSum -= arr[windowStart] windowStart += 1 if smallestLength == len(arr) + 1: smallestLength = 0 return smallestLength # Time complexity O(N) # Space complexity O(1)
Longest subarray with at most K distinct characters Given a string, find the length of the longest substring in it with no more than K distinct characters. Example 1: Input: String="araaci", K=2 Output: 4 Explanation: The longest substring with no more than '2' distinct characters is "araa". Example 2: Input: String="araaci", K=1 Output: 2 Explanation: The longest substring with no more than '1' distinct characters is "aa". Example 3: Input: String="cbbebi", K=3 Output: 5 Explanation: The longe…
def longest_substring_with_k_distinct_characters(k, str): length = 0 windowStart = 0 charFrequency = {} for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar not in charFrequency: charFrequency[rightChar] = 0 charFrequency[rightChar] += 1 # Shrink the sliding window until we have k distinct characters in charFrequency while len(charFrequency) > k: leftChar = str[windowStart] charFrequency[leftChar] -= 1 # decrememnt the character frequency if charFrequency[leftChar] == 0: #…
Fruits into baskets # Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit. # You can start with any tree, but once you have started you can’t skip a tree. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type. # Write a function to return the…
def fruits_into_baskets(fruits): windowStart = 0 fruitCounts = {} maxFruitCount = 0 for windowEnd in range(len(fruits)): right = fruits[windowEnd] if right not in fruitCounts: fruitCounts[right] = 0 fruitCounts[right] += 1 while len(fruitCounts) > 2: left = fruits[windowStart] fruitCounts[left] -= 1 if fruitCounts[left] == 0: del fruitCounts[left] windowStart += 1 maxFruitCount = max(maxFruitCount, windowEnd - windowStart + 1) return maxFruitCount # Time complexity O(N) # Space complexity O(1)…
# Given a string, find the length of the longest substring which has no repeating characters. # Input: String="aabccbb" # Output: 3 # Explanation: The longest substring without any repeating characters is "abc". # Input: String="abbbb" # Output: 2 # Explanation: The longest substring without any repeating characters is "ab". # Input: String="abccde" # Output: 3 # Explanation: Longest substrings without any repeating characters are "abc" & "cde".
def non_repeat_substring(str): longest = 0 windowStart = 0 characterIndexMap = {} # Contains last index of each character as we loop through the string. for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar in characterIndexMap: # If right character already in our window, we set windowStart to the next index along # If windowStart is already ahead of our last rightChar index, it stays as is. windowStart = max(windowStart, characterIndexMap[rightChar] + 1) characterIndexMap[r…
# Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement. # Example 1 # Input: String="aabccbb", k=2 # Output: 5 # Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb". # Example 2 # Input: String="abbcb", k=1 # Output: 4 # Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb". # Example 3…
def length_of_longest_substring(str, k): windowStart = 0 maxLength = 0 maxRepeatLetterCount = 0 frequencyMap = {} for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar not in frequencyMap: frequencyMap[rightChar] = 0 frequencyMap[rightChar] += 1 maxRepeatLetterCount = max(maxRepeatLetterCount, frequencyMap[rightChar]) # Shift the window along if maxRepeatLetterCount has not increased - this is the key step if windowEnd - windowStart + 1 - maxRepeatLetterCount > k: leftChar =…
# Given an array containing 0s and 1s, if you are allowed to replace no more than ‘k’ 0s with 1s, find the length of the longest contiguous subarray having all 1s. # Example 1: # Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2 # Output: 6 # Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6. # Example 2: # Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3 # Output: 9 # Explanation: Replace the '0' at index 6, 9, and 10 to have…
def length_of_longest_substring(arr, k): windowStart = 0 maxOnes = 0 maxLength = 0 for windowEnd in range(len(arr)): if arr[windowEnd] == 1: maxOnes += 1 if windowEnd - windowStart + 1 - maxOnes > k: if arr[windowStart] == 1: maxOnes -= 1 windowStart += 1 maxLength = max(maxLength, windowEnd - windowStart + 1) return maxLength # Time complexity O(N) # Space complexity O(1)
# Given a string and a pattern, find out if the string contains any permutation of the pattern. # Permutation is defined as the re-arranging of the characters of the string. For example, “abc” has the following six permutations: # abc # acb # bac # bca # cab # cba # If a string has ‘n’ distinct characters it will have n! permutations. # Example 1: # Input: String="oidbcaf", Pattern="abc" # Output: true # Explanation: The string contains "bca" which is a permutation of the given pattern. # Examp…
def find_permutation(str, pattern): windowStart = 0 result = False frequencyHash = {} patternHash = {} for index in range(len(pattern)): char = pattern[index] if char not in patternHash: patternHash[char] = 0 patternHash[char] += 1 for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar not in frequencyHash: frequencyHash[rightChar] = 0 frequencyHash[rightChar] += 1 if windowEnd >= len(pattern) - 1: if frequencyHash == patternHash: result = True break leftChar = str[windowStar…
# Given a string and a pattern, find all anagrams of the pattern in the given string. # Anagram is actually a Permutation of a string. For example, “abc” has the following six anagrams: # abc # acb # bac # bca # cab # cba # Write a function to return a list of starting indices of the anagrams of the pattern in the given string. # Example 1: # Input: String="ppqp", Pattern="pq" # Output: [1, 2] # Explanation: The two anagrams of the pattern in the given string are "pq" and "qp". # Example 2: # I…
def find_string_anagrams(str, pattern): windowStart = 0 anagrams = [] frequencyHash = {} patternHash = {} for char in range(len(pattern)): if char not in patternHash: patternHash[char] = 0 patternHash[char] += 1 for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar not in frequencyHash: frequencyHash[rightChar] = 0 frequencyHash[rightChar] += 1 if windowEnd >= len(pattern) - 1: if frequencyHash == patternHash: anagrams.append(windowStart) leftChar = str[windowStart]. frequen…
# Given a string and a pattern, find the smallest substring in the given string which has all the characters of the given pattern. # Example 1: # Input: String="aabdec", Pattern="abc" # Output: "abdec" # Explanation: The smallest substring having all characters of the pattern is "abdec" # Example 2: # Input: String="abdabca", Pattern="abc" # Output: "abc" # Explanation: The smallest substring having all characters of the pattern is "abc". # Example 3: # Input: String="adcad", Pattern="abc" # Ou…
def find_substring(str, pattern): windowStart = 0 patternHash = {} minLength = len(str) + 1 substringStart = 0 matches = 0 for char in pattern: if char not in patternHash: patternHash[char] = 0 patternHash[char] += 1 for windowEnd in range(len(str)): rightChar = str[windowEnd] if rightChar in patternHash: patternHash[rightChar] -= 1 if patternHash[rightChar] == 0: matches += 1 while matches == len(patternHash): windowLength = windowEnd - windowStart + 1 if windowLength < minLength: minLength =…
# Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target. # Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target. # Example 1: # Input: [1, 2, 3, 4, 6], target=6 # Output: [1, 3] # Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6 # Example 2: # Input: [2, 5, 9, 11], target=11 # Output: [0, 2] # Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11 What…
def pair_with_target_sum(arr, target): left = 0 right = len(arr) - 1 while left < right: sum = arr[left] + arr[right] if sum == target: return [left, right] if sum < target: left += 1 else: right -= 1 return [-1, -1] # Time complexity O(N) # Space complexity O(1) # ALTERNATIVE APPROACH - WOULD WORK FOR UNSORTED ARRAY def pair_with_targetsum(arr, target): nums = {} for i, num in enumerate(arr): if target - num in nums: return [i, nums[target - num]] else: nums[num] = i return [-1, 1] # Time comp…
# Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the new length of the array. # Example 1: # Input: [2, 3, 3, 3, 6, 9, 9] # Output: 4 # Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9]. # Example 2: # Input: [2, 2, 2, 11] # Output: 2 # Explanation: The first two elements after removing the duplicates will be [2, 1
def remove_duplicates(arr): nextNonDuplicate = 1 index = 1 while index < len(arr): if arr[nextNonDuplicate - 1] != arr[index]: arr[nextNonDuplicate] = arr[index] nextNonDuplicate += 1 index += 1 return nextNonDuplicate # Time Complexity # The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array. # Space Complexity # The algorithm runs in constant space O(1).
# Given a sorted array, create a new array containing squares of all the number of the input array in the sorted order. # Example 1: # Input: [-2, -1, 0, 2, 3] # Output: [0, 1, 4, 4, 9] # Example 2: # Input: [-3, -1, 0, 1, 2] # Output: [0 1 1 4 9]
def make_squares(arr): n = len(arr) squares = [0 for x in range(n)] insertionIndex = n - 1 right = n - 1 left = 0 while left < right: leftSquare = arr[left] * arr[left] rightSquare = arr[right] * arr[right] if leftSquare > rightSquare: squares[insertionIndex] = leftSquare left += 1 else: squares[insertionIndex] = rightSquare right -= 1 insertionIndex -= 1 return squares # Time complexity O(N) - one traversal of the array # Space Complexity O(N) - space used for output array
# Given an array of unsorted numbers, find all unique triplets in it that add up to zero. # Example 1: # Input: [-3, 0, 1, 2, -1, 1, -2] # Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1] # Explanation: There are four unique triplets whose sum is equal to zero. # Example 2: # Input: [-5, 2, -1, -2, 3] # Output: [[-5, 2, 3], [-2, -1, 3]] # Explanation: There are two unique triplets whose sum is equal to zero.
def search_triplets(arr): arr.sort() triplets = [] for i in range(len(arr)): if i > 0 and arr[i] == arr[i - 1]: continue search_pairs(arr, -arr[i], i + 1, triplets) # we pass in left because we have already found all triplets involving elements to the left of i at this point return triplets def search_pairs(arr, target, left, triplets): right = len(arr) - 1 while left < right: leftNum = arr[Left] rightNum = arr[right] sum = leftNum + rightNum if sum == target: triplets.append([leftNum, rightNum…
# Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum. # Example 1: # Input: [-2, 0, 1, 2], target=2 # Output: 1 # Explanation: The triplet [-2, 1, 2] has the closest sum to the target. # Example 2: # Input: [-3, -1, 1, 2], target=1 # Output: 0 # Explanation: The triplet [-3, 1, 2] has…
def search_triplet(arr, target): arr.sort() smallestDifference = inf for i in range(len(arr) - 2): left = i + 1 right = len(arr) - 1 while left < right: sum = arr[left] + arr[right] + arr[i] if sum == target: return target difference = target - sum smallestDifference = difference if abs(difference) < abs(smallestDifference) else smallestDifference if sum > target: right -= 1 else: left += 1 return target - difference # Time Complexity # Sorting O(NlogN) # For each element, we loop through each…
# Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i] + arr[j] + arr[k] < target where i, j, and k are three different indices. Write a function to return the count of such triplets. # Example 1: # Input: [-1, 0, 2, 3], target=3 # Output: 2 # Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2] # Example 2: # Input: [-1, 4, 2, 1, 3], target=5 # Output: 4 # Explanation: There are four triplets whose sum is le…
def triplet_with_smaller_sum(arr, target): arr.sort() count = 0 for i in range(len(arr) - 2): # Pay attention to the - 2 here!!! Don't forget it count += search_pairs(arr, target - arr[i], i + 1) return count def search_pairs(arr, target, left): count = 0 right = len(arr) - 1 while left < right: if arr[left] + arr[right] < target: # originally had count += 1 here, but we can say count += right - left since arr[right] will always be greater than arr[left] # so arr[left] + arr[right] is always le…
Dutch national flag problem Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array. The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem. Example 1: Input: [1, 0, 2, 1, 0] Output: [0 0 1 1 2] Example 2: Input: [2, 2, 0, 1, 2, 0] Output:…
def dutch_flag_sort(arr): # All elements < low are 0, all elements > high are 2 # All elements from >= low < i are 1 low = 0 high = len(arr) - 1 i = 0 while i < high: if arr[i] < 1: temp = arr[i] arr[i] = arr[low] arr[low] = temp low += 1 i += 1 elif arr[i] == 1: i += 1 elif arr[i] > 1: temp = arr[i] arr[i] = arr[high] arr[high] = temp # Only decrement high - after the swap the number at index i could be 0, 1 or 2 high -= 1 # Time complexity O(N) # Space complexity O(1)
Comparing Strings containing Backspaces Given two strings containing backspaces (identified by the character ‘#’), check if the two strings are equal. Example 1: Input: str1="xy#z", str2="xzz#" Output: true Explanation: After applying backspaces the strings become "xz" and "xz" respectively. Example 2: Input: str1="xy#z", str2="xyz#" Output: false Explanation: After applying backspaces the strings become "xz" and "xy" respectively. Example 3: Input: str1="xp#", str2="xyz##" Output: true Explana…
def backspace_compare(str1, str2): # Use two pointer approach to compare the strings # Compare from the ends of both strings index1 = len(str1) - 1 index2 = len(str2) - 1 while index1 >= 0 or index2 >= 0: i1 = get_next_valid_char_index(str1, index1) i2 = get_next_valid_char_index(str2, index2) if i1 < 0 and i2 < 0: # reached the end of both strings without a difference return True if i1 <0 or i2 < 0: # reached end of one of the strings. Means there must be a difference. return False if str1[i1]…
Minimum Window Sort Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array. Example 1: Input: [1, 2, 5, 3, 7, 10, 9, 12] Output: 5 Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted Example 2: Input: [1, 3, 2, 0, -1, 7, 10] Output: 5 Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted Example 3: Input: [1, 2, 3] Output: 0 Explanation: The array is already so…
def shortest_window_sort(arr): # To start, we find the first non sorted element from the right and left # Then we find the maximum and minimum of the unsorted window # Extend subarray from the beginning to include any number which is bigger than the minimum and therefore unsorted # Likewise extend from the end to include any number smaller than the maximum left = 0 right = len(arr) - 1 while arr[left] <= arr[left + 1]: if left + 1 == right: # array is already sorted return 0 left += 1 while rig…
LinkedList Cycle Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not. Given the head of a LinkedList with a cycle, find the length of the cycle
def has_cycle(head): # If there is a cycle, it is guaranteed that the fast pointer will equal the slow pointer # at some point during the slow pointer's first loop of the cycle fast, slow = head while fast != None and fast.next != None: fast = fast.next.next slow = slow.next if slow == fast: return True return False # Time complexity O(N) # Space complexity O(1) # Similar problem: Given the head of a LinkedList with a cycle, find the length of the cycle # Solution: find the point where fast and…
Start of linkedlist cycle Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.
def find_cycle_start(head): # We first find the point where fast and slow pointer meet within the cycle # Then calculate the length of the cycle, k # Then set two pointers to head, move one ahead k steps. # Iterate both pointers until they meet - meet node will be start of cycle # Because one has walked k steps more, which is the cycle length fast, slow = head cycleLength = 0 while fast != None and fast.next != None: fast = fast.next.next slow = slow.next if slow == fast: cycleLength = find_cyc…
Happy Number Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’. All other (not-happy) numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’. Example 1: Input: 23 Output: true (23 is a happy number) Explanations: Here are the steps to find out that 23 is a happy number: 2^2 + 3^2 = 4 + 9 = 13 1^2 + 3^2 = 1 + 9 = 10 1^2 + 0^2 = 1 +…
def find_happy_number(number): fast, slow = number while fast != slow: slow = sum_square_of_digits(slow) fast = sum_square_of_digits(sum_square_of_digits(fast)) return slow == 1 def sum_square_of_digits(number): sum = 0 for digitString in str(number): digit = int(digitString) sum += digit * digit return sum # alternative def find_square_sum(number): sum = 0 while number > 0: digit = num % 10 sum += digit * digit num //= 10 return sum # Time complexity # The time complexity of the algorithm is d…
Middle of the LinkedList Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList. If the total number of nodes in the LinkedList is even, return the second middle node. Example 1: Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3 Example 2: Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4 Example 3: Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4
def find_middle(head): fast, slow = head while fast.next != None and fast.next.next != None: fast = fast.next.next slow = slow.next return slow # Time complexity O(N) # Space complexity O(1)
Palindrome LinkedList Given the head of a Singly LinkedList, write a method to check if the LinkedList is a palindrome or not. Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished. The algorithm should have O(N) time complexity where ‘N’ is the number of nodes in the LinkedList. Example 1: Input: 2 -> 4 -> 6 -> 4 -> 2 -> null Output: true Example 2: Input: 2 -> 4 -> 6 -> 4 -> 2 -> 2 -> null Output: false
def is_palindrome(head): # Find middle of linked list # reverse second half of list # check if first half equals second half # reverse second half again and attach it to first half # Find middle fast, slow = head while fast.next != None and fast.next.next != None: fast = fast.next.next slow = slow.next headSecondHalf = reverse_list(slow) copy = headSecondHalf while (head != None and headSecondHalf != None): if head.value != headSecondHalf.value: break # Not a palindrome head = head.next headSec…