Algorithm Practice - 1/23/2019

Posted on | Edited on | In | Comments: | Views: | Views:
  1. Repeated Substring Pattern
  2. Number of Boomerangs
  3. Multi-keyword Sort

1. Repeated Substring Pattern

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    """
    @param s: a string
    @return: return a boolean
    """
    def repeatedsubStringPattern(self, s):
        n = len(s)
        for i in [x for x in range(2, n+1) if n % x == 0]:
            if s[: int(n/i)] * i == s:
                return True
        return False

2. Number of Boomerangs

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.

O(n^2) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param points: a 2D array
    @return: the number of boomerangs
    """
    def numberOfBoomerangs(self, points):
        # Write your code here
        count = 0
        for fixed in points:
            d = {}
            for moving in points:
                if fixed == moving:
                    continue
                distance = self.getDistance(fixed, moving)
                countofdistance = d.get(distance, 0)
                d[distance] = countofdistance + 1 
            for distance in d:
                count += d[distance] * (d[distance] - 1)
        
        return count 
                
    def getDistance(self, x, y):
        return (x[1] - y[1]) ** 2 + (x[0] - y[0]) ** 2

3. Multi-keyword Sort

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.

1
2
3
4
5
6
7
8
class Solution:
    """
    @param array: the input array
    @return: the sorted array
    """
    def multiSort(self, array):
        # Write your code here
        return sorted(array, key = lambda x : (-x[1], x[0]))