Instantly share code, notes, and snippets.

# jrusev/coding_problems.md Last active Nov 16, 2016

tests

### Problem 1. Ransom Note

A kidnapper wishes to write a ransom note using letters from a magazine. Given the ransom note and the magazine, find if the kidnapper can write the note by cutting letters out of the magazine.

### Problem 2. Brackets

Write a function that takes a string and checks if all square `[]` round `()` and curly `{}` brackets are properly paired and legally nested.

### Problem 3. Maximum Subarray

Given a sequence of integers, find the maximum possible sum of a contiguous subsequence. An empty sequence is considered to have the sum of 0.

For example, given the array `[-2,1,-3,4,-1,2,1,-5,4]`, the contiguous subarray `[4,-1,2,1]` has the largest sum of 6.

### Problem 4. Word Chains

A word chain is a sequence of words such that each word differs by only one letter from the words directly before and after it. The difference can be either an insertion, a deletion, or a substitution. Here is an example word chain:

``````cat -> cot -> coat -> oat -> hat -> hot -> hog -> dog
``````

Write a function which checks if a set of words can be arranged into one continuous word chain.

Examle input:

``````{'hog', 'hot', 'hat', 'dog', 'oat'} # True
``````

### Problem 5. Array 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.

``````[4, 3, 5, -1] and [3, 6, 4, 2] => [4, 6] # swap 4 and 6
``````

### Problem 6. Subsort

Given an unsorted array, find the minimum subarray such that sorting this subarray makes the whole array sorted. Return the start and end index of the subarray.

``````[0, 1, 15, 25, 6, 7, 30, 40, 50] => [2, 5] # sort [15, 25, 6, 7]
[10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60] => [3, 8] # sort [30, 25, 40, 32, 31, 35]
``````

### Problem 7. Word Break

Given a string `s` and a dictionary of words, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

``````'catsanddog', ['cat','at','cats','a','an','and','sand','dog'] => ['cat sand dog', 'cats and dog']
``````

### Problem 8. Stack of Boxes

You have a stack of boxes. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height and depth. Find the height of the tallest possible stack (the sum of the heights of each box in the stack).

``````# [width, height, depth]
[3, 4, 1], [8, 6, 2], [7, 8, 3] => 12 (8 + 4)
[6, 4, 4], [8, 6, 2], [5, 3, 3], [7, 8, 3], [4, 2, 2], [9, 7, 3] => 13 (7 + 6)
``````

### Problem 9. Missing Two

You are given an array with all the numbers from 1 to N appearing exactly once, except for one number that is missing. How can you find the missing number in O(N) time and O(1) space? What if there were two numbers missing?

### Problem 10. Word Rectangle

Given a list of millions of words, design an algorithm to create the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). The words need not be chosen consecutively from the list, but all rows must be the same length and all columns must be the same height. This is an example of a word rectangle:

``````S A W
A R E
M E N
E A T
``````