Fundamentals Flashcards
Longest Palindromic Substring (DP)
Find the longest palindrome in a string. s =”cbbd”
dp = [[False] * m for _ in range(m)]
for i in range(m):
dp[i][i] = True
start = 0
max_len = 1
for length in range(2, m+1):
for i in range(m-length+1):
j = i + length -1
if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
dp[i][j] = True
if length > max_len:
start = i
max_len = length
return s[start:start+max_len]
Have a bool dp to track the palindromes. Check the palindromes for len.
Check first and last chars of the current length and look up dp to see if what’s in between is a palindrome.
Longest Common Subsequence (DP)
Find the longest common subsequence between two strings.
str1 = “abcde”, str2 = “ace”
m = len(str1)
n = len(str2)
dp = [[0] * (n+1) for _ in range(m+1)
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
Track how many characters the two strings have in common.
Increase count while you find chars in common. If the current position is not a match, update the dp with the max from either of the previous positions ([i-1][j], or [i][j-1])
Unique Number of Occurences
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
hash_map = {}
for item in arr:
hash_map.setdefault(item, 0)
hash_map[item] += 1
return len(list(hash_map.values)) == len(list(set(hash_map.values)))
Store the number of occurences of each item in a hash map. Using the built in setdefault function is ideal. Return a length array which is created by the values of the hash map compared to its set.
Check If String Is a Prefix of Array
Given a string s and an array of strings words, determine whether s is a prefix string of words.
A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.
Return true if s is a prefix string of words, or false otherwise.
comparison_str = ""
for word in words:
comparison_str += word
if len(comparison_str) > len(s):
return False
if comparison_str == s:
return True
return False
Create a string to compare the words to the given string s. Append each word one by one to this comparison_str and check if the length of this comparison string exceeded the length of the given string or if they are equal.
Valid Parantheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
stack = []
hash_map = {")":"(", "]":"[", "}":"{"}
for character in s:
if not stack:
stack.append(character)
elif character in hash_map:
if hash_map[character] == stack[-1]:
stack.pop()
else:
return False
else:
stack.append(character)
return len(stack) == 0
Backspace String Compare
Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
stack_1 = []
stack_2 = []
for char in s:
if char != "#":
stack_1.append(char)
elif stack_1:
stack_1.pop()
for char in t:
if char != "#":
stack_2.append(char)
elif stack_2:
stack_2.pop()
return stack_1 == stack_2
“If you encounter a “#” pop the last element. If there’s no element in the stack simply continue.”
Minimum String Length After Removing Substrings
You are given a string s consisting only of uppercase English letters.
You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings “AB” or “CD” from s.
Return the minimum possible length of the resulting string that you can obtain.
Note that the string concatenates after removing the substring and could produce new “AB” or “CD” substrings.
stack = []
for char in s:
if not stack:
stack.append(char)
if (stack[-1] == "A" and char == "B") or (stack[-1] == "C" and char == "D"):
stack.pop()
else:
stack.append(char)
return len(stack)
“Go through the string char by char append until you encounter the sequence you are looking for. If you have the sequence that you are looking for pop and continue”.
Removing Stars From a String
You are given a string s, which contains stars *.
In one operation, you can:
Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.
stack = []
for char in s:
if char != "*":
stack.append(char)
elif stack:
stack.pop()
str = ""
while stack:
str += stack.pop()
str = str[::-1]
return strSort Array by Increasing Frequency
Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array.
hash_map = {}
result =[]
for num in nums:
if num not in hash_map:
hash_map[num] = 1
else:
hash_map[num] += 1
return sorted(nums, key = lambda x: (hash_map[x], -x))Find Subsequence of Length K With the Largest Sum
You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.
Return any such subsequence as an integer array of length k.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
min_heap = []
top_k_indices = []
for idx, val in enumerate(nums):
heapq.heappush(min_heap, (val, idx))
if len(max_heap) > k:
heapq.heappop(min_heap)
while min_heap:
_, idx = heapq.heappop(min_heap)
top_k_indices.append(idx)
top_k_indices.sort()
for idx in top_k_indices:
result.append(nums[idx])
return result
Use min heap to store the values. Pop the smallest element each time the size gets greater than k. In the end you will end up with the largest k elements.
K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
import heapq
max_heap = []
result =[]
for idx, point in enumerate(points):
temp_val = sqrt(point[0]**2 + point[1]**2)
heapq.heappush(max_heap, (-temp_val, idx))
if len(max_heap) > k:
heapq.heappop(max_heap)
for item in max_heap:
_, idx = item
result.append(points[idx])
return resultKth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
import heapq
min_heap = []
result = 0
for idx, num in enumerate(nums):
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
return heapq.heappop(min_heap)Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
import heapq
min_heap = []
hash_map = {}
result = []
for num in nums:
if num not in hash_map:
hash_map[num] = 1
else:
hash_map[num] += 1
for key in hash_map:
heapq.heappush(min_heap, (hash_map[key], key))
if len(min_heap) > k:
heapq.heappop(min_heap)
for _, num in min_heap:
result.append(num)
return resultSort Characters By Frequency
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
hash_map = {}
for char in s:
if char in hash_map:
hash_map[char] += 1
else:
hash_map[char] = 1
return ''.join(sorted(s, key = lambda x: (-hash_map[x], x)))
Maximum Ice Cream Bars
It is a sweltering summer day, and a boy wants to buy some ice cream bars.
At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.
Note: The boy can buy the ice cream bars in any order.
Return the maximum number of ice cream bars the boy can buy with coins coins.
You must solve the problem by counting sort.
counter = 0
sorted_arr = self.counting_sort(costs)
for num in sorted_arr:
if num > coins:
return counter
else:
coins -= num
counter += 1
return counter
