Find the median of two sorted arrays

[Jamin2112]

Well ... I completely failed that job interview. That was one of the programming questions. He said I answered it completely wrong.

 

[jedishrfu]

how did you answer it?

The median is the middle value as in the list { 1, 5, 9 } 5 is the median

or if the list is { 1, 3, 5, 7 } then the median would be the average of (3+5)/2 = 4

 

[Mark44]

Was the idea to merge the two sorted arrays, and then find the median of the resulting array?

 

[Jamin2112]

Was the idea to merge the two sorted arrays, and then find the median of the resulting array?

No! That's what I originally suggested.

Use the Java library List member functions to:

(1) Merge the arrays
(2) Resort the merged array

Then,

(3) write a simple function to return the middle element if the length of the merged array odd, or the average of two middle ones if it's even.

He then told me to answer the question "without merging the arrays."

I said, Ok, and I described a procedure where you start going through the array with the smaller smallest number, counting up and switching between the arrays at appropriate times until the count has reached the point where you're at the median or the two elements that average to the median depending on the combined size of the two arrays. I explained everything cogently on the white board.

He said that's "completely wrong" and the interview ended early.

 

[jedishrfu]

Don't take it bad in interviews the interviewer is always right even when he's wrong or inflexible. Basically if you get caught in argument you've blown the interview. Sometimes interviewers are hostile if they perceive you are a threat to their job.

I know being on the interviewer side my manager once asked me if I'd be bothered if they hired so and so because they didn't want to mess up the group dynamic of the department. She knew this guy was hard to handle and had the ear of a higher level manager (meaning a spy in the mix).

I've done numerous interviews over my career and have run into many types of people some who are nice and some who are real jerks and then there's the sit around the converence table interview where multiple people follow a script asking questions often during lunch where they can eat but you can't. Those kinds of interviews are interesting if you can get them off script with some dialog like as in asking about the work environment and then you get to see the group dynamics and then you get to decide whether its even worth it.

In one case at work, a better candidate was not selected because they couldn't answer a sorting question immediately that a more inexperienced candidate answered. (She had just done this problem as homework the week before and so lucked out at the interview.)

So basically, don't feel bad, live and learn and just be prepared next time to answer questions on projects you did that listed on your resume. Also you could research these types of interview problems for next time (remember the website too so you can mention it). Dr Dobbs journal had an article some years ago on C++ interview questions, during one interview the guy asked me one on the list and I andswered it quickly and said oh so you read Dr Dobbs Journal. He said no so I gave him one of the questions from the article and he couldn't answer it that broke the ice and the interview went smoothly to the end when the manager tried to make me a project/release lead and not a senior programmer (I hate project lead crap so I turned them down).

 

[rcgldr]

On a side note, a true "merge" (merge based on comparason) of two sorted arrays would produce a single sorted array, without requiring a sort step aftewards.

Your suggested method was not "all wrong". It may not have been the optimal solution, but it was not all wrong.

Was it stated if the two array were the same size or not? If the arrays are the same size, then it's easier to optimize this algorithm. Do a web search for "median of two sorted arrays", to find various algorithms to implement this. The key idea is for each iteration is to eliminate "k" "outer" elements from each array, (note - "k" is the same value for both arrays even if both arrays are not the same size), until the median is found.

This seems like a bad way to conduct an interview, since as jedishrfu posted, a lesser experienced programmer might have learned about this specifc case in some recent class, while the more experience programmer never dealt with this problem before. The interview should have included more than one main challenge, and should have been based on the experience in your resume and/or the type of programming the company does. I doubt that the company has the need to find the median of two sorted arrays.

 

[jedishrfu]

On a side note, a true "merge" (merge based on comparason) of two sorted arrays would produce a single sorted array, without requiring a sort step aftewards.

Your suggested method was not "all wrong". It may not have been the optimal solution, but it was not all wrong.

Was it stated if the two array were the same size or not? If the arrays are the same size, then it's easier to optimize this algorithm. Do a web search for "median of two sorted arrays", to find various algorithms to implement this. The key idea is for each iteration is to eliminate "k" "outer" elements from each array, (note - "k" is the same value for both arrays even if both arrays are not the same size), until the median is found.

This seems like a bad way to conduct an interview, since as jedishrfu posted, a lesser experienced programmer might have learned about this specifc case in some recent class, while the more experience programmer never dealt with this problem before. The interview should have included more than one main challenge, and should have been based on the experience in your resume and/or the type of programming the company does. I doubt that the company has the need to find the median of two sorted arrays.

To continue the bad experiences in interviews, I went to one company for the senior programmer position and was interviewed by a junior programmer who asked me to swap to variables around in a specific language that he was familiar with. He didn't even know what job I was interviewing for.

On another note, a friend recently got a job offer from a new company. The old company knew she was looking and did nothing to keep until she got the job then they matched and when she said no they bumped the offer up. What should she have done?

The answer is to contact the new company and see if they'll match the latest offer. In any event, she should go to the new company. Why? because if she doesn't then she can never apply there again as they won't take her seriously and two the old company is probably just accelerating her raise to keep her and will then delay future raises to cover the action (stingy company promotion policy). It's almost like the Monty Hall problem where your odds are always better if you switch.

 

[D H]

He said that's "completely wrong" and the interview ended early.

