- Repeated Substring Pattern
- Number of Boomerangs
- Multi-keyword Sort
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Solution: a. Find out all divisors - i of len(s)
b. Compare that if sub string * i and s are the same.
O(len(s) * i) time
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Solution: Use double loop. First one for a fixed point, second for a moving point. Then find out how many points have the same distance and save in count. At last, use permutation to count how many points together.
Given n students and their test scores, expressed as (student number, test scores), sort by test scores in descending order, if the test scores are the same, sort the student number in ascending order.
Solution: Use lambda, one sentence.