Author |
Topic: Microsoft Questions (Read 1542 times) |
|
vodangkhoa
Newbie
Posts: 20
|
 |
Microsoft Questions
« on: Jan 31st, 2007, 2:55pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Jan 31st, 2007, 11:37pm by vodangkhoa » |
 IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Microsoft Questions
« Reply #1 on: Jan 31st, 2007, 6:39pm » |
Quote Modify
|
suffix tree for the second.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
|
Re: Microsoft Questions
« Reply #2 on: Feb 4th, 2007, 1:32am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 4th, 2007, 1:34am by jollytall » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Microsoft Questions
« Reply #3 on: Feb 4th, 2007, 1:46am » |
Quote Modify
|
This for the 3rd.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print