Welcome to AlgoPro
Welcome to AlgoPro! In this series, you join ex-Google and ex-Facebook software engineers (“TechLead” and “Joma”) to learn exactly how to pass interview whiteboard coding challenges.
Within the past decade, the interview game has become a form of “art” that many college and schools simply do not teach .
It is also a game. Inside the walls of tech companies, most engineers do realize how ridiculous the process is. The most optimal form of candidate assessment may be to spend a week watching a candidate code a small project – however, that process is just too slow and expensive. And so with thousands of potential candidates and limited time, companies continue to use coding exercises for interviewing. This game’s rules are not perfect, but you have to play the game if you wish to win.
Interview skills are a different beast from the practical hands-on application of code, which usually involves putting together websites, creating layouts, buttons, UI, and wiring-up backend APIs. A lot of “on-the-job” skills actually don’t utilize complex algorithms, and you’d be lucky to encounter a chance to use recursion - even at FANG companies. As a result, we find that our skills as developers degrade over time, and we forget the traditional data structures & algorithms that we may have learned in school. It is said that half of engineers at Google probably couldn’t even pass their own interviews. We have personally seen colleagues from Facebook or Google fail interviews when trying to switch out. What we’re trying to say is, i nterviewing is a long-term game, and becoming good at it will pay off throughout your career.
With AlgoPro, we take a focus on coding, data structures, and algorithms. This is one of the key areas that especially junior engineers must focus on. It doesn’t matter how good your other pet projects are or how impressive your background is, if you can’t get past the whiteboarding question.
We believe that anyone can become an “algo pro.” Coding is not a talent - it is pure skill acquired through practice and repetition. The more of these you tackle and solve, the more familiar you will become. You’ll find there aren’t so many different data structures or algorithms in practice – just a few hash tables, stacks, queues, arrays, variables, and clever use of recursion or iteration is often all that you need. As you solve more and more exercises, you’ll realize that it’s just the same algorithms and data structures over and over again. Our goal in this course is to help you become a pro at these.
We also ensure to talk through a complete time-space complexity analysis, or “Big O”. This analysis is absolutely essential in an interview setting and especially so in top-tier tech companies due to the larger data sets and focus on application performance. A non-efficient solution may cost just a few milliseconds in a coding exercise, but can cost massive performance loss across millions of users and gigantic datasets. A lot of candidates may get tripped up on the analysis, but in this course we show you exactly how to deliver that analysis with confidence.
In this course, we generally use the language Python to teach. Why Python? It’s a fairly simple language to read (and very similar to Javascript, Java, or C). So, even if you don’t know it well you’ll still be able to understand it and adapt it to any other language like Javascript, C, PHP, Java, etc., Python is also widely used at Google/YouTube, Facebook/Instagram, Netflix, Uber, Dropbox, and many more. It is a modern language and its conciseness makes it an ideal choice for interviews.
Thank you for joining us, and without further ado, enjoy the series!
Patrick Shyu “TechLead”
Jonathan Ma “Joma”
General Approach
Firstly, let’s take a step back and cover the general approach in tackling a coding interview question. These are often asked in phone-interviews or on-site interviews.
Also, if you haven’t already, we recommend checking out our other program Tech Interview Pro ( discounted for AlgoPro members ) for a more comprehensive guide on the entire interview process, including systems design, behavior, communication, and a breakdown of the algorithms & data structures you need to know.
At Google (as well as many other top-tier tech companies), you will be evaluated across a set of criteria. It is not simply a question of whether you solve the question or not. YES/NO does not deliver enough signal to a hiring committee or manager, rather your technique and approach matter a ton too. This is why you may often hear that it’s not if you reach the solution, but how you reach that solution. Here are some common criteria:
- Coding - How clean & structured is your code? Could you write the code that you said you would write? Did you cover the edge and base cases? Are your variables and functions well-named?
- Data Structures & Algorithms - Could you come up with a suitable algorithm or data structure to solve the problem efficiently? Could you analyze that solution in terms of time & space complexity and the trade-offs? Did you demonstrate mastery of the data structures available and create your own data structures as necessary with private/public APIs? Could you think critically to analyze various alternatives and compare brute force solutions versus more optimal solutions?
- Communication - Were you able to clarify the problem as needed, and then explain the solution? Many software engineers will try to talk as they are coding, and the words come out as a jumble of stuttered " uhmm… hold on… ah… wait… give me 2 seconds… oh… ,nevermind… " Some engineers simply talk in a way that is too technical and incomprehensible " … then we increment the variable i by the variable j minus one and check if j is equal to k… " The ability to communicate effectively is crucial because coding is a team sport at the end of the day.
- Speed & Efficiency - Unlike in the old days, tech companies have been trying to avoid " aha !" moments where candidates either know or don’t know the answer. It is far more favored for interviewers to ask questions that can build atop of itself (such as increasingly adding restrictions or pushing for faster time/space), so that interviewers can get some signal on the candidate’s ability beyond just “pass” or “no pass.” This is why fluidity & confidence is essential. So, even if you may have heard of some of these problems before once or twice, it really helps to become great at these and see how “the pros” solve these problems to help you recognize patterns in code and in crafting elegant & simple solutions.
Throughout these exercises, keep these 4 criteria in mind: coding, data structure & algorithms, communication, and speed. If you can hit all 4, you’ll be golden.
Time-Space Complexity
A lot of candidates get stuck up on “Big O” time-space complexity analysis, so we wanted to give you a primer on this.
Essentially, " Big O " is the worst-case usage of time or space of a problem in relation to the size of input. For instance, for a tree problem, one would usually assume that the tree is unbalanced and looks like a single branch to evaluate “Big O,” because the single branch often leads to the worst case performance of an algorithm.
In the diagram above, for a well-balanced tree (on the left), it may take " log(n) " time to find node “5” but in the worst-case scenario it would take " n " time to iterate through every single node in the tree.
There aren’t that many types of complexity. We can assume that " n " indicates the length of the input, and implicitly any runtime can be assumed to be multiplied by some constant factor k . O(n) is the same as O(2n), O(3n), O(4n), O(kn) etc., Here are some common time-space complexities:
- Linear. O(n) - Most optimal algorithms run in linear time. An easy way to identify this is to determine if you’re visiting every node or item once and only once. If you are, it is linear… it doesn’t matter how many operations you’re doing whether it’s 1, 2, 3, or 4 lines of code you’re executing per node. Generally, you are still doing a constant amount of work per input.
- Constant . O(k) - Constant time algorithms have a running time independent of the input size. Mathematical formulas for instance have fixed running times and are considered constant time.
- Logarithmic. O(log(n)) - Logarithmic algorithms are often seen in trees. It’s best to think of “logarithmic” as the “height of the tree.” So, a binary search, for instance, often includes traversing down the height of a tree and can be considered logarithmic in time. (Although, it may still be more accurate to say that for an unbalanced tree, the runtime is in the worst case linear.)
- Superlinear . O(nlog(n))* . Most sorts operate in “n log n” time. This includes popular sorting algorithms like quicksort, mergesort, or heapsort. (Actually, quicksort is O(n2) time in the worst-case scenario generally).
- Quadratic or Cubic / Polynomial. O(n2) or O(n3). Brute force algorithms often run in O( n2 ) or O(n3) time where you may be looping within a loop. It’s easy to identify if you see a for-loop inside a for-loop, where for each element i you iterate through another element j , for instance. A common scenario is, given two arrays, find the common elements in each array where you would simply go through each element and check whether it exists in the other array. This would execute in O(nm)* time, where n and m are the sizes of each array. It’s still great to name these brute force algorithms if you can identify them.
- Exponential. O(2n) . Exponential algorithms are quite terrible in running time. A classic example is determining every permutation of a set of n bits (it would take 2n combinations). Another example is computing the fibonacci sequence fib(n) = fib(n-1) + fib(n-2), where for each item, it requires the computation of two more subproblems.
- Factorial. O(n!). These algorithms are the slowest and don’t show up that often. You might see this in combinatorial problems, or like a “traveling salesman” problem where given n nodes, you need to find the optimal path from start to finish. In your first iteration, you have a selection of n cities to visit, then n-1 cities, then n-2 cities, n-3 cities, etc., until you reach the last city. That runtime is n * (n -1 ) * (n - 2) * (n -3 ) … 1 = O(n!) .
A lot of candidates get stuck here by either getting too deep in nitty gritty details and overcomplicating this like saying “This is O(3 * k * n2) , where k is the number of comparisons…” Most software engineers don’t care about this level of detail, and you can often get away with simply saying “This is quadratic time because we have two for-loops, each one iterating from 1 to n.”
One more tip - do not say “This is O(m + v + e),” when you haven’t defined what m, v, or e are. You generally want to say “… where m is the height of the matrix, v is the number of vertices, e is the number of edges, etc.,” Once you start reciting formulas without defining the constants you’re using, your analysis will appear amateurish.
Most interviewers will focus on time-complexity, but it is great to also consider space-complexity too. Algorithms are commonly tradeoffs between time and space. For instance, you may be able to take a polynomial algorithm and convert it to an O(n) algorithm, but it requires creation of a hashmap of size O(n) . That’s a good trade-off to be able to talk about because additional space is needed.
How to practice
In your coding practices, we have a few tips for you.
- Try to solve the problems. Watch the videos, and then pause and try to solve these problems on your own before viewing the solutions. Practicing these will help you appreciate where your own flaws are and where you need to improve, before simply just jumping to the solutions.
- Dig in deep. Rather than simply solving the problem and moving on, we’d encourage you to try re-solving the problem using other techniques. Challenge yourself to write the brute force solution and to analyze it, or to write the iterative version of a recursive solution that we might provide. See if you can create custom data structures like a “Grid class,” “Point class,” or “Binary Search Tree class” to add more object-oriented structure to your code. You’d be surprised how tricky a problem still is, even if you think you’ve solved it optimally just once. As we’ve mentioned, the fluidity & speed is what sets you apart – remember that many candidates solve a problem and still do not receive offers, because they cannot solve the problems fluidly & quickly .
- Be Consistent . Work on at least one problem a day to keep your skills sharp and this process of repetition will keep your mind engaged. There are patterns in these algorithms and data structures that if you do over and over, you will learn to recognize.
- Write by hand. Practice writing out the problems by hand on paper or a whiteboard. It will help you better gauge your usage of time and appreciate how valuable time is in an interview. In a real interview setting, it wouldn’t be rare to actually be writing half pseudocode to save on time.
- Efficiency & confidence. The speed and fluidity at which you can analyze a problem, propose an algorithm, and then code that algorithm reveal a lot about a candidate. If you solved the problem, try doing it again faster later.
-
Other Resources. Pair your practice regimen with other resources. We recommend checking out:
- Daily Interview Pro (http://dailyinterviewpro.com) - Daily Interview Pro is is similar to AlgoPro, but in written format with many more problems (one problem a day). It is a FREE service where we email you a handpicked coding exercise each day.
With that said, we’ve worked hard to cover as many of these as possible for you. If you think we’ve made any mistakes or bugs (or if you find an even more optimal solution!), feel free to let us know too! We’d love to see it. Just email us at contact@techseries.dev.
Sincerely,
Patrick Shyu “TechLead”
Jonathan Ma “Joma”
Setup
Coding Sessions
To follow along in the coding exercises, you can use any Python environment you like to write and run code. The simplest setup may be to just create a textfile untitled.py and run it in a terminal with a command:
python3 untitled.py
If you’re curious about TechLead’s setup, he is using the free Visual Studio Code text editor with the Code Runner extension, which allows you to quickly run snippets of code. If you choose to use Code Runner, add these to your settings.json for Python 3:
“code-runner.clearPreviousOutput”: true, “code-runner.executorMap”: { “python”:“python3”, },
You can also just use an online Python interpreter like https://repl.it/languages/python3, or any editor you like as well of course!
OK, let’s get started.
Valid Binary Search Tree
Coding Sessions
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isValidBST(self, root):
def helper(node, lower, upper):
if not node:
return True
val = node.val
if val <= lower or val >= upper:
return False
if not helper(node.right, val, upper):
return False
if not helper(node.left, lower, val):
return False
return True
return helper(root, float('-inf'), float('inf'))
node = TreeNode(5)
node.left = TreeNode(4)
node.right = TreeNode(7)
print(Solution().isValidBST(node))
# True
Ransom Note
import collections
class Solution:
def canConstruct(self, ransomNote, magazine):
mag_dict = collections.defaultdict(int)
for char in magazine:
mag_dict[char] += 1
for char in ransomNote:
mag_dict[char] -= 1
if mag_dict[char] < 0:
return False
return True
print(Solution().canConstruct('aa', 'aab'))
# True
Add two numbers as a linked list
class Node(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
return self.addTwoNumbersRecursive(l1, l2, 0)
# return self.addTwoNumbersIterative(l1, l2)
def addTwoNumbersRecursive(self, l1, l2, c):
val = l1.val + l2.val + c
c = val // 10
ret = Node(val % 10)
if l1.next != None or l2.next != None:
if not l1.next:
l1.next = Node(0)
if not l2.next:
l2.next = Node(0)
ret.next = self.addTwoNumbersRecursive(l1.next, l2.next, c)
elif c:
ret.next = Node(c)
return ret
def addTwoNumbersIterative(self, l1, l2):
a = l1
b = l2
c = 0
ret = current = None
while a or b:
val = a.val + b.val + c
c = val // 10
if not current:
ret = current = Node(val % 10)
else:
current.next = Node(val % 10)
current = current.next
if a.next or b.next:
if not a.next:
a.next = Node(0)
if not b.next:
b.next = Node(0)
elif c:
current.next = Node(c)
a = a.next
b = b.next
return ret
l1 = Node(2)
l1.next = Node(4)
l1.next.next = Node(3)
l2 = Node(5)
l2.next = Node(6)
l2.next.next = Node(4)
answer = Solution().addTwoNumbers(l1, l2)
while answer:
print(answer.val, end=' ')
answer = answer.next
# 7 0 8
Two Sum
class Solution:
def twoSum(self, nums, target):
dict = {}
for i, num in enumerate(nums):
if target-num in dict:
return [dict[target-num], i]
dict[num] = i
return "ASDFASDFSAD"
First and Last Indices of an Element in a Sorted Array
class Solution:
def getRange(self, arr, target):
first = self.binarySearchIterative(arr, 0, len(arr) - 1, target, True)
last = self.binarySearchIterative(arr, 0, len(arr) - 1, target, False)
return [first, last]
def binarySearch(self, arr, low, high, target, findFirst):
if high < low:
return -1
mid = low + (high - low) // 2
if findFirst:
if (mid == 0 or target > arr[mid - 1]) and arr[mid] == target:
return mid
if target > arr[mid]:
return self.binarySearch(arr, mid + 1, high, target, findFirst)
else:
return self.binarySearch(arr, low, mid - 1, target, findFirst)
else:
if (mid == len(arr)-1 or target < arr[mid + 1]) and arr[mid] == target:
return mid
elif target < arr[mid]:
return self.binarySearch(arr, low, mid - 1, target, findFirst)
else:
return self.binarySearch(arr, mid + 1, high, target, findFirst)
def binarySearchIterative(self, arr, low, high, target, findFirst):
while True:
if high < low:
return -1
mid = low + (high - low) // 2
if findFirst:
if (mid == 0 or target > arr[mid - 1]) and arr[mid] == target:
return mid
if target > arr[mid]:
low = mid + 1
else:
high = mid - 1
else:
if (mid == len(arr)-1 or target < arr[mid + 1]) and arr[mid] == target:
return mid
elif target < arr[mid]:
high = mid - 1
else:
low = mid + 1
arr = [1, 3, 3, 5, 7, 8, 9, 9, 9, 15]
x = 9
print(Solution().getRange(arr, 9))
# [6, 8]
Permutations
class Solution:
def permute(self, nums):
res = []
def permuteHelper(start):
if start == len(nums) - 1:
res.append(nums[:])
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
permuteHelper(start + 1)
nums[start], nums[i] = nums[i], nums[start]
permuteHelper(0)
return res
print(Solution().permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
Sorting a list with 3 unique numbers
def sortNums(nums):
counts = {}
for n in nums:
counts[n] = counts.get(n, 0) + 1
return ([1] * counts.get(1, 0) +
[2] * counts.get(2, 0) +
[3] * counts.get(3, 0))
def sortNums2(nums):
one_index = 0
three_index = len(nums) - 1
index = 0
while index <= three_index:
if nums[index] == 1:
nums[index], nums[one_index] = nums[one_index], nums[index]
one_index += 1
index += 1
elif nums[index] == 2:
index += 1
elif nums[index] == 3:
nums[index], nums[three_index] = nums[three_index], nums[index]
three_index -= 1
return nums
print(sortNums2([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]
Queue Reconstruction By Height
class Solution:
def reconstructQueue(self, people):
people.sort(key=lambda x: (-x[0], x[1])) # O(nlogn)
res = []
for p in people: # O(N)
res.insert(p[1], p) # O(n)
return res
# Time Complexity O(N^2)
# Space : O(N)
print(Solution().reconstructQueue(
[[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]))
# [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
Find the non-duplicate number
class Solution(object):
def singleNumber(self, nums):
occurrence = {}
for n in nums:
occurrence[n] = occurrence.get(n, 0) + 1
for key, value in occurrence.items():
if value == 1:
return key
def singleNumber2(self, nums):
unique = 0
for n in nums:
unique ^= n
return unique
print(Solution().singleNumber2([4, 3, 2, 4, 1, 3, 2]))
# 1
Reverse A Linkedlist
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def __str__(self):
result = str(self.val)
if self.next:
result += str(self.next)
return result
class Solution:
def reverseList(self, head):
prev = None
curr = head
while (curr != None):
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
node = ListNode(1)
node.next = ListNode(2)
node.next.next = ListNode(3)
print(Solution().reverseList(node))
# 321
Maximum In A Stack
class MaxStack(object):
def __init__(self):
self.stack = []
self.maxes = []
def push(self, val):
self.stack.append(val)
if self.maxes and self.maxes[-1] > val:
self.maxes.append(self.maxes[-1])
else:
self.maxes.append(val)
def pop(self):
if self.maxes:
self.maxes.pop()
return self.stack.pop()
def max(self):
return self.maxes[-1]
s = MaxStack()
s.push(1)
s.push(2)
s.push(3)
s.push(2)
print('max', s.max())
print(s.pop())
print('max', s.max())
print(s.pop())
print('max', s.max())
print(s.pop())
print('max', s.max())
print(s.pop())
Course Schedule
class Solution:
def canFinish(self, numCourses, prerequisites):
graph = collections.defaultdict(list)
for edge in prerequisites:
graph[edge[0]].append(edge[1])
visited = set()
# True if there is a cycle, False if not
def visit(vertex):
visited.add(vertex)
for neighbour in graph[vertex]:
if neighbour in visited or visit(neighbour):
return True
visited.remove(vertex)
return False
for i in range(numCourses):
if visit(i):
return False
return True
Find Pythagorean Triplets
def findPythagoreanTriplets(nums):
for a in nums:
for b in nums:
for c in nums:
if a*a + b*b == c*c:
return True
return False
def findPythagoreanTriplets2(nums):
squares = set([n*n for n in nums])
for a in nums:
for b in nums:
if a * a + b * b in squares:
return True
return False
print(findPythagoreanTriplets2([3, 5, 12, 5, 13]))
# True
Push Dominoes
class Solution:
def pushDominoes(self, dominoes):
N = len(dominoes)
force = [0] * N
# Populate Rs
f = 0
for i in range(N):
if dominoes[i] == 'R':
f = N
elif dominoes[i] == 'L':
f = 0
else:
f = max(f-1, 0)
force[i] += f
# Populate Ls
for i in range(N-1, -1, -1):
if dominoes[i] == 'L':
f = N
elif dominoes[i] == 'R':
f = 0
else:
f = max(f-1, 0)
force[i] -= f
for i in range(N):
if force[i] == 0:
force[i] = '.'
elif force[i] > 0:
force[i] = 'R'
else:
force[i] = 'L'
return "".join(force)
Simple Calculator
class Solution(object):
def __eval_helper(self, expression, index):
op = '+'
result = 0
while index < len(expression):
char = expression[index]
if char in ('+', '-'):
op = char
else:
value = 0
if char.isdigit():
value = int(char)
elif char == '(':
(value, index) = self.__eval_helper(expression, index + 1)
if op == '+':
result += value
if op == '-':
result -= value
index += 1
return (result, index)
def eval(self, expression):
return self.__eval_helper(expression, 0)[0]
print(Solution().eval('(1 + (2 + (3 + (4 + 5))))'))
# 15
Product Of Array Except Self
class Solution:
def productExceptSelf(self, nums):
res = [1] * len(nums)
for i in range(1, len(nums)):
res[i] = res[i-1] * nums[i-1]
right = 1
for i in range(len(nums) - 2, -1, -1):
right *= nums[i+1]
res[i] *= right
return res
Longest Sequence with Two Unique Numbers
def findSequence(seq):
if len(seq) < 2:
return len(seq)
a, b = seq[0], seq[1]
last_num = b
last_num_count = 1 if (a == b) else 0
length = 1
max_length = 1
for n in seq[1:]:
if n in (a, b):
length += 1
if b == n:
last_num_count += 1
else:
last_num = a
last_num_count = 1
else:
a = last_num
b = n
last_num = b
length = last_num_count + 1
last_num_count = 1
max_length = max(length, max_length)
return max_length
print(findSequence([1, 3, 5, 3, 1, 3, 1, 5]))
# 4
print(findSequence([1, 1, 3, 3, 4, 4]))
# 4
Great Job! Keep Going!
Non Decreasing Array
class Solution:
def checkPossibility(self, nums):
idx = None
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
# if there's two dip or more
if idx is not None:
return False
idx = i
# if there's no dip
if idx is None:
return True
# if there's only one dip
if idx == 0:
return True
if idx == len(nums) - 2:
return True
if nums[idx] <= nums[idx + 2]:
return True
if nums[idx - 1] <= nums[idx + 1]:
return True
return False
Word Search
class Grid(object):
def __init__(self, matrix):
self.matrix = matrix
def __wordSearchRight(self, index, word):
for i in range(len(self.matrix[index])):
if word[i] != self.matrix[index][i]:
return False
return True
def __wordSearchBottom(self, index, word):
for i in range(len(self.matrix)):
if word[i] != self.matrix[i][index]:
return False
return True
def wordSearch(self, word):
for i in range(len(self.matrix)):
if self.__wordSearchRight(i, word):
return True
for i in range(len(self.matrix[0])):
if self.__wordSearchBottom(i, word):
return True
return False
matrix = [
['F', 'A', 'C', 'I'],
['O', 'B', 'Q', 'P'],
['A', 'N', 'O', 'B'],
['M', 'A', 'S', 'S']]
print(Grid(matrix).wordSearch('FOAM'))
# True
Top K Frequent Elements
class Solution:
def topKFrequent(self, nums, k):
count = collections.defaultdict(int)
for n in nums:
count[n] += 1
heap = []
for key, v in count.items():
heapq.heappush(heap, (v, key))
if len(heap) > k:
heapq.heappop(heap)
res = []
while len(heap) > 0:
res.append(heapq.heappop(heap)[1])
return res
Remove Kth Last Element From Linked List
class Node:
def __init__(self, val, next):
self.val = val
self.next = next
def __str__(self):
n = self
answer = ''
while n:
answer += str(n.val)
n = n.next
return answer
def remove_kth_from_linked_list(node, k):
slow, fast = node, node
for i in range(k):
fast = fast.next
if not fast:
return node.next
prev = None
while fast:
prev = slow
fast = fast.next
slow = slow.next
prev.next = slow.next
return node
head = Node(1, Node(2, Node(3, Node(4, Node(5, None)))))
print(head)
# 12345
head = remove_kth_from_linked_list(head, 1)
print(head)
# 1234
Valid Parentheses
class Solution:
def isValid(self, s):
stack = []
for c in s:
if c == '(':
stack.append('(')
if c == ')':
if len(stack) == 0:
return False
if stack[-1] != '(':
return False
else:
stack.pop()
if c == '{':
stack.append('{')
if c == '}':
if len(stack) == 0:
return False
if stack[-1] != '{':
return False
else:
stack.pop()
if c == '[':
stack.append(']')
if c == ']':
if len(stack) == 0:
return False
if stack[-1] != ']':
return False
else:
stack.pop()
if len(stack) > 0:
return False
else:
return True
Find the Kth Largest Element in a List
import heapq
import random
def findKthLargest(nums, k):
return sorted(nums)[len(nums) - k]
def findKthLargest2(nums, k):
return heapq.nlargest(k, nums)[-1]
def findKthLargest3(nums, k):
def select(list, l, r, index):
if l == r:
return list[l]
pivot_index = random.randint(l, r)
# move pivot to the beginning of list
list[l], list[pivot_index] = list[pivot_index], list[l]
# partition
i = l
for j in range(l + 1, r + 1):
if list[j] < list[l]:
i += 1
list[i], list[j] = list[j], list[i]
# move pivot to the correct location
list[i], list[l] = list[l], list[i]
# recursively partition one side
if index == i:
return list[i]
elif index < i:
return select(list, l, i - 1, index)
else:
return select(list, i + 1, r, index)
return select(nums, 0, len(nums) - 1, len(nums) - k)
print(findKthLargest3([3, 5, 2, 4, 6, 8], 3))
# 5
3 Sum
class Solution:
def threeSum(self, nums):
res = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
# two sum
j = i + 1
k = len(nums) - 1
while j < k:
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
elif nums[i] + nums[j] + nums[k] > 0:
k -= 1
else:
j += 1
# end two sum
return res
print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]
Spiral Traversal
RIGHT = 0
UP = 1
LEFT = 2
DOWN = 3
class Grid(object):
def __init__(self, matrix):
self.matrix = matrix
def __next_position(self, position, direction):
if direction == RIGHT:
return (position[0], position[1] + 1)
elif direction == DOWN:
return (position[0] + 1, position[1])
elif direction == LEFT:
return (position[0], position[1] - 1)
elif direction == UP:
return (position[0] - 1, position[1])
def __next_direction(self, direction):
return {
RIGHT: DOWN,
DOWN: LEFT,
LEFT: UP,
UP: RIGHT
}[direction]
def __is_valid_position(self, pos):
return (0 <= pos[0] < len(self.matrix) and
0 <= pos[1] < len(self.matrix[0]) and
self.matrix[pos[0]][pos[1]] is not None)
def spiralPrint(self):
remaining = len(self.matrix) * len(self.matrix[0])
current_direction = RIGHT
current_position = (0, 0)
result = ''
while remaining > 0:
remaining -= 1
result += str(self.matrix[current_position[0]]
[current_position[1]]) + ' '
self.matrix[current_position[0]][current_position[1]] = None
next_position = self.__next_position(current_position, current_direction)
if not self.__is_valid_position(next_position):
current_direction = self.__next_direction(current_direction)
current_position = self.__next_position(
current_position, current_direction)
else:
current_position = self.__next_position(
current_position, current_direction)
return result
grid = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20]]
print(Grid(grid).spiralPrint())
# 1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12
Unique Paths
class Solution:
def uniquePaths(self, m, n):
matrix = []
for i in range(m):
matrix.append([0]*n)
for i in range(m):
matrix[i][0] = 1
for j in range(n):
matrix[0][j] = 1
for i in range(1, m):
for j in range(1, n):
matrix[i][j] = matrix[i][j-1] + matrix[i-1][j]
return matrix[m-1][n-1]
Queue Using Stacks
class Queue(object):
def __init__(self):
self.s1 = []
self.s2 = []
def enqueue(self, val):
self.s1.append(val)
def dequeue(self):
if self.s2:
return self.s2.pop()
if self.s1:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
return None
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
# 1 2 3 4
Remove Zero Sum Consecutive Nodes
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeZeroSumSublists(self, head):
curr = dummy = ListNode(0)
dummy.next = head
prefix = 0
seen = collections.OrderedDict()
while curr:
prefix += curr.val
if prefix not in seen:
seen[prefix] = curr
else:
node = seen[prefix]
node.next = curr.next
while list(seen.keys())[-1] != prefix:
seen.popitem()
curr = curr.next
return dummy.next
Great Job! Keep Going!
Merge K Sorted Linked Lists
class Node(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
def __str__(self):
c = self
answer = ''
while c:
answer += str(c.val) if c.val else ""
c = c.next
return answer
def merge(lists):
arr = []
for node in lists:
while node:
arr.append(node.val)
node = node.next
head = root = None
for val in sorted(arr):
if not root:
head = root = Node(val)
else:
root.next = Node(val)
root = root.next
return head
def merge2(lists):
head = current = Node(-1)
while any(list is not None for list in lists):
current_min, i = min((list.val, i)
for i, list in enumerate(lists) if list is not None)
lists[i] = lists[i].next
current.next = Node(current_min)
current = current.next
return head.next
a = Node(1, Node(3, Node(5)))
b = Node(2, Node(4, Node(6)))
print(a)
# 135
print(b)
# 246
print(merge2([a, b]))
# 123456
Generate Parentheses
class Solution:
def generateParentheses(self, n):
res = []
def backtrack(S, left, right):
if len(S) == 2*n:
res.append(S)
return
if left < n:
backtrack(S+'(', left+1, right)
if left > right:
backtrack(S+')', left, right+1)
backtrack('', 0, 0)
return res
print(Solution().generateParentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']