The dreaded Whiteboard Interview scenario

m1nder

I recently went through it. This time the question was - "given a sentence, write some code to find the longest word."

Of course, when you are in these whiteboard interview scenarios, you are to say the least, under pressure. It's hard to think let alone be creative or apply reasoning.

First I started discussing an iteration to look for all spaces. When it finds one, it sub iterates across the next set of characters until it finds the next space. Then the values in between are stored as a word in an array. We then sort the array.........zzzzzzzzz

He put me out of my misery by asking - "Have you come across string.split"? Oh for god sakes, of course I have. My middle name is string.split. Why didn't I think of that? What the hell is wrong with me???? Sweat, gulp but try not to show it. Look calm and talk as if you know what you are doing.

Here's what I then went with. I scribbled out a lot of this, talking as I went, trying to sound as though I was cool, boasting about a test first / try to break it approach etc. Of course I only scribbled out the helper method, and a bit of the bubble sorter but this is what I was going for.

        static string sen = "this is a warning to all cats.";

        static void Main(string[] args)
        {
            Console.WriteLine (FindMaxWord(sen));
            Console.ReadLine();
        }


        private static string FindMaxWord(string sen)
        {
            string[] words = sen.Split(' ');
            SortArrayByItemLength(words);
            return words.Last();
        }

        private static void SortArrayByItemLength(string[] arr)
        {
            for (int y = 0; y <= arr.Length-1; y++)
            {
                for (int z = y+1; z <= arr.Length-1; z++)
                {
                    if (arr[y].Length > arr[z].Length)
                    {
                        string tmp = arr[y];
                        arr[y] = arr[z];
                        arr[z] = tmp;
                    }
                }
            }
        }

Well, anyway, after a bit of humming and hawing and discussion with the interviewer, he finally gave me a bit of a prompt. "What about LINQ?" he asked.....

DOH! Of course. But you know, I always approach these dam whiteboard sessions under the impression that the interviewer is looking for the geek in me, rather than the productivity savvy common sense person. All I needed was this...

        private static string FindMaxWord(string sen)
        {
            string[] words = sen.Split(' ');
            var query = from w in words
                        where w.Length == words.Max(o => o.Length)
                        select w;

            return query.Single();
        }

Now I knew all the above. But when I faced the whiteboard at the interview, I was rendered useless. I was mortified at my lack of ability to do such a simple task. I've been through it before at a very well known Software house. So it's not good. They are horrible scenarios and I'm wondering if I'm alone here?

Has anyone else lost the ability to be intelligent at a whiteboard interview session. Tell us your horror story....

murphaph

Forgive my ignorance and not to divert the thread but I had never heard of LINQ until now and when I googled it I found some SO threads saying there's no such thing as LINQ in Java? What is the code you've written there (the efficient stuff)? (Java n00b here!)

m1nder

murphaph wrote: »

Forgive my ignorance and not to divert the thread but I had never heard of LINQ until now and when I googled it I found some SO threads saying there's no such thing as LINQ in Java? What is the code you've written there (the efficient stuff)? (Java n00b here!)

c#

yawha

O(n) in C:

int get_longest(char * str) {
   int max = 0;
   for(int i = 0; str[i] != '\0'; i++)
      for(int j = 0; str[i] != ' ' && str[i] != '\0'; j++, i++)
         max = j > max ? j : max;

   return max;
}

Kinda surprised he wanted you to use high level string functions and LINQ for such a basic task.

EDIT: Oh wait, the longest word. That's a bit different.

char* get_longest_word(char * str) {
   char * res = malloc (sizeof(char) * 100);
   int maxlen = 0, maxindx = 0;
   for(int i = 0; str[i] != '\0'; i++)
      for(int j = 0, k = i; str[i] != ' ' && str[i] != '\0'; j++, i++)
         if (j > maxlen) { 
            j = maxlen; 
            maxindx = k; 
         }

   strcpy(res, &str[maxindx], maxlen);
   return res;
}

I have been guilty of jumping into things without thinking about them in whiteboard interview situations before...

Giblet

murphaph wrote: »

