/interview

Interview Q&A to keep my skills sharp

Primary LanguageGoMIT LicenseMIT

About

A collection of solutions to questions asked during the coding portion of an interview. Just trying to keep this particular set of skills fresh.

Questions

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

  1. You cannot use division
  2. 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.