The sad truth about the software engineering industry is that the challenges presented in programming interviews and actual day-to-day work couldn’t be more different.
This page is dedicated to different categories of programming puzzles that will be thrown out during interviews, including sample solutions.
These are personal solutions that are absolutely not the best, fastest, or most memory efficient, though I do try my best to target these metrics. It is solely for personal reference so I don’t have to re-solve the same problem over and over and over again.
For this round, I’m solving everything in Python3. I wish I could start thinking with a functional language, but right now I need to pay off my student loans and would like to have a relatively seamless transition from Job A to Job B if that happens.
Leetcode¶
By far the most famous platform for alleged 10x L33T hackerz, leetcode.com is full of programming challenges.
Top Interview Questions: Easy¶
This is a Leetcode collection with easy questions frequently asked in interviews. I’ll be running through Medium and Hard afterwards, but this is a good place to start and warm up again.
View the problems here.
Arrays¶
You know, these: [ 1, 2, 3 ]
Remove Duplicates from Sorted Array¶
Given an integer array nums sorted in non-decreasing order, remove the duplicates
in-place
such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Submitted Solution:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
length = len(nums)
indice = 0
max_indice = length - 1
while indice < max_indice:
if nums[indice] == nums[indice+1]:
del nums[indice+1]
max_indice = max_indice - 1
else:
indice = indice + 1
return max_indice + 1
Other Notable Solutions:
class Solution:
def removeDuplicates(self, nums):
nums[:] = sorted(set(nums))
return len(nums)
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
x = 1
for i in range(len(nums)-1):
if nums[i]!=nums[i+1]:
nums[x] = nums[i+1]
x+=1
return (x)
Best Time to Buy and Sell Stock II¶
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Submitted Solution:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profits = 0
for i in range(len(prices)-1):
if prices[i] < prices[i+1]:
profits += prices[i+1] - prices[i]
return profits
Rotate Array¶
Given an array, rotate the array to the right by k steps, where k is non-negative.
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Submitted Solution:
Originally I had something very close to the notable solution but forgot to replace the full slice ([:]) instead of merely trying to replace the variable.
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
x = k % len(nums)
while x > 0:
temp = nums.pop()
nums.insert(0, temp)
x -= 1
Other Notable Solutions:
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
newarr=collections.deque(nums)
newarr.rotate(k%len(nums))
nums[:]=list(newarr)
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
if k % len(nums) == 0:
return # this edge case pushes this answer into the top results
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""Lower memory than the others."""
k=k%len(nums)
nums2=[]
for i in range(len(nums)-k,len(nums)):
nums2.append(nums[i])
for i in range(len(nums)-k):
nums2.append(nums[i])
nums[:]=nums2
Contains Duplicate¶
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Submitted Solution:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i+1]:
return True
return False
Other Notable Solutions:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return True if (len(set(nums))<len(nums)) else False
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
#return not len(nums) == len(set(nums))
nums_count = {}
for n in nums:
if n in nums_count:
return True
nums_count[n] = 1
return False
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return not (len(set(nums)) == len(nums))
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
helper = set(nums)
return len(helper) != len(nums)
The big takeaway here is to use the set function to efficiently reduce a list to its unique elements.
A set object is an unordered collection of distinct hashable objects. Common uses include membership testing, removing duplicates from a sequence, and computing mathematical operations such as intersection, union, difference, and symmetric difference. (For other containers see the built-in
dict,list, andtupleclasses, and thecollectionsmodule.)
Find the Single Number¶
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Input: nums = [2,2,1]
Output: 1 # one is the loneliest number ;)
Input: nums = [4,1,2,1,2]
Output: 4
Submitted Solution:
My initial solution beat 95% of other solutions for runtime and 97% of other solutions for memory usage!
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(0, len(nums)-1, 2):
if nums[i] != nums[i+1]:
return nums[i]
return nums[len(nums)-1]
Other Notable Solutions:
All faster solutions involved XOR-ing the entire array.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
'''
[
1, 001
2, 010
3, 011
4, 100
5, 101
]
'''
res = 0 # n ^ 0 = n
# XOR the entire list
# everything besides the single number becomes 0 with XOR
# we know n ^ 0 = n , so n is the single number
for n in nums:
res = n ^ res
return res
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = nums[0]
for n in nums[1:]:
ans ^= n
return ans
Intersection of Two Arrays II¶
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.
Submitted Solution:
This was a dumb first attempt - I’m certain this problem can be solved with far fewer resources.
Apparently this solution beats 79% of other solutions for speed and 89% for memory use. Ha!
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
full_set = set(nums1 + nums2)
count1 = dict.fromkeys(full_set, 0)
count2 = dict.fromkeys(full_set, 0)
combined = dict.fromkeys(full_set, 0)
for item in nums1:
count1[item] += 1
for item in nums2:
count2[item] += 1
for key in combined.keys():
if count1[key] or count2[key]:
combined[key] = min(count1[key], count2[key])
synthesis = []
for key in combined.keys():
if combined[key]:
synthesis += [key] * combined[key]
return synthesis
Other Notable Solutions:
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = []
for num1 in nums1:
for num2 in nums2:
if num1 == num2:
nums2.remove(num2)
result.append(num1)
break
return result
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
d = dict()
arr = []
for i in nums1:
if i not in d:
d[i] = 1
else:
d[i] += 1
for i in nums2:
if i in d and d[i] != 0:
arr.append(i)
d[i] -= 1
return arr
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = []
for num1 in nums1:
for num2 in nums2:
if num1 == num2:
nums2.remove(num2)
result.append(num1)
break
return result
Plus One¶
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.
Increment the large integer by one and return the resulting array of digits.
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Submitted Solution:
Ack, let’s take a closer look at this one, my solution is in the lowest 10% for speed, but beats 99.1% of other implementations for memory usage. Let’s go another round before checking other solutions.
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in reversed(range(len(digits))):
if digits[i] == 9:
digits[i] = 0
if i == 0:
digits.insert(0,1)
else:
digits[i] += 1
break
return digits
Here I converted the list to a number, incremented it, then broke it back into a list of numbers with simple string manipulation. This on beats 40% on runtime and 96.4% on memory usage.
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
num = int("".join(list(map(lambda x: str(x), digits))))
return map(lambda x: int(x), list(str(num + 1)))
Other Notable Solutions:
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
# better solution
n = len(digits)
for i in range(n-1,-1,-1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
return [1] + digits
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
s = ""
for i in digits:
s+=str(i)
s = int(s)
return list(str(s+1))
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
carry = 1
for i in range(len(digits)-1, -1, -1):
if carry + digits[i] >= 10:
digits[i] = digits[i] + carry - 10
carry = 1
else:
digits[i] = digits[i] + 1
return digits
if carry:
digits.insert(0, carry)
return digits
Move Zeroes¶
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Submitted Solution:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
index = 0
length = len(nums)
while index < length:
if nums[index] == 0:
del nums[index]
nums.append(0)
length -= 1
else:
index += 1
Other Notable Solutions:
# Fast solution
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
arr = []
for num in nums:
if num != 0:
arr.append(num)
for i in range(len(arr), len(nums)):
nums[i] = 0
for i in range(len(arr)):
nums[i] = arr[i]
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
index = 0
for n in nums:
if(n != 0):
nums[index] = n
index += 1
for i in range(index, len(nums)):
nums[i] = 0
return nums
Two Sum¶
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
Submitted Solution:
My initial/dumb solution sorted and cropped the possible solution set. It’s better than a straight comparison of every pair of numbers, and it passes all the unit tests, but I feel like it would fail if the combination of numbers relied on one of the last few numbers in the set.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Get some information about the set.
sorted_nums = sorted(nums)
last_indice = len(sorted_nums)-1
lowest_number = sorted_nums[0]
greatest_possible_number = target - lowest_number
# print(f"Lowest number: {lowest_number}")
# print(f"Greatest number: {greatest_possible_number}")
# Find indice of greatest number and delete the rest
greatest_indice = last_indice
while sorted_nums[greatest_indice] > greatest_possible_number:
# print(f"Ignoring {sorted_nums[greatest_indice]}")
greatest_indice -= 1
del sorted_nums[greatest_indice+1:]
# print(sorted_nums)
for i in range(len(sorted_nums)):
for j in range(len(sorted_nums)-1, i, -1):
# print(f"Checking {i} and {j}")
if sorted_nums[i] + sorted_nums[j] == target:
# print(f"Found match at indices {i} and {j}")
a = nums.index(sorted_nums[i])
b = nums.index(sorted_nums[j])
if a != b:
return sorted([a,b])
else:
a = nums.index(sorted_nums[i], b+1)
return sorted([a,b])
Other Notable Solutions:
ALL of the other notable solutions are variants on this ’enumerate’ loop.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
complement = {}
for i, n in enumerate(nums):
c = target-n
if c in complement:
return [complement[c], i]
complement[n]=i
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for ix, num in enumerate(nums):
need = target - num
if need in seen:
return [ix, seen[need]]
seen[num] = ix
Resumbitted Solution:
This still beats about half of solutions but not the notable ones above.
We convert the entire list to a hashmap first. Surprisingly fast given the size of the operation.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = dict(map(reversed, enumerate(nums)))
for i, v in enumerate(nums):
needed = target - v
if needed in hashmap:
ni = hashmap[needed]
if ni > i:
return [i, ni]
Interestingly, changing the hashing function kicks us into the top 95%+ of speed results.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {key: i for i, key in enumerate(nums)}
for i, v in enumerate(nums):
needed = target - v
if needed in hashmap:
ni = hashmap[needed]
if ni > i:
return [i, ni]
Note that, for duplicate items, the hashing function ensures that the last instance of a duplicate number will always be stored as ni, so checking if the number is greater (>) is a valid check, though not equal (!=) would do just as well.
Valid Sudoku¶
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Submitted Solution:
Brute force/dumb but fairly elegant.
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def add_counts(hashmap, numlist):
"""Adds elements to a hashmap."""
for elem in numlist:
if elem > 0:
if elem in hashmap:
hashmap[elem] += 1
else:
hashmap[elem] = 1
def bad_counts(hashmap) -> bool:
"""Returns true if counts are bad."""
vals = hashmap.values()
if vals:
return max(hashmap.values()) > 1
return False
# Convert board to ints
for i, row in enumerate(board):
for j, value in enumerate(row):
if value == ".":
board[i][j] = 0
else:
board[i][j] = int(value)
# Check rows
for i, row in enumerate(board):
row_map = {}
add_counts(row_map, row)
if bad_counts(row_map):
print(f"Found bad row: {i} : {row}")
return False
# Check Cols
for col in range(9):
col_map = {}
for row in range(9):
add_counts(col_map, [board[row][col]])
if bad_counts(col_map):
print(f"Found bad col: {col} : {col_map.keys()}")
return False
# Check cels
for i in range(3):
for j in range(3):
# Operate on cel i,j
print(f"Cel {i},{j}")
cel_map = {}
for k in range((i*3),((i*3)+3)):
run = board[k][(j*3):((j*3)+3)]
add_counts(cel_map, run)
print(run)
print(cel_map)
if bad_counts(cel_map):
print(f"Found bad cel: {i},{j} : {cel_map.keys()}")
return False
return True
Other Notable Solutions:
Both are fast.
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
N = 9
# Use an array to record the status
rows = [[0] * N for _ in range(N)]
cols = [[0] * N for _ in range(N)]
boxes = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
# Check if the position is filled with number
if board[r][c] == ".":
continue
pos = int(board[r][c]) - 1
# Check the row
if rows[r][pos] == 1:
return False
rows[r][pos] = 1
# Check the column
if cols[c][pos] == 1:
return False
cols[c][pos] = 1
# Check the box
idx = (r // 3) * 3 + c // 3
if boxes[idx][pos] == 1:
return False
boxes[idx][pos] = 1
return True
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
cols = collections.defaultdict(set)
rows = collections.defaultdict(set)
squares = collections.defaultdict(set)
for r in range(9):
for c in range(9):
if board[r][c] == ".":
continue
if (board[r][c] in rows[r] or
board[r][c] in cols[c] or
board[r][c] in squares[(r // 3, c // 3)]):
return False
cols[c].add(board[r][c])
rows[r].add(board[r][c])
squares[(r // 3, c // 3)].add(board[r][c])
return True
Rotate Image¶
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place , which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Submitted Solution:
Easy mode: makes a deep copy and re-inserts into original matrix.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
N = len(matrix) - 1 # max indice
copy = [row[:] for row in matrix]
for x, row in enumerate(copy):
for y, value in enumerate(row):
matrix[y][N-x] = value
The first improvement I’d make is holding each layer (4-array set of rows/cols n-deep into the image) in temporary memory and rotating those all at once.
Other Notable Solutions:
Like this guy.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n=len(matrix)
for i in range(n//2+n%2):
for j in range(i,len(matrix)-i-1):
tmp = matrix[i][j]
tmp2 = matrix[j][len(matrix)-i-1]
tmp3 = matrix[len(matrix)-j-1][i]
tmp4 = matrix[len(matrix)-i-1][len(matrix)-j-1]
matrix[i][j]=matrix[len(matrix)-j-1][i]
matrix[len(matrix)-j-1][i]=tmp4
matrix[j][len(matrix)-i-1]=tmp
matrix[len(matrix)-i-1][len(matrix)-1-j]=tmp2
Strings¶
Leetcode list here.
Reverse String¶
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array
in-place
with O(1) extra memory.
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = reversed(s)
Notably:
class Solution:
def reverseString(self, s: List[str]) -> None:
mid = len(s) // 2
l = len(s) - 1
for i in range(mid):
s[i], s[l] = s[l], s[i]
l -= 1
Reverse Integer¶
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Input: x = 123
Output: 321
Submitted Solution:
# Keep high/low bound as constants.
hi_bound = 2147483647
lo_bound = -2147483648
class Solution:
def reverse(self, x: int) -> int:
if x == 0:
return 0
# Learn a bit about X
new = 0
sign_x = (1, -1)[x<0] # get the sign of x
a = abs(x)
length = int(math.log(a, 10)) # For use with range.
base = (10**length)
# Move the bits around
while length >= 0:
end = a % 10
new += end * base
base //= 10
a //= 10
length -= 1
# Check if result is out of bounds
reversed_x = int(new * sign_x)
if reversed_x > hi_bound or reversed_x < lo_bound:
return 0
return reversed_x
The other solutions literally just do string transformations.
# Keep high/low bound as constants.
hi_bound = 2147483647
lo_bound = -2147483648
class Solution:
def reverse(self, x: int) -> int:
a = list(str(x))[::-1]
if a[-1] == "-":
del a[-1]
a.insert(0,"-")
xr = int("".join(a))
if xr > hi_bound or xr < lo_bound:
return 0
return xr
Other Notable Solutions:
class Solution:
def reverse(self, x: int) -> int:
result = int(str(x)[::-1]) if x > 0 else (int(str(abs(x))[::-1]) * -1)
return 0 if (result > 2147483647 or result < -2147483647) else result
First Unique Character in a String¶
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Input: s = "leetcode"
Output: 0
Input: s = "loveleetcode"
Output: 2
Submitted Solution:
First submission beats 45% of entries for speed and 67% for mem usage.
class Solution:
def firstUniqChar(self, s: str) -> int:
s_list = list(s)
counts = { x: 0 for x in set(s_list)}
for val in s_list:
counts[val] += 1
for i, val in enumerate(s_list):
if counts[val] == 1:
return i
return -1
Other Notable Solutions:
class Solution:
def firstUniqChar(self, s: str) -> int:
n = len(s)
res = float('inf')
for c in 'abcdefghijklmnopqrstuvwxyz':
i = s.find(c)
if i != -1 and i == s.rfind(c):
res = min(res, i)
if res == float('inf'):
return -1
return res
class Solution:
def firstUniqChar(self, s: str) -> int:
letters = 'abcdefghijklmnopqrstuvwxyz'
return min([s.index(l) for l in letters if s.count(l) == 1] or [-1])
Valid Anagram¶
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Submitted Solution:
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_counts = {x: s.count(x) for x in set(list(s))}
t_counts = {x: t.count(x) for x in set(list(t))}
return s_counts == t_counts
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return {x: s.count(x) for x in set(list(s))} == {x: t.count(x) for x in set(list(t))}
A two-stage approach beats 2/3 of other results for speed.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
s_counts = {x: s.count(x) for x in set(list(s))}
for x in set(list(t)):
if x not in s_counts or t.count(x) != s_counts[x]:
return False
return True
Here’s our winner, though.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return collections.Counter(s) == collections.Counter(t)
Keys:
- Instantiating a dictionary with zeroes
- Instantiating a dictionary with string character counts.
Valid Palindrome¶
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Submitted Solutions:
class Solution:
def isPalindrome(self, s: str) -> bool:
alphas = [ ch.lower() for ch in s if ch.isalnum() ]
length = len(alphas)-1
halfway = int((length+1)/2)
if not alphas:
return True
for i, val in enumerate(alphas):
if i >= halfway:
return True
if val != alphas[length-i]:
return False
return False
class Solution:
def isPalindrome(self, s: str) -> bool:
sa = "".join([ ch.lower() for ch in s if ch.isalnum() ])
half = int(len(sa)/2)
neg_half = len(sa) - half
return (sa[0:half]) == (sa[neg_half:])[::-1]
This beats 85% of other submissions for speed.
class Solution:
def isPalindrome(self, s: str) -> bool:
sa = list(filter(lambda x: x in 'abcdefghijklmnopqrstuvwxyz0123456789', list(s.lower())))
return sa == sa[::-1]
class Solution:
def isPalindrome(self, s: str) -> bool:
sa = re.sub(r'[^A-Za-z0-9]+', '', s).lower()
return sa == sa[::-1]
Other Notable Solutions:
class Solution:
def isPalindrome(self, s: str) -> bool:
if s == " ":
return True
s = "".join(filter(str.isalnum, s)).lower()
test = s[::-1]
if test == s:
return True
else :
return False
A low memory solution:
class Solution:
def isPalindrome(self, s: str) -> bool:
head = 0
tail = len(s) - 1
while head < tail and tail > 0:
if not s[head].isalnum():
head +=1
elif not s[tail].isalnum():
tail -=1
elif s[head].lower() != s[tail].lower():
return False
else:
head +=1
tail -= 1
return True
String to Integer (atoi)¶
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm for myAtoi(string s) is as follows:
- Read in and ignore any leading whitespace.
- Check if the next character (if not already at the end of the string) is
'-'or'+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. - Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer (i.e.
"123" -> 123,"0032" -> 32). If no digits were read, then the integer is0. Change the sign as necessary (from step 2). - If the integer is out of the 32-bit signed integer range
[-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than-231should be clamped to-231, and integers greater than231 - 1should be clamped to231 - 1. - Return the integer as the final result.
Note:
- Only the space character
' 'is considered a whitespace character. - Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Submitted Solution:
…I think there’s a bug with the Leetcode test cases for this problem.
Implement strStr()¶
Implement strStr() .
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s
strstr()
and Java’s
indexOf()
.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Example 3:
Input: haystack = "", needle = ""
Output: 0
Submitted Solution:
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
try:
return haystack.index(needle)
except:
return -1
Longest Common Prefix¶
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Submitted Solution:
Other Notable Solutions:
Linked Lists¶
Leetcode list here.
Delete Node in a Linked List¶
Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list.
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Submitted Solution:
Other Notable Solutions:
Remove Nth Node From End of List¶
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Submitted Solution:
Other Notable Solutions:
Reverse Linked List¶
Given the head of a singly linked list, reverse the list, and return the reversed list.
Submitted Solution:
Other Notable Solutions:
Merge Two Sorted Lists¶
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Submitted Solution:
Other Notable Solutions:
Palindrome Linked List¶
Given the head of a singly linked list, return true if it is a palindrome.
Submitted Solution:
Other Notable Solutions:
Linked List Cycle¶
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Submitted Solution:
Other Notable Solutions:
Trees¶
Leetcode list here.
Maximum Depth of Binary Tree¶
Submitted Solution:
Other Notable Solutions:
Validate Binary Search Tree¶
Submitted Solution:
Other Notable Solutions:
Symmetric Tree¶
Submitted Solution:
Other Notable Solutions:
Binary Tree Level Order Traversal¶
Submitted Solution:
Other Notable Solutions:
Convert Sorted Array to Binary Search Tree¶
Submitted Solution:
Other Notable Solutions:
Sorting and Searching¶
Leetcode list here.
Merge Sorted Array¶
Submitted Solution:
Other Notable Solutions:
First Bad Version¶
Submitted Solution:
Other Notable Solutions:
Dynamic Programming¶
Leetcode list here.
Climbing Stairs¶
Submitted Solution:
Other Notable Solutions:
Best Time to Buy and Sell Stock¶
Submitted Solution:
Other Notable Solutions:
Maximum Subarray¶
Submitted Solution:
Other Notable Solutions:
House Robber¶
Submitted Solution:
Other Notable Solutions:
Design¶
Leetcode list here.
Shuffle an Array¶
Submitted Solution:
Other Notable Solutions:
Min Stack¶
Submitted Solution:
Other Notable Solutions:
Math¶
Leetcode list here.
Fizz Buzz¶
Submitted Solution:
Other Notable Solutions:
Count Primes¶
Submitted Solution:
Other Notable Solutions:
Power of Three¶
Submitted Solution:
Other Notable Solutions:
Roman to Integer¶
Submitted Solution:
Other Notable Solutions:
Miscallaneous¶
Leetcode list here.
Number of 1 Bits¶
Submitted Solution:
Other Notable Solutions:
Hamming Distance¶
Submitted Solution:
Other Notable Solutions:
Reverse Bits¶
Submitted Solution:
Other Notable Solutions:
Pascal’s Triangle¶
Submitted Solution:
Other Notable Solutions:
Valid Parentheses¶
Submitted Solution:
Other Notable Solutions:
Missing Number¶
Submitted Solution:
Other Notable Solutions:
Top Interview Questions: Medium¶
Leetcode list here,
Array and Strings¶
Linked List¶
Trees and Graphs¶
Backtracking¶
Sorting and Searching¶
Dynamic Programming¶
Design¶
Math¶
Others¶
Top Interview Questions: Hard¶
Leetcode list here,
Array and Strings¶
Linked List¶
Trees and Graphs¶
Backtracking¶
Sorting and Searching¶
Dynamic Programming¶
Design¶
Math¶
Others¶
Amazon 2022 SDE-1 List¶
Leetcode list here.
Integer to Roman¶
Valid Parentheses¶
Merge k Sorted Lists¶
First Missing Positive¶
Jump Game II¶
Insert Interval¶
Word Search¶
Binary Tree Level Order Traversal¶
Binary Tree Zigzag Level Order Traversal¶
Best Time to Buy and Sell Stock III¶
Binary Tree Maximum Path Sum¶
Word Ladder II¶
Word Ladder¶
Longest Consecutive Sequence¶
Copy List with Random Pointer¶
Word Break¶
Word Break II¶
Min Stack¶
Binary Tree Right Side View¶
Number of Islands¶
Word Search II¶
Product of Array Except Self¶
Integer to English Words¶
Find Median from Data Stream¶
Best Time to Buy and Sell Stock with Cooldown¶
Coin Change¶
Russian Doll Envelopes¶
Find All Anagrams in a String¶
LFU Cache¶
Concatenated Words¶
Number of Provinces¶
Knight Probability in Chessboard¶
My Calendar I¶
Asteroid Collision¶
All Paths From Source to Target¶
Rectangle Overlap¶
K-Similar Strings¶
Reorder Data in Log Files¶
Squares of a Sorted Array¶
Rotting Oranges¶
Stream of Characters¶
Longest Happy Prefix¶
Making File Names Unique¶
BUILDMEH