C code. C code run. Run code run… please!
This little blog is served on Google Cloud. Since the last day of October, it was stopped by my mistake and I cannot restart the service. Google Cloud always complains: Operation type [start] failed with message “The zone ‘projects/???/zones/us-west2-b’ does … Read More »
This question is available on both Leetcode (No. 270) and Lintcode (No. 901). The question is not too hard, if we do not chase the best time complexity. For example, we can traversal all the nodes and book-keep the closest … Read More »
Months ago, I coded a tiny crawler to monitor some electronics deals. I extracted a list of my target products from the homepage, and on each product page tried to add it to my cart. Basically I need to: Check … Read More »
Security is always one of the top concerns about websites, including WordPress. And login security is the foundation of many other security features, and usually the first line of defense. Aside from using vulnerabilities in WordPress, a less-skilled but much … Read More »
Question: https://codility.com/demo/take-sample-test/rectangle_builder_greater_area/ Question Name: Rectangle-Builder-Greater-Area or RectangleBuilderGreaterArea This key is the binary search.
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 | def solution(A, X): fence_count = {} for fence in A: fence_count[fence] = fence_count.get(fence, 0) + 1 num_of_pens = 0 usable_fences = [] for fence in fence_count: if fence_count[fence] < 2: # Less than one pair. We cannot use it. continue elif fence_count[fence] < 4: usable_fences.append(fence) else: usable_fences.append(fence) # We consider the square pen here. if fence * fence >= X: num_of_pens += 1 # We consider the non-square pen here. usable_fences.sort() candidate_size = len(usable_fences) for i in xrange(candidate_size): # Use binary search to find the first fence pair, that # could be used with current pair to form a pen. begin = i + 1 end = candidate_size - 1 while begin <= end: mid = (begin + end) // 2 if usable_fences[mid] * usable_fences[i] >= X: end = mid - 1 else: begin = mid + 1 # Now the usable_fences[end + 1] is the first qualified # fence. combination_num = candidate_size - (end + 1) num_of_pens += combination_num if num_of_pens > 1000000000: return -1 return num_of_pens |
Question: https://codility.com/demo/take-sample-test/dwarfs_rafting/ Question Name: Dwarfs-Rafting or DwarfsRafting Need some simple mathematical knowledge. The code is unnecessarily long. A 2-d array is better to write much shorter code. However, I keep the long version for better readability.
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 | def solution(N, S, T): quadrant_left_front = (N // 2) * (N // 2) quadrant_left_back = (N // 2) * (N // 2) quadrant_right_front = (N // 2) * (N // 2) quadrant_right_back = (N // 2) * (N // 2) boundary = N // 2 # Compute how many slots are available in each quadrant. for barrel in S.split(): # Adjust to 0-based index. row = int(barrel[:-1]) - 1 column = ord(barrel[-1]) - ord("A") if row < boundary: # The barrel is in the front. if column < boundary: # The barrel is in the left. quadrant_left_front -= 1 else: # The barrel is in the right. quadrant_right_front -= 1 else: # The barrel is in the back. if column < boundary: # The barrel is in the left. quadrant_left_back -= 1 else: # The barrel is in the right. quadrant_right_back -= 1 # lf is short for left front, etc. # To keep balance, we need: # 1. weight_lf + weight_lb = weight_rf + weight_rb # 2. weight_lf + weight_rf = weight_rf + weight_rb # Solve the equations and we can get the answer: # 1. weight_lf = weight_rb # 2. And weight_rf = weight_lb allowance_lf = min(quadrant_left_front, quadrant_right_back) allowance_rb = min(quadrant_left_front, quadrant_right_back) allowance_lb = min(quadrant_left_back, quadrant_right_front) allowance_rf = min(quadrant_left_back, quadrant_right_front) # Minus the seats, which are already occupied by dwarfs. for dwarf in T.split(): # Adjust to 0-based index. row = int(dwarf[:-1]) - 1 column = ord(dwarf[-1]) - ord("A") if row < boundary: # The dwarf is in the front. if column < boundary: # The dwarf is in the left. allowance_lf -= 1 if allowance_lf < 0: return -1 else: # The dwarf is in the right. allowance_rf -= 1 if allowance_rf < 0: return -1 else: # The dwarf is in the back. if column < boundary: # The dwarf is in the left. allowance_lb -= 1 if allowance_lb < 0: return -1 else: # The dwarf is in the right. allowance_rb -= 1 if allowance_rb < 0: return -1 return allowance_lf + allowance_rb + allowance_lb + allowance_rf |
Question: https://codility.com/programmers/lessons/90-tasks_from_indeed_prime_2015_challenge/slalom_skiing/ Question Name: Slalom-Skiing or SlalomSkiing This is a wonderful variant of longest increasing subsequence. Because the longest increasing subsequence is a very classic question withe O(NlogN) solution, the key point to solve this question is to covert its original form … Read More »
Question: https://codility.com/demo/take-sample-test/flood_depth/ Question Name: Flood-Depth or FloodDepth This is a variant of Trapping Rain Water by LeetCode. The undergoing concept is the same. However, the implementation is a bit different.
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 | from collections import namedtuple def solution(A): if len(A) < 3: return 0 # The blocks in the stack is in strictly height descending order. # For the first block in the stack, its max_depth is maximum water # depth of its (exclusive) left area. # The other blocks' max_depth is the maximum water depth between its # previous block in the stack and itself, both exclusive. Block = namedtuple("Block", ["height", "max_depth"]) stack = [Block(A[0],0)] for height in A[1:]: if height == stack[-1].height: # These two adjacent blocks have the same height. They act # totally the same in building any water container. continue elif height < stack[-1].height: stack.append(Block(height, 0)) else: max_depth = 0 # Let the current iterating block be C, the previous two # blocks in the stack be A and B. And their positions are # demoed as: # C # A C # A ... B ... C # while the blocks between A and B are omitted. So do the # blocks between B and C. # # The additional_depth consider the blocks A, B, and C only, # and igonres all the omitted blocks, such as: # C # A C # A B C (no block is between A and B, or B and C) # # HOWEVER, the additional_depth is not always the maximum # water depth between A and C, because there may be some # water between A and B, or B and C, as exists in the omitted # blocks. We need to adjust the additional_depth to get the # maximum water depth between A and C, both exclusive. while len(stack) > 1 and height > stack[-1].height: additional_depth = min(stack[-2].height, height) - \ stack[-1].height max_depth = max(max_depth, stack[-1].max_depth) + \ additional_depth stack.pop() # Combine leftward same-or-less-height blocks. These dropped # blocks are never going to be part of the remaining water # container. while len(stack) > 0 and height >= stack[-1].height: max_depth = max(max_depth, stack[-1].max_depth) stack.pop() stack.append(Block(height, max_depth)) overall_max_depth = 0 for block in stack: if block.max_depth > overall_max_depth: overall_max_depth = block.max_depth return overall_max_depth |
Question: https://codility.com/demo/take-sample-test/longest_password/ Question Name: Longest-Password or LongestPassword The solution could be more Pythonic with some additional space.
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 | def solution(S): longest = -1 num_of_letters = 0 num_of_digits = 0 num_of_others = 0 for letter in S: if letter.isalpha(): num_of_letters += 1 elif letter.isdigit(): num_of_digits += 1 elif letter == " ": # Check whether it's a valid password. if num_of_others == 0 and \ num_of_letters % 2 == 0 and \ num_of_digits % 2 == 1: if longest < num_of_letters + num_of_digits: longest = num_of_letters + num_of_digits # Reset the counters for the next word. num_of_letters = 0 num_of_digits = 0 num_of_others = 0 else: num_of_others += 1 # Check whether the last word is a valid password. if num_of_others == 0 and \ num_of_letters % 2 == 0 and \ num_of_digits % 2 == 1: if longest < num_of_letters + num_of_digits: longest = num_of_letters + num_of_digits return longest |
Question: https://codility.com/demo/take-sample-test/sql_sum/ Question Name: Sql-Sum or SqlSum This question is too easy to be a serious training lesson. Most likely, it’s a live test for SQL challenges on Codility.com. The following solution works in both PostgreSQL and SQLite.
1 | SELECT SUM(v) FROM elements |