Please register to participate in our discussions with 2 million other members - it's free and quick! Some forums can only be seen by registered members. After you create your account, you'll be able to customize options and access all our 15,000 new posts/day with fewer ads.
lol I'd never seen this problem and I used a method which does work. I felt good about myself for coming up with it on the spot, even if there is a better way. The funny thing is that he sat there for 20 minutes watching me think aloud as my put together my method .... then I asked if it was sufficient and he said, "No, it's completely wrong."
My procedure, which I explained on the whiteboard:
Suppose we have two arrays,
A = {a(1), a(2), ..., a(m)},
B = {b(1), b(2), ..., b(n)},
Set V = min{a(1), a(2)} and count = 1. We iterate until count = (n+m)/2 (where I'm using (n+m)/2 to mean what it means in code language ... the integer division with no remainder part).
If V = a(2) = a(1), then count++ and V = a(2).
If V = a(2) > a(1), then check whether b(1) .......... blah blah blah.
Hubby says: the interviewers were correct, and your algorithm was incomplete.
If V = min{a(1), a(2)} then V will never = a(2)> a(1). Your second statement will never be true.
A better solution is:
Set V = min{a(1), b(1)}
If V= a(1) then increment count by 1, and then compare min{a(2), b(1)} ....
The opposite if V = b(1)Iterate until count = (n+m)/2
Type-O on my part. I did put min{a(1), b(1)} and that's what I meant.
Quote:
If V= a(1) then increment count by 1, and then compare min{a(2), b(1)} ....
The opposite if V = b(1)Iterate until count = (n+m)/2
That's the idea, yea.
In any case, he wasn't having any of it. I'm just disappointed because I know it'll probably be at least another couple weeks before I get a chance demonstrate what I know. I didn't even get to demonstrate any actual programming.
From what I hear, the question about finding the median of two sorted arrays (not necessarily of the same says) is one that even very experienced programmers would have trouble solving on the spot.
Hubby says:
"I've had to write that algorithm on the spot in interviews before. Honestly, if 'very experienced programmers' could not write that algorithm on the spot, they're not as experienced as they think they are."
Sorry, he's just being honest.
[My husband is a software engineer with an MSCS with 8 years experience in the field. He also has several years teaching experience in CS at the university level.]
Hubby says:
"I've had to write that algorithm on the spot in interviews before. Honestly, if 'very experienced programmers' could not write that algorithm on the spot, they're not as experienced as they think they are."
Sorry, he's just being honest.
[My husband is a software engineer with an MSCS with 8 years experience in the field. He also has several years teaching experience in CS at the university level.]
That's maybe to be expected from an MSCS and 8 yrs experience. This was for a junior position.
I told one computer genius about my horrible performance at the interview today and he said:
"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."
Type-O on my part. I did put min{a(1), b(1)} and that's what I meant.
That's the idea, yea.
In any case, he wasn't having any of it. I'm just disappointed because I know it'll probably be at least another couple weeks before I get a chance demonstrate what I know. I didn't even get to demonstrate any actual programming.
Write a function to reverse a string, or the digits (decimal or binary) of a given number.
Write a simple complex number class, with various useful operators.
Hubby says:
With the typo fix, your idea is correct-
As for the rest: in very few of my recent interviews have I sat in front of a computer creating a program. Most of the questions were of the type you experienced. A good reference would be the Google Guide to Interviews (I believe that is what its called). Many companies pull questions based on them.
Most technical interview questions tend to be the "create this algorithm on the fly" type where you don't even see a computer most of the time. The idea is to watch you think, not watch you code.
You're supposed to feel on the spot, unfortunately (or fortunately, depending on how you look at it). They're looking for mental agility instead of only technical competency. They want to see how your brain works in real time.
Many IDEs today handle technical errors automatically for you, they don't handle logic errors. Therefore, there's less emphasis today on technical correctness and more emphasis on logic.
It does sound like you got a raw deal with your interview. Don't give up.
That's maybe to be expected from an MSCS and 8 yrs experience. This was for a junior position.
I told one computer genius about my horrible performance at the interview today and he said:
"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."
What does hubby say?
Hubby says:
Yeah, he got screwed. They should have given him more chance to argue it or work it out.
[Disclaimer: LOL_Whut has no idea what any of the technical stuff meant - I'm the social sciences major]
Hubby says:
With the typo fix, your idea is correct-
As for the rest: in very few of my recent interviews have I sat in front of a computer creating a program. Most of the questions were of the type you experienced. A good reference would be the Google Guide to Interviews (I believe that is what its called). Many companies pull questions based on them.
Most technical interview questions tend to be the "create this algorithm on the fly" type where you don't even see a computer most of the time. The idea is to watch you think, not watch you code.
You're supposed to feel on the spot, unfortunately (or fortunately, depending on how you look at it). They're looking for mental agility instead of only technical competency. They want to see how your brain works in real time.
Many IDEs today handle technical errors automatically for you, they don't handle logic errors. Therefore, there's less emphasis today on technical correctness and more emphasis on logic.
It does sound like you got a raw deal with your interview. Don't give up.
Can I ask you another programming question from a different place I applied online?
OP, unfortunately that's how most interviews work in this field. You need to bite the bullet and learn algorithms . Some companies (like google) want to be sure that they hire smart people with strong cs fundamentals so that they can throw them on any project they need. Some companies just don't know how to do technical interviews and go through relational dbs theory, basic algorithms and data structures instead of checking if the candidate can actually code (which is more important in my opinion). What's funny is that after the interview the chances are VERY high that you won't do any serious algorithmic programming except for very few places. I would say it's a very good idea to became aware of the most popular algorithms (merge sort, quick sort, heap sort etc.) and data structures (maps, trees, linked list) and implement them at least once. You you've ever implemented the merge algorithm, you'd see a solution to the problem of finding the median of 2 sorted arrays right away. Is it important to know the implementations at any given point? No. If I was interviewing someone, that would not be high on the priority list. But like I said it's nice to be at least aware and bigger companies will test you knowledge in this area. I'd recommend to pick up a book and learn.
I hate bad interviews in fact interviews in general. May I ask how old are you? Just keep going.
Please register to post and access all features of our very popular forum. It is free and quick. Over $68,000 in prizes has already been given out to active posters on our forum. Additional giveaways are planned.
Detailed information about all U.S. cities, counties, and zip codes on our site: City-data.com.