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.

Advertisements

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:

    Hello,

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

    thanks

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: