{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Codility Sample Tasks\n", "\n", "What follows are my solutions to [Codility](https://codility.com) sample tasks. I did lots of both serious and stupid mistakes getting to decent solutions and my first submits were just sad. For the first one I forgot to return $-1$ in the case where there is no equilibrium index. For the second, this one took me the longest, I had forgotten I had to uncount repeated cases and returned the exception case way too early. I also did not know how to run binary searches using Python (at least now I know.) For the third, the easiest of them all, I was using a list instead of a dictionary as a checked bag and thus spending too much time asking if an element had been checked already while iterating over the list.\n", "\n", "I felt that the expected complexity requirements for each problem end up giving up too much information about the nature of the solutions.\n", "\n", "**Note**: Initially I only had the solution for three problems. I've continued practicing and I'll be adding solutions here as I go over each problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Equilibrium index \n", "\n", "A zero-indexed array $A$ consisting of $N$ integers is given. An _equilibrium index_ of this array is any integer $P$ such that $0 \\leq P < N$ and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e. $$A[0] + A[1] + \\cdots + A[P\u22121] = A[P+1] + \\cdots + A[N\u22122] + A[N\u22121].$$\n", "\n", "Sum of zero elements is assumed to be equal to $0$. This can happen if $P = 0$ or if $P = N\u22121$.\n", "\n", "Write a function `def solution(A)` that, given a zero-indexed array $A$ consisting of $N$ integers, returns any of its equilibrium indices. The function should return $\u22121$ if no equilibrium index exists.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(A):\n", " uppersum = sum(A)\n", " lowersum = 0\n", " term = 0\n", " for i, x in enumerate(A): \n", " lowersum += term\n", " term = x\n", " uppersum -= term\n", " if lowersum == uppersum:\n", " return i\n", " return -1" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 27 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Intersecting discs\n", "\n", "Given an array $A$ of $N$ integers, we draw $N$ discs in a 2D plane such that the $I$-th disc is centered on $(0,I)$ and has a radius of $A[I]$. We say that the $J$-th disc and $K$-th disc intersect if $J \\neq K$ and $J$-th and $K$-th discs have at least one common point.\n", "\n", "Write a function `def solution(A)` that, given an array $A$ describing $N$ discs as explained above, returns the number of pairs of intersecting discs. \n", "\n", "The function should return $\u22121$ if the number of intersecting pairs exceeds $10^7$.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N*log(N))$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "from bisect import bisect_right\n", "\n", "def solution(A):\n", " n = len(A)\n", " upper = sorted([i + x for i, x in enumerate(A)])\n", " lower = sorted([i - x for i, x in enumerate(A)])\n", " counter = 0\n", " for v in upper:\n", " counter += bisect_right(lower, v)\n", " counter -= n * (n + 1) / 2\n", " if counter > 1e7:\n", " return -1\n", " return counter " ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 32 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. First covering index\n", "\n", "A non-empty zero-indexed array $A$ consisting of $N$ integers is given. The _first covering prefix_ of array $A$ is the smallest integer $P$ such that $0 \\leq P < N$ and such that every value that occurs in array $A$ also occurs in sequence $A[0], A[1], \\ldots, A[P]$.\n", "\n", "Write a function `def solution(A)` that, given a zero-indexed non-empty array $A$ consisting of $N$ integers, returns the first covering prefix of $A$.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(A):\n", " checked = {}\n", " r = 0\n", " for i, x in enumerate(A):\n", " if not x in checked:\n", " checked[x] = True\n", " r = i\n", " return r" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 72 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Binary gap\n", "\n", "A _binary gap_ within a positive integer $N$ is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of $N$.\n", "\n", "Write a function `def solution(N)` that, given a positive integer $N$, returns the length of its longest binary gap. The function should return $0$ if $N$ doesn't contain a binary gap." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(N):\n", " zeros = bin(N)[2:].split('1')\n", " zeros = zeros[:-1] # Just in case there are trailing zeros\n", " return max(map(len, zeros))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 87 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Frog jumping \n", "\n", "A small frog wants to get to the other side of the road. The frog is currently located at position $X$ and wants to get to a position greater than or equal to $Y$. The small frog always jumps a fixed distance, $D$. Count the minimal number of jumps that the small frog must perform to reach its target.\n", "\n", "Write a function `def solution(X, Y, D)` that, given three integers $X$, $Y$ and $D$, returns the minimal number of jumps from position $X$ to a position equal to or greater than $Y$.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(1)$;\n", "* expected worst-case space complexity is $O(1)$." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# This one is silly:\n", "def solution(X, Y, D):\n", " distance = Y - X\n", " if distance % D == 0:\n", " return (Y - X) / D\n", " else:\n", " return ((Y - X) / D) + 1 # Abussing Python's broken division." ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 88 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. Missing element\n", "\n", "A zero-indexed array $A$ consisting of $N$ different integers is given. The array contains integers in the range $[1\\ldots(N + 1)]$, which means that exactly one element is missing.\n", "\n", "Your goal is to find that missing element.\n", "\n", "Write a function `def solution(A)` that, given a zero-indexed array $A$, returns the value of the missing element.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(1)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(A):\n", " A = sorted(A) # The complexity is O(N log(N)), unfortunately. But Codility wasn't able to tell. \n", " for i in range(len(A)):\n", " if A[i] != i + 1:\n", " return i + 1\n", " return len(A) + 1" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 89 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 7. Permutation checking\n", "\n", "A non-empty zero-indexed array $A$ consisting of $N$ integers is given.\n", "\n", "A permutation is a sequence containing each element from $1$ to $N$ once, and only once.\n", "\n", "The goal is to check whether array $A$ is a permutation.\n", "\n", "Write a function `def solution(A)` that, given a zero-indexed array $A$, returns $1$ if array $A$ is a permutation and $0$ if it is not.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(A):\n", " n = len(A)\n", " check = {i+1:False for i in xrange(n)}\n", " for x in A:\n", " if x not in check:\n", " return 0\n", " else:\n", " if check[x] == True:\n", " return 0\n", " else:\n", " check[x] = True\n", " for x in check:\n", " if check[x] == False:\n", " return 0\n", " return 1" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8. Distinct\n", "\n", "Write a function `def solution(A)` that, given a zero-indexed array $A$ consisting of $N$ integers, returns the number of distinct values in array $A$.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N*log(N))$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Minimal solution \n", "# A detailed version would require ordering the array \n", "# and run over it while counting the times the value changes.\n", "# (Which I guess is more or less the way Python turns a list into a set.)\n", "def solution(A):\n", " return len(set(A))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 5 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 9. Nesting\n", "\n", "A string $S$ consisting of $N$ characters is called properly nested if:\n", "\n", "* $S$ is empty;\n", "* $S$ has the form $(U)$ where $U$ is a properly nested string;\n", "* $S$ has the form $VW$ where $V$ and $W$ are properly nested strings.\n", "\n", "Write a function `def solution(S)` that, given a string $S$ consisting of $N$ characters, returns $1$ if string $S$ is properly nested and $0$ otherwise.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(1)$ (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def solution(S):\n", " stack = 0\n", " for x in S:\n", " if x == '(':\n", " stack += 1\n", " if x == ')':\n", " stack -= 1\n", " if stack < 0:\n", " return 0\n", " if stack == 0:\n", " return 1\n", " else:\n", " return 0" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 10. Fish\n", "\n", "You are given two non-empty zero-indexed arrays $A$ and $B$ consisting of $N$ integers. Arrays $A$ and $B$ represent $N$ voracious fish in a river, ordered downstream along the flow of the river.\n", "\n", "The fish are numbered from $0$ to $N \u2212 1$. If $P$ and $Q$ are two fish and $P < Q$, then fish $P$ is initially upstream of fish $Q$. Initially, each fish has a unique position.\n", "\n", "Fish number $P$ is represented by $A[P]$ and $B[P]$. Array $A$ contains the sizes of the fish. All its elements are unique. Array $B$ contains the directions of the fish. It contains only $0$s and/or $1$s, where:\n", "\n", "* $0$ represents a fish flowing upstream,\n", "* $1$ represents a fish flowing downstream.\n", "\n", "If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive \u2212 the larger fish eats the smaller one. More precisely, we say that two fish $P$ and $Q$ meet each other when $P < Q$, $B[P] = 1$ and $B[Q] = 0$, and there are no living fish between them. After they meet:\n", "\n", "* If $A[P] > A[Q]$ then $P$ eats $Q$, and $P$ will still be flowing downstream,\n", "* If $A[Q] > A[P]$ then $Q$ eats $P$, and $Q$ will still be flowing upstream.\n", "\n", "We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.\n", "\n", "Write a function `def solution(A, B)` that, given two non-empty zero-indexed arrays $A$ and $B$ consisting of $N$ integers, returns the number of fish that will stay alive.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is $O(N)$;\n", "* expected worst-case space complexity is $O(N)$, beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# First time I got 100% with my first submit.\n", "def solution(A, B):\n", " fish_downstream = []\n", " up_survivors = 0\n", " for i, direction in enumerate(B):\n", " if direction == 1:\n", " fish_downstream.append(A[i])\n", " else: \n", " is_active = 1\n", " up = A[i]\n", " while is_active:\n", " if len(fish_downstream) != 0:\n", " down = fish_downstream.pop()\n", " if down > up:\n", " fish_downstream.append(down)\n", " is_active = 0\n", " else:\n", " is_active = 0\n", " up_survivors += 1\n", " return len(fish_downstream) + up_survivors" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 8 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 11. Ladder\n", "\n", "You have to climb up a ladder. The ladder has exactly $N$ rungs, numbered from $1$ to $N$. With each step, you can ascend by one or two rungs. More precisely: \n", "\n", "* with your first step you can stand on rung $1$ or $2$,\n", "* if you are on rung K, you can move to rungs $K + 1$ or $K + 2$,\n", "* finally you have to stand on rung $N$.\n", "\n", "Your task is to count the number of different ways of climbing to the top of the ladder.\n", "\n", "Write a function `def solution(A, B)` that, given two non-empty zero-indexed arrays $A$ and $B$ of $L$ integers, returns an array consisting of $L$ integers specifying the consecutive answers; position $I$ should contain the number of different ways of climbing the ladder with $A[I]$ rungs modulo $2^{B[I]}$.\n", "\n", "**Complexity:**\n", "\n", "* expected worst-case time complexity is O(L);\n", "* expected worst-case space complexity is O(L), beyond input storage (not counting the storage required for input arguments)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def count_down(n, dicc):\n", " for m in [1,2]:\n", " if n-m in dicc:\n", " dicc[n] = dicc.get(n,0)+dicc[n-m] \n", " return dicc\n", "\n", "def climbing_ways_counter(L):\n", " dicc = {0:1}\n", " for n in xrange(L):\n", " count_down(n,dicc)\n", " return dicc\n", "\n", "def solution(A, B):\n", " L = len(A) + 1\n", " # Weird optimization trick. Modulo operation is too slow...\n", " # Had to look up online for it:\n", " B = [(1<