[techseries.dev] - AlgoPro - part 1

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.


Patrick Shyu “TechLead”

Jonathan Ma “Joma”


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)
# 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)
        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)
        return self.binarySearch(arr, low, mid - 1, target, findFirst)
      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)
        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
          high = mid - 1
        if (mid == len(arr)-1 or target < arr[mid + 1]) and arr[mid] == target:
          return mid
        elif target < arr[mid]:
          high = mid - 1
          low = mid + 1

arr = [1, 3, 3, 5, 7, 8, 9, 9, 9, 15]
x = 9
print(Solution().getRange(arr, 9))
# [6, 8]


class Solution:
  def permute(self, nums):
    res = []

    def permuteHelper(start):
      if start == len(nums) - 1:
      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]
    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)

    [[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)

# 321

Maximum In A Stack

class MaxStack(object):
  def __init__(self):
    self.stack = []
    self.maxes = []

  def push(self, val):
    if self.maxes and self.maxes[-1] > val:

  def pop(self):
    if self.maxes:
    return self.stack.pop()

  def max(self):
    return self.maxes[-1]

s = MaxStack()
print('max', s.max())
print('max', s.max())
print('max', s.max())
print('max', s.max())

Course Schedule

class Solution:
  def canFinish(self, numCourses, prerequisites):
    graph = collections.defaultdict(list)
    for edge in prerequisites:

    visited = set()

    # True if there is a cycle, False if not
    def visit(vertex):
      for neighbour in graph[vertex]:
        if neighbour in visited or visit(neighbour):
          return True
      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
        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
        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'
        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
        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
        last_num = a
        last_num_count = 1
      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']]

# 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:
    res = []
    while len(heap) > 0:
    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)))))
# 12345

head = remove_kth_from_linked_list(head, 1)
# 1234

Valid Parentheses

class Solution:
  def isValid(self, s):
    stack = []
    for c in s:
      if c == '(':
      if c == ')':
        if len(stack) == 0:
          return False
        if stack[-1] != '(':
          return False
      if c == '{':
      if c == '}':
        if len(stack) == 0:
          return False
        if stack[-1] != '{':
          return False
      if c == '[':
      if c == ']':
        if len(stack) == 0:
          return False
        if stack[-1] != ']':
          return False
    if len(stack) > 0:
      return False
      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)
      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 = []
    for i in range(len(nums) - 2):
      if i > 0 and nums[i] == nums[i - 1]:
      # 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
          j += 1
      # end two sum
    return res

print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

Spiral Traversal

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

  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)
        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]]

# 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):
    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):

  def dequeue(self):
    if self.s2:
      return self.s2.pop()

    if self.s1:
      while self.s1:
      return self.s2.pop()

    return None

q = Queue()
# 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
        node = seen[prefix]
        node.next = curr.next
        while list(seen.keys())[-1] != prefix:
      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:
      node = node.next
  head = root = None
  for val in sorted(arr):
    if not root:
      head = root = Node(val)
      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)))

# 135
# 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:
      if left < n:
        backtrack(S+'(', left+1, right)
      if left > right:
        backtrack(S+')', left, right+1)
    backtrack('', 0, 0)
    return res

# ['((()))', '(()())', '(())()', '()(())', '()()()']