code style

1/27/2008

Re: Microsoft Interview Question

作者: Baudelaire (Sunnyvale) 看板: Oversea_Job
標題: Re: Microsoft Interview Question
時間: Sun Jan 27 06:41:54 2008

※ 引述《Baudelaire (Sunnyvale)》之銘言:
: 這題據強者我ebay的朋友說,Google在on-campus也問過他這題。
: Array Rotation
: You should be able to do this in less than linear time.
: Implement the following function, FindSortedArrayRotation,
: which takes as its input an array of unique integers that has
: been sorted in ascending order, then rotated by an unknown
: amount X where 0 <= X <= (arrayLength - 1). An array rotation
: by amount X moves every element array[i] to array[(i + X) %
: arrayLength]. FindSortedArrayRotation discovers and returns X
: by examining the array. Consider performance, memory utilization
: and code clarity and elegance of the solution when implementing
: the function.

基本上算是binary search的變形:

public static int FindSortedArrayRotation(int array[]) {
int begin = 0, end = array.length - 1;

while (end-begin>1) {

if (array[begin] > array[(begin + end) / 2]) {
end = (begin + end) / 2;
} else if (array[(begin + end) / 2] > array[end]) {
begin = (begin + end) / 2;
} else {
return (begin+end)/2+1;
}
}
return end;
}

: ----
: Partitioning
: Given an array of balls, which can be one of two colors (RED or BLUE),
: write a function that partitions the array in-place such that on exit
: from the function all the balls of the same color are contiguous. It
: does not matter whether the red or blue balls come first. The return
: value from the function is the index of the first ball of the second
: color. If there is only one color of balls in the array then the
: return value should be 0. It is not legal to change the color of a
: ball. They must be moved. Consider performance, memory utilization
: and code clarity and elegance of the solution when implementing the
: function.

算是quicksort裡面的in-place partition,也不會太難。


public static int Partition(Ball[] aBalls) {
int left = 0, right = aBalls.length - 1;
BallColor pivotColor = aBalls[0].Color();

while (left <= right) {
BallColor leftColor = aBalls[left].Color();
BallColor rightColor = aBalls[right].Color();

if (leftColor == pivotColor) && rightColor == pivotColor)
left++;
} else if (leftColor == pivotColor && rightColor != pivotColor) {
left++;
} else if (leftColor != pivotColor && rightColor != pivotColor) {
right--;
} else if (leftColor != pivotColor && rightColor == pivotColor) {
Ball tmp = aBalls[left];
aBalls[left] = aBalls[right];
aBalls[right] = tmp;

left++; right--;
}
}
return left;
}

--
Je t'aime,o capitale infame.
 Tu m'as donne ta boue et j'en ai fait de l'or.
 Charles Baudelaire 1821-67

http://wonderfultown.spaces.live.com/

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.21.111.81