Posts tagged array

“Bidirectionally multiplied” array

Jan 22nd

Another small problem before I go to sleep tonight:

There is an array A[N] of N numbers.
You have to compose an array Output[N] such that Output[i] will be equal
to multiplication of all the elements of A[N] except A[i].

For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1]
will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

What is funny of the problem, is the fact that the O(n) constraint, makes it sound like is going to be hard to solve. Doesn’t it? Well, it’s not.

The solution is quite simple, so I suggest you take your 10 minutes to think about it, then continue to see the code. More >

array, bidirectional, code, english, multiplication, problem, simple, solution

Largest square array of same integers

Jan 7th

Posted by Detro in IT / Comp-Sci / Code

No comments

Tonight it’s a challenging one. Or, better, a problem of which is really difficult to find a good solution in < O(n³). Indeed, it’s a question that an ex-colleague was asked during an interview with Big-G.

The guy, a part from being a REALLY smart guy, is also very humble, and he doesn’t want to be mentioned by name. So, sorry for girls looking for a young, smart, promising young man: you need to find who he is yourself.

Problem Definition

Given a 2D array (not necessarily square) of integers 1-9 :
{
 { 8 8 8 8 8 },
 { 8 8 8 8 8 },
 { 8 8 3 8 8 },
 { 8 8 8 5 5 },
 { 8 8 8 5 5 }
}
Return:

The dimension of the largest square consisting of the same integer (in this case 2 because the largest is 2×2 square of 8s).

The integer which appears in that square (in this case

The indices of the top left corner of the square (this this case (0,0) )

If there are multiple squares of the same dimension, you have to return the first one (i.e. the 8 one, not 5).