We pay for user submitted tutorials and articles that we publish. Anyone can send in a contribution

Learn More-
## Recent Posts

## Editor Pics

## Tags

.Net AJAX alexa Array ASP.Net ASP.NET MVC Binding blog stats C# challenge Class Code Controller DataTemplate earnings Event Free Interface JavaScript job interview jQuery LINQ List MVC page views Posts problem programming question RSS Shortcuts Silverlight Software SQL stats string Tool Traffic visits Visual Studio Web Window WPF Xaml Xml

By Shahar Y

This is the fourth post in the series of programming job interview challenge. Today, I will provide the answer to job interview challenge #3, talk about readers answers (all of the comments are now approved) and give you a new challenge. So, lets get into business:

**The correct answer to challenge #3:**

- Start with the lower left cell (first column, last row).
- If the value matches, you’re done.
- If the searched value is bigger than the current cell, go right. That way an entire column is eliminated (all of the values left in that column are lower than the searched value). If you can’t go right – the searched value is not in the matrix.
- If the searched value is smaller than the current cell, go up. That way an entire row is eliminated (all of the values left in that row are bigger than the searched value). If you can’t go up – the searched value is not in the matrix.
- Go back to 2.

Take a look at the example and assume we are looking for 11. As described, start with the lower left cell which contains number 8, because 11 is bigger than 8 – go right. 11 is bigger than 9 – go right, 11 is smaller than 17 – go up, 11 is smaller than 12 – go up, 11 is bigger than 9 – go right, 11 is smaller than 12 – go up, 11 is bigger than 10 – go right. 11 is found!** **The complexity of that solution is **O(m+n)** because the worst case scenario would be to search along an entire row and an entire column. This question could be also solved by starting from the upper right cell and going to the opposite directions so the winners are: **Tristan**, **David**, **Marcos Silva Pereira** and **Anton Irinev**.

**Other Solutions:**

Due to the fact that we received a lot of answers, I won’t be able to refer to each one of them. Instead, I will try to categorize some of the answers and relate to bunches of solutions. The first category is **“The complexity is not as good as O(m+n)”** so its obvious why those are not the “winners”.

This little 3X3 example matrix is for the **“Start from the upper-left corner”** category. If you start searching from that corner, you won’t be able to find number 5. Those who best described these kind of solution wrote “Move to the cell which has a greater value but is not greater than the search value”, so the path would be: 1 -> 4 -> Value not found in the matrix, which is wrong.

Another category is the **“Two-dimensional recursive binary search”** (I don’t want to mention names in that section, so look in the comments for the full algorithms). Although those solution are correct, their complexity is not as good as some of the readers thought. It took me half a day of wondering about those solution to realize that there is a basic wrong assumption in all of them. They all split the matrix into two other smaller matrixes and so on (recursively). The problem is that you may end up with rectangular matrixes (or even begin with such matrix, I said it is mXn matrix), and that is where those solutions fail. Just take a look at the following matrix – trying to find 14 will lead you to search the whole matrix… and the complexity would be O(mXn).

The only one who posted his solution in his blog – Adam’s Tech Thoughts is **Adam B **so I have to refer to his solution too. Adam, you will fail to find 12 in the example matrix to the left.

All of the other commentators: please accept my apologizes if I didn’t cover your solution. If you still think that you provided a better solution, just let me know (with an explanation).

One lesson I learned from the previous post is that it is very hard to read an undocumented code. Some of the readers provided code without any explanation and it is very difficult to understand whether their solution is correct or not. So, **next time please avoid sending code without any explanations**.

**This weeks question:**

How would you implement the following method: Foo(7) = 17 and Foo(17) = 7. Any other input to that method is not defined so you can return anything you want. Just follow those rules:

- Conditional statements (if, switch, …) are not allowed.
- Usage of containers (hash tables, arrays, …) are not allowed.

I must admit that I wouldn’t ask this weeks question in a job interview, but it is a really nice question. Because last weeks challenge was difficult, I am providing you with a little **“fun”** challenge that is more of an experiment than a job interview. This is not a real world problem but it does check how simple can we think, so think - **simplicity!** I believe that all of your answers will be correct, but it will be interesting to see how simple will they be.

Reminder: **Comment with answers will not be approved until next weeks challenge** (if readers will see the correct answer in one of the comments, it will become pointless).

The answer is now provided in Challenge #5 (Record Sorting)

Tags :

answerchallengecorrecteficienthi techimagesjob interviewpixelproblemprogrammingquestionsolution- May 22, 2008: Programming Job Interview Challenge « Jendrik Illner’s Blog
- May 23, 2008: Programming Interview Question #4 from Dev102 at KeithRousseau.com
- May 23, 2008: Honest Illusion : DEV102's Programming Job Interview Challenge #4
- May 26, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #5 - RECORDS SORTING | Dev102.com

Copyright © 2012 Dev102.com

Breeze : Designed by Amit Raz and Nitzan Kupererd

Kirill SorokinSaid on May 19, 2008 :

Foo(x) {

return 24 – x;

}

Foo(7): 24 – 7 == 17

Foo(17): 24 – 17 == 7

Essentially, as far as I understand, this can be generalized to an arbitrary number of [x, y] pairs. One would just need to build a polynomial, which passes through all these points. In case of two points, this defines a straight line.

MarianoSaid on May 19, 2008 :

int foo(int num){

return (12-num)+12;

}

JacekSaid on May 19, 2008 :

function Foo(i)

{

return 24 – i;

}

Brian CanzanellaSaid on May 19, 2008 :

How about this…

static int Foo(int i)

{

return 119/i;

}

BrunoSaid on May 19, 2008 :

This one is too easy.

Foo(x)=(x+10)%20

For x=7, we have Foo(7)=17%20=17

For x=17, we have Foo(17)=27%20=7

Bruno

dreaSaid on May 19, 2008 :

In Python…

def foo(n):

a = -10 * (n / 10) # integer division

return a + 17

print foo(7), foo(17)

>>>

17 7

MennoSaid on May 19, 2008 :

Do I not understand the challenge or is the solution (JavaScript):

function Foo(x) {

return 24 – x;

}

Which of course returns 7 for x=17 and 17 for x=7.

Or even simpler (JavaScript 1.8)

function Foo(x) 24 – x;

Chris JobsonSaid on May 19, 2008 :

Solution to challenge #4:

Foo(x) = 24-x

Poul Foged NielsenSaid on May 19, 2008 :

int foo(int x)

{

return 24-x;

}

Timea AlbertSaid on May 19, 2008 :

My first idea is the following:

int foo(int x){

return (x + 10) % 20;

}

Is that simple enough? I’ll try to think of other solutions as well.

Anton IrinevSaid on May 19, 2008 :

// idea: mathematical operations

static int Foo(int input)

