C code. C code run. Run code run… please!
Question: https://codility.com/demo/take-sample-test/max_nonoverlapping_segments/ Question Name: Max-Nonoverlapping-Segments or MaxNonoverlappingSegments It is an easy solution, but a bit hard to prove it. Let’s scan from left to right, according to the end points. Since the input has already been sorted with the end … Read More »
Question: https://codility.com/demo/take-sample-test/delta2011 Question Name: Delta2011 or Min-Abs-Sum or MinAbsSum I did not solve it in a golden way. The official solution is so elegant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | def solution(A): # Since S could be 1 or -1, it does not matter that # each element in A is positive or negative. A = [abs(item) for item in A] sumOfA = sum(A) # Get the number distribution. So we do not need to try # each number for multiple times. numbers = {} for item in A: numbers[item] = numbers.get(item, 0) + 1 # This is the KEY point. # Typically, we will use possible = [False] * len to track, which numbers # could be the result by summing up subsets of A. # For a number, appeared for many times, there will be multiple attempts # for it. But in this way, when we are trying number n, # possible[i] == -1 means it is impossible. # possible[i] == i >= 0 means it is possible and there are i n(s) left to use. # So for ALL number n(s), we only need ONE scan over the record. possible = [-1] * (sumOfA // 2 + 1) possible[0] = 0 for number in numbers: # Try each distinct number for trying in xrange(sumOfA//2+1): if possible[trying] >= 0: # Can be reached with previous numbers possible[trying] = numbers[number] elif trying >= number and possible[trying-number] > 0: # Cannot be reached with only previous numbers. # But could be achieved with previous numbers AND current one. possible[trying] = possible[trying-number] - 1 # Divide the A into two parts: P and Q, with restriction P <= Q. # So P <= sumOfA // 2 <= Q. We want the largest possible P, so that # Q-P is minimized. for halfSum in xrange(sumOfA//2, -1, -1): if possible[halfSum] >= 0: return sumOfA - halfSum - halfSum raise Exception("Should never be here!") return 0 |
Question: https://codility.com/demo/take-sample-test/str_symmetry_point Question Name: Str-Symmetry-Point or StrSymmetryPoint
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def solution(S): sLen = len(S) # Symmetry point is possible, when and only when the # string's length is odd. if sLen % 2 == 0: return -1 # With a odd-length string, the only possible symmetry # point is the middle point. mid = sLen // 2 begin, end = 0, sLen-1 # The middle point of an odd-length string is symmetry # point, only when the string is symmetry. while begin < mid: if S[begin] != S[end]: return -1 begin += 1 end -= 1 return mid |
Question: https://codility.com/demo/take-sample-test/tie_ropes Question Name: Tie-Ropes or TieRopes
1 2 3 4 5 6 7 8 9 10 11 12 | def solution(K, A): # The number of tied ropes, whose lengths # are greater than or equal to K. count = 0 # The length of current rope (might be a tied one). length = 0 for rope in A: length += rope # Tied with the previous one. # Find a qualified rope. Prepare to find the # next one. if length >= K: count += 1; length = 0 return count |
Question: https://codility.com/demo/take-sample-test/count_factors Question Name: Count-Factors or CountFactors
1 2 3 4 5 6 7 8 9 10 | def solution(N): candidate = 1 result = 0 while candidate * candidate < N: # N has two factors: candidate and N // candidate if N % candidate == 0: result += 2 candidate += 1 # If N is square of some value. if candidate * candidate == N: result += 1 return result |
Question: https://codility.com/demo/take-sample-test/missing_integer Question Name: Missing-Integer or MissingInteger
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def solution(A): ''' Solve it with Pigeonhole principle. There are N integers in the input. So for the first N+1 positive integers, at least one of them must be missing. ''' # We only care about the first N+1 positive integers. # occurrence[i] is for the integer i+1. occurrence = [False] * (len(A) + 1) for item in A: if 1 <= item <= len(A) + 1: occurrence[item-1] = True # Find out the missing minimal positive integer. for index in xrange(len(A) + 1): if occurrence[index] == False: return index + 1 raise Exception("Should never be here.") return -1 |
Question: https://codility.com/demo/take-sample-test/wire_burnouts Question Name: psi2012 or Wire-Burnouts or WireBurnouts A good application of weighted quick union algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | class WeightedQuickUnion(object): ''' A class for weighted quick union data structure Details: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf ''' ID = None # ID[i] = component identifier of i weight = None # weight[i] = number of nodes in the subtree(component) # with i being the root def __init__(self, size): assert size > 0 # Each individual cell is a component self.ID = [i for i in xrange(size)] # Each component has only one item initially self.weight = [1 for i in xrange(size)] return def findRoot(self, cell): ''' Return the root of tree, to which cell belongs. That is, the component identifier of cell. ''' assert 0 <= cell < len(self.ID) while cell != self.ID[cell]: cell = self.ID[cell] return cell def isConnected(self, p, q): ''' Check whether p and q belong to same component/tree. ''' assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID) return self.findRoot(p) == self.findRoot(q) def union(self, p, q): ''' Merge the components (trees), to which p and q belong ''' assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID) rootP = self.findRoot(p) rootQ = self.findRoot(q) # Already the same component if rootP == rootQ: return if self.weight[rootP] >= self.weight[rootQ]: self.ID[rootQ] = rootP self.weight[rootP] += self.weight[rootQ] else: self.ID[rootP] = rootQ self.weight[rootQ] += self.weight[rootP] return class Grid(object): ''' A wrapper class of WeightedQuickUnion for the current grid ''' grid = None size = -1 def __init__(self, size): self.grid = WeightedQuickUnion(size*size) # This is a size * size grid self.size = size return def isConnected(self, x1, y1, x2, y2): ''' Check whether the nodes (x1, y1) and (x2, y2) in the grid is connected or not. ''' p = x1 * self.size + y1 q = x2 * self.size + y2 return self.grid.isConnected(p, q) def union(self, x1, y1, x2, y2): ''' Connect two nodes (x1, y1) and (x2, y2) in the grid ''' p = x1 * self.size + y1 q = x2 * self.size + y2 self.grid.union(p, q) return def solution(N, A, B, C): # Not enough burn out wires to stop the current from flowing if len(A) < N + N - 2: return -1 grid = Grid(N) # Get all the wires, which will burn out. removed = {} for index in xrange(len(A)): if C[index] == 0: removed[(A[index], B[index], A[index], B[index]+1)] = True else: removed[(A[index], B[index], A[index]+1, B[index])] = True # Add all the never-burn wires to the grid for x in xrange(N): for y in xrange(N): if y + 1 < N and not (x, y, x, y+1) in removed: grid.union(x, y, x, y+1) if x + 1 < N and not (x, y, x+1, y) in removed: grid.union(x, y, x+1, y) # Even if all the wires in A, B, and C burn out, the current is still flowing if grid.isConnected(0, 0, N-1, N-1): return -1 for index in xrange(len(A)-1, -1, -1): # Recovery one burn-out wire if C[index] == 0: grid.union(A[index], B[index], A[index], B[index]+1) else: grid.union(A[index], B[index], A[index]+1, B[index]) # After recovery, the current could flow. if grid.isConnected(0, 0, N-1, N-1): return index + 1 # Would never be here. return -1 |
Question: https://codility.com/demo/take-sample-test/min_abs_sum_of_two Question Name: Min-Abs-Sum-Of-Two or MinAbsSumOfTwo There are two O(nlogn) solutions for this question. Both solutions have the same overall time complexity and space complexity. And both solutions need to sort the array in non-decreasing order first. The first … Read More »
Question: https://codility.com/demo/take-sample-test/count_distinct_slices Question Name: Count-Distinct-Slices or CountDistinctSlices
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def solution(M, A): accessed = [-1] * (M + 1) # -1: not accessed before # Non-negative: the previous occurrence position front, back = 0, 0 result = 0 for front in xrange(len(A)): if accessed[A[front]] == -1: # Met with a new unique item accessed[A[front]] = front else: # Met with a duplicate item # Compute the number of distinct slices between newBack-1 and back # position. newBack = accessed[A[front]] + 1 result += (newBack - back) * (front - back + front - newBack + 1) / 2 if result >= 1000000000: return 1000000000 # Restore and set the accessed array for index in xrange(back, newBack): accessed[A[index]] = -1 accessed[A[front]] = front back = newBack # Process the last slices result += (front - back + 1) * (front - back + 2) / 2 return min(result, 1000000000) |
Question: https://codility.com/demo/take-sample-test/count_triangles Question Name: Count-Triangles or CountTriangles This problem is nearly the same as the exercise in presentation of lesson 13. Update on May 24, 2014: Thanks to @Adam. Fix a bug, which lower the performance.
1 2 3 4 5 6 7 8 9 10 11 | def solution(A): n = len(A) result = 0 A.sort() for first in xrange(n-2): third = first + 2 for second in xrange(first+1, n-1): while third < n and A[first] + A[second] > A[third]: third += 1 result += third - second - 1 return result |