#### Write for Dev102!

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

## A Programming Job Interview Challenge #4

May 19, 2008

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:

2. If the value matches, you’re done.
3. 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.
4. 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.
5. 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)

## 219 Responses to “A Programming Job Interview Challenge #4”

1. Kirill Sorokin

Said 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.

2. Mariano

Said on May 19, 2008 :

int foo(int num){
return (12-num)+12;
}

3. Jacek

Said on May 19, 2008 :

function Foo(i)
{
return 24 – i;
}

4. Said on May 19, 2008 :

static int Foo(int i)
{
return 119/i;
}

5. Said 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

6. drea

Said 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

7. Said 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;

8. Chris Jobson

Said on May 19, 2008 :

Solution to challenge #4:
Foo(x) = 24-x

9. Said on May 19, 2008 :

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

10. Timea Albert

Said 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.

11. Said 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;
}

12. Said on May 19, 2008 :

foo(x) = 24 – x

foo(7) = 17
foo(17) = 7

13. pavan kumar

Said on May 19, 2008 :

func(inputValue){
return (24-inputValue)
}

14. Rob Guest

Said on May 19, 2008 :

int foo(int x) {
return Math.abs(x – 24);
}

15. Kristoffer Edvinsson

Said on May 19, 2008 :

Foo( i ) {
return ( i + 10 ) % 20;
}

16. drea

Said on May 19, 2008 :

Then again…

def foo(n):
return 24 – n

Damned simplicity ;o)

17. Justin

Said on May 19, 2008 :

Simplest I can come up with is (OCAML)

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

18. Henry Fieger

Said on May 19, 2008 :

public int Foo(int i)
{
return (i + 10) Mod 20;
}

19. Hmm...

Said on May 19, 2008 :

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

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

20. Shahriar

Said on May 19, 2008 :

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

21. Haha

Said 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.

22. Said 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.

23. Said 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)

24. Chris H

Said on May 19, 2008 :

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

25. Jason Kikel

Said on May 19, 2008 :

in ruby

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

26. Said on May 19, 2008 :

Obviously,

Foo(x) = 24 – x

27. Amrinder Sandhu

Said on May 19, 2008 :

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

28. Said 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;
}

29. Said 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;
}

30. Joe McFall

Said 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;
}

31. Henning B

Said on May 19, 2008 :

In standard C:

int foo( int n )
{
return n ^ 0x16;
}

32. Said on May 19, 2008 :

I’d say that this solution is pretty simple:

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

33. eiro

Said on May 19, 2008 :

hi

public int Foo(int number)
{
return number ^ 22;
}

regards

34. cowardlydragon

Said 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

35. Said 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);
}

36. Said on May 19, 2008 :

Easy enough

public int Foo(int x)
{
return -1 * x + 24;
}

37. Said 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?

38. Said on May 19, 2008 :

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)

39. eiro

Said on May 19, 2008 :

hi,

another version, but not so clean as XOR 22:

public int Foo(int number)
{
}

regards

40. Maciej Lotkowski

Said on May 19, 2008 :

def foo(arg)
arg == 17 && 7 || 17
end

41. verborghs

Said 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);

}
}

42. Markus Pointner

Said 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.

43. Said 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?

44. Carina

Said 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

45. Mooglegiant

Said 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.

46. Random

Said on May 19, 2008 :

xor 22

47. mdub

Said on May 19, 2008 :

abs(x-24)

48. Jake

Said on May 19, 2008 :

Quick Clarification:
Are loops allowed?

49. Peter R

Said on May 19, 2008 :

def foo(x)
return (x + 3) % 20 + 7

50. someone

Said on May 19, 2008 :

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

51. Said on May 19, 2008 :

Jake,

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

52. Said 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”)
);
}

Said on May 19, 2008 :

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

54. Kim

Said on May 19, 2008 :

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

55. Josh Goldie

Said 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));
}

56. Niki

Said on May 19, 2008 :

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

57. Catweazle

Said on May 19, 2008 :

int Foo(int input) {
return (input ^ 7 ^ 17);
}

(where ^ means XOR)

58. Said on May 19, 2008 :

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

psuedo code for foo:

foo(i)
return i ^ 0x17 + 1;

0x17 = 0001 0111 = 23
xor 7 with 0x17 and u get 16
xor 16 with 0x17 and u get 6

59. Said on May 19, 2008 :

Update on the solution I posted:

return (i ^ 0x17) | 0x01;

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

60. Trung Dinh

Said on May 19, 2008 :

Foo(x) {
return x == 7 ? 17 : 7;
}

61. vaporetto

Said on May 19, 2008 :

public static int Foo(int z)
{
return Math.Abs(10 – z) / (10 – z) * 10 + z;
}

Cheers,
Vapo

62. Said 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

63. Trung Dinh

Said on May 19, 2008 :

Another solution not requiring ? : operator.

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

64. Guy Gervais

Said on May 19, 2008 :

Result = 24 – X

65. Trung Dinh

Said on May 19, 2008 :

Even simpler solution:

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

66. Trung Dinh

Said on May 19, 2008 :

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

67. Ken Snyder

Said on May 19, 2008 :

// Yes, MS Excel taught me something about programming
function foo(num) {
return (intval(num == 17) * 7) + (intval(num == 7) * 17);
}

68. Jake

Said 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;
}

69. Trung Dinh

Said on May 19, 2008 :

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

Foo(x) { return 119 / x; }

70. Daniel Gary

Said on May 19, 2008 :

function foo(x)
{
return 24 – x;
}

Said on May 19, 2008 :

Hi!

Foo(x) = 24 – x;

regards,

72. Trung Dinh

Said on May 19, 2008 :

Last one. I promise.

Foo(x) { return x ^ 0x16; }

73. Grundlefleck

Said on May 19, 2008 :

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

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

Grundlefleck

74. cube

Said on May 19, 2008 :

return (input + 10) % 20

75. Said 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
>>>

76. Kevin

Said 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

77. Jonathan Gilbert

Said 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.

78. Said 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!

79. Chris Miller

Said 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

80. Said 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;
}

81. Sven

Said 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.

82. Goran J

Said on May 19, 2008 :

I tried to use loops but at the end they all end with:
Foo(x)=24-x

83. Said on May 19, 2008 :

// C# Code:

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

84. Said on May 19, 2008 :

public static int Foo(int input)
{
return (input + 10) % 20;
}

85. Paul

Said on May 19, 2008 :

def Foo(n)
return n^22
end

86. Kimmen

Said on May 19, 2008 :

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

87. Loren

Said 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;
}

88. Justin

Said 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;
}

}

89. Said on May 19, 2008 :

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

90. Said 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);
}

91. Igor Karp

Said on May 19, 2008 :

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

92. James

Said on May 19, 2008 :

function foo(value) {
return -(value – 24);
}

93. Said on May 19, 2008 :

int foo(x) {
return (-1 * x) + 24;
}

94. Kia Kroas

Said 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

95. Said 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.

96. Said on May 19, 2008 :

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

97. Said 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?

98. Peter R

Said on May 19, 2008 :

def(x):
return x ^ 22

99. tksh

Said on May 19, 2008 :

xor with 22

100. efrain

Said on May 19, 2008 :

foo(x)
{
return 7 + (17 – x);
}

101. Justin

Said on May 19, 2008 :

int foo(int x) {
return (x^0x0016);
}

102. Said on May 19, 2008 :

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

103. Mark Smith

Said 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;
}

104. Said on May 19, 2008 :

public static int Foo(int x)
{
return Math.Abs((x+25) ^ 1);
}

105. Said on May 19, 2008 :

public static int Foo(int x)
{
return ~(x)+25;
}

106. David

Said on May 19, 2008 :

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

107. Said 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

108. 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!

109. Amrinder Sandhu

Said on May 20, 2008 :

Another solution: Use XOR

int foo(int x)
{
return (17 ^ 7) ^ x;
}

Said on May 20, 2008 :

int foo(int i) {
return 24-i;
}

111. Johnny Ye

Said on May 20, 2008 :

Foo(x){
return (1-x/10)*10+7
}

112. Cedric

Said on May 20, 2008 :

return (arg+10)%20

113. Dmitry S.

Said on May 20, 2008 :

int foo(int x)
{
return Math.Abs(x-24);
}

114. MikiM

Said on May 20, 2008 :

public int foo(int value) {
return 24 – value;
}

115. Said 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
}

116. Said on May 20, 2008 :

The Groovy Code:

def foo(num) {
int mul = (num – 10)/Math.abs(num – 10)
return num – (10 * mul)
}

Kind Regards

117. Said on May 20, 2008 :

int foo(int n) {
return (17 + 7) – n;
}

118. Compuboy

Said on May 20, 2008 :

Foo(input) = 17 + 7 – input

C# Code:

public int Foo(int input)
{
return 24 – input;
}

119. JyriS

Said on May 20, 2008 :

public int foo(int x) {
return Math.abs(x – 24);
}

120. SwedishFish

Said on May 20, 2008 :

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

121. atin sood

Said 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;
}
}

122. Maarten

Said on May 20, 2008 :

Foo(x) = 24-x

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

public static class HelperClass {
public static int Foo(int x) {
return 24 – x;
}
}

123. Said 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

124. christian

Said 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;
}

125. David Steele

Said 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))

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

126. Jacob Seleznev

Said on May 20, 2008 :

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

127. Harsh

Said 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 )
}

128. pavan

Said on May 20, 2008 :

func(input){
return (24-input);
}

129. Antony Raj

Said 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;
}

130. Said on May 20, 2008 :

public void int foo(int i){
return i ^ 15 ;
}

131. Said on May 20, 2008 :

public void int foo(int i){
return i ^ 15 ;
}

132. Jonas Christensen.

Said on May 20, 2008 :

Think it cant be more simple than this.

return 24 – n;

133. Dan S

Said on May 20, 2008 :

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

134. Sebastian U

Said 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;
}

135. Omar

Said 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);
}

136. Pete

Said on May 20, 2008 :

