Skip to content

Instantly share code, notes, and snippets.

@jrusev
Last active November 16, 2016 15:36
Show Gist options
  • Save jrusev/1eeb4bc57ef72216b7268bfed6a2e8a4 to your computer and use it in GitHub Desktop.
Save jrusev/1eeb4bc57ef72216b7268bfed6a2e8a4 to your computer and use it in GitHub Desktop.

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment