So it depends on sort of, I mean, most devices, this will fit a memory is the short answer. 100 megs is not so much memory, or, you know, some factor that, but it's a fair bit of memory. Professor Squirrel: In this case, we're fine. Immutable Automaton: Do you think that it can fit in memory?
#Nearest restaurants code
So even if n was like, larger than 100 million it didn't fit in memory or something, you could sort of also do something that took like disk IO or network IO, and adapt this code to run that way. And that way also you can write it streaming. So all in all, I think the heap is a lot more favourable in terms of performance. And then we can get it down to the log k factor and the memory also Yeah, I mean, depending on if this is in place, you need some extra memory up to like, O(n) memory, whereas here you can just say O(k) memory. So, it would be preferable to do something like a left to right scan with a heap of size or a priority queue of size k. Sorts will take n log n time to sort it and then describe the first k things guessing in general though we expecting k to be rather small. I mean, it's, it's a pretty big thing to sort so we could do is a naive sort. Roughly, I mean, there's really we're going to take differences between the user location and the restaurant location, but we'll call that like the restaurants like value basically, it's the thing we're ordering by and trying to find the 10 smallest. The basic concept is we want the 10 smallest values from 100 million values. So we've kind of abstracted with the details of this being restaurants and locations and like Euclidean distance.
Right, 100 million restaurants for the K nearest restaurants? Umm Sure. And the other input is just the user's location. Professor Squirrel: So I guess it's really the location, this restaurant location. Professor Squirrel: Probably rust if that's okay. Immutable Automaton: What language will you be using? Restaurants are x and y's and x and y are bounded by negative one and one. Immutable Automaton: Right now they are just coordinates.
#Nearest restaurants plus
And how are we representing these restaurants today have like some just unique identifier plus their location? So for the purpose of this question, 100 million will be n and k. So given a list of 100 million restaurants, write a function that takes a user's location and returns the 10 nearest. Today, we're going to implement a back end piece that, that powers this. Okay, so let's say you have you have a website that allows users to find the 10 nearest restaurants to your location. Immutable Automaton: Okay, let's try this one. Professor Squirrel: Anything really, graphs are always fun, but like basically anything, just sort of mix it up, I guess. Immutable Automaton: So any type, like dynamic programming, or graphs, trees? And then we did whether your parking pass to traffic cones? We did the K smallest element from two arrays. Professor Squirrel: I'm Afraid I don't remember. Would you like to do something? Do you have a specific type that you want to try? We did. So I believe last time you did really well, I'm looking at the previous feedback. Immutable Automaton: Sorry what at Google? Professor Squirrel: Actually, right now Google, and now it's fuchsia at Google.
Just to confirm you are interviewing for WeMo. So uh, we did two questions last time, right. Their performance is good enough for L4 and maybe even L5 interviews though I would not encourage leveling up this way as day to day engineering work still takes time to pick up.įeedback about Immutable Automaton (the interviewer) With this level performance I have no doubt about their ability to nail their Google interviews. Overall, the candidate was fantastic, their performance is easily one of the best I have encountered for the approximately 400 interviews I have conducted, both on the coding and problem solving fronts. My only gripe would be that "find_kth_nearest" should not be a method of the QuadNode class.
They were not only able to write code for the core part of the problem, they were also able to at the same time implement the supporting data structure. Their coding ability was the highlight of the interview. They were able to figure out the need to segment the search space with a little hint and they managed to arrive at the intended solution without little guidance. The candidate was able to come up with expected brute force solution right away - iterating through all 100 million, but using a max heap to keep track of the 10 nearest. The problem we worked on today was the 100 million restaurant problem. This is our second session, the candidate blazed through their interview the last time round so we worked on a slightly harder problem this time.
0 kommentar(er)