{

return (24 – input);

// (119 / input) with try-catch, etc.

}

// idea: strings

static int Foo(int input)

{

string str = input.ToString().Replace(“7″, “17″).Replace(“11″, “”);

int result = 0;

int.TryParse(str, out result);

return result;

}

// idea: binary representation

static int Foo(int input)

{

return 22 ^ input;

}

EricSaid on May 19, 2008 :

foo(x) = 24 – x

foo(7) = 17

foo(17) = 7

pavan kumarSaid on May 19, 2008 :

func(inputValue){

return (24-inputValue)

}

Rob GuestSaid on May 19, 2008 :

int foo(int x) {

return Math.abs(x – 24);

}

Kristoffer EdvinssonSaid on May 19, 2008 :

Foo( i ) {

return ( i + 10 ) % 20;

}

dreaSaid on May 19, 2008 :

Then again…

def foo(n):

return 24 – n

Damned simplicity ;o)

JustinSaid on May 19, 2008 :

Simplest I can come up with is (OCAML)

let func x = 7 + 10 * ( 7 / x mod 10)

Henry FiegerSaid on May 19, 2008 :

public int Foo(int i)

{

return (i + 10) Mod 20;

}

Hmm...Said on May 19, 2008 :

int Foo(int x)

{

return (x + 10) % 20;

}

… I know – no comments, but I guess it is … simple.

ShahriarSaid on May 19, 2008 :

Hi dear. Would You Explain “foo” word To We?

Thanks.

HahaSaid on May 19, 2008 :

And simpler:

int Foo(int x)

{

return 24 – x;

}

I have to admit. At first I was bored, now I am actually laughing at myself – for not thinking simple enough.

JonathanSaid on May 19, 2008 :

int Foo(int x) { return 24-x; }

More data points would just result in a more complicated formula. For N input/output values, a polynomial of degree N-1 can be constructed that will yield the desired values.

Shahar YSaid on May 19, 2008 :

Hi Shahriar,

Foo is a common name for sample methods and classes – take this following MSDN page: http://msdn.microsoft.com/en-us/library/aa479030.aspx and search Foo in it…

BTW – after 5 hours, there are already 19 comments with answers (which are not approved yet)

Chris HSaid on May 19, 2008 :

int Foo(int n) { return (24 – n); }

Jason KikelSaid on May 19, 2008 :

in ruby

def Foo(arg)

“1#{arg}”.sub(/11/,”)

end

configuratorSaid on May 19, 2008 :

Obviously,

Foo(x) = 24 – x

Amrinder SandhuSaid on May 19, 2008 :

int foo(int x)

{

return 24 – x;

}

Jose M. AguilarSaid on May 19, 2008 :

Just a low-tech solution:

public int foo(int a)

{

for (int i = a + 10; i 6; ) return i;

return 0;

}

Jose M. AguilarSaid on May 19, 2008 :

I think my previous comment had html entities, so it couldn’t be viewed properly. Another try:

private static int display(int a)

{

for (int i = a + 10; i < 18; ) return i;

for (int i = a – 10; i > 6; ) return i;

return 0;

}

Joe McFallSaid on May 19, 2008 :

Here’s the simplest solution I can think of:

int Foo(int input)

{

// 7 * 17 = 119

// so divide 119 by input

return 119 / input;

}

Henning BSaid on May 19, 2008 :

In standard C:

int foo( int n )

{

return n ^ 0×16;

}

Igor OstrovskySaid on May 19, 2008 :

I’d say that this solution is pretty simple:

int Foo(int x) { return 24 – x; }

eiroSaid on May 19, 2008 :

hi

the answer is:

public int Foo(int number)

{

return number ^ 22;

}

regards

cowardlydragonSaid on May 19, 2008 :

It is possible to design a binary search for each rowsearch performed that would beat linear for large datasets. In your worst-case scenario, binary search would finish in two operations searching for 14.

challenge 4 is a simple add and modulus.

(x+10) % 20 should do it

AlexSaid on May 19, 2008 :

The super-mega-naive-”don’t worry about what happens with any input outside of 7 and 17″ answer: It’s a simple toggle.

public int foo(int input)

{

return (24 – input);

}

Jon von GillernSaid on May 19, 2008 :

Easy enough

http://www.vonsharp.net/ProgrammingJobInterviewChallenge4Answer.aspx

public int Foo(int x)

{

return -1 * x + 24;

}

Chad MyersSaid on May 19, 2008 :

I want to make sure I understand the Foo(7) = 17 and Foo(17) = 7 requirement, because in C# language, that means something very different from what I think you’re trying to say. Would the following NUnit test better represent the requirements?

Assert.That(17 == Foo(7));

Assert.That(7 == Foo(17));

That’s what I’m working towards.

Also, by conditionals, I assume you also mean the ?: operator, right?

Shahar YSaid on May 19, 2008 :

Hi Chad Myers,

You are absolutely right, I should have written == instead of =

About the ?: operator – you are right again…

Another update – after 7 hours, there are already 33 comments with answers (which are not approved yet)

eiroSaid on May 19, 2008 :

hi,

another version, but not so clean as XOR 22:

public int Foo(int number)

{

return Convert.ToInt32(number.ToString().PadLeft(2, ‘X’).Replace(’1′, ’0′).Replace(‘X’, ’1′));

}

regards

Maciej LotkowskiSaid on May 19, 2008 :

def foo(arg)

arg == 17 && 7 || 17

end

verborghsSaid on May 19, 2008 :

public class Test {

public static void main(String[] args) {

int x = Integer.parseInt(args[0]);

System.out.println(“in: ” + x);

int y = (~x)+25;

System.out.println(“out: ” + y);

}

}

Markus PointnerSaid on May 19, 2008 :

ruby:

def foo(n)

n ^ 22 # ‘^’ => XOR

end

i thought that i’d have to limit the number of bits involved, but it works even without doing it.

Robert 'Groby' BlumSaid on May 19, 2008 :

Hm. How about our good old friend, the modulo function…

Let’s define foo(x) as (x+10) mod 20

foo(7) = 17 mod 20 = 17

foo(17) = 27 mod 20 = 7

Simple enough?

CarinaSaid on May 19, 2008 :

I’d say

function Foo(x){

return 24-x;

}

But I guess I’m just overlooking something in the question. Tht seems a little bit *too* simple to me

MooglegiantSaid on May 19, 2008 :

Well, since no other input is defined. we know these two given input and will just use simple math to solve.

in which case are formula is ((x1 * x2) / x1)-1

so the function will look like this, sort of:

Foo(int x)

{

//119 is the product of 7 and 17

return ((x + 119)/x)-1;

}

granted, every other input would give a wierd answer, but we don’t care since its not defined.

Though it would crash if x was 0.

RandomSaid on May 19, 2008 :

xor 22

mdubSaid on May 19, 2008 :

abs(x-24)

JakeSaid on May 19, 2008 :

Quick Clarification:

Are loops allowed?

Peter RSaid on May 19, 2008 :

def foo(x)

return (x + 3) % 20 + 7

someoneSaid on May 19, 2008 :

Answer:

x + (((8 – x) / abs (8 – x))) * 10

Shahar YSaid on May 19, 2008 :

Jake,

You can use loops, but I can assure you that you don’t really need them here.

Chad myersSaid on May 19, 2008 :

Ok, here’s the dirt simplest answer I can come up with that meets the requirements:

private static int Foo(int i)

{

return Convert.ToInt32(

(i – 10 + “”).Replace(“-3″, “17″)

);

}

AdrianSaid on May 19, 2008 :

Foo(int x) { return x ^ 22; }

KimSaid on May 19, 2008 :

int f(int x)

{

return 24-x;

}

Josh GoldieSaid on May 19, 2008 :

//

// For input of 17, function evaluates to (Sign(17-17) * 17) + (Sign(17-7) * 7) = (0 * 17) + (1 * 7) = 7

// For input of 7, function evaluates to (Sign(17-7) * 17) + (Sign(7-7) * 7) = (1 * 17) + (0 * 7) = 17

//

static int Foo(int i)

{

return ((Math.Sign(17 – i) * 17) + (Math.Sign(i-7) * 7));

}

NikiSaid on May 19, 2008 :

How about int Foo(int x) { return 17+7-x; } I wonder if you can do it simpler than that?

CatweazleSaid on May 19, 2008 :

int Foo(int input) {

return (input ^ 7 ^ 17);

}

(where ^ means XOR)

EddieShenSaid on May 19, 2008 :

In this case, I believe submitting the code is good enough…

psuedo code for foo:

foo(i)

return i ^ 0×17 + 1;

0×17 = 0001 0111 = 23

xor 7 with 0×17 and u get 16

xor 16 with 0×17 and u get 6

Eddie ShenSaid on May 19, 2008 :

Update on the solution I posted:

return (i ^ 0×17) | 0×01;

Don’t see how it can get any faster than this

Trung DinhSaid on May 19, 2008 :

Foo(x) {

return x == 7 ? 17 : 7;

}

vaporettoSaid on May 19, 2008 :

public static int Foo(int z)

{

return Math.Abs(10 – z) / (10 – z) * 10 + z;

}

Cheers,

Vapo

Steve BarhamSaid on May 19, 2008 :

That seemed a bit easy…

class FooTest {

public static void main(String[] args) {

System.out.println(Integer.toString(foo(Integer.parseInt(args[0]))));

}

static int foo(int input) {

return Math.abs(input – 24);

}

}

Although I’m guessing you’re looking for something a bit more involved

Trung DinhSaid on May 19, 2008 :

Another solution not requiring ? : operator.

int Foo(int x) {

return (x + 10) % 20;

}

Guy GervaisSaid on May 19, 2008 :

Result = 24 – X

Trung DinhSaid on May 19, 2008 :

Even simpler solution:

int Foo(x) {

return 23 – x;

}

Trung DinhSaid on May 19, 2008 :

Typo in my last answer. Should read:

int Foo(int x) {

return 24 – x;

}

Ken SnyderSaid on May 19, 2008 :

// Yes, MS Excel taught me something about programming

function foo(num) {

return (intval(num == 17) * 7) + (intval(num == 7) * 17);

}

JakeSaid on May 19, 2008 :

Both of these numbers are just a series of zeros and ones:

7: 00000111

17: 00010001

^ ^^

And they only differ at three different places. All we have to do is flip those bits in our input, and we have the right answer.

There’s the XOR (eXclusive OR) operator. It shows us which bits are different between two numbers:

7: 00000111

17: 00010001

^ ^^

7 xor 17 00010110 (the bits that change)

XOR is also reversible: a xor b xor b == a

and associative and commutative: a xor b xor b = b xor a xor b == b xor b xor a == a

So:

(7 xor 17) xor 7 is 17 and

(7 xor 17) xor 17 is 7

In C-like languages, the xor operator is written as the caret symbol (^). In other languages, you’re on your own.

int Foo(int x)

{

return (17 ^ 7) ^ x;

}

Trung DinhSaid on May 19, 2008 :

Ok. Got to throw another “simple” answer in.

Foo(x) { return 119 / x; }

Daniel GarySaid on May 19, 2008 :

function foo(x)

{

return 24 – x;

}

VladSaid on May 19, 2008 :

Hi!

Foo(x) = 24 – x;

regards,

Vlad

Trung DinhSaid on May 19, 2008 :

Last one. I promise.

Foo(x) { return x ^ 0×16; }

GrundlefleckSaid on May 19, 2008 :

If there’s anything simpler I’ll be shocked:

public int foo( int x ){

return ( x + 10 ) % 20;

}

Grundlefleck

cubeSaid on May 19, 2008 :

return (input + 10) % 20

AsimSaid on May 19, 2008 :

Way to easy; stick to CS questions =).

Here it is in Python:

>>> def Foo(n):

… return (n+10) % 20

…

>>> Foo(7)

17

>>> Foo(17)

7

>>>

KevinSaid on May 19, 2008 :

Solution (in VB.NET):

Function Foo(ByVal pnNumber As Integer) As Integer

Return 17 – (10 * (pnNumber.ToString.Length – 1))

End Function

For Foo(7), this yields 17 – (10 * 0) = 17

For Foo(17), this yields 17 – (10 * 1) = 7

Jonathan GilbertSaid on May 19, 2008 :

int Foo(int x) { return x ^ 22; }

or:

int Foo(int x) { return 24 – x; }

or:

int Foo(int x) { return (x + 10) % 20; }

Anything else that I can think of is just a convolution of one of the above.

Marc BollingerSaid on May 19, 2008 :

I can’t tell offhand how everyone else has done it, but hopefully this way is novel enough. The first I did was write out the bit patterns of 7 and 17, and after a couple minutes’ worth of scribbling came up with the following (noting that we’re only working on a field of 5 bits for rotate and reverse):

- invert bits

- rotate bitwise (bit-width of 5, e.g. 11000 -> 10001)

- reverse bit ordering (this only really requires two bit swaps: most/least significant bits, and 2nd most/ 2nd least significant bits)

which yielded the following C code:

int foo(int var)

{

char i;

var = ~var;

/* Rotate 1 bit to the left (on a 5-bit field) */

var <> 5);

/* Swap Most/Least sig. bits */

i = (var & 16) >> 4;

var = var & ~16 | ((var & 1) <> 2;

var = var & ~8 | ((var & 2) << 3) | i;

return 31 & var;

}

Of course, there went the simplicity right out the window. So then I sat down and noticed it was even easier than that, since generalizing doesn’t buy us anything:

- invert bits

- set bit 1 (1-based, counting from least sig.)

- unset bit 4

int foo2(int var)

{

var = ~var;

var |= 1;

var &= 31 & ~8;

return var;

}

Yikes. Much easier!

Chris MillerSaid on May 19, 2008 :

public int Foo(int in) {

return in ^ 22;

}

It’s trivial to determine the “magic number”, since:

if a XOR b = c

then a XOR c = b

and b XOR c = a

Since 7 ^ 17 = 22 it follows that 7 ^ 22 = 17 and 17 ^ 22 = 7

NickSaid on May 19, 2008 :

The answer is rooted in basic algebra. Given 2 points (7,17) and (17,7) we find the formula of the line through these points to be f(x)= -x + 24 . This is translated to a programming function as follows. I’m very interested to see if someone comes up with an even simpler solution.

python…

def foo(x):

return -x + 24

c#…

public int foo(int x)

{

return -x + 24;

}

SvenSaid on May 19, 2008 :

Hi Shahriar,

I’d go for this:

int Foo(int x) {

return x * -1 + 24;

}

I hope this does not need any extra explanation :-).

Just found this mentioned on dzone, very nice idea!

Greetings,

Sven.

Goran JSaid on May 19, 2008 :

I tried to use loops but at the end they all end with:

Foo(x)=24-x

Abou OsamaSaid on May 19, 2008 :

// C# Code:

double Foo(double x)

{

return 24 – x;

}

Mark HeathSaid on May 19, 2008 :

public static int Foo(int input)

{

return (input + 10) % 20;

}

PaulSaid on May 19, 2008 :

def Foo(n)

return n^22

end

KimmenSaid on May 19, 2008 :

Foo(int n)

{

return (n + 10) % 20;

}

LorenSaid on May 19, 2008 :

Don’t overthink this one. Remember your high school math and connecting two points on a line.

Foo(x) {

return -x + 24;

}

JustinSaid on May 19, 2008 :

Here is an answer I beleive:

If the substring is out of range, you get an exception and you know the param passed in is only one digit 7, otherwise its 17

private static int test(int i)

{

try

{

i.ToString().Substring(1, 1);

return 7;

}

catch (ArgumentOutOfRangeException)

{

return 17;

}

}

AmjithSaid on May 19, 2008 :

int Foo(int n)

{

return (24-n);

}

Mykola DzyubaSaid on May 19, 2008 :

Here is the answer to the Foo(7) = 17 and Foo(17) = 7 question:

public int foo(int x) {

double n = (17.0*17.0 – 49.0)/10.0;

double k = (17.0 – n) / 7.0;

double y = k * x + n;

return (int) y;

}

Here is a JUnit test for it:

public void testFoo() {

int t1 = test.foo(7);

assertEquals(17, t1);

int t2 = test.foo(17);

assertEquals(7, t2);

}

Igor KarpSaid on May 19, 2008 :

int Foo(int x) { return 7 + 17 – x;}

JamesSaid on May 19, 2008 :

My Answer:

function foo(value) {

return -(value – 24);

}

MrSquirrelSaid on May 19, 2008 :

int foo(x) {

return (-1 * x) + 24;

}

Kia KroasSaid on May 19, 2008 :

Sorry to be a spoiler but this is basic math:

f(x) = -x + 24

f(7) = -7 + 24 = 17

f(17) = -17 + 24 = 7

Eddie ShenSaid on May 19, 2008 :

I already submitted, but if code readability is an issue, this solution may be better:

foo(i):

return (i + 10) % 20;

I still like my first solution due to perf optimizations though.

SamSaid on May 19, 2008 :

This would require me to think, so I won’t participate–but it is interesting to skim

Eric LarsonSaid on May 19, 2008 :

So, I’m not sure if this is what you mean by simplicity, but …

def foo(x):

// 7 + 17 = 24 so…

return 24 – x

Is that what you were looking for?

Peter RSaid on May 19, 2008 :

def(x):

return x ^ 22

tkshSaid on May 19, 2008 :

xor with 22

efrainSaid on May 19, 2008 :

foo(x)

{

return 7 + (17 – x);

}

JustinSaid on May 19, 2008 :

int foo(int x) {

return (x^0×0016);

}

abhikSaid on May 19, 2008 :

foo = lambda x: (x+10) % 20

Mark SmithSaid on May 19, 2008 :

public int Foo(int n){

return n + 10 – ((n / 10) * 20);

}

or

public int Foo(int n){

return 7 + ((n/10)^1) * 10;

}

Phillip JacobsSaid on May 19, 2008 :

public static int Foo(int x)

{

return Math.Abs((x+25) ^ 1);

}

Phillip JacobsSaid on May 19, 2008 :

public static int Foo(int x)

{

return ~(x)+25;

}

DavidSaid on May 19, 2008 :

public int Foo(int x){

return 24-x;

}

Jamie PenneySaid on May 19, 2008 :

I’ve come up with the following:

public int Foo(int input)

{

return input – ((int)(input/10))*20 + 10;

}

That should work in C#, although I haven’t actually tried to compile it. The middle section should be rounded down to 0 for input = 7 and down to 1 for input = 17. So for each input you get the following:

7 – 0*20 + 10 = 17

17 – 1*20 + 10 = 7

Thanks for the interesting question, gave me something to think about over my lunch break

Kevin Q.Said on May 19, 2008 :

OK, this seems like a simple polynomial interpolation problem. Given two data points (7,17), (17,7), now find a first degree polynomial (which is a straight line) such that f(x)=y.

m = (y2-y1)/(x2-x1) = -1

y-7=-(x-17) =>

y=-x+24

def Foo(num):

return -1 * num + 24

Done!

Amrinder SandhuSaid on May 20, 2008 :

Another solution: Use XOR

int foo(int x)

{

return (17 ^ 7) ^ x;

}

Mark BradshawSaid on May 20, 2008 :

int foo(int i) {

return 24-i;

}

Johnny YeSaid on May 20, 2008 :

Foo(x){

return (1-x/10)*10+7

}

CedricSaid on May 20, 2008 :

return (arg+10)%20

Dmitry S.Said on May 20, 2008 :

int foo(int x)

{

return Math.Abs(x-24);

}

MikiMSaid on May 20, 2008 :

public int foo(int value) {

return 24 – value;

}

AntonioSaid on May 20, 2008 :

Pseudocode

Foo(bar)

{

bar = Format(bar, “##”)

bar = Replace(bar, “1″, “X”)

bar = Replace(bar, “0″, “Y”)

bar = Replace(bar, “X”, “”)

bar = Replace(bar, “Y”, “1″)

return bar

}

Marcos Silva PereiraSaid on May 20, 2008 :

The Groovy Code:

def foo(num) {

int mul = (num – 10)/Math.abs(num – 10)

return num – (10 * mul)

}

Kind Regards

stephenSaid on May 20, 2008 :

int foo(int n) {

return (17 + 7) – n;

}

CompuboySaid on May 20, 2008 :

Foo(input) = 17 + 7 – input

C# Code:

public int Foo(int input)

{

return 24 – input;

}

JyriSSaid on May 20, 2008 :

public int foo(int x) {

return Math.abs(x – 24);

}

SwedishFishSaid on May 20, 2008 :

int Foo(int x) { return 24 – x; }

atin soodSaid on May 20, 2008 :

hmm.. u said itz more of a fun challenge.. so m expecting my ans(though pretty stupid) might be right …..

public class Testing {

public static void main(String[] args) {

System.out.println(function(7));

System.out.println(function(17));

}

private static int function(int number){

return 24 – number;

}

}

MaartenSaid on May 20, 2008 :

My answer to your problem #4 would be:

Foo(x) = 24-x

In C# (quickly typed, not compiled & checked)

public static class HelperClass {

public static int Foo(int x) {

return 24 – x;

}

}

Jose M. AguilarSaid on May 20, 2008 :

I have optimized my previous version:

private static int display(int a)

{

for (int i = a + 10; i < 18; ) return i;

return 7;

}

But remember:

“optimization is the root of all evil.”

Knuth, Donald

christianSaid on May 20, 2008 :

Here is my solution

I must admit I had to think about a solution without using any conditional statements, nor libs that take use of them. But it was fun finding a solution.

It works, but I really wonder what simple solution you have prepared for us.

You can also write it all in one line of code, but it does not realy make it readable:

public static double f(double n) {

// 7:7=1 -> f will be 1

// whereas 17:7 must be exactly 2 higher (therefore 3). -> f will be -1

// the trick is that the difference between the values of the divison is exactly 2.

double f = ((Math.ceil(n / 7.0d)) – 2) * -1;

// f defines, if 10 will be added or subtracted

return n + f * 10;

}

David SteeleSaid on May 20, 2008 :

I dont know why but I have a feeling I should be doing this in c#, but since I couldnt find any rules I’m posting in vb.

Sub Main()

Console.WriteLine(Foo(7))

Console.WriteLine(Foo(17))

Console.WriteLine(Foo(1))

Console.WriteLine(Foo(11))

Console.ReadLine()

End Sub

Private Function Foo(ByVal InputValue As Integer) As Integer

Return (Math.Abs(CInt(Not (InputValue > 10))) * 10) + InputValue Mod 10

End Function

This solution will also provide similar behaviour for any number 11 – 19. The same solution will not work in c# as boolean to int conversions are not allowed.

Regards

David Steele

Jacob SeleznevSaid on May 20, 2008 :

int Foo(int n){ return 24 -n; }

HarshSaid on May 20, 2008 :

Did you mean that passing 7 to Foo() returns 17 and vice-versa?

If this is the case:

Foo(int n)

{

return -( n – 17 – 7 )

}

pavanSaid on May 20, 2008 :

func(input){

return (24-input);

}

Antony RajSaid on May 20, 2008 :

Hi Guys,

I guess, The following will solve your problem. The implementation is in java.

public int Foo(int s){

return s ^ 15;

}

Antony RajSaid on May 20, 2008 :

Hi, I guess following would be answer for your question.

public void int foo(int i){

return i ^ 15 ;

}

AntonySaid on May 20, 2008 :

Hi, I guess following would be answer for your question.

public void int foo(int i){

return i ^ 15 ;

}

Jonas Christensen.Said on May 20, 2008 :

Think it cant be more simple than this.

return 24 – n;

Dan SSaid on May 20, 2008 :

Foo(x) = (x + 10) mod 20

Sebastian USaid on May 20, 2008 :

If you think of the values as points (in 1-dimensional space), swapping two values is just point reflection across their arithmetic mean.

Using http://en.wikipedia.org/wiki/Point_reflection:

p = (7 + 17) / 2 = 12

int Foo(int x)

{

return 24 – x;

}

OmarSaid on May 20, 2008 :

Hi nice question, here’s what I have:

7 : 0 0 0 0 0 1 1 1

17: 0 0 0 1 0 0 0 1

XOR with 22 will swap between the two

22: 0 0 0 1 0 1 1 0

so (not sure what the .net syntax is exactly):

int foo(int n)

{

return (n xor 22);

}

PeteSaid on May 20, 2008 :

foo(n) = 17 + 7 – n

foo(n) = 17 * 7 / n

foo(n) = 17 ^ 7 ^ n (if ^ is xor)

Shai OnSaid on May 20, 2008 :

return 24-x;

OJSaid on May 20, 2008 :

In C:

int Foo(int f) { return f ^ 22; }

fooSaid on May 20, 2008 :

fun Foo x = 24 – x;;

HarryCSaid on May 20, 2008 :

The sum of 17 + 7 is 24, so it’s simple arithmetic to get the other back given the one:

int foo( int i )

{

return 24 – i;

}

Vivek KanalaSaid on May 20, 2008 :

foo(x){

return 24-x;

}

SisoSaid on May 20, 2008 :

Hi,

I’d say:

BYTE Foo( BYTE x ) {

return x ^ (BYTE)0×16;

}

The 0×16 == 22 == 17 ^ 7

cz35iekSaid on May 20, 2008 :

foo(x):

return (x+10) mod 20

Kener LipscombSaid on May 20, 2008 :

public int foo(int x)

{

try

{

x = 1 / (x.ToString().Length – 1);

return 7;

}

catch (DivideByZeroException e)

{

return 17;

}

}

Chaz AndrewsSaid on May 20, 2008 :

Sorry, I dont have a blog, but here’s my answer:

int function Foo(int a){

return 144-(12*a);

}

TristanSaid on May 20, 2008 :

Wow, I am surprised at how many people went for the binary search approach.

When I first looked at the problem it seemed obvious to me that I had the solution, then i tried binary search, quickly realizing that nlogn is slow, and went back to the linear approach.

TristanSaid on May 20, 2008 :

i am assuming this is just a simple xor…

17 in bits is 10001 and 7 is 00111.

so if we xor with 22(10110) 17 will become 7 and 7 will become 17.

function foo(input){

return (input XOR 22)

}

Heiko HatzfeldSaid on May 20, 2008 :

Ok… Here are a few solutions…

I hope you dont find this to crazy… I could g on and Add configuration files, databases etc… But thats to much to setup So here are some “code only” solutions

Enjoy…

—————

/*

* Created by: hathei

* Created: 20 Mai 2008 00:00

*/

using NUnit.Framework;

using System;

using System.Reflection;

namespace ClassLibrary1

{

[TestFixture]

public class Interview4

{

private readonly int mask = 7185;

enum results

{

result7 = 17,

result17 = 7

}

private int[] resultArray = {17, 42, 42, 42, 42, 42, 42, 42, 42, 42,7};

[Test]

public void Verify_Functions()

{

Assert.AreEqual(Xor(7), 17);

Assert.AreEqual(Xor(17), 7);

Assert.AreEqual(Shift(7), 17);

Assert.AreEqual(Shift(17), 7);

Assert.AreEqual(ExceptionCheat(7), 17);

Assert.AreEqual(ExceptionCheat(17), 7);

Assert.AreEqual(enums(7), 17);

Assert.AreEqual(enums(17), 7);

Assert.AreEqual(ArrayFunction(7), 17);

Assert.AreEqual(ArrayFunction(17), 7);

Assert.AreEqual(Reflect(7), 17);

Assert.AreEqual(Reflect(17), 7);

Assert.AreEqual(Reflect(99), 42);

}

///

/// Uses a lookup array. The results are prefilled, and I just fetch the ones I need.

/// Using % to prevent the use of try/catch if i am outside of the array bounds. The

/// Exceptions that where saved here will be reused later on

///

/// The input.

///

private int ArrayFunction(int input)

{

return resultArray[input-7 % 10];

}

///

/// Uses Exceptions as control flow.

/// This is cheating

///

/// The input.

///

private int ExceptionCheat(int input)

{

int dummy;

try

{

dummy = 1 / (7 – input);

}

catch (Exception)

{

return 17;

}

try

{

dummy = 1 / (17 – input);

}

catch (Exception)

{

return 7;

}

return 42;

}

///

/// Uses a predefined Bitmask (7185 = 1110000010001)

/// It is shifted N-7 Places to the right, and then

/// all but the last 5 bits are masked

///

/// The input.

///

private int Shift(int input)

{

try

{

return mask >> (input – 7) % 18 & 31;

}

catch (Exception)

{

return 42;

}

}

///

/// I think this is the Solution you wanted…

///

/// The input.

///

private int Xor(int input)

{

return input ^ 22;

}

///

/// Uses an Enumeration that defines the requiered results.

///

/// The input.

///

private int enums(int input)

{

try

{

return (int)Enum.Parse(typeof(results), “result” + input);

}

catch (Exception)

{

return 42;

}

}

///

/// Reflects the specified input and gets a class that contains the correct result….

///

/// The input.

///

private int Reflect(int input)

{

IResult result;

Type t = Type.GetType(“ClassLibrary1.Interview4+Result” + input) ?? typeof(ResultDefault);

result = (IResult) Activator.CreateInstance(t);

return result.result;

}

private class ResultDefault : IResult

{

public int result

{

get { return 42; }

}

}

private class Result7:IResult

{

public int result

{

get { return 17; }

}

}

private class Result17 : IResult

{

public int result

{

get { return 7; }

}

}

}

internal interface IResult

{

int result { get;}

}

}

Heiko HatzfeldSaid on May 20, 2008 :

Edit… Ooops… I overlooked the restiction on arrays.. So i guess I am down to 5 possible solutions only

Kener LipscombSaid on May 20, 2008 :

Like this one liner better than my first:

public int foo(int x)

{

return ((((x.ToString().Length-2)*2)+1)*-10)+x;

}

MarkSaid on May 20, 2008 :

return Math.Abs(int.Parse(foo.ToString(“00″)[0].ToString()) – 1) * 10 + 7;

DaveSaid on May 20, 2008 :

Func Foo = i => “hhhhhhh17hhhhhhhh7h”.Substring(i, “hhhhhhh17hhhhhhhh7h”.Substring(i).IndexOf(“h”));

A bit weird, but more fun than the:

Replace(“7″, “17″).Replace(“11″, “”);

Method.

Dave

DanSaid on May 20, 2008 :

I’ll take your “simplicity” hint to heart:

int Foo(int i)

{

return 119 / i;

}

Igor KarpSaid on May 20, 2008 :

I believe the #3 analysis is incomplete. I would not write off binary search completely. In the case where m=1 the “correct” solution above will give you O(n) time while binary search will deliver at O(log(n)).

The applicability of binary search could actually be extended beyond this case. Let’s use this algorithm: use binary search for each row. Then complexity will be O(m*log(n)). This is better than O(m+n) for m < n/(C*log(n)).

Therefore repetitive binary search is better for comparatively flat (or thin) matrices

Csaba TruczaSaid on May 20, 2008 :

Here is my take on the challenge. Includes discussion on simplicity.

http://notesonprogramming.blogspot.com/2008/05/many-faces-of-simplicity.html

AvishkarSaid on May 20, 2008 :

int foo(int a) {

return (a+10)%20;

}

KimmenSaid on May 20, 2008 :

Why don’t I keep it simple? The solution is of course:

public int Foo(int n)

{

return 24 – n;

}

Shahar YSaid on May 20, 2008 :

Igor Karp,

m+n is linear while mlogn is not, so linear is faster!!

According to your approach O(mXn) is better than O(m+n) because if m=n=1 than mXn=1 but m+n=2, while It is obvious that O(m+n) is better…

Tim KingtonSaid on May 20, 2008 :

How about this?

int f(int x) {

return x – (2 * (x – 12));

}

Don MarchSaid on May 20, 2008 :

>> def foo(number)

>> (number + 10) % 20

>> end

>> foo(7)

=> 17

>> foo(17)

=> 7

bob smithSaid on May 20, 2008 :

In this week’s challenge, are you also disallowing conditional expressions? ( ? : )

Shahar YSaid on May 20, 2008 :

Hi bob smith,

Yes, conditional expressions are disallowed.

MrSquirrelSaid on May 20, 2008 :

Hint: Solve y=mx+b for the line that goes through points 17,7 and 7,17. The resulting solution becomes the one line of code in your program.

Kevin HSaid on May 20, 2008 :

simple answer:

fn(x) return 24 – x

And I still think that there is an O(lgn + lgm) solution to #3, just that I had a slight problem with what I posted. I’ll implement an actual solver instead of doing pseudocode and make a diagram for it.

Mike DunkerSaid on May 20, 2008 :

Look at the bits for 17 and 7 (00010001 and 00000111). For bits that match, XOR that bit with 0. For bits that do not match, XOR that bit with 1 (which will flip the bit).

You just need to XOR the incoming value with 22 (00000111 XOR 00010110 = 00010001, and 00010001 XOR 00010110 = 00000111).

Greg YoungSaid on May 20, 2008 :

Foo(x) = x ^ 22

Kevin HSaid on May 20, 2008 :

I’ve determined that the recursive binary search solution (with pruning) degenerates to O(m + n). A way to show this would be to assign the numbers that are strictly less than the target number to red, and the numbers strictly greater than the target number to blue. The binary search will reveal all regions with a red and a blue square in them, and filter out the rest. However, these regions are the same regions that are scanned along the linear path, so they have the same complexity.

The counter-example given, where m = 2 means that m is fixed, so both the recursive binary search and the linear ones are O(n), however the binary search has more constant overhead.

MarkCSaid on May 20, 2008 :

I would return -x + 24

Jack FSaid on May 20, 2008 :

Instead of explaining it I’ll just give a really easy python implementation.

def foo(x):

return abs(x – 17) + 7

Anthony YSaid on May 21, 2008 :

Do you mean this:

function Foo(int x) {

return 24 – x;

}

Ho ho..

Nikhil GupteSaid on May 21, 2008 :

I couldn’t find where to send the solution and hence posting it here.

****SPOILER WARNING****

def f(x) 24 – x end

Eugene EfimochkinSaid on May 21, 2008 :

Don’t we just have to return (24 – argument)?

FooSaid on May 21, 2008 :

A weird quiz, I wonder if there would ever be a business case for this kind of trickery.

Here’s my take. A lookup table, based on array:

int Foo(int bar){

bar = Math.Abs(bar); // handle bar<0

int[] arr = new int[bar+18]; // at least 17 elements are required for the lookup table. mind the zero index.

arr[7] = 17; // set up the lookup values

arr[17] = 7;

return arr[bar]; // int[] elements are zero if not initialized to any other value.

}

+ Handles most values of bar gracefully.

+ Is not tricked for bar overflow.

Joel PetracciSaid on May 21, 2008 :

int foo(int num)

{

return (7^17)^num;

}

Kener LipscombSaid on May 21, 2008 :

Or

public int Foo(int x)

{

return (24-x);

}

bugSaid on May 21, 2008 :

int Foo(int x)

{

return 7 + (x / 10) * 10;

}

bugSaid on May 21, 2008 :

One more 24 – x

LJSaid on May 21, 2008 :

public int Foo(int input)

{

return (24 – input);

}

bill budgeSaid on May 21, 2008 :

Simple if you know the trick – XOR. You can also do this with subtraction.

int Foo(int x)

{

const int mask = 7 ^ 17;

return x ^ mask;

}

Mike SSaid on May 21, 2008 :

foo(x) = (x + 10) mod 20

bugSaid on May 21, 2008 :

7 XOR 22 = 17

17 XOR 22 = 7

bugSaid on May 21, 2008 :

The first one should be 7 + (10 / x) * 10

DirkSaid on May 21, 2008 :

simplicity, right?

return (x + 10) % 20;

Matt HowellsSaid on May 21, 2008 :

2D binary search is complexity O(log(m*n)), not O(m * log(n)). This is more scalable than the linear solution.

Note that one of the suggestions, a binary search on each row in turn, is O(m log(n)) – but this is not a true 2D binary search.

Imagine a 1000×1000 matrix. In the worst case (value is in the top right corner), the suggested linear solution will make 1999 comparisons. 2D binary search will make 20 comparisons in the worst case (log2(1000*1000)).

Shahar YSaid on May 22, 2008 :

Matt Howells,

What is 2D binary search? We received several kinds of varaitions to that solution. Some were incorrect while the others complexity is not O(log(m*n)). As I wrote in the post, you assume that you always end up with non-rectangular matrixes, which is always not the case. log(m*n) is not the correct complexity from another reason – what about the operations made on each sub-matrix? Those are not O(1)!

Raymond WongSaid on May 22, 2008 :

int foo(int x)

{

return 24 – x;

}

vPSaid on May 22, 2008 :

After sleeping on it, here is another one with simple lookup table.

int foo(int bar){

bar = Math.abs(bar); // handle bar17 is mapped to values [0,17[. Neat, huh?

int[] arr=new int[18]; // large enough an array.

arr[7]=17; // init lookup values

arr[17]=7;

return arr[bar];

}

+ Handles all cases of bar.

+ Constant memory consumption.

christianSaid on May 22, 2008 :

Hi

Another solution just came to my mind, when I sent this quiz to a friend of mine.

I don’t think that any explanation is necessary for this piece of code:

public static int f(int n) {

String s = String.valueOf(n);

try {

s.charAt(1);

return 7;

} catch (Exception e) {

return 17;

}

}

bizonulSaid on May 22, 2008 :

int foo(int x)

{

return (x+10)%20

}

AndreySaid on May 22, 2008 :

int Foo(int x) { return 24 – x; }

Matt HowellsSaid on May 22, 2008 :

Shahar,

The 2D binary search I am referring to is my algorithm which I posted on challenge #3 thread. I have not seen any other posts calling their algorithm ’2D Binary Search’.

I make no assumption about non-rectangular matrices; the algorithm works perfectly well on a rectangular matrix, and your comment above that such an algorithm would search every element of the rectangular matrix to find element 14 is wrong.

The worst-case implementation of the algorithm I outlined would eliminate cells from that 7×2 matrix as follows:

OOOOOOO

OOOOOOO

….OOO

OOOOOOO

….OOO

..OOOOO

….OOO

…OOOO

….OOO

….OOO

……O

….OOO

…….

….OOO

…….

……O

…….

……X

Completed.

You can see that the algorithm makes only 8 comparisons in the worst case, not 14 as you suggest. Your linear solution also makes 8 comparisons in the worst case for this matrix.

Here is another matrix, showing worst-case performance:

OOO

OOO

OOO

..O

..O

OOO

..O

..O

.OO

..O

..O

..O

…

…

..O

…

…

..X

Completed.

Note that this takes 5 comparisons – exactly the same number as the linear algorithm!

I initially thought the complexity of the 2D binary search would be O(log(m*n)), thinking that half of the elements in the matrix would be eliminated in each step, but you can see from the above that I was wrong.

In fact it seems that whichever matrix you take, the worst-case performance of the two algorithms is identical, so I think it would be safe to say they both have the same complexity, O(m+n), and indeed that the two algorithms, while appearing quite different, are actually mathematically equivalent. The linear search almost certainly wins on simplicity though!

Thanks for your interesting questions.

Matt HowellsSaid on May 22, 2008 :

Oh and the answer to challenge #4 is:

Foo(int x)

{

return x ^ 22;

}

Cristian IonescuSaid on May 22, 2008 :

int Foo(int x)

{

return 24-x;

}

Matt HowellsSaid on May 22, 2008 :

An explanation of why this works.

In binary:

7 = 00111

17 = 10001

We want to switch the bits somehow so that 00111 is converted to 10001, and vice versa.

To do this, take the eXclusive OR of 7 and 17:

00111 ^ 10001 = 10110

7 ^ 17 = 22

22 is our magic number, which when XORed with either 7 or 17 will produce 17 or 7.

Jendrik IllnerSaid on May 22, 2008 :

I just posted my solution for challenge #4 on my blog http://jendrikillner.wordpress.com/2008/05/22/programming-job-interview-challenge4/

AnisSaid on May 22, 2008 :

The psuedo code of the fuction will be

Input argument XOR 22

i.e. 17 XOR 22 = 7 and 7 XOR 22 = 17

Best Regards

Anis

DavidSaid on May 22, 2008 :

Foo(n){

a = – a + 24

return a

}

ericSaid on May 22, 2008 :

24-?

ericSaid on May 22, 2008 :

it is simple. My son can get solution.

Ryan EmerleSaid on May 22, 2008 :

1. convert to string

2. prepend “1″

3. remove everything but right 2 chars

4. remove (originalLen – 1) chars from left

1. 7

2. 17

3. 17

4. 17

1. 17

2. 117

3. 17

4. 7

Tim OSaid on May 23, 2008 :

Two alternatives I can think of, both fairly simple though the first definately wins on machine cycles!

int Foo(int value)

{

return 24 – value;

}

or

int Foo(int value)

{

return (value + 10) % 20;

}

Ryan EmerleSaid on May 23, 2008 :

Foo( input ) {

return 7 + (17 – input);

}

Foo( 7 )

7 + ( 17 – 7 )

7 + 10

17

Foo( 17 )

7 + ( 17 – 17 )

7 + 0

7

TristanSaid on May 23, 2008 :

Matt,

I would have to agree that with this updated algorithm would be comparable. however your first attempt had a few nomenclature issues which lead to a massive headache. (ie the “y direction” when your axis had already been labeled without explanation)

can you please explain to me how you would create the new matrices using

1 2 3 4 5 6 7

8 9 10 11 12 13 14

my naive understanding would have assumed

x x x x [ 5 6 7

[8 9 10 11] 12 13 14](1 comparison+2matrices)

x x x x x x [ 7

x x[10 11] [12 13] 14](3 comparison+5matrices)

x x x x x x x

x x x [11] x [13] [14](6 comparison+8matrices)

x x x x x x x

x x x x x x [14](9 comparison+8matrices)

from the example you give above it seems that your criteria fow where the different matrices are formed changes.

TristanSaid on May 23, 2008 :

wow, that got mangled.

first compare 4.

create [8 9 10 11] and

5 6 7

12 13 14

next round compare 9 and 6 (8 and 9 removed, 5 and 6 removed) so far this seems to follow your example)

