wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Microsoft Questions
        
(Message started by: vodangkhoa on Jan 31^st, 2007, 2:55pm)

Title: Microsoft Questions
Post by vodangkhoa on Jan 31^st, 2007, 2:55pm

Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;

Given an arbitrarily long string, design an algorithm to find the maximum repetitive substring. For example, the maximum repetitive substring of "abcabcabc" is "abcabc"

There is a series of numbers in ascending order. In binary, all these numbers have N number of 1s set in them. Given N, write an algorithm/C program to find the nth number in the series.

Title: Re: Microsoft Questions
Post by sk on Jan 31^st, 2007, 6:39pm

suffix tree for the second.

Title: Re: Microsoft Questions
Post by jollytall on Feb 4^th, 2007, 1:32am

For the first one.
There is a question though whether we want to optimise for speed or for memory usage.

Anyway a possible algorith, although more difficult to write than to program it.

Make two matrixes nxn of integer;

In the first one write how many blacks are right starting from this one (0 = it is white, 1 = it is black but the right neighbour is white, etc.).
The algorith for this piece is something like (Pascal like, though not fully):
for i:=1 to n do
begin
if A(i,n)=Black then B(i,n):=1 else B(i,n):=0;
for j:=n-1 downto 1 do
if A(i,j)=Black then B(i,j):=B(i,j+1)+1 else B(i,j):=0;
end;

Similarly make the C matrix vertically (you can combine the two cycles if you want).

Define a variable BestSoFar, initially 0;

For each cell check first what is the best possible matrix using only right and down. If that is more than BestSoFar then check whether that works. If not then try a one smaller if that is still more thank BestSoFar:
BestSoFar:=0;
for i,j:=1 to n do
begin
BestPossible:=Min(B(i,j),C(i,j));
while BestPossible>BestSoFar do
begin
if (C(i,j+BestPossible)>=BestPossible) and (B(i+BestPossible,j)>=BestPossible) then BestSoFar:=BestPossible;
dec(BestPossible);
end;
end;

That's it.

Title: Re: Microsoft Questions
Post by Barukh on Feb 4^th, 2007, 1:46am

This (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1144397342;start=1#1) for the 3rd.