[Solution]Problem 78: Finding the Distance between 2 sets[Goldman Sachs]
Math, Problem Solving, Logic, Generation
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
Hey hey,
Sorry about the delay in the solution. Had a bunch of exams and submissions yesterday, which took up my attention.
Problem
Some terms for those of you that need them-
R^n is the n-dimensional space of real numbers. X and Y would be sets of n-d sets in that dimension.
|x| refers to the distance of the point x from the origin (a list of 0s n times). When the type of distance is not given, you can assume Euclidean Distance.
inf(D) is just the lower bound of D. In our case, you can just assume the lowest distance given the 2 sets. This is not always true, but that’s only a concern when you start getting into infinite sets etc.
Step 1: Understanding the Problem
This problem can be solved in many ways. If you were a data scientist, then you might consider monte-carlo simulations (problems like this are often used to introduce the concept). However, there is a much quicker way to solve this, which requires some degree of insight. And we gain this insight by studying this problem closely.
So what does mean? Let’s begin by first understanding what each of those sets represents-
X is defined as the set of points at a distance of lesser than or equal 2 from the origin.
Y will be the set of points that are between 3 and 4 units of distance away from the origin.
We are asked to find the minimum distance between 2 points in these sets.
This can seem a daunting task. Do you run through every point, and compare them? However, this will get expensive, especially when you remember that mathematically- these sets have an infinite number of points. So what can we do?
This is where we pull a trusty tool from our kit. One of the most powerful techniques in a programmers/engineer’s arsenal.
Step 2: Visualization
If you’re stuck on a problem, and unsure of what to do next, visualizing it can work wonders. We have a whole Technique Tuesday post dedicated to visualizations here.
This gives us another question - How do we visualize n-dimensional spaces? We are 3D creatures, so trying to imagine anything beyond that is physically impossible.
The solution is to rely on simple cases we can visualize. We know that we can imagine 2D and 3D spaces. So we can plot out what our sets would look like in 2D and 3D. This gives us the following representation of x and y and how they look in 2D-
I’ll let you flex your 3D art skills, but you will find that it looks very similar. In fact,you can generalize this representation to n dimensions. X will be a n-d ball of points closer than 2 units of distance, and Y will be slice of a ball, containing points between 3 and 4 units of distance. That being said, we can now move on to our quick solution.
Step 3: Computing the Minimum Distance
We know that X is an n-dim sphere of radius 2, centered at the origin.
Similarly, Y is an n-dim hollowed sphere of inner radius 3 and out radius 4 centered at the origin (except the points which are at distance 3 from the origin). Since both have the same center and are spheres the distance between the two sets is 3-2 =1
There. You don’t even need code to solve this. There are a few questions like this, which you can solve efficiently with problem-solving and a bit of math. Below is another example of such a question, although it requires a little bit more knowledge. Fair warning, I recorded this 2 years ago, so the recording quality isn’t great. Check it out if you’d like to test yourself out, and let me know how you do-
Time Complexity- O(1)
Space Complexity- O(1)
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Small Snippets about Tech, AI and Machine Learning over here
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd