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)
By Kirill Sorokin on May 19, 2008 | Reply
Foo(x) {
return 24 - x;
}
Foo(7): 24 - 7 == 17
Foo(17): 24 - 17 == 7
By Mariano on May 19, 2008 | Reply
int foo(int num){
return (12-num)+12;
}
By Jacek on May 19, 2008 | Reply
function Foo(i)
{
return 24 - i;
}
By Brian Canzanella on May 19, 2008 | Reply
How about this…
static int Foo(int i)
{
return 119/i;
}
By Bruno on May 19, 2008 | Reply
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
By drea on May 19, 2008 | Reply
In Python…
def foo(n):
a = -10 * (n / 10) # integer division
return a + 17
print foo(7), foo(17)
>>>
17 7
By Menno on May 19, 2008 | Reply
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;
By Chris Jobson on May 19, 2008 | Reply
Solution to challenge #4:
Foo(x) = 24-x
By Poul Foged Nielsen on May 19, 2008 | Reply
int foo(int x)
{
return 24-x;
}
By Timea Albert on May 19, 2008 | Reply
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.
By Anton Irinev on May 19, 2008 | Reply
// 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;
}
By Eric on May 19, 2008 | Reply
foo(x) = 24 - x
foo(7) = 17
foo(17) = 7
By pavan kumar on May 19, 2008 | Reply
func(inputValue){
return (24-inputValue)
}
By Rob Guest on May 19, 2008 | Reply
int foo(int x) {
return Math.abs(x - 24);
}
By Kristoffer Edvinsson on May 19, 2008 | Reply
Foo( i ) {
return ( i + 10 ) % 20;
}
By drea on May 19, 2008 | Reply
Then again…
def foo(n):
return 24 - n
Damned simplicity ;o)
By Justin on May 19, 2008 | Reply
Simplest I can come up with is (OCAML)
let func x = 7 + 10 * ( 7 / x mod 10)
By Henry Fieger on May 19, 2008 | Reply
public int Foo(int i)
{
return (i + 10) Mod 20;
}
By Hmm... on May 19, 2008 | Reply
int Foo(int x)
{
return (x + 10) % 20;
}
… I know - no comments, but I guess it is … simple.
By Shahriar on May 19, 2008 | Reply
Hi dear. Would You Explain “foo” word To We?
Thanks.
By Haha on May 19, 2008 | Reply
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.
By Jonathan on May 19, 2008 | Reply
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.
By Shahar Y on May 19, 2008 | Reply
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)
By Chris H on May 19, 2008 | Reply
int Foo(int n) { return (24 - n); }
By Jason Kikel on May 19, 2008 | Reply
in ruby
def Foo(arg)
“1#{arg}”.sub(/11/,”)
end
By configurator on May 19, 2008 | Reply
Obviously,
Foo(x) = 24 - x
By Amrinder Sandhu on May 19, 2008 | Reply
int foo(int x)
{
return 24 - x;
}
By Jose M. Aguilar on May 19, 2008 | Reply
Just a low-tech solution:
public int foo(int a)
{
for (int i = a + 10; i 6; ) return i;
return 0;
}
By Jose M. Aguilar on May 19, 2008 | Reply
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;
}
By Joe McFall on May 19, 2008 | Reply
Here’s the simplest solution I can think of:
int Foo(int input)
{
// 7 * 17 = 119
// so divide 119 by input
return 119 / input;
}
By Henning B on May 19, 2008 | Reply
In standard C:
int foo( int n )
{
return n ^ 0×16;
}
By Igor Ostrovsky on May 19, 2008 | Reply
I’d say that this solution is pretty simple:
int Foo(int x) { return 24 - x; }
By eiro on May 19, 2008 | Reply
hi
the answer is:
public int Foo(int number)
{
return number ^ 22;
}
regards
By cowardlydragon on May 19, 2008 | Reply
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
By Alex on May 19, 2008 | Reply
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);
}
By Jon von Gillern on May 19, 2008 | Reply
Easy enough
http://www.vonsharp.net/ProgrammingJobInterviewChallenge4Answer.aspx
public int Foo(int x)
{
return -1 * x + 24;
}
By Chad Myers on May 19, 2008 | Reply
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?
By Shahar Y on May 19, 2008 | Reply
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)
By eiro on May 19, 2008 | Reply
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
By Maciej Lotkowski on May 19, 2008 | Reply
def foo(arg)
arg == 17 && 7 || 17
end
By verborghs on May 19, 2008 | Reply
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);
}
}
By Markus Pointner on May 19, 2008 | Reply
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.
By on May 19, 2008 | Reply
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?
By Carina on May 19, 2008 | Reply
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
By Mooglegiant on May 19, 2008 | Reply
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.
By Random on May 19, 2008 | Reply
xor 22
By mdub on May 19, 2008 | Reply
abs(x-24)
By Jake on May 19, 2008 | Reply
Quick Clarification:
Are loops allowed?
By Peter R on May 19, 2008 | Reply
def foo(x)
return (x + 3) % 20 + 7
By someone on May 19, 2008 | Reply
Answer:
x + (((8 - x) / abs (8 - x))) * 10
By Shahar Y on May 19, 2008 | Reply
Jake,
You can use loops, but I can assure you that you don’t really need them here.
By Chad myers on May 19, 2008 | Reply
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″)
);
}
By Adrian on May 19, 2008 | Reply
Foo(int x) { return x ^ 22; }
By Kim on May 19, 2008 | Reply
int f(int x)
{
return 24-x;
}
By Josh Goldie on May 19, 2008 | Reply
//
// 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));
}
By Niki on May 19, 2008 | Reply
How about int Foo(int x) { return 17+7-x; } I wonder if you can do it simpler than that?
By Catweazle on May 19, 2008 | Reply
int Foo(int input) {
return (input ^ 7 ^ 17);
}
(where ^ means XOR)
By EddieShen on May 19, 2008 | Reply
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
By Eddie Shen on May 19, 2008 | Reply
Update on the solution I posted:
return (i ^ 0×17) | 0×01;
Don’t see how it can get any faster than this
By Trung Dinh on May 19, 2008 | Reply
Foo(x) {
return x == 7 ? 17 : 7;
}
By vaporetto on May 19, 2008 | Reply
public static int Foo(int z)
{
return Math.Abs(10 - z) / (10 - z) * 10 + z;
}
Cheers,
Vapo
By Steve Barham on May 19, 2008 | Reply
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
By Trung Dinh on May 19, 2008 | Reply
Another solution not requiring ? : operator.
int Foo(int x) {
return (x + 10) % 20;
}
By Guy Gervais on May 19, 2008 | Reply
Result = 24 - X
By Trung Dinh on May 19, 2008 | Reply
Even simpler solution:
int Foo(x) {
return 23 - x;
}
By Trung Dinh on May 19, 2008 | Reply
Typo in my last answer. Should read:
int Foo(int x) {
return 24 - x;
}
By Ken Snyder on May 19, 2008 | Reply
// Yes, MS Excel taught me something about programming
function foo(num) {
return (intval(num == 17) * 7) + (intval(num == 7) * 17);
}
By Jake on May 19, 2008 | Reply
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;
}
By Trung Dinh on May 19, 2008 | Reply
Ok. Got to throw another “simple” answer in.
Foo(x) { return 119 / x; }
By Daniel Gary on May 19, 2008 | Reply
function foo(x)
{
return 24 - x;
}
By Vlad on May 19, 2008 | Reply
Hi!
Foo(x) = 24 - x;
regards,
Vlad
By Trung Dinh on May 19, 2008 | Reply
Last one. I promise.
Foo(x) { return x ^ 0×16; }
By Grundlefleck on May 19, 2008 | Reply
If there’s anything simpler I’ll be shocked:
public int foo( int x ){
return ( x + 10 ) % 20;
}
Grundlefleck
By cube on May 19, 2008 | Reply
return (input + 10) % 20
By Asim on May 19, 2008 | Reply
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
>>>
By Kevin on May 19, 2008 | Reply
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
By Jonathan Gilbert on May 19, 2008 | Reply
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.
By Marc Bollinger on May 19, 2008 | Reply
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!
By Chris Miller on May 19, 2008 | Reply
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
By Nick on May 19, 2008 | Reply
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;
}
By Sven on May 19, 2008 | Reply
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.
By Goran J on May 19, 2008 | Reply
I tried to use loops but at the end they all end with:
Foo(x)=24-x
By Abou Osama on May 19, 2008 | Reply
// C# Code:
double Foo(double x)
{
return 24 - x;
}
By Mark Heath on May 19, 2008 | Reply
public static int Foo(int input)
{
return (input + 10) % 20;
}
By Paul on May 19, 2008 | Reply
def Foo(n)
return n^22
end
By Kimmen on May 19, 2008 | Reply
Foo(int n)
{
return (n + 10) % 20;
}
By Loren on May 19, 2008 | Reply
Don’t overthink this one. Remember your high school math and connecting two points on a line.
Foo(x) {
return -x + 24;
}
By Justin on May 19, 2008 | Reply
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;
}
}
By Amjith on May 19, 2008 | Reply
int Foo(int n)
{
return (24-n);
}
By Mykola Dzyuba on May 19, 2008 | Reply
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);
}
By Igor Karp on May 19, 2008 | Reply
int Foo(int x) { return 7 + 17 - x;}
By James on May 19, 2008 | Reply
My Answer:
function foo(value) {
return -(value - 24);
}
By MrSquirrel on May 19, 2008 | Reply
int foo(x) {
return (-1 * x) + 24;
}
By Kia Kroas on May 19, 2008 | Reply
Sorry to be a spoiler but this is basic math:
f(x) = -x + 24
f(7) = -7 + 24 = 17
f(17) = -17 + 24 = 7
By Eddie Shen on May 19, 2008 | Reply
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.
By Sam on May 19, 2008 | Reply
This would require me to think, so I won’t participate–but it is interesting to skim
By Eric Larson on May 19, 2008 | Reply
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?
By Peter R on May 19, 2008 | Reply
def(x):
return x ^ 22
By tksh on May 19, 2008 | Reply
xor with 22
By efrain on May 19, 2008 | Reply
foo(x)
{
return 7 + (17 - x);
}
By Justin on May 19, 2008 | Reply
int foo(int x) {
return (x^0×0016);
}
By abhik on May 19, 2008 | Reply
foo = lambda x: (x+10) % 20
By Mark Smith on May 19, 2008 | Reply
public int Foo(int n){
return n + 10 - ((n / 10) * 20);
}
or
public int Foo(int n){
return 7 + ((n/10)^1) * 10;
}
By Phillip Jacobs on May 19, 2008 | Reply
public static int Foo(int x)
{
return Math.Abs((x+25) ^ 1);
}
By Phillip Jacobs on May 19, 2008 | Reply
public static int Foo(int x)
{
return ~(x)+25;
}
By David on May 19, 2008 | Reply
public int Foo(int x){
return 24-x;
}
By Jamie Penney on May 19, 2008 | Reply
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
By Kevin Q. on May 19, 2008 | Reply
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!
By Amrinder Sandhu on May 20, 2008 | Reply
Another solution: Use XOR
int foo(int x)
{
return (17 ^ 7) ^ x;
}
By Mark Bradshaw on May 20, 2008 | Reply
int foo(int i) {
return 24-i;
}
By Johnny Ye on May 20, 2008 | Reply
Foo(x){
return (1-x/10)*10+7
}
By Cedric on May 20, 2008 | Reply
return (arg+10)%20
By Dmitry S. on May 20, 2008 | Reply
int foo(int x)
{
return Math.Abs(x-24);
}
By MikiM on May 20, 2008 | Reply
public int foo(int value) {
return 24 - value;
}
By Antonio on May 20, 2008 | Reply
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
}
By Marcos Silva Pereira on May 20, 2008 | Reply
The Groovy Code:
def foo(num) {
int mul = (num - 10)/Math.abs(num - 10)
return num - (10 * mul)
}
Kind Regards
By stephen on May 20, 2008 | Reply
int foo(int n) {
return (17 + 7) - n;
}
By Compuboy on May 20, 2008 | Reply
Foo(input) = 17 + 7 - input
C# Code:
public int Foo(int input)
{
return 24 - input;
}
By JyriS on May 20, 2008 | Reply
public int foo(int x) {
return Math.abs(x - 24);
}
By SwedishFish on May 20, 2008 | Reply
int Foo(int x) { return 24 - x; }
By atin sood on May 20, 2008 | Reply
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;
}
}
By Maarten on May 20, 2008 | Reply
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;
}
}
By Jose M. Aguilar on May 20, 2008 | Reply
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
By christian on May 20, 2008 | Reply
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;
}
By David Steele on May 20, 2008 | Reply
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
By Jacob Seleznev on May 20, 2008 | Reply
int Foo(int n){ return 24 -n; }
By Harsh on May 20, 2008 | Reply
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 )
}
By pavan on May 20, 2008 | Reply
func(input){
return (24-input);
}
By Antony Raj on May 20, 2008 | Reply
Hi Guys,
I guess, The following will solve your problem. The implementation is in java.
public int Foo(int s){
return s ^ 15;
}
By Antony Raj on May 20, 2008 | Reply
Hi, I guess following would be answer for your question.
public void int foo(int i){
return i ^ 15 ;
}
By Antony on May 20, 2008 | Reply
Hi, I guess following would be answer for your question.
public void int foo(int i){
return i ^ 15 ;
}
By Jonas Christensen. on May 20, 2008 | Reply
Think it cant be more simple than this.
return 24 - n;
By Dan S on May 20, 2008 | Reply
Foo(x) = (x + 10) mod 20
By Sebastian U on May 20, 2008 | Reply
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;
}
By Omar on May 20, 2008 | Reply
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);
}
By Pete on May 20, 2008 | Reply
foo(n) = 17 + 7 - n
foo(n) = 17 * 7 / n
foo(n) = 17 ^ 7 ^ n (if ^ is xor)
By Shai On on May 20, 2008 | Reply
return 24-x;
By OJ on May 20, 2008 | Reply
In C:
int Foo(int f) { return f ^ 22; }
By foo on May 20, 2008 | Reply
fun Foo x = 24 - x;;
By HarryC on May 20, 2008 | Reply
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;
}
By Vivek Kanala on May 20, 2008 | Reply
foo(x){
return 24-x;
}
By Siso on May 20, 2008 | Reply
Hi,
I’d say:
BYTE Foo( BYTE x ) {
return x ^ (BYTE)0×16;
}
The 0×16 == 22 == 17 ^ 7
By cz35iek on May 20, 2008 | Reply
foo(x):
return (x+10) mod 20
By Kener Lipscomb on May 20, 2008 | Reply
public int foo(int x)
{
try
{
x = 1 / (x.ToString().Length - 1);
return 7;
}
catch (DivideByZeroException e)
{
return 17;
}
}
By Chaz Andrews on May 20, 2008 | Reply
Sorry, I dont have a blog, but here’s my answer:
int function Foo(int a){
return 144-(12*a);
}
By Tristan on May 20, 2008 | Reply
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.
By Tristan on May 20, 2008 | Reply
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)
}
By Heiko Hatzfeld on May 20, 2008 | Reply
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;}
}
}
By Heiko Hatzfeld on May 20, 2008 | Reply
Edit… Ooops… I overlooked the restiction on arrays.. So i guess I am down to 5 possible solutions only
By Kener Lipscomb on May 20, 2008 | Reply
Like this one liner better than my first:
public int foo(int x)
{
return ((((x.ToString().Length-2)*2)+1)*-10)+x;
}
By Mark on May 20, 2008 | Reply
return Math.Abs(int.Parse(foo.ToString(”00″)[0].ToString()) - 1) * 10 + 7;
By Dave on May 20, 2008 | Reply
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
By Dan on May 20, 2008 | Reply
I’ll take your “simplicity” hint to heart:
int Foo(int i)
{
return 119 / i;
}
By Igor Karp on May 20, 2008 | Reply
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
By Csaba Trucza on May 20, 2008 | Reply
Here is my take on the challenge. Includes discussion on simplicity.
http://notesonprogramming.blogspot.com/2008/05/many-faces-of-simplicity.html
By Avishkar on May 20, 2008 | Reply
int foo(int a) {
return (a+10)%20;
}
By Kimmen on May 20, 2008 | Reply
Why don’t I keep it simple? The solution is of course:
public int Foo(int n)
{
return 24 - n;
}
By Shahar Y on May 20, 2008 | Reply
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…
By Tim Kington on May 20, 2008 | Reply
How about this?
int f(int x) {
return x - (2 * (x - 12));
}
By Don March on May 20, 2008 | Reply
>> def foo(number)
>> (number + 10) % 20
>> end
>> foo(7)
=> 17
>> foo(17)
=> 7
By bob smith on May 20, 2008 | Reply
In this week’s challenge, are you also disallowing conditional expressions? ( ? : )
By Shahar Y on May 20, 2008 | Reply
Hi bob smith,
Yes, conditional expressions are disallowed.
By MrSquirrel on May 20, 2008 | Reply
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.
By Kevin H on May 20, 2008 | Reply
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.
By Mike Dunker on May 20, 2008 | Reply
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).
By Greg Young on May 20, 2008 | Reply
Foo(x) = x ^ 22
By Kevin H on May 20, 2008 | Reply
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.
By MarkC on May 20, 2008 | Reply
I would return -x + 24
By Jack F on May 20, 2008 | Reply
Instead of explaining it I’ll just give a really easy python implementation.
def foo(x):
return abs(x - 17) + 7
By Anthony Y on May 21, 2008 | Reply
Do you mean this:
function Foo(int x) {
return 24 - x;
}
Ho ho..
By Nikhil Gupte on May 21, 2008 | Reply
I couldn’t find where to send the solution and hence posting it here.
****SPOILER WARNING****
def f(x) 24 - x end
By Eugene Efimochkin on May 21, 2008 | Reply
Don’t we just have to return (24 - argument)?
By Foo on May 21, 2008 | Reply
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.
By Joel Petracci on May 21, 2008 | Reply
int foo(int num)
{
return (7^17)^num;
}
By Kener Lipscomb on May 21, 2008 | Reply
Or
public int Foo(int x)
{
return (24-x);
}
By bug on May 21, 2008 | Reply
int Foo(int x)
{
return 7 + (x / 10) * 10;
}
By bug on May 21, 2008 | Reply
One more 24 - x
By LJ on May 21, 2008 | Reply
public int Foo(int input)
{
return (24 - input);
}
By bill budge on May 21, 2008 | Reply
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;
}
By Mike S on May 21, 2008 | Reply
foo(x) = (x + 10) mod 20
By bug on May 21, 2008 | Reply
7 XOR 22 = 17
17 XOR 22 = 7
By bug on May 21, 2008 | Reply
The first one should be 7 + (10 / x) * 10
By Dirk on May 21, 2008 | Reply
simplicity, right?
return (x + 10) % 20;
By Matt Howells on May 21, 2008 | Reply
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)).
By Shahar Y on May 22, 2008 | Reply
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)!
By Raymond Wong on May 22, 2008 | Reply
int foo(int x)
{
return 24 - x;
}
By vP on May 22, 2008 | Reply
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.
By christian on May 22, 2008 | Reply
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;
}
}
By bizonul on May 22, 2008 | Reply
int foo(int x)
{
return (x+10)%20
}
By Andrey on May 22, 2008 | Reply
int Foo(int x) { return 24 - x; }
By Matt Howells on May 22, 2008 | Reply
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.
By Matt Howells on May 22, 2008 | Reply
Oh and the answer to challenge #4 is:
Foo(int x)
{
return x ^ 22;
}
By Cristian Ionescu on May 22, 2008 | Reply
int Foo(int x)
{
return 24-x;
}
By Matt Howells on May 22, 2008 | Reply
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.
By Jendrik Illner on May 22, 2008 | Reply
I just posted my solution for challenge #4 on my blog http://jendrikillner.wordpress.com/2008/05/22/programming-job-interview-challenge4/
By Anis on May 22, 2008 | Reply
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
By David on May 22, 2008 | Reply
Foo(n){
a = - a + 24
return a
}
Â
Â
By eric on May 22, 2008 | Reply
24-?
By eric on May 22, 2008 | Reply
it is simple. My son can get solution.
By Ryan Emerle on May 22, 2008 | Reply
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
By Tim O on May 23, 2008 | Reply
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;
}
By