The dreaded Whiteboard Interview scenario

yawha

You could cache results though:

int fibs(int n)
{
   static int cache[100];
   static bool initialized = false;

   if(!initialized)
   {
      for(int i = 0; i < 100; i++)
         cache[i] = -1;
      initialized = true;
   }

   switch(n)
   {
      case 0:
         return 0;
      case 1:
         return 1;
      default:
         if (cache[n] == -1)
            cache[n] = fibs(n - 1) + fibs(n - 2);
         return cache[n];
   }
}

jester77

m1nder wrote: »

ah, ok. Does this fix it?

static int Fibonacci(int pos)
        {
            if (pos <= 1) return pos;
            return Fibonacci (pos-1) + Fibonacci (pos-2);
        }

Looks good

So, I would now ask you if there was an alternative way to solve this problem and ask you to show me a solution?

komodosp

carveone wrote: »

a = 1;
b = 1;

if ((a == 2) && (b=2))
    printf("Hello\n);

What is the value of b after this?

Not sure I understand the point of that as an interview question... Seems to be just a smart-arse trying to catch you out. If it occurred in real life, it would take you less than a minute to wonder why b=2 and then spot the problem.

Suppose you have a number and you need to divide it by 2, but you have no division operator or facility to divide whatsoever, how might you approach this.....

I would have thought count how many times you can subtract 2 from it, but then it took me a short while to think of that, not sure I'd have done it in an interview situation...

Colonel Panic

komodosp wrote: »

Not sure I understand the point of that as an interview question... Seems to be just a smart-arse trying to catch you out. If it occurred in real life, it would take you less than a minute to wonder why b=2 and then spot the problem.

I dunno, I work on a pretty big code base and still find issues related to assignment instead of equality all the time. Plus knowing about short circuiting conditionals is a basic but important thing too.

SirLemonhead

komodosp wrote: »

Not sure I understand the point of that as an interview question... Seems to be just a smart-arse trying to catch you out. If it occurred in real life, it would take you less than a minute to wonder why b=2 and then spot the problem.


I would have thought count how many times you can subtract 2 from it, but then it took me a short while to think of that, not sure I'd have done it in an interview situation...

a = 1;
b = 1;

if ((2 == a) && (2=b))
    printf("Hello\n);

write comparisons with the constant on the left side and let the compiler tell you you're wrong

also, depending on language, does doing a 'value =>> 1' satisfy the criteria for the divide by 2 problem?

Procasinator

SirLemonhead wrote: »

also, depending on language, does doing a 'value =>> 1' satisfy the criteria for the divide by 2 problem?[/QUOTE]

Won't work for odd numbers. 5 >> 1 = 2, where as 5/2 = 2.5.

You could determine if n is odd, and if so, add 0.5:
[code]
function divideByTwo(n)
{
	if (n&1) return (n >> 1) + 0.5;
	else return n >> 1;
}

SirLemonhead

Procasinator wrote: »

Won't work for odd numbers. 5 >> 1 = 2, where as 5/2 = 2.5.

You could determine if n is odd, and if so, add 0.5:

function divideByTwo(n)
{
	if (n&1) return (n >> 1) + 0.5;
	else return n >> 1;
}

oh woops, yeah, I'm too used to using it with power of 2 numbers

shootermacg

Hi LINQ is fun and all but I think if you disable late binding you cannot use it.
The other thing with LINQ is although it is easy to read it isn't always optimal.

m1nder

Procasinator wrote: »

Won't work for odd numbers. 5 >> 1 = 2, where as 5/2 = 2.5.

You could determine if n is odd, and if so, add 0.5:

function divideByTwo(n)
{
    if (n&1) return (n >> 1) + 0.5;
    else return n >> 1;
}

Ah it should.
If you divide odd integers, the result is a floor (rounding down).
5/2 = 2. You could get clarification on this before suggesting it, might show you have a good handle on types etc.

Procasinator

m1nder wrote: »

Ah it should.
If you divide odd integers, the result is a floor (rounding down).
5/2 = 2. You could get clarification on this before suggesting it, might show you have a good handle on types etc.

It really depends on the language in question. Many dynamic languages will return a float (like JavaScript, PHP, Perl, Python 3, e.t.c.). Bit-shifting won't.

fergalr

m1nder wrote: »

Its fascinating isn't it. So elegant, almost magical. Not to mention the Fibonacci numbers themselves. I have seen the relation to nature, the magic ratio etc.

You might find this amusing:
http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm

k.p.h

fergalr wrote: »

You might find this amusing:
http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm

Conclusively debunked their, I'm sticking with 42

[-0-]

int countwords(char *str)
{   int i = 0;
    for(str=strtok(str, " -.!,;"); str; str=strtok(NULL, " -.!,;")) { i++; }
     return i;
}

I've had a few whiteboard interviews and strtok has often saved me in them. They have usually been count the number of x in y. Granted some of them may be looking for you to come up with your own version of strtok to see how you brain works but I never reinvent the wheel and strtok is highly optimized.

I agree with the OP though. The whiteboard scares the crap out of me and I ALWAYS go blank when I'm tasked with it.

yenoah

[-0-] wrote: »

int countwords(char *str)
{   int i = 0;
    for(str=strtok(str, " -.!,;"); str; str=strtok(NULL, " -.!,;")) { i++; }
     return i;
}

I've had a few whiteboard interviews and strtok has often saved me in them. They have usually been count the number of x in y. Granted some of them may be looking for you to come up with your own version of strtok to see how you brain works but I never reinvent the wheel and strtok is highly optimized.

I agree with the OP though. The whiteboard scares the crap out of me and I ALWAYS go blank when I'm tasked with it.

What's strtok?

Giblet

yenoah wrote: »

What's strtok?

Tokenizes a string based on a set of delimiters passed into the function

yenoah

Giblet wrote: »

Tokenizes a string based on a set of delimiters passed into the function

so you pass a set of delimiters into a function and get a string back? can you explain?

Giblet

You get an array of strings back.

yenoah

Giblet wrote: »

You get an array of strings back.

ah, so akin to string.split(delimiter);

Procasinator

Well, rather than a array of string each new call returns the next token from the last successful call (not thread-safe) until the end of the string.

It differs from split in most implementations that the split goes through the whole string in one call, whereas you could decide to use strtok to only get a portion of the sub-strings.

[-0-]

I should note that strtok is not good for threaded applications and can cause issues, so usually after I use it I discuss the various functions in c with issues (strcpy, etc) and lead them into talking about how to write thread safe applications and what sort of practices they have and I show them how to rewrite what I wrote using strstr()