which leaves [10 11] and either [7] + [12 13 14] which does not follow the first cut or the second example, or [12 13] [7 14] which does.

obviously the first option (which you took) is more advantageous.

so following the majority of your examples we are left comparing 7,10, and 12 at this stage, then 11, 13 and 14 at the last stage.

Patrick McElweeSaid on May 23, 2008 :

public static int Foo(int x)

{

return x ^ 22;

}

BenSaid on May 23, 2008 :

24-x

Northern code monkeySaid on May 23, 2008 :

input XOR 22 does the trick?

RichardSaid on May 24, 2008 :

I’m going to take you at your word that the only Foo(n) results we care about are when n is 7 or 17, so let me throw this quickie out there:

public int foo(n)

{

return abs(n – 10);

}

rajSaid on May 24, 2008 :

if n is number

answer=(17-n)+(n%10)

OJSaid on May 25, 2008 :

Navigating this site is extremely confusing. You have the solution to one question posted in the same post as the next question. The comment threads are spread across the original question post and the one that contains the answer. Nothing seems to be in one place.

May I suggest that instead of polluting posts with lots of different stuff, edit your original post to include the answer? Then all of the comments, solutions, etc are in the one place rather than spread across multiple posts?

It might just be me, but I’m not a fan of the topics being mingled into the same comment threads.

