- #1
Jamin2112
- 986
- 12
Well ... I completely failed that job interview. That was one of the programming questions. He said I answered it completely wrong.
Mark44 said:Was the idea to merge the two sorted arrays, and then find the median of the resulting array?
rcgldr said: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.
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.Jamin2112 said:He said that's "completely wrong" and the interview ended early.
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.jedishrfu said:What should she have done?
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 said:Well ... I completely failed that job interview. That was one of the programming questions. He said I answered it completely wrong.
rcgldr said:Was it stated if the two array were the same size or not?
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).Jamin2112 said:He immediately says, "They're not different size."
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.rcgldr said: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 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).jbunniii said: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.
The median is the middle value in a dataset when arranged in ascending or descending order. It divides the dataset into two equal parts, where half of the values are less than or equal to the median, and the other half are greater than or equal to the median.
To find the median of two sorted arrays, first merge the two arrays into one sorted array. Then, if the total number of elements in the merged array is odd, the median will be the middle element. If the total number is even, the median will be the average of the two middle elements.
The time complexity of finding the median of two sorted arrays is O(n+m), where n and m are the lengths of the two arrays. This is because the merging process and finding the median both require iterating through each element in the arrays.
No, there can only be one median in a dataset. The median is a single value that represents the middle of the dataset when arranged in ascending or descending order. If there are an even number of elements in the dataset, the median will be the average of the two middle values.
The median is a useful measure of central tendency in a dataset because it is not affected by extreme values, unlike the mean. It also provides a better representation of the "typical" value in the dataset, especially if the data is skewed or has outliers. The median is commonly used in statistical analysis and data comparisons.