Noisebridge Whiteboarding Workshop

This is an archive of whiteboarding problems discussed at weekly whiteboarding meetups at Noisebridge. Make a PR if you've written a solution. To pose an algorithm problem to the group, open an issue in this repository.

Starting out

If you're new to whiteboarding, here's a miniature prerequisite roadmap to help prepare you for the experience:

1. Learn programming fundamentals (variables, functions, loops, arrays, etc). Python is a popular language choice; however, most algorithm books use Java, C or C++, so exposure to one of those is recommended.
2. Explore the basics of data structures and algorithms (big-O, stacks, queues, graphs, hashing, sorting, searching, etc).
3. Grab a copy of Cracking the Coding Interview (4th ed here)
4. Sign up for LeetCode and other coding challenge sites and keep solving!

Pull request guidelines

• Please adhere to your language's typical style guidelines for indentation, whitespace and casing.
• Focus on realistic solutions to whiteboarding problems (cap lines of code at a reasonable amount but feel free to subtract lines used to write larger helper functions that an interviewer would typically allow to be abbreviated, like a disjoint-set).
• Add a simple test suite or driver code.

Past problems

11/07/2018

1. Longest path in DAG
2. BST to linked list
3. K smallest numbers in array

11/14/2018

1. Rotate array
2. Detect cycle in undirected graph
3. Roads and Libraries
4. New Year Chaos

11/21/2018

1. Bouquet of flowers
2. First missing positive
3. Median of two sorted arrays

11/28/2018

1. Find the duplicate number
2. N-th Fibonacci Number
3. Shortest Supersequence
4. Design a spreadsheet

12/05/2018

1. Collect maximum points in a grid using two traversals (similar: Cherry Pickup)
2. Largest time for given digits
3. Reveal cards in increasing order
4. Flip equivalent binary trees
5. Design an elevator
6. Given a sequence of points where consecutive points are connected by line segments to make a path, return the point along the path that corresponds to a given percentage along the path.

12/12/2018

1. Longest file path
2. Write the most efficient data structure that stores the last N records of orders to a company that supports two operations: (1) Return the record for the ith last order and (2) add a new record for a new order.
3. Write a post-order traversal of a binary tree using iteration
4. Concurrent sum
5. Force order in concurrency (Similar)
6. Select a random number from a stream with O(1) space
7. Find missing number in an array of N-1 elements where number from 1 to N is missing. (Similar)
8. CTCI 17.24, Max Submatrix: Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum. Variant: submatrix is not necessarily square.

12/19/2018

1. Dependency resolution (Similar to CTCI 4.7)
2. CTCI 2.5: Add two numbers stored in linked lists
3. CTCI 2.3: Delete a node in the middle of a singly linked list, given only access to that node
4. Regions cut by slashes

12/26/2018

1. Generate all binary strings of length n with k bits set
2. Print all paths from top left to bottom right of an n by m matrix moving only right and down
3. 2-sum, 3-sum, 4-sum and variants
4. Encode and decode strings

01/02/2019

1. CTCI 1.1: Is unique
2. CTCI 1.2: Check permutations
3. CTCI 1.3: URLify
4. CTCI 1.5: One away
5. CTCI 1.6: String compression
6. All possible full BSTs
7. Range sum of BST
8. Find itinerary (variant: return origin city)
9. LRU cache
10. CTCI 15.7: Multithreaded FizzBuzz

01/09/2019

1. CTCI 4.1: Routes between nodes
2. Save the Queen!
3. Balanced parenthesis
4. Combine fruits
5. Find and replace in string
6. Word break
7. Best time to buy and sell stock

01/16/2019

1. Decode String
2. Binary parse trees
3. Reverse Vowels in a String
4. Valid parenthesis string
5. Connected Cell in a Grid
6. Longest palindromic substring

01/23/2019

1. Valid Perfect Square
2. Product of Array Except Self
3. Almost Sorted
4. Find Peak Element
5. CTCI 8.14 Boolean Evaluation

1/30/2019

1. Larry's Array
2. Given a number k and an array of numbers, return an array of the k largest elements in the array in any order.
3. String without AAA or BBB
4. Shortest palindrome

2/6/2019

1. Find leftmost 1 in linear time in a matrix of 1 and 0 where each row is sorted ascending (all 0s are left of the 1s).
2. Write rand5() using only rand7()
3. House Robber
4. Largest Rectangle in Histogram
5. Remove nth node in linked list

2/13/2019

1. Return deepest node in a binary tree
2. Binary Search Tree Iterator
3. Roll a string
4. Hungry Rabbit in Garden of Carrots

