Problem received at an interview for an embedded C programmer position

… 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 4×2, sum in this case is 2

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.


3 Responses to Problem received at an interview for an embedded C programmer position

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

  2. kellogs says:


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: