Microsoft Interview Question

[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.

----
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.




--
           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

> -------------------------------------------------------------------------- <

作者: 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

> -------------------------------------------------------------------------- <

發信人: [e-mail] (宇恆), 看板: Oversea_Job
標  題: Re: Microsoft Interview Question
發信站: 批踢踢參 (Sun Jan 27 15:11:29 2008)
轉信站: ptt!Group.NCTU!grouppost!Group.NCTU!ptt3

※ 引述《[e-mail] (Sunnyvale)》之銘言：
: ※ 引述《Baudelaire (Sunnyvale)》之銘言：
: 基本上算是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;
: }

    我想方向是正確的, 但是如果 X = 0 的話,似乎會有問題.....

    我精簡你的版本,在最後return前確定是真的rotate過.


public static int FindSortedArrayRotation(int array[]) {

    int i = 0, j = array.length -1;

    while(j-i > 1)
    {
        if(array[(i+j)/2] > array[i])
            i = (i+j)/2;
        else
            j = (i+j)/2;
    }

    if(array[j] < array[i])
        return j; // Make sure array did rotate.
    else
        return 0 ;


歡迎指正

--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 168.7.230.23


> -------------------------------------------------------------------------- <

發信人: [e-mail] (宇恆), 看板: Oversea_Job
標  題: Re: Microsoft Interview Question
發信站: 批踢踢參 (Sun Jan 27 16:11:26 2008)
轉信站: ptt!Group.NCTU!grouppost!Group.NCTU!ptt3

※ 引述《[e-mail] (Sunnyvale)》之銘言：
: ※ 引述《Baudelaire (Sunnyvale)》之銘言：
: : 這題據強者我ebay的朋友說，Google在on-campus也問過他這題。
: 算是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;
: }


    直接改Cormen那本書裡的partition似乎可以提供更精簡的答案

    請參考

    Partition(Ball A[])
    {
        i = -1;
        k = A.length - 1;
        x = A[k];
        Ball temp;

        for(j=0; j < k; ++j)
        {
            if(A[j] != x) // Here is the key modification.
            {
               ++i;
               temp = A[i];
               A[i] = A[j];
               A[j] = temp;
            }
        }

        return (i+1);
    }


--
※ 發信站: 批踢踢參(ptt3.cc) 
◆ From: 168.7.230.23