2/20/2019

1. Median of binary search tree
2. Find a path from top left to bottom right of a matrix
3. Cousins in Binary Tree
4. Word Ladder
5. Sort floating point numbers by decimal portion of the number only
6. Perfectly Balanced (follow-up: with wildcards)

2/27/2019

1. Time complexity of the harmonic series

3/6/2019

1. Spiral Matrix
2. Rotting Oranges
3. Array Manipulation
4. Train of Dominoes
5. CTCI 16.14 Best Line

3/13/2019

1. CTCI 16.19 Pond Sizes
2. Score bowling
3. Split a common address into parts
4. Name matching

3/20/2019

1. CTCI 16.21 Sum Swap: Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.
2. Can you hop through an array of numbers from beginning to end? Each a[i] is the max potential step size. [1,2,0,1] => true, [2,1,0,1] => false.
3. Find a duplicate in an array containing numbers 1..N in O(n) time and O(1) space
4. Trapping Rain Water
5. Determine if a graph is a tree, and if it isn't, delete edges to make it into one.
6. Magic list: longest consecutive list of words made by changing one letter, given a word list and a start letter.
7. Make a bunch of separate API calls and return the results in an array.

3/27/2019

1. Partition array into three parts with equal sum
2. Valid Palindrome II
3. Find all anagrams of string b in string a in O(n) time and O(1) space.
4. Minimum size subarray sum

4/3/2019

1. Balanced binary tree
2. Invert binary tree
3. Longest common prefix
4. Cycle in linked list
5. Desert crossing

4/10/2019

1. Trapping Rain Water II
2. Repair HTML Brackets
3. Permutation Sequence
4. Basic Calculator II
5. Count vowels in all substrings of a string
6. Waffle Choppers

4/17/2019

1. Egg drop problem
2. maximum sum of any subsequence of non-adjacent numbers in array
3. Binary tree right side view
4. Online election

4/24/2019

1. Merge strings with common last and first word
2. Count primes between 1 and n (both exclusive).
3. Sort array of 0s, 1s and 2s in O(n)

5/1/2019

1. Code insertion sort.
2. Design and code Minesweeper.

5/8/2019

1. Implement a class that supports the following operations: addStr(str), containsPrefix(prefix), contains(str).
2. Grid illumination

5/15/2019

1. Break number into sum of decimal places, e.g. 5206 => "5000 + 200 + 6".
2. Merge two binary trees
3. Recover a tree from preorder traversal

5/22/2019

1. Remove all adjacent duplicates in string
2. Next greater node in linked list
3. Longest string chain
4. Longest duplicate substring

5/29/2019

1. Move Zeroes
2. Flipping an Image
3. Height Checker
4. Sum of Subarray Minimums
5. Explain how a web browser works.

6/5/2019

1. Sort int array according to sum of digits
2. Find length of longest increasing set of numbers anywhere in an array.
3. Given an array of positive and negative numbers, determine if the array can be partitioned into more than one subarray such that all subarrays have the same sum.
4. Number of Submatrices That Sum to Target

6/12/2019

1. Merge intervals
2. Reverse a linked list in place

6/19/2019

1. Find all anagrams of a word in a list of words.
2. Counting Bits
3. Shortest Common Supersequence
4. Given a scrabble tray of letters (possibly containing duplicates) and an unordered valid word list array ("dictionary"), how many words in the dictionary can be formed using some or all words in the scrabble tray?
5. What happens when you type google.com into a browser and press enter?

6/26/2019

1. Insert interval
2. Intersection of two lists
3. Two sum variant where sum should be as close to a target value but not more, e.g. [1,4,6,8], target = 12 returns [4, 6].
4. Fix an almost-correct BST by swapping two nodes
5. Perfectly balanced strings (follow up: any letters of the alphabet may be present)

7/3/2019

1. Distribute candies to people
2. Create an in-memory transactional database like Redis (log(n) lookup times). Ops include save [key] [val], get [key], begin xact, commit, rollback.
3. Write map/filter/reduce functions from scratch.

7/10/2019

1. Maximum width of binary tree

2. Given an array of candidates and vote times [["a", 1], ["b", 2]] and a time t, return the candidate who won the most votes at that time.

3. Find the point where the most intervals overlap

   • variant 1: find the best range given as a paramater
   • variant 2: compress the data for sequential hours like RLE
   • variant 3: Array Manipulation

4. Design a blackjack game

5. Explain HTTP

10/20/2019

1. Brick Wall
2. Minimum Cost Tree From Leaf Values
3. All Possible Full Binary Trees
4. Interleaving String
5. Remove K Digits