Yahoo Interview Question
Software Engineer / DevelopersMy 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"]))
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)
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
- Nat September 12, 2010pubic 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];
}