Algorithm Practice - 1/26/2019

Posted on | Edited on | In | Comments: | Views: | Views:
  1. Radar Detection
  2. Number of Boomerangs
  3. Multi-keyword Sort

1. Radar Detection

There is a bunch of radars on a 2D plane(Radar has x, y coordinates, and a radius r which is the range can be detected). Now, there is a car that passes through the range of y = 0 and y = 1 and cannot be detected by the radar. If the car is detected, return YES, otherwise NO.(You can consider that the car is a line segment of length 1 and goes straight from x = 0 to the right)

Solution:
Find out the minimum distance between the car and coordinates, which is y of coordinates. Then compare the distance and radius.

O(n) 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

"""
Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
"""

class Solution:
    """
    @param coordinates: The radars' coordinate
    @param radius: Detection radius of radars
    @return: The car was detected or not
    """
    def radarDetection(self, coordinates, radius):
        # Write your code here
        for i in range(len(coordinates)):
            dis = abs(coordinates[i].y)
            r = radius[i]
            if dis <= r:
                return "YES" 
        return "NO"

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).

Example
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Solution: Make one point fixed and calculate all the distance and store the same ones in to dictionary. Then use combination to calculate how much in total.

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
25
26
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