Forgive my ignorance and not to divert the thread but I had never heard of LINQ until now and when I googled it I found some SO threads saying there's no such thing as LINQ in Java? What is the code you've written there (the efficient stuff)? (Java n00b here!)

Lambdas.


I would rather someone came up with the verbose solution (if it worked and showed they knew what they were doing, rather than being verbose because they haven't a notion).

Imagine you were stuck with .NET 2.0.

To be honest, if he said "What about LINQ" I would immediately say "Ah, I can show you how I would do it in LINQ too"

"a sentence with a long word in it!".Split(' ').OrderByDescending(p => p.Length).First();

The above would tell me nothing about your ability to program other than you can use LINQ to do stupid crap, probably abusing intellisense or resharper.

m1nder

You know, god bless this forum. In my experience No one ever really reads the op (requirements), People just respond with their code one trying to better / out do the other in a race to see who the best coder is.

What are the requirements of this thread? Ask yourself....
I'd say, the requirements here are anecdotes, stories, experiences. But look what we're getting (again).


Now let the backlash and the abuse begin

carveone

m1nder wrote: »

Has anyone else lost the ability to be intelligent at a whiteboard interview session. Tell us your horror story....

Dear god yeah. I remember being at an interview where they wrote something like this: (C code):

a = 1;
b = 1;

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

What is the value of b after this?

First time I've said the F word in an interview. Thing is, I know that C and most other languages have "short circuit" behaviour. I used it all the time in bash. Sure otherwise this could crash:

if(p == NULL || *p == '\0')
		{ /* no string */ }

I just didn't put two and two together and I refused to bluff. I just said it was bad code and I wouldn't type that. They kinda looked at me

amen

What are the requirements of this thread

sure why let requirements get in the way of showing off.

Procasinator

It's a good interview question actually. Most people will forget about punctuation, for instance (seems the case here: http://stackoverflow.com/questions/5100019/how-to-find-the-largest-word-from-the-string-using-c), which could skew your result.

"I am a cat, hear me meow"

With Giblet code, I would get the result of "cat,". With the LINQ version from m1nder I get an exception, as Single expects there to be only result, where multiple strings could have the same max string length. (You probably meant first over single).

Depending on how the question is defined, this is okay, but for me a sentence can contain punctuation and probably that punctuation shouldn't be considered part of the word. It get's further complicated with things like hyphenated words.

To complicate things more then, do we have to worry about i18n and l10n?

Overall, though, if I were to get this interview question, first thing I would do (no matter how simple it seemed), is take a moment to think. Ask a couple questions, or in the very least, state your assumptions. Often enough, the interviewer would probably say they are just looking for a simple solution (i.e. split(" ")), but you've shown you can analyse a problem, understand various systems and issues, and that probably have had to solve real problems, not just college assignments.

Giblet

I forgot how to do an inner join in my first interview...
I was using Hibernate for a few months and completely forgot how to write SQL.

m1nder

I did an intern interview at Microsoft a few years back. It went badly in general, don't even get me started on the whiteboard.......but then he sat me down and asked me the following questions..

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

Silence, stare, more silence.......2 minutes later I whimper "I don't know!"

How might you do the opposite. Suppose I have a number and I need to multiply it by 2 but I have no multiplication operator or facility whatsoever......hmmmm?

tap tap tap (tick tock tick tock) Oh dear god!!! Whats happening to me. Ground I need a hole right now please. I just could not think. I froze on the inside.

The answer was so f'n simple

(a) n * 0.5
(b) n / 0.5

Now having said that, I actually got the job, but that interview was awful. I have no idea why they employed me, but they did.

k.p.h

Jesus lads, stop it. As a Comp Science student hoping to do development this thread is scaring the crap out of me. It takes 20 min for me to even figure out what I'm trying to do not to mention have a go at coding it. I would definitely brick myself.

Procasinator

k.p.h wrote: »

Jesus lads, stop it. As a Comp Science student hoping to do development this thread is scaring the crap out of me. It takes 20 min for me to even figure out what I'm trying to do not to mention have a go at coding it. I would definitely brick myself.

Just find sample problems, and try to solve them. Even more difficult ones, have a look, and see how other people did them. Eventually, you will build up your skills. Most problems share similar building blocks and insights, so you'd be surprised how quickly you can solve various problems.

m1nder

k.p.h wrote: »

Jesus lads, stop it. As a Comp Science student hoping to do development this thread is scaring the crap out of me. It takes 20 min for me to even figure out what I'm trying to do not to mention have a go at coding it. I would definitely brick myself.

kp.
In my experience, interviewers are looking for two things at the whiteboard. a) your approach and how you go about solving problems, and b) how you might behave under pressure. They all realise that the whiteboard is a mental block for many, they are very forgiving of that. If you are showing signs of blanking, they start helping you with prompts and turn the whole thing into a discussion.

