Skip to content

Instantly share code, notes, and snippets.

@kn0ch3n

kn0ch3n/Five-problems

Created May 8, 2015 16:04
Show Gist options
  • Save kn0ch3n/f21315e462f72e3d458b to your computer and use it in GitHub Desktop.
Save kn0ch3n/f21315e462f72e3d458b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Five-problems
{
"metadata": {
"name": "",
"signature": "sha256:3889b568d4c64c981644c595418fd02cb1cef5f6f0b20c4279a9d722fb0542f7"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"See https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem 1\n",
"Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def sum_for(nums):\n",
" sum = 0\n",
" for n in nums:\n",
" sum += n\n",
" \n",
" return sum\n",
"\n",
"def sum_while(nums):\n",
" sum = i = 0\n",
" while i < len(nums):\n",
" sum += nums[i]\n",
" i += 1\n",
" \n",
" return sum\n",
"\n",
"def sum_rec(nums):\n",
" if len(nums) is 0:\n",
" return 0\n",
" \n",
" return nums[0] + sum_rec(nums[1:])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 16
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"nums = [1, 2, 3]\n",
"\n",
"print(sum_for(nums))\n",
"print(sum_while(nums))\n",
"print(sum_rec(nums))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n",
"6\n",
"6\n"
]
}
],
"prompt_number": 17
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem 2\n",
"Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3]."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def combine(l1, l2):\n",
" return [item for pair in zip(l1, l2) for item in pair]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"l1 = [1, 2, 3]\n",
"l2 = [4, 5, 6]\n",
"\n",
"print(combine(l1, l2))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[1, 4, 2, 5, 3, 6]\n"
]
}
],
"prompt_number": 36
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem 3\n",
"Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def fibo(n):\n",
" f = fibo_gen()\n",
" return [next(f) for _ in range(n)]\n",
"\n",
"def fibo_gen():\n",
" a, b = 0, 1\n",
" yield a\n",
" yield b\n",
" while True:\n",
" yield a + b\n",
" a, b = b, a + b"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 59
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"fibo(100)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 61,
"text": [
"[0,\n",
" 1,\n",
" 1,\n",
" 2,\n",
" 3,\n",
" 5,\n",
" 8,\n",
" 13,\n",
" 21,\n",
" 34,\n",
" 55,\n",
" 89,\n",
" 144,\n",
" 233,\n",
" 377,\n",
" 610,\n",
" 987,\n",
" 1597,\n",
" 2584,\n",
" 4181,\n",
" 6765,\n",
" 10946,\n",
" 17711,\n",
" 28657,\n",
" 46368,\n",
" 75025,\n",
" 121393,\n",
" 196418,\n",
" 317811,\n",
" 514229,\n",
" 832040,\n",
" 1346269,\n",
" 2178309,\n",
" 3524578,\n",
" 5702887,\n",
" 9227465,\n",
" 14930352,\n",
" 24157817,\n",
" 39088169,\n",
" 63245986,\n",
" 102334155,\n",
" 165580141,\n",
" 267914296,\n",
" 433494437,\n",
" 701408733,\n",
" 1134903170,\n",
" 1836311903,\n",
" 2971215073,\n",
" 4807526976,\n",
" 7778742049,\n",
" 12586269025,\n",
" 20365011074,\n",
" 32951280099,\n",
" 53316291173,\n",
" 86267571272,\n",
" 139583862445,\n",
" 225851433717,\n",
" 365435296162,\n",
" 591286729879,\n",
" 956722026041,\n",
" 1548008755920,\n",
" 2504730781961,\n",
" 4052739537881,\n",
" 6557470319842,\n",
" 10610209857723,\n",
" 17167680177565,\n",
" 27777890035288,\n",
" 44945570212853,\n",
" 72723460248141,\n",
" 117669030460994,\n",
" 190392490709135,\n",
" 308061521170129,\n",
" 498454011879264,\n",
" 806515533049393,\n",
" 1304969544928657,\n",
" 2111485077978050,\n",
" 3416454622906707,\n",
" 5527939700884757,\n",
" 8944394323791464,\n",
" 14472334024676221,\n",
" 23416728348467685,\n",
" 37889062373143906,\n",
" 61305790721611591,\n",
" 99194853094755497,\n",
" 160500643816367088,\n",
" 259695496911122585,\n",
" 420196140727489673,\n",
" 679891637638612258,\n",
" 1100087778366101931,\n",
" 1779979416004714189,\n",
" 2880067194370816120,\n",
" 4660046610375530309,\n",
" 7540113804746346429,\n",
" 12200160415121876738,\n",
" 19740274219868223167,\n",
" 31940434634990099905,\n",
" 51680708854858323072,\n",
" 83621143489848422977,\n",
" 135301852344706746049,\n",
" 218922995834555169026]"
]
}
],
"prompt_number": 61
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem 4\n",
"Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def largest_from(nums):\n",
" from functools import cmp_to_key, reduce\n",
" def compare(x, y):\n",
" if x == y:\n",
" return 0\n",
" sx, sy = str(x), str(y) # string representations for doing stuff\n",
" l = min(len(sx), len(sy)) # numer of digits that both numbers have\n",
" \n",
" # compare the number of digits that are in both numbers\n",
" for i in range(l): \n",
" if(sx[i] < sy[i]):\n",
" return 1\n",
" if(sx[i] > sy[i]):\n",
" return -1\n",
" \n",
" # if all digits match, compare the next digit in the bigger number to the first digit in the smaller number\n",
" # TODO: make sure all return values are right\n",
" if x > y:\n",
" if sx[l] > sy[0]:\n",
" return -1\n",
" if sx[l] < sy[0]:\n",
" return 1\n",
" if y > x:\n",
" if sy[l] > sx[0]:\n",
" return 1\n",
" if sy[l] < sx[0]:\n",
" return -1\n",
" \n",
" sorted_nums = sorted(nums, key=cmp_to_key(compare))\n",
" return reduce(lambda l, r: l + str(r), sorted_nums, \"\")\n"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 122
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(largest_from([50, 2, 1, 9]))\n",
"print(largest_from([4, 50, 5]))\n",
"print(largest_from([4, 56, 5]))\n",
"print(largest_from([4, 40, 5]))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"95021\n",
"5504\n",
"5654\n",
"5440\n"
]
}
],
"prompt_number": 123
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem 5\n",
"Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 \u2013 5 + 67 \u2013 8 + 9 = 100."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from itertools import product\n",
"values = list(map(str, range(1, 9)))\n",
"for p in product(['', ' + ', ' - '], repeat=8):\n",
" sumText = reduce(lambda l, r: l + r[0] + r[1], zip(values, p), '') + '9'\n",
" if eval(sumText) == 100:\n",
" print(sumText)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"123 + 45 - 67 + 8 - 9\n",
"123 + 4 - 5 + 67 - 89\n",
"123 - 45 - 67 + 89\n",
"123 - 4 - 5 - 6 - 7 + 8 - 9\n",
"12 + 3 + 4 + 5 - 6 - 7 + 89\n",
"12 + 3 - 4 + 5 + 67 + 8 + 9\n",
"12 - 3 - 4 + 5 - 6 + 7 + 89"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"1 + 23 - 4 + 56 + 7 + 8 + 9\n",
"1 + 23 - 4 + 5 + 6 + 78 - 9\n",
"1 + 2 + 34 - 5 + 67 - 8 + 9\n",
"1 + 2 + 3 - 4 + 5 + 6 + 78 + 9"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 184
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment