Important Questions/Algos Flashcards
Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length. Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:
If S[i] == “I”, then A[i] < A[i+1]
If S[i] == “D”, then A[i] > A[i+1]
Example 1:
Input: “IDID”
Output: [0,4,1,3,2]
def diStringMatch(self, S: str) -> List[int]:
left = right = 0
res = [0]
for i in S:
if i == "I":
right += 1
res.append(right)
else:
left -= 1
res.append(left)
return [i - left for i in res]
You have to try the solution on notebook to understand.
This solution takes high low unlike to other one. The other one goes into negative and then deals with it.
high = len(S)
low = 0
res = []
for i in S:
if i=='I':
res.append(low)
low+=1
else:
res.append(high)
high-=1
res.append(low)
return res
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
# s = set()
# for i in range(len(nums)):
# t = target - nums[i]
# if t in s:
# return [i,nums.index(t)]
# else:
# s.add(nums[i])
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
Given two arrays A and B, the elements of B are distinct, and all elements in B are also in A.
Sort the elements of A such that the relative ordering of items in A are the same as in B. Elements that don’t appear in B should be placed at the end of A in ascending order.
Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
def relativeSortArray(self, A, B):
k = {b: i for i, b in enumerate(B)}
return sorted(A, key=lambda a: k.get(a, 1000 + a))
Every element in B is less than or equal to 1000. This solution uses a genius trick. The get command returns the index stored in dict k iff a exists in it as a key. If a doesn't exist in k, then it returns the default value(default of get function) i.e 1000+a. Now we are sorting as per B which is stored in k as num:index pairs.
So first priority is given to this k. But on second priority, we want basic ascending order. And that second priority is done as 1001,1002,1003....
Let us take an example that a =3,4 both are not in k. Then they will be sorted based on the priority 1003 and 1004. Clearly 1003 is smaller and it will be gain lower sort priority while sorting. It is a complex but very important trick.
1-liner
def relativeSortArray(self, A, B):
return sorted(A, key=(B + sorted(A)).index)
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Input: words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
Output: 6
Explanation:
The strings that can be formed are “cat” and “hat” so the answer is 3 + 3 = 6.
def countCharacters(self, words: List[str], c: str) -> int:
out,char_counter = 0,collections.Counter(c)
for word in words:
word_counter = collections.Counter(word)
included = True
for letter in word_counter:
if word_counter[letter]>char_counter[letter]:
included = False
break
if included:
out = out+len(word)
return out
Note that counter is faster than loops! Hence above approach preferred than making a list of chars and removing elements from it if there’s a match. Since counter works as a hash map, so its faster and should be used.
.Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer. You may return the answer in any order. Example 1: Input: ["bella","label","roller"] Output: ["e","l","l"]
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
a = collections.Counter(A[0])
print(a)
for word in A[1:]:
b = collections.Counter(word)
for i in a:
a[i] = min(a[i],b[i])
print(a)
return a.elements()Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.
Note that elements beyond the length of the original array are not written.
Do the above modifications to the input array in place, do not return anything from your function.
Example 1:
Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
shift = 0
l = len(arr)
for i in range(l):
if arr[i] == 0:
shift += 1
for i in range(l-1, -1, -1):
# put the shifted number in the right spot
if i + shift < l:
arr[i+shift] = arr[i]
# This happens every time
# if we meet a 0, we need to duplicate 0, we do
# this in the same run i.e. both if statements run
if arr[i] == 0:
shift -= 1
if i + shift < l:
arr[i+shift] = 0On a N * N grid, we place some 1 * 1 * 1 cubes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).
Return the total surface area of the resulting shapes. Example 1: Input: [[2]] Output: 10 Example 2: Input: [[1,2],[3,4]] Output: 34 Draw it to understand, then solve. This solution is very very important to understand how to use multiple ifs (not elifs) and how to do things column wise and row wise i.e. how to let columns take care of themselves and rows take care of themselves instead of making the cube take care of all its sides.
n, res = len(grid), 0
for i in range(n):
for j in range(n):
if grid[i][j]:
print(grid[i][j])
res += 2 + grid[i][j] * 4
# This includes all surfaces except the ones in between # the cubes in a single tower
if i:
print(grid[i][j])
res -= min(grid[i][j], grid[i - 1][j]) * 2
# This cares only about the previous tower in a row-wise
# manner i.e. only one side of the tower(west)
if j:
print(grid[i][j])
res -= min(grid[i][j], grid[i][j - 1]) * 2
# This cares only about the previous tower in a column-# wise manner i.e. only one side of the tower(south)
return res
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
for i in range(len(nums)):
x = abs(nums[i])
nums[x-1] = -1*abs(nums[x-1])
return [i+1 for i in range(len(nums)) if nums[i]>0]
Here we pick each number of the array, then we put a minus sign in front of the number represented by our number as index i.e. index=num-1. This way all numbers in array will become negative except for the numbers at the indexes which don’t exist in array.
In given example [4,3,2,7,8,2,3,1], number 5 and 6 don’t exist, hence the index = 5-1 and index = 6-1 i.e the numbers 8 and 2 won’t become negative since no number points to them as index.
We get [-4,-3,-2,-7, 8, 2,-3,-1] after marking.
Given a column title as appear in an Excel sheet, return its corresponding column number. Input: "A" Output: 1 Input: "AB" Output: 28 Input: "ZY" Output: 701
s = list(s)
mul = len(s)-1
result = 0
for letter in s:
result += (ord(letter)-64)*(26**mul)
mul -= 1
return result
**Very important to learn property of dicts and how to replace a counter.
Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
first,count,result,degree = {},{},0,0
for i,num in enumerate(nums):
first.setdefault(num,i)
count[num] = count.get(num,0)+1
if count[num]>degree:
degree = count[num]
result = i-first[num]+1
elif count[num]==degree:
result = min(result,i-first[num]+1)
return resultSay you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
if not prices:
return 0
max_profit, min_price = 0, float('inf')
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
On an 8x8 chessboard, there can be multiple Black Queens and one White King.
Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.
def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
seen, ans = set(map(tuple,queens)), []
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
r, c = king
if dr or dc:
while 0 <= r < 8 > c >= 0:
r += dr
c += dc
if (r, c) in seen:
ans += [[r, c]]
break
return ans
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
Example 1:
Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
ans = 0
while head:
ans = (ans << 1) | head.val
head = head.next
return ans
OR
out = 0
while head:
out = 2*out + head.val
head = head.next
return out
Reveal Cards In Increasing Order
Input: [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation:
We get the deck in the order [17,13,11,2,3,5,7] (this order doesn’t matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom. The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom. The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom. The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom. The deck is now [13,17].
We reveal 13, and move 17 to the bottom. The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.
N = len(deck)
index = collections.deque(range(N))
ans = [None]*N
for card in sorted(deck):
ans[index.popleft()] = card
if index:
index.append(index.popleft())
return ans
# d = collections.deque()
# for x in sorted(deck)[::-1]:
# d.rotate()
# d.appendleft(x)
# return list(d)
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
res = 0
for num in nums:
res ^= num
return res
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
Examples:
Input: S = “a1b2”
Output: [“a1b2”, “a1B2”, “A1b2”, “A1B2”]
res = [’’]
for ch in S:
if ch.isalpha():
res = [i+j for i in res for j in [ch.upper(), ch.lower()]]
else:
res = [i+ch for i in res]
return res
Sieve of Eratosthenes
def SieveOfEratosthenes(n):
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
if (prime[p] == True):
for i in range(p * p, n+1, p):
prime[i] = False
p += 1
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Input: “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
First, I count the number of 1 or 0 grouped consecutively.
For example “0110001111” will be [1, 2, 3, 4].
Second, for any possible substrings with 1 and 0 grouped consecutively, the number of valid substring will be the minimum number of 0 and 1.
For example “0001111”, will be min(3, 4) = 3, (“01”, “0011”, “000111”)
s = [len(i) for i in s.replace(‘01’, ‘0 1’).replace(‘10’, ‘1 0’).split()]
return sum(min(a, b) for a, b in zip(s, s[1:]))