Syntax really is trivial. You get to know it over time and experience. You get more proficient in a particular syntax as you use it. Interviewers know that. With the above in mind, you can always search the web for programming interview questions, there are loads out there and its a great exercise to sit down in front of the tele and try them out on a laptop.

m1nder

This video is a great example. The guy is going about the problem in a syntactically poor fashion, yet he is communicating his thought process and the interview is a relative success.

http://channel9.msdn.com/Blogs/TheChannel9Team/Gary-Daniels-and-Evan-Goldring-Mock-whiteboard-problem

yawha

m1nder wrote: »

You know, god bless this forum. In my experience No one ever really reads the op (requirements), People just respond with their code one trying to better / out do the other in a race to see who the best coder is.

Huh? I always do any short interview type question I see. It keeps me sharp. I couldn't care less about outdoing anyone.

Anyways, I was pretty much asked to design tetris on a whiteboard before for an internship interview. I'd never done any GUI programming (nor do I like it). It was a disaster complete with waffling and handwaving.

Robdude

Was this at SIG by any chance?

jester77

It's not about the solution or getting it right, it's about the approach and how you handle the situation. One of my favourite questions to give is to have someone to write a method to return the Fibonnaci sequence for a given number. I even give the formula, so you think it would be easy-ish to do but everyone seems to struggle. But what is good about it is you get to see how the interviewee handles it and how they think about the problem. I would then ask them about an alternative way of implementing the solution (iterative vs recursion) and about the efficiencies of one method over the other. And to wrap it up, I would get them to write a test for it and ask them what test data they would use to test it.

I don't care if the syntax is wrong, I just want see how the person thinks. Lots of hints & tips are given when the person is struggling just to see how far they progress.

m1nder

jester77 wrote: »

It's not about the solution or getting it right, it's about the approach and how you handle the situation. One of my favourite questions to give is to have someone to write a method to return the Fibonnaci sequence for a given number. I even give the formula, so you think it would be easy-ish to do but everyone seems to struggle. But what is good about it is you get to see how the interviewee handles it and how they think about the problem. I would then ask them about an alternative way of implementing the solution (iterative vs recursion) and about the efficiencies of one method over the other. And to wrap it up, I would get them to write a test for it and ask them what test data they would use to test it.

I don't care if the syntax is wrong, I just want see how the person thinks. Lots of hints & tips are given when the person is struggling just to see how far they progress.

Id like to have a go at that myself. Just to clarify...wouldn't you would have to start off with 2 given numbers? IIUC the Fibonnaci function for any given number is the sum of the prev 2 numbers. So wont I need 2 to start with ?

or

do you mean work backwards from a given number such as f(8) = 0 1 1 2 3 5 ?

jester77

m1nder wrote: »

Id like to have a go at that myself. Just to clarify...wouldn't you would have to start off with 2 given numbers? IIUC the Fibonnaci function for any given number is the sum of the prev 2 numbers. So wont I need 2 to start with ?

or

do you mean work backwards from a given number such as f(8) = 0 1 1 2 3 5 ?

I would give you the following formula, telling you that it calculates the Fibonacci sequence and ask you to to write a method to return the Fibonacci number for n. (Or you could print the whole sequence)

f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1)

m1nder

jester77 wrote: »

I would give you the following formula, telling you that it calculates the Fibonacci sequence and ask you to to write a method to return the Fibonacci number for n. (Or you could print the whole sequence)

