CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

SM!

- Anonymous September 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cmon anon. Not helpful.

I guess what he/she meant to say was: Stable Matching!

- LOLer September 23, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the question seems quite complex to me. has anyone got any clue on any working solution ? please put it here.

- majnuKaTila September 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Draw a directed graph with men on one side and women on the other side... Edges carry preferences as their weight... Now, all you need to do is, pick all the edges having max preferences!

- PrettyDumb September 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That wont work i guess.

- Erik September 24, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would suggest the following

Round 1 : we review the 1st preference of all men and women. All the matches get married. All these people get married with their 1st choice. They're happily married and we can forget about them

Round 2 : we review the 1 and 2 preferences of all men and women. All the matches get married. In each couple, one of the partner gets married with his 2nd choice. The other gets married with his 1st choice or 2nd choice.

Round n : we review the n first preferences of all men and women. All the matches get married. In each couple, one of the partner gets married with his n choice. These marriages can't be broken because neither the man nor the woman can find a better partner.
All the ones that are not married yet are not interesting for them (they're ranked after their n-preference).
All the ones that are already married will never switch for them, as they're already found a partner that ranks better than n in their preference list.

- Christophe September 25, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

With your strategy, things could get ambiguous starting from Round 2, because one could have more than one candidate on his/her preference list and there would be multiple ways to match them. The correct way to do it is to get the maximum matching at each round.

- shany November 12, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Christophe: your solution looks okey to me.
any other solution, anybody ?

- chinni chor October 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a Bipartite graph matching problem, refer link: http://www.mcs.csuhayward.edu/~simon/handouts/4245/hall.html

- KK October 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the aim here :
1] Get as many as possible, ppl married
2] Get as many as possible, ppl married with their highest choice

In 1] case, some1 might get married to his/her second choice just to avoid deadlock and have more married couples

In 2] case, if there are perfect matches they will get married, irrespective of if some1 stays single.

- Hash October 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the stable matching problem. look it up on wiki. The soln remains unstable when a woman W and man M both have each other as their first pref.

- k October 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it's a classical graph problem - bipartite matching.

- Anonymous October 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

http :// en.wikipedia . org/wiki/Stable_marriage_problem

- Anonymous April 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

http :// en.wikipedia. org/wiki/Hall%27s_theorem

- Anonymous August 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

computer scientist just keep re-inventing what mathematicians already found.

- Anonymous August 05, 2010 | 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