31–40 of 97 posts
Who does a sort for this D:
You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
Who does a sort for this D:
You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
Quickselect is fairly simple to understand if you already understand Quicksort. You use use a binary division but you avoid sorting sections where the order doesn't matter.
Let's start with a 7 element array
[ 2, 4, 7, 5, 3, 6, 1 ]
[ 2, 4, 3, 1, 5, 7, 6 ]
We pivot the first partition (first 4 elements) on 3 and get
[ 2, 1, 3, 4, 5, 7, 6 ]
Earlier quoted context omitted.
I got that recently, I really didn't like that question. For the n-th percentile version, the obvious solution is sorting and it takes 10 seconds to get to that point, 5 minutes of implementation with tests. Good. It's all downhill from here. Then you get hit with the "it's a data stream" and you realize you have to implement a balanced tree on the spot which I wouldn't describe as fun. You may or may not be able to…
Literally the second I read "it's a data stream" I knew the answer was going to be reservoir sampling. RS is really interesting to me. many people you talk to can realize you can compute the mean of a data stream ( https://www.geeksforgeeks.org/web-tech/expression-for-mean-a... ) without knowing the exact formulation. And it's not far from that to think of a sampling strategy to decide if a new sample should go into…
But it was clear in this case that the interviewer just took a question from the company's bank of questions and was alt-tabbed for half the interview, I have felt the energy early and I was also half-checked out.
I'm aware I'm saying this post factum, but I had a very fun first interview with that company and matched well with the first interviewer so my expectations were high, and then I got hit by the big tech style interview when it was an early stage startup.
Huh, feels overly simple to me. How about something like the beginnings of a spreadsheet engine? Or.. count the number of distinctly shaped black regions in a bitmap image.
"Write me a function in any language of your choosing, that takes an array of integers and returns the sum."
I loved it. Here is why:
1. I'd get to see them write code, in a low pressure way, but they'd have to write something
2. A shocking number of people would struggle to write the code. That was my signal to end the interview early.
3. I'd get to ask "So tell me how it works" and they'd sometimes look at me like I'm a moron, but others would be respectful and kind, and that would tell me how they'd answer other people who ask questions they felt had obvious answers.
4. I'd ask "what could go wrong at runtime?" - this would be where most people got surprised by their own responses, but it was a fun conversation to have about a seemingly simple function.
5. I'd ask how they would fix any potential runtime exceptions or potential undesirable behaviours
6. I'd try break it, and ask how they would handle that (if i could, i often could)
7. If we got this far, then we could move onto other questions and they're warmed up and generally feeling safe about how the conversation would go. I'd like to switch from coding into data structure related questions normally.
I hate high pressure coding interviews, also, who the hell doesn't just sit there and Google / LLM the answer anyway. The real question I want to know is "How curious are you? Do you want to learn? What kind of person are you? Will I enjoy working with you when things get hard". That's hard to figure out, but you're not going to do that if you just try stump someone in an interview. I think it's on the interviewer to find a way to ask questions that are revealing and accessible in an interview environment...and frankly, I think you get more out of it if you make the effort to keep it simple.
[flagged]
Candidates who could implement an O(n) median algorithm but chose to implement an O(n log n) weighted median algorithm might be someone who rote remembered the O(n) algorithm. Truly excellent strong hires can adapt their O(n) algorithm to weighted median too.
I don't know... I've been coding for ~30 years, and I've never had to write code to compute the median so it doesn't seem that useful unless it's somehow relevant to the job
A binary search[0] of a sorted collection requires the median of each region being considered for each iteration.
But they don't. I hope you, as an interviewer, have the grace to learn when one of your interviewees points out your mistake. :-) Median is O(n), not nlogn