# Problem received at an interview for an embedded C programmer position

March 5, 2010 3 Comments

… even if this is for an embedded software developer the problem itself has much more to do with algorithms.

So … let’s just don’t waist the time and tackle the problem, it sounds like this:

Given a square matrix of dimension N, as the one below, please implement a C function which has as inputs (parameters) the matrix itself (actually a pointer to the first element, you know what I am talking about) and its size and as output the largest sum of its sub-rectangles. Here some explanations need to be provided, the elements of matrix can be positive or negative integers and a sub-rectangle can have any size from 1×1 to AxB, where A

The matrix is like this (this a 4×4 example, but the algorithm has to be for a generic one, NxN)

A sub-rectangle of this one may be any combination like the one below (the sub-rectangle is is yellow).

It can be of 1×2 size, this one has a sum of 5

or 2×4, sum of this one is 12 (-11+6+3+4+12+0+5+(-7))

or just one single element, as it is 14 in this case

It can’t be something like this, because this is not a rectangle:

Wish you good luck.

PS: I could not solve it at the interview 🙂 (or at least I could not find an *exhaustive *solution) but I made several tries afterwards and some of them proved to be correct, I will post them in the future

What was astonishing to me was that the interviewer also kept saying that this is trivial.

Pingback: A possible solution for the interview problem « Bazaar 2.0

Hello,

may I ask if this interview took place in romania or abroad ?

thanks

Hello,

it took place in Bucharest, Romania. some guys from Johnson Controls Sofia came to Romania in order to find cheap and good Embedded SW engineers 🙂