Microsoft Interview Question for Software Engineer / Developers


Team: Bing
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 3 vote

The question is phrased poorly and lacking details. I will assume you can only inspect one car at a time to see if it is your car, and that you must physically visit each car to inspect it (ie: you cannot visually inspect a car from the other side of the road). I will also assume that it takes the same amount of time to walk across the street as it does to walk from one adjacent car to the next, and that as a human being you have the ability to easily keep track of the location of cars you've previously visited. Lastly, I will assume that the road is the same length on both sides and that no cars are being added or removed while you are searching. For discussion's sake, let us assume the two sides of the road are East and West, while the road spans seemingly infinite distance North and South. I will label the starting position as zero, and cars going North on the West side of the road as 1, 2, 3, etc. and on the East side of the road as 1`, 2`, 3`... Cars going South are -1, -2, -3... and -1`, -2`, -3`... respectively.

One approach is to split your time evenly going North and South and on both sides of the street until you come across the car. In other words, given the origin 0, visit cars 1 and 1` going North , then back-track and visit cars -1 and -1` going South. Repeat this process by visiting 1 extra car on each side going North and then South again until you find the car. The advantage to this approach is that it's guaranteed to find the car -- even with an infinite number of cars in each direction -- as long as the car has some finite position. The problem with this approach is that it wastes a lot of time walking past cars you've already inspected.

If you expect that the data is not truly infinite, or you're more interested in your probability of finding the car in some given amount of time, there is a better approach. You can guarantee to only visit each car one time, never walking past a car you've previously inspected by, for example, walking only down one side of the street infinitely. If you do come across an end to the road, return down the other side of the street. Repeat this process until you've visited every car (or until you die from walking infinitely). You could use many other search patterns like checking every other car on alternating sides of the road, etc. However, your pattern is irrelevant given the question as posed. This approach minimizes the wasted time visiting cars more than once, and thus gives a much lower "expected time until car found." However, it does not guarantee you will find the car if the road is infinite.

An actual solution would depend on circumstances not elaborated upon in the original problem.

- Ross August 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or maybe they expect you to talk about your vision distance, or the range of your keyless etc...

- Anonymous August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unfortunately since we only have the question as phrased on this page to go by, some assumptions have to be made. There is not space on this page to discuss the problem for every given permutation of assumptions. In an interview you can interact with the interviewer and they can direct the course of your solution as you explore and discuss it. On this page, we rely on the question being complete, which sadly they never are. We are lucky when one is phrased with intelligible grammar.

- Ross August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Ross: This is not a Q&A site like stackoverflow. You can always post ideas.

I agree with you though, people tend to post horribly interpreted and and terribly written questions.

Perhaps trying to figure out what the question is, would help people in the interviews!

- Anonymous September 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"There is not space on this page to discuss the problem for every given permutation of assumptions."

That, good sir/madam, is very well put.

- eugene.yarovoi September 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Nice question. I think the presumptions should be:
1) c1 - cost of moving one step along the road
2) c2 - cost of checking the car on the same side
3) c3- cost of crossing road (to check the car on the other side).

Now, you have to find out an algorithm which gives you the minimal average cost of searching, which will be the best of all functions SearchCost(uint c1, uint c2, uint c3, int Distance, bool bSameSide), where Distance is a distance to your car from the starting point, bSameSide - true if the car is on the same side of the road as the starting point, false - opposite. Well...the answer is not trivial :-).
=========================================
Well...my second thought is - the answer IS trivial: as the car we search can be at any place in the parking with equal probability, we have just go through all parking places (as fast as possible) : go to the right to the end, switch side, go back to the end, switch side, go to the right again...

- celicom September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

my thought , its just like searching the element in sorted array of infinite length , bin search in 2^i where i=0 to n .

Assume location of car is x and o to infinite (length of road its unknown )

- shashank7android September 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Had we knew the location of the car, we could have reached there in finite constant time,
refer the question again

- Ashupriya September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple, call up your two friends who have high speed vehicles (say, racer bikes). One chooses to go north side of the road and the other goes south. Off you go!!!

- rajarshi129 October 01, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More