Cheers

Shahar YSaid on May 25, 2008 :

Hi OJ,

You are right.

1) We will add a link from each question to its answer post (when it will be published).

2) We will ask readers to add their comments to the right post.

MartinSaid on May 28, 2008 :

Hi, if I am not badly mistaken I have a O(log(m+n)) algorithm for this problem. It does not make sense for the small examples you have here, but for larger matrices it is definitely faster. It is a simple recursive search, I will write a blog entry with source code on my homepage about this today.

Daniel CSaid on July 25, 2008 :

As Martin pointed out, there exists an O(log(m+n)) algorithm for this problem.

The pseudo for such an algorithm goes along the lines of:

1) perform binary search along the diagonal of the matrix (stopping at the max diagonal value <= search value after ensuring the value one down and one across has been search).

2) perform two binary searchs, one to the right (values greater in that row), and one down (values greater in that column) from the result of 1)

Complexity of algorithm:

Step 1 is O(log (m+n))

Step 2 is O(log (n) + log (m))

O(log(m+n)) < O(m+n) which is better than the linear solution

A binary search along the diagonal will find the maximum value less than or equal to the search value. The implementation of the diagonal search is less straight-forward than a normal binary search as the implementation must ensure that when it terminates, it has searched the value one down & across on the diagonal. Once step 1 has completed, we know that the answer must be below or across from it in the same row or column (otherwise we would voilate or sorted constraint).

For your three examples given in this post the following (worst case) would be searched:

Example 1 (3×3):

Step1: 6, 1 [we now know it's below/to the right of in the column/row containing the 1]

Step2: 4, 7, 2, 5 (found!)

Example 2 (2×7):

Step 1: 4, 13

Step 2: 14 (found!)

Example 3 (4×4):

Step 1: 8, 12 (found!)

A good way of thinking of the problem is by formatting the data in an equivalent structure. The 2D grid is equivalent to a sorted 1D array (the diagonals). Each node in this array would contain two sorted 1D arrays with values less than the next the node. Example 3 (4×4) can be rewritten as:

1 (2,3,4), (5,6,7)

8 (9,10), (11, 14)

12 (13), (15)

16

As you can see, my implementation is equivalent to a binary search on the first array, then two more binary searches on each of the child arrays.

Daniel CSaid on July 25, 2008 :

Actually, the sorted constraint will only guarantee that it is not less (row or column) than the smaller diagonal value or greater (row or column) than the greater diagonal value.

Eg for a value v (A < v < B) and the following matrix:

__**

_A**

**B_

**__

The value could lie anywhere within the * region so you have to recurse twice. O(exp(n+m))*O(log(n+m))=O(m+n) which is a rather complicated way of arriving at a solution with the same complexity as the straight-forward one.

asddSaid on May 2, 2009 :

heh, it’s weird noone write haskell version

it would be:

foo 7 = 17

foo 17 = 7

foo n = undefined