What he meant by "completely wrong" is that you gave an O(n) algorithm. He wanted a faster algorithm -- and that is what he should have said as a hint. By not doing that, he is not getting the kinds of people he thinks he is getting. He's getting mostly people who happened to have read how to solve this particular puzzle.

Whether the people he hires can program -- his interview style is not catching that problem. Apparently computer science programs produce a lot of CS graduates who cannot program. It's a huge problem, and it is the reason this interview format has become so popular. There's a corollary to the "most CS graduates can't program" problem: Most interviewers can't interview.

Be glad you didn't get this job. This interviewer is probably a manager, and is probably what I call a "wrong rock" kind of manager. This type of manager says "Show me a rock!" He doesn't say what kind, so you go find a garden variety rock. Easy, right? Wrong. "No, not that kind of rock. That's the wrong rock. Show me another rock!" He never says what's wrong with the rocks you show to him, and he never gets any more specific than "show me another rock." You do not want to work for a "wrong rock" manager. It is not a pleasant experience.

 

[D H]

What should she have done?

Switch. In the Monty Hall problem, staying has a 1/3 chance of succeeding. The chances of succeeding with a cheap*** employer are much less than one out of three.

 

[Borg]

Well ... I completely failed that job interview. That was one of the programming questions. He said I answered it completely wrong.

Don't let it get you down. There will be other interviews and not all of them insist on giving pop quizzes. I'll second DH in saying that you don't want to work for the "Show me a rock" manager. You can waste your life trying to please those types.

 

[Jamin2112]

Was it stated if the two array were the same size or not?

Alright, get this. The first thing I did was write on the board:

Let the 2 arrays be A and B:

A = {a₁, a₂, ..., a_m}, a₁ ≤ a₂ ≤ ... ≤ a_m,
B = {b₁, b₂, ..., b_n}, b₁ ≤ b₂ ≤ ... ≤ b_n.

He immediately says, "They're not different size." To which I replied, "Yes, I'm not necessarily saying m≠n."

Now that I think about it, I might've screwed myself over by trying to do a generalized method that was far more complicated.

 

[rcgldr]

He immediately says, "They're not different size."

Did he not mention this in the first place? Anyway, it's the same principle, each step of an optimized algorithm "drops" the first or last "k" elements of each array, depending on which array has the lower median, you can repeat this until one or both arrays only have 1 element each (there's a "clever" method that could stop at 2 elements each).

Still for someone that has never seen this before, I doubt most experienced programmers would realize an optimal solution without spending more than just a couple of minutes analyzing the problem or going through a few examples.

This was more of a test of an algorithm knowledge than algorithm discovery process or programming.

It would be like asking someone to develop a greatest common divisor algorithm that wan't aware of Euclid's method.

 

[jbunniii]

Was it stated if the two array were the same size or not? If the arrays are the same size, then it's easier to optimize this algorithm. Do a web search for "median of two sorted arrays", to find various algorithms to implement this. The key idea is for each iteration is to eliminate "k" "outer" elements from each array, (note - "k" is the same value for both arrays even if both arrays are not the same size), until the median is found.

I had to think about it for a few minutes even after reading this hint, but I think I understand the algorithm now. It's actually pretty cool, but what a dumb question for an interview. At best, it will help you to find candidates who can come up with quick solutions to cute but useless puzzles, and more likely it will be someone who just happened to have already seen the puzzle. In either case, I don't see how that indicates software engineering ability.

At my employer, our interview slots are only 45-60 minutes long. I can't imagine wanting to waste any of that time on something silly like this. Far better in my opinion to ask several straightforward, non-trick questions, the kind that are basic enough that you wouldn't want to work with someone who couldn't answer them. The goal is to filter out the obvious incompetents (which turns out to be surprisingly many applicants who look good on paper), not to eliminate good people with trick questions.

 

[rcgldr]

I had to think about it for a few minutes even after reading this hint, but I think I understand the algorithm now. It's actually pretty cool, but what a dumb question for an interview.

I agree. Having never seen this "puzzle" before, it would take me a few iterations to figure it out how to optimize it. Perhaps you could have handed the interviewer a Rubik's cube, and stated you'd probably solve the problem by the time he solved the Rubik's cube (assuming he had never seen one before).

I do recall some companies using IQ like tests back in the 1970's and 1980's, mostly for entry level jobs, where a candidate would have little experience and these tests were presumed to give an idea of how quickly a candidate could learn new skills. Apparently this was a similar case for your interview, but the "puzzle(s)" were too specific and perhaps too complicated for someone unfamiliar with the "puzzle(s)" to develop an algorithm on the spot.

For experienced candidates, generally the goal of an interview is to look at the accomplishments listed on a resume and get an idea of just how much the candidate was involved in those listed accomplishments, such as being able to provide details on key aspects and issues of the stated projects.

 

[jedishrfu]

Microsoft and Google have used these although Google likes to use out of the box thinking where its not so much the answer but how quickly you came up with the answer and the means / assumptions you used.

http://www.huffingtonpost.co.uk/2013/06/18/google-interview-questions_n_3458986.html

 

[Solkar]

Put it this way - the interviewer was in a position to play silly games with you: adding constraints on the prob and solution AFTER the candidate already started working on the solution is eristic for the lesser gifted.

If that guy had been your team leader, be glad you won by getting out of that mess early enough.