foo(n) = 17 + 7 – n

foo(n) = 17 * 7 / n

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

137. Said on May 20, 2008 :

return 24-x;

138. Said on May 20, 2008 :

In C:

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

139. foo

Said on May 20, 2008 :

fun Foo x = 24 – x;;

140. Said 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;
}

141. Vivek Kanala

Said on May 20, 2008 :

foo(x){
return 24-x;
}

142. Siso

Said on May 20, 2008 :

Hi,

I’d say:

BYTE Foo( BYTE x ) {
return x ^ (BYTE)0x16;
}

The 0x16 == 22 == 17 ^ 7

143. cz35iek

Said on May 20, 2008 :

foo(x):
return (x+10) mod 20

144. Said on May 20, 2008 :

public int foo(int x)
{
try
{
x = 1 / (x.ToString().Length – 1);
return 7;
}
catch (DivideByZeroException e)
{
return 17;
}

}

145. Chaz Andrews

Said on May 20, 2008 :

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

int function Foo(int a){
return 144-(12*a);
}

146. Tristan

Said 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.

147. Tristan

Said 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)
}

148. Said 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
{

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;}
}
}

149. Said on May 20, 2008 :

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

150. Said 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;
}

151. Mark

Said on May 20, 2008 :

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

152. Said 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

153. Dan

Said on May 20, 2008 :

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

int Foo(int i)
{
return 119 / i;
}

154. Igor Karp

Said 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

155. Csaba Trucza

Said 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

156. Said on May 20, 2008 :

int foo(int a) {
return (a+10)%20;
}

157. Kimmen

Said on May 20, 2008 :

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

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

158. Said 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…

159. Tim Kington

Said on May 20, 2008 :

int f(int x) {
return x – (2 * (x – 12));
}

160. Said on May 20, 2008 :

>> def foo(number)
>> (number + 10) % 20
>> end

>> foo(7)
=> 17
>> foo(17)
=> 7

161. bob smith

Said on May 20, 2008 :

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

162. Said on May 20, 2008 :

Hi bob smith,

Yes, conditional expressions are disallowed.

163. Said 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.

164. Said on May 20, 2008 :

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.

165. Mike Dunker

Said 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).

166. Said on May 20, 2008 :

Foo(x) = x ^ 22

167. Said 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.

168. MarkC

Said on May 20, 2008 :

I would return -x + 24

169. Jack F

Said 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

170. Anthony Y

Said on May 21, 2008 :

Do you mean this:

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

Ho ho..

171. Nikhil Gupte

Said 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

172. Said on May 21, 2008 :

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

173. Foo

Said 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.

174. Joel Petracci

Said on May 21, 2008 :

int foo(int num)
{
return (7^17)^num;
}

175. Said on May 21, 2008 :

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

176. bug

Said on May 21, 2008 :

int Foo(int x)
{
return 7 + (x / 10) * 10;
}

177. bug

Said on May 21, 2008 :

One more 24 – x

178. LJ

Said on May 21, 2008 :

public int Foo(int input)
{
return (24 – input);
}

179. bill budge

Said 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;
}

180. Mike S

Said on May 21, 2008 :

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

181. bug

Said on May 21, 2008 :

7 XOR 22 = 17
17 XOR 22 = 7

182. bug

Said on May 21, 2008 :

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

183. Dirk

Said on May 21, 2008 :

simplicity, right?

return (x + 10) % 20;

184. Matt Howells

Said 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)).

185. Said 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)!

186. Raymond Wong

Said on May 22, 2008 :

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

187. vP

Said 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.

188. christian

Said 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;
}
}

189. bizonul

Said on May 22, 2008 :

int foo(int x)
{
return (x+10)%20
}

190. Andrey

Said on May 22, 2008 :

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

191. Matt Howells

Said 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!

192. Matt Howells

Said on May 22, 2008 :

Oh and the answer to challenge #4 is:
Foo(int x)
{
return x ^ 22;
}

193. Cristian Ionescu

Said on May 22, 2008 :

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

194. Matt Howells

Said 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.

195. Jendrik Illner

Said 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/

196. Anis

Said 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

197. David

Said on May 22, 2008 :

Foo(n){
a = – a + 24
return a
}

198. eric

Said on May 22, 2008 :

24-?

199. eric

Said on May 22, 2008 :

it is simple. My son can get solution.

200. Said 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

201. Tim O

Said 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;
}

202. Said 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

203. Tristan

Said 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.

204. Tristan

Said 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.

205. Patrick McElwee

Said on May 23, 2008 :

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

206. Ben

Said on May 23, 2008 :

24-x

207. Said on May 23, 2008 :

input XOR 22 does the trick?

208. Richard

Said 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);
}

209. raj

Said on May 24, 2008 :

if n is number

210. Said 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

211. Said 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).

212. Said 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.

213. Daniel C

Said 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.

214. Daniel C

Said 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.

215. asdd

Said on May 2, 2009 :

heh, it’s weird noone write haskell version
it would be:
foo 7 = 17
foo 17 = 7
foo n = undefined