Find Most Similar Places

MediumPython

Problem

Yelp wants to recommend places similar to a user-selected business. Given a collection of places, a target place ID, and a number k, return the IDs of the k most similar other places.

Each place is represented by a dictionary containing an id, a two-dimensional location, and a list of categories. Similarity is defined by the Jaccard index of the category sets: intersection_size / union_size. Higher Jaccard similarity ranks first. If two places have equal category similarity, the place with the smaller squared Euclidean distance from the target ranks first. If both values are equal, sort by place ID in lexicographic order.

Formal Specification

Implement find_similar_places(places, target_id, k), where places is a list of dictionaries and each location is [x, y]. Return a list of place ID strings. Exclude the target place itself. If fewer than k other places exist, return all available places.

Constraints

1 <= len(places) <= 10^5
1 <= k <= len(places)
Every place ID is unique and target_id exists
Each category list contains strings and may be empty
Coordinates are integers or finite floating-point values

Function Signature

def find_similar_places(places, target_id, k):

Yelp wants to recommend places similar to a user-selected business. Given a collection of places, a target place ID, and a number k, return the IDs of the k most similar other places.