Amazon Software Engineer vs. Binary Search! | Software Engineering Mock Interviews (
Вставка
- Опубліковано 14 лип 2024
- Visit Our Website: interviewpen.com/?...
Join Our Discord: / discord
Join Our Newsletter - The Blueprint: theblueprint.dev/subscribe
Like & Subscribe: / @interviewpen
Table of Contents:
0:00 - Problem Introduction
2:15 - Clarifying Assumptions
6:42 - Identifying the Brute Force
7:29 - Looking for a Better Solution
13:06 - Outlining Binary Search Solution
14:55 - Starting to Code
16:55 - Starting the Binary Search
23:30 - Choosing Search Direction
25:19 - Running the Code
25:55 - Debugging
30:52 - Clarifying the Search
37:45 - Working Solution
38:40 - Time & Space Analysis
40:42 - How Do You Think You Did?
42:50 - How Has This Compared To Other Interview Questions?
43:50 - Tips On Working with the Interviewer
45:35 - When To Code the Brute Force?
46:23 - Visit interviewpen.com
Erratum:
0:24 - The table exemplifies being exclusive on both bounds. I am mistaken when I mention us being inclusive on both bounds for the example.
(let us know of any errors & they will be added here)
Socials:
Twitter: / interviewpen
Twitter (The Blueprint): / theblueprintdev
LinkedIn: / inte. .
Website: interviewpen.com/?...
We'd recommend you play these at 1.5x-2x! Thanks for watching! Visit interviewpen.com/? for more great Data Structures & Algorithms + System Design content 🧎
I think we can solve this by two pointers and sorting the both array , and start looping from the applicants and check the matched apartment , and then you can either go to the next apartment or next applicant .
if the current applicant (i) requirement is bigger than the current apartment , these means other applicants will also not fit the current apartment (j) so we can skip the current apartment , etc
Correct - yes that is the 2ptr solution
Nice problem statement, I can totally relate myself with the interviewee 😊
yes - thanks for watching
Really very good question. Getting binary search though is good. Otherwise very difficult to achieve it in better complexity
Thanks! and yes things progressed well - we try to mix the person not knowing the question with things actually being educational to watch so nice that this went smoothly. Thanks for watching
I think we can solve this problem in 0(n+m) time. Idea is we create new object for the range and override equals and hash method of it. Equals method looks like if the desired value is in the range, we could assume these objs are equal. We could store these obj into Set and we can look from set O(1). But space complexity would be O(n)
This sounds like it could work, but I don't think this is correct. It overlooks the nature of us dealing with intervals here rather than precise data-points we can query. Overarchingly, (n applicants, m apartments) we can't do better than Ω(n) since we must check every applicants desire. If we must use O(1) space (no auxiliary space) then we are Ω((m * log(m)) + n * log(m)) for the binary search approach (sort step + search step doing log(m) work for each of n applicants.
If we can create auxiliary space, then yes:
1) we can go through the applicants
2) change each applicant preference integer to a range object
3) add the range object to a Set (uniqueness + fast existence check is guaranteed by the hash method as you said)
...
Issues:
1) What if there are multiple applicants with the same apartment preference? Iterating over each apartment, we would want to know the total applicants that fit in the range...then how do we dedupe an applicant fitting into multiple ranges? etc
...
Just voicing my thoughts. It sounds like it'd work, I'm just thinking how we efficiently do the range querys (efficient lookup)...I imagine we will expense more than a base of multilinear time.
...
Aside: I asked chatgpt and it said:
"The original problem is a form of interval matching. To optimize the solution to O(n + m), a form of hashing or map could be used, but keep in mind that it would need to handle interval data instead of just specific data points, which is inherently complex.
Unfortunately, utilizing a set in this context would not work effectively due to the interval nature of the problem. A set only contains distinct elements and doesn't provide a built-in way to handle ranges or intervals. For instance, if you have an apartment of size 60, a set won't tell you which applicants are within a range of 60 +/- k.
A possible data structure that could help would be an interval tree, which stores intervals and allows for efficient querying of all intervals that overlap with any given interval or point. However, building such a tree and querying it would exceed O(n + m) complexity.
So the simplest and most efficient known solution to this problem would be sorting the arrays and using a two-pointer approach, which results in O(n log n + m log m) time complexity due to the sorting process. As of my knowledge cutoff in 2021, no O(n + m) solution exists for this problem."
Applicant 3 would match right 80, -5=75
Applicant 2 would match to apartment 2, if we are inclusive, correct. The table represents an example exclusive on bounds. I mentioned we are inclusive - this is corrected later. Note has been left in the description.
@@interviewpen Yes when I completed the video I was able to notice.
What's the maximum value of the apartment size? If it's reasonable to be fit in the memory, we can build a bitmap representation of the available range with 0s and 1s. Lookup time will be constant o(1). Total time complexity will be o(n).
Yes, I'd say we can assume it fits in memory. & I don't remember this problem well enough (we do a lot) to review, but what you said sounds reasonable
What I don't get about this kind of mock interviews is how detached they are from the actual experience. Most of the time they involve surprisingly simple problems you'd be expected to solve in 20 mins tops, yet the guys often spend up to an hour going back and forth just to come up with the solution they often spell out in the very beginning.
I guess it's more of a performance and is done for the sake of going through all the interview dance moves in details, but it just ends up being a much more relaxed and simplified version of what you'd end up facing on a real FAANG interview. Not saying it's bad in and of itself, just that it can be a bit misleading for people who can end up expecting real interviews to be similar to these videos.
Yeah, this is valid - we could have a lot of these initial ones be shorter and yes I did choose easier questions because most engineers in-industry would fail at even medium-level questions (unprepped, which everyone was).
What you’re missing is how hard it is to serendipitously & by coincidence execute a perfect production that tight & high-pressure. For some of these the candidates would have failed - but you have to make a video out of it. So these can be better, we just started doing them.
@@interviewpen I totally get it, and I'm not blaming you guys here, it's just I remember watching similar videos while prepping for my first interview and thinking "hey, maybe it's not that bad if seasoned faang developers spend so much time solving it", then I started reading on those interviews elsewhere and realized how wrong I was.
I'd still love to see these guys face more complex problems even without any time constraints, regardless of whether they succeed or fail in solving them. The approach and logical framework other people use is much more interesing than the outcome itself.