Skip to content

Instantly share code, notes, and snippets.

@jrusev
Last active January 24, 2018 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jrusev/408dfa0f0d8abd0f132e6173d7aaec3a to your computer and use it in GitHub Desktop.
Save jrusev/408dfa0f0d8abd0f132e6173d7aaec3a to your computer and use it in GitHub Desktop.

problems

Problem 1. Ransom note

'one sentence from a magazine', 'ransom note' => True
'one payment', 'pay money' => False
'downpayment', 'pay now' => True

stdin

3
one sentence from a magazine
ransom note
one payment
pay money
downpayment
pay now

Problem 2. Brackets

"This string has no brackets." => True
"(fn [f s] (reduce #(merge-with concat % {(f %2) [%2]}) {} s))" => True
"(start, end]" => False
"())" => False
"[ { ] } " => False
"([]([(()){()}(()(()))(([[]]({}()))())]((((()()))))))" => True
"([]([(()){()}(()(()))(([[]]({}([)))())]((((()()))))))" => False
"[" => False

stdin

8
This string has no brackets.
(fn [f s] (reduce #(merge-with concat % {(f %2) [%2]}) {} s))
(start, end]
())
[ { ] } 
([]([(()){()}(()(()))(([[]]({}()))())]((((()()))))))
([]([(()){()}(()(()))(([[]]({}([)))())]((((()()))))))
[

Problem 3. Maximum Subarray

[-2, 1, -3, 4, -1, 2, 1, -5, 4] => 6 (4, -1, 2, 1)
[2, 3, -6, -1, 2, -1, 6, 4, -8, 8] => 11 (2, -1, 6, 4)
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1] => 15 (3, 5, 6, -2, -1, 4)
[-1, -2, -3, -4, -5] => 0
[] => 0
[7, -6, -8, 5, -2, -6, 7, 4, 8, -9, -3, 2, 6, -4, -6] => 19 (7, 4, 8)
[0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] => 3 (0, 1, 2)
[1, 2, 3, 4, 5, -8, -9, -20, 40, 25, -5] => 65 (40, 25)

stdin

7
-2 1 -3 4 -1 2 1 -5 4
2 3 -6 -1 2 -1 6 4 -8 8
-1 -2 3 5 6 -2 -1 4 -4 2 -1
-1 -2 -3 -4 -5
7 -6 -8 5 -2 -6 7 4 8 -9 -3 2 6 -4 -6
0 1 2 -3 3 -1 0 -4 0 -1 -4 2
1 2 3 4 5 -8 -9 -20 40 25 -5

Problem 4. Word Chains

['hat', 'coat', 'dog', 'cat', 'oat', 'cot', 'hot', 'hog'] => True
['hog', 'hot', 'hat', 'dog', 'oat'] => True
['cot', 'hot', 'bat', 'fat'] => False
['to', 'top', 'stop', 'tops', 'toss'] => False
['spout', 'do', 'pot', 'pout', 'spot', 'dot'] => True
['share', 'hares', 'shares', 'hare', 'are'] => True
['share', 'hares', 'hare', 'are'] => False

stdin

7
hat coat dog cat oat cot hot hog
hog hot hat dog oat
cot hot bat fat
to top stop tops toss
spout do pot pout spot dot
share hares shares hare are
share hares hare are

Problem 5. Array Swap

[4, 3, 5, -1], [3, 6, 4, 2] => [4, 6]
[4, 1, 5], [9, 3, 2] => [1, 3]
[4, 3, 4], [5, 10] => [3, 5]
[5, 10], [4, 3, 4] => [5, 3]
[-1, 3, 9], [14, 1] => [-1, 1]
[14, 1], [-1, 3, 9] => [1, -1]
[-4, -3, -4], [-5, -10] => [-3, -5]
[-5, -10], [-4, -3, -4] => [-5, -3]
[4, 3, 4], [5, 11] => []
[4, 3, 4], [3, 12] => []
[], [0] => []
[0], [] => []
[], [] => []

Problem 6. Subsort

[0, 1, 15, 25, 6, 7, 30, 40, 50] => [2, 5]
[10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60] => [3, 8]
[1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19] => [3, 9]
[1, 2, 4, 7, 10, 11, 8, 12, 5, 6, 16, 18, 19] => [3, 9]
[1, 2, 4, 7, 10, 17, 8, 11, 6, 9, 13, 18, 19] => [3, 10]
[1, 3, 4, 6, 10, 6, 16, 12, 13, 15, 16, 19, 20, 22, 25] => [4, 9]
[0, 1, 15, 25, 6, -1, 7, 30, 40, 50] => [0, 6]
[1, 3, 2] => [1, 2]
[2, 1, 3] => [0, 1]
[2, 1, 3, 4] => [0, 1]
[3, 2, 1, 4] => [0, 2]
[3, 1, 2, 4] => [0, 2]
[3, 2, 1, 4] => [0, 2]
[1, 3, 2, 4] => [1, 2]
[1, 2, 4, 3] => [2, 3]
[1, 3, 4, 2] => [1, 3]
[3, 2, 4, 1] => [0, 3]

Problem 7. Word Break

'applepie', ['apple','pie'] => ['apple pie']
'peanutbutter', ['pea','nut','peanut','but','butt','butter'] => ['pea nut butter', 'peanut butter']
'windowsteamblog', ['window','windows','steam','team','blog'] => ['window steam blog', 'windows team blog']
'catsanddog', ['cat','at','cats','a','an','and','sand','dog'] => ['cat sand dog', 'cats and dog']
'intowords', ['in','to','into'], []

Problem 8. Stack of Boxes

# Let the 2nd dimension be the height.
[[3, 4, 1], [8, 6, 2], [7, 8, 3]] => 8 + 4
[[6, 4, 4], [8, 6, 2], [5, 3, 3], [7, 8, 3], [4, 2, 2], [9, 7, 3]] => 7 + 6
[[6, 4, 4], [8, 6, 2], [5, 3, 3], [7, 8, 3], [4, 2, 2], [9, 7, 3], [7, 5, 1]] => 7 + 6 + 5

Problem 9. Missing Two

N = 2, arr = [] => 1, 2
N = 3, arr = [1] => 2, 3
N = 4, arr = [4, 2] => 1, 3
N = 5, arr = [2, 1, 4] => 3, 5
N = 9, arr = [9, 5, 4, 6, 3, 7, 8] => 1, 2
N = 9, arr = [4, 5, 7, 3, 6, 2, 8] => 1, 9
N = 9, arr = [6, 8, 7, 1, 4, 3, 9] => 2, 5
N = 9, arr = [6, 9, 7, 8, 2, 1, 5] => 3, 4
N = 9, arr = [2, 8, 7, 6, 1, 3, 5] => 4, 9
N = 9, arr = [8, 3, 7, 1, 2, 9, 4] => 5, 6
N = 9, arr = [3, 1, 2, 5, 4, 8, 9] => 6, 7
N = 9, arr = [1, 3, 4, 8, 6, 5, 2] => 7, 9
N = 9, arr = [5, 6, 1, 2, 3, 7, 4] => 8, 9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment