Yahoo Interview Question for Software Engineer / Developers






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

It's a 0/1 partitioning problem, we can swap the balls using two pointers traversing the list. Let's say we put red at the front

pubic int BallPartitioning(Ball* balls, int n)
{
int first = 0;
int last = n-1;
while(( first < last ) && ( balls[last].Color == Color.blue ))
{
last--;
}
while( (first < last) && (balls[first].Color == Color.red))
{
first++;
}
if(first == last)
{
return last;
}
// swap
swap(balls[first],balls[last];
}

- Nat September 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution... i think it's the simplest and more obvious.. in Python

def order_balls(balls):
    position=0
    for i in range(0,len(balls)-1):
        for j in range(i,len(balls)):
            if balls[i]>balls[j]:
                tmp=balls[i]
                balls[i]=balls[j]
                balls[j]=tmp
                position=i+1
                break
    return balls,position


#Test
print (order_balls(["blue","red","blue","blue","red","blue","blue","red","red","blue"]))

- Carlo September 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is just a sort and find . n log(n) complex

- sort and find September 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, it's easier than just sorting. We know everything is either red or blue. Red goes at the beginning, blue goes at the end.

array balls
int bpointer = balls.length - 1
int rpointer = 0
while(1)
   while(balls[rpointer] == blue)
      if rpointer == bpointer : return rpointer
      balls[rpointer] = balls[bpointer]
      balls[bpointer] = blue
      bpointer--
   rpointer++

Runs through the array, shuffling balls so blues move to the end. When rpointer hits bpointer, then we must've reached the end. There are a couple of minor flaws with my code (hypothetically, rpointer might end up being bpointer+1, or it's possible they both end on the last red instead of the first blue), but these are problems easily fixed. This is definitely an O(n) problem, not O(n2) or even O(nlogn)

- Anonymous September 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question mentions "List". So it would be better to assume singly linked list. In that case the most efficient solution will not be so simple.

- Sanjay September 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do it in O(n) time.

- beyondfalcon June 15, 2013 | 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