f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1)

I dont understand the requirements.
Are you asking for a function that returns two numbers ?
The f(8) for example = 5 and 3
so what does the signature of this method look like if it needs to return two ints?

Seifer

m1nder wrote: »

I dont understand the requirements.
Are you asking for a function that returns two numbers ?
The f(8) for example = 5 and 3
so what does the signature of this method look like if it needs to return two ints?

He's not. For example n = 5 would be 5, n = 6 would be 8 etc.

m1nder

ah, so is the function taking in a position and returning the number? as in f(8) returns 13 or f(10) returns 34. Is that it?

Seifer

Well f(8) would be 21 and f(10) = 55 (remember it is zero based) but yes it is asking you to return the nth value of the Fibonacci sequence.

m1nder

Seifer wrote: »

Well f(8) would be 21 and f(10) = 55 (remember it is zero based) but yes it is asking you to return the nth value of the Fibonacci sequence.

Ok zero based. Can I ask, is there a correlation between the position and the number itself or would you always have to start at zero and iterate your way up?

Robdude

m1nder wrote: »

Ok zero based. Can I ask, is there a correlation between the position and the number itself or would you always have to start at zero and iterate your way up?

I've always seen it used in software development as an introduction to recursion. It's very easy to define a fibonacci number in terms of itself.

But it can be done with a moderately simple mathematical formula. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html I mean, I don't know enough math to figure it out myself, but if you have the formula it's easy to apply it. You do run into rounding errors and all the useful pitfalls though.

Having said that, I've never seen a legit reason for needing to find a fibonacci number other than 'just because'

m1nder

Robdude wrote: »

I've always seen it used in software development as an introduction to recursion. It's very easy to define a fibonacci number in terms of itself.

But it can be done with a moderately simple mathematical formula. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html I mean, I don't know enough math to figure it out myself, but if you have the formula it's easy to apply it. You do run into rounding errors and all the useful pitfalls though.

Having said that, I've never seen a legit reason for needing to find a fibonacci number other than 'just because'

Ok, after a bit of reading, firstly I now understand the question. Secondly, I am looking into recursion. I have used recursion before to walk through folder structures on disk etc.

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

Now I will admit, I did do a bit of research here so not quite a whiteboard situation. From debugging the above with test numbers and mapping out the tree in a spreadsheet, I now get it.

The function recurses back on itself twice for every call UNLESS the input "pos" is <= 1. That condition will eventually be reached because we are always subtracting from pos. The function is adding all the 1's returned to form the eventual answer.

Ive drawn out the tree here


You can see that if we run f(3) fro example, it recurses on itself eventually returning 3 x 1's. When added the result is 3.

So, then I have to ask, what if I input a large number? How many times will the function get called? It ran 5 times in the above example. There is a corellation there. So it eventually becomes very expensive perhaps.

yawha

Read the specification again:

f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1)

Also, while a good exercise to work it out on paper, don't think of recursion in terms of every little step, but rather, assume the nested function calls return what you expect, and check the correctness of all the base cases and the recursive cases.

You should check out Haskell. It's great for training the mind to think recursively.

m1nder

yawha wrote: »

Read the specification again:



Also, while a good exercise to work it out on paper, don't think of recursion in terms of every little step, but rather, assume the nested function calls return what you expect, and check the correctness of all the base cases and the recursive cases.

You should check out Haskell. It's great for training the mind to think recursively.

ah, ok. Does this fix it?

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

yawha

Yup.

Until someone enters a negative number, of course

EDIT: Actually, negative numbers will just cause themselves to be returned here, so it's not too bad. There's a potential for a loop until n overflows if you were to check for 0 and 1 explicitly. It's good in an interview to call out cases involving erroneous input, I think, to let the interviewer know you're thinking about it in depth. Adding an assert or using an unsigned int would be a good idea here.

m1nder

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.

The recursive solution, while beautiful and elegant is cumbersome. I just ran it for f(28). The answer was 417811. But to achieve that, the function was called 1028457 times. Took the program quite a while to run.