A collection of solutions to questions asked during the coding portion of an interview. Just trying to keep this particular set of skills fresh.
partial_products.go
Asked by Uber
Given a list of integers [1, 2, 3, 4], produce a set of partial products such that each index contains the product of the set, sans the current index.
Restrictions
- You cannot use division
- Solution must be O(n)
Example Input: [1, 2, 3, 4] Output: [24, 12, 8, 6]
topo_hydro_volume.go
Asked by Google
You're given a list of integers that represent the topology of an island; find the total volume of water your island can hold.
Example Input: [1, 3, 5, 1, 7, 2, 3, 6] Output: 11
+ +--+
7| | | +--+
| | | | |
6| | | | |
| | | | |
5| +--+ | | | |
| | | | | | |
4| | | | | | |
| | | | | +--+ |
3| +--+ | | | | | |
| | | | | | | | |
2| | | | | +--+ | |
| | | | | | | | |
1+-+ | +--+ | | | |
| | | | | | | | |
0| | | | | | | | |
+------|--|--|--|--|--|--|--|--+
|0 1 2 3 4 5 6 7
+
numeric_compliment.go
Asked by Twitch
Find all numeric compliments in a list.
Example Input: [2, 1, 3, -2, -1, 2] Output: [2, 1]
stock_prices.go
Asked by Interview Cake
You're given a list of integers, each value denoting the price of a stock, and each index the minute after stock opening. Determine the maximum amount of money that could have been made without shorting, meaning you must buy low and sell high.
Example Input: [10, 12, 8, 14, 13] Output: 6
interleave_queue_stack.go
Asked by Google
Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue.
Example Input: [1, 2, 3, 4, 5] Output: [1, 5, 2, 4, 3]
serialize_tree.go
Asked by Google
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
maze.go
Asked by Google
You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.
Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.
Example [[f, f, f, f], [t, t, f, t], [f, f, f, f], [f, f, f, f]]
and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.
remove_kth_element.go
Asked by Google
Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.
The list is very long, so making more than one pass is prohibitively expensive.
Do this in constant space and in one pass.
balancing_braces.go
Asked by Facebook
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string "([])", you should return true.
Given the string "([)]" or "((()", you should return false.