# Tough Interview Questions

**URL:** <https://boards.straightdope.com/t/tough-interview-questions/267937>\
**Category:** In My Humble Opinion\
**Created:** [October 6, 2004, 10:38pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937 "2004-10-06T22:38:43Z")\
**Posts on this page:** 18\
**Page:** 3

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 7, 2004, 3:56pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/41 "2004-10-07T15:56:08Z")

</div>

> [@NE Texan](#):
>
> It’s possible that I didn’t quite grasp what you intended, but did you mean that:
> 
> (A [symbol]´[/symbol] B) [symbol]Ç[/symbol] (C [symbol]´[/symbol] D) = (A [symbol]Ç[/symbol] C) [symbol]´[/symbol] (B [symbol]Ç[/symbol] D) ?

Yes, yes I did. I just wasn’t having a good time of it last night.

---

<div class="post-metadata">

**Author:** ![NE\_Texan](https://avatars.discourse-cdn.com/v4/letter/n/e99b99/32.png) [@NE\_Texan](https://boards.straightdope.com/u/NE_Texan)\
**Post date:** [October 7, 2004, 5:23pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/42 "2004-10-07T17:23:48Z")

</div>

> [@ultrafilter](#):
>
> Yes, yes I did. I just wasn’t having a good time of it last night.

Good. I wasn’t trying to nitpick; this means that I understood what you were trying to say, where otherwise, it would mean I didn’t, and I’d have to try to figure it out.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [October 7, 2004, 5:31pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/43 "2004-10-07T17:31:46Z")

</div>

> [@ultrafilter](#):
>
> It’s probably easier to read that code correctly if you add in the ! operator that I left out of the line that should read if ( !badPointer ). Mea culpa.

With that change, the program will run fine. The pointer is never dereferenced.

---

<div class="post-metadata">

**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\
**Post date:** [October 7, 2004, 6:28pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/44 "2004-10-07T18:28:03Z")

</div>

> [@Punoqllads](#):
>
> Well, how about:
> 
> The sum of integers from 1 to n is n[sup]2[/sup] + n. So, in O(n) time and O(1) space you can get the sum of the array, S. n[sup]2[/sup] + n - S will be o - t, where t is the number that appears twice and o is the number that is omitted. If that number is odd, the solution is simple – sum the even numbers and compare that number to 2 \* (floor(n/2)[sup]2[/sup] + floor(n/2)). From that you can easily work out t and o. If t - o isn’t odd, you’ll have to wait until tomorrow, because I’m sleepy.

[spoiler]I’m sure you meant that the sum of the integers from 1 to n is (n[sup]2[/sup] + n)/2; correspondingly, the sum of the even integers should be floor(n/2)[sup]2[/sup] + floor(n/2). I’ve never seen this particular math hack before, but you might be able to get it to work, if you can figure out the odd case.

Most people think of summing the integers in the array and subtracting n(n+1)/2 to find the difference between the repeated and the missing integers. But they differ in what they do after that. As I said, there are variations on the same theme.  
[/spoiler]

---

<div class="post-metadata">

**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\
**Post date:** [October 7, 2004, 6:31pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/45 "2004-10-07T18:31:54Z")

</div>

> [@bitwise](#):
>
> [spoiler]I’m sure you meant that the sum of the integers from 1 to n is (n[sup]2[/sup] + n)/2; correspondingly, the sum of the even integers should be floor(n/2)[sup]2[/sup] + floor(n/2). I’ve never seen this particular math hack before, but you might be able to get it to work, if you can figure out the odd case.
> 
> Most people think of summing the integers in the array and subtracting n(n+1)/2 to find the difference between the repeated and the missing integers. But they differ in what they do after that. As I said, there are variations on the same theme.  
> [/spoiler]

I meant, “… if you can figure out the even case,” i.e., the case where the repeated and the missing integer have the same parity.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [October 7, 2004, 6:37pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/46 "2004-10-07T18:37:14Z")

</div>

Continuing on from by previous response to **bitwise** :

If the difference is not an odd number, determine how large a right shift would turn the difference into an odd number. Sum the terms that are odd (or even, just pick one) when shifted that far, and evaluate the difference between that sum and what the sum would be if all terms were in there exactly once. From that difference you can calculate what the values of t and o are. The shift calculation is O(1), the two sums are each O(n), so the whole calculation is O(n).

Pseudocode to follow.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [October 7, 2004, 8:59pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/47 "2004-10-07T20:59:22Z")

</div>

Pseudocode (note: assumes that arrays are 1-based, not 0-based):

```auto

Spoilerfied!
sum = 0
compare = 0

for i [1 .. n]
    sum += array*
    compare += i
end for

difference = compare - sum
shift = 0
odd = difference

while (0 == (odd & 0x1))
    odd >>= 1
    ++shift
end while

sum = 0
compare = 0

for i [1 .. n]
    if ((i >> shift) & 0x1)
        compare += i
    end if

    if ((array* >> shift) & 0x1)
        sum += array*
    end if
end for

if (compare - sum > 0)
    printline "The omitted value is ", compare - sum, "."
else
    printline "The omitted value is ", sum - compare + difference , "."
end if

```

---

<div class="post-metadata">

**Author:** ![EllisDee](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ellisdee/32/4531_2.png) [@EllisDee](https://boards.straightdope.com/u/EllisDee)\
**Post date:** [October 8, 2004, 1:39am UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/48 "2004-10-08T01:39:28Z")

</div>

I don’t think many of these questions would be asked in a real world interview. I’ve been on interviews where I was asked tricky questions. I of course got the job due to my awe inspiring programming ability, but the questions were nothing like what some of you guys are offering.

They gave me several printouts of functions and asked me what they did. I got all of them but one. The one I missed, the interviewer (my boss) couldn’t answer my questions about it, so they brought in their lead programmer. During the ensuing 10 minute debate about the function, he was able to show me how and why I had misunderstood the function.

That 10 minutes was the greatest performance of my life. In hostile territory without any allies, I was able to demonstrate my solid fundamental grasp of actual code they really used, and that I would be expected to help maintain, despite having gotten it wrong.

So, really, the idea is to present code and ask what it does. **ultrafilter** and **Punoqllads** did a good job of presenting that type of question.

I (obviously) don’t have the code snippet from my 10 minute debate, but I can probably recreate something close:

```auto

FUNC FUNCT1
PARA VAR1, VAR2
DO WHIL LEN(VAR1) > 0
  VAR3 = VAR2
  FOR VAR4 = 1 TO LEN(VAR1)
    IF SUBS(VAR1,VAR4,1) = ' '
      IF VAR4 <= VAR2
        VAR3 = VAR4
      ENDI
    ENDI
  NEXT
  IF VAR3 >= LEN(VAR1)
    VAR5 = VAR5 + CHR(13) + VAR1
    VAR1 = ''
  ELSE
    VAR5 = SUBS(VAR1,1,VAR3)
    VAR1 = SUBS(VAR1,VAR3,LEN(VAR1)-VAR3)
  ENDI
ENDD  
RETU (VAR5)

```

What does this function do?  
What parameters do you send it?  
What can you not send it?

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 8, 2004, 3:38am UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/49 "2004-10-08T03:38:38Z")

</div>

For what it’s worth, **bitwise** ’s question about the array is a special case of a question that I was actually asked when I interviewed with Microsoft.

The purpose of my question, if I had presented the right code, isn’t so much to see if you know what it’ll do, but to see if you know C++ inside out. Explaining why badPointer-\>foo() doesn’t crash requires you to understand at least a little bit what object-oriented code looks like when it’s compiled, which I think is necessary for expertise.

---

<div class="post-metadata">

**Author:** ![LtningBug](https://avatars.discourse-cdn.com/v4/letter/l/73ab20/32.png) [@LtningBug](https://boards.straightdope.com/u/LtningBug)\
**Post date:** [October 8, 2004, 6:46am UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/50 "2004-10-08T06:46:06Z")

</div>

> [@Ellis Dee](#):
>
> I don’t think many of these questions would be asked in a real world interview. I’ve been on interviews where I was asked tricky questions. I of course got the job due to my awe inspiring programming ability, but the questions were nothing like what some of you guys are offering.
> 
> They gave me several printouts of functions and asked me what they did. I got all of them but one. The one I missed, the interviewer (my boss) couldn’t answer my questions about it, so they brought in their lead programmer. During the ensuing 10 minute debate about the function, he was able to show me how and why I had misunderstood the function.
> 
> That 10 minutes was the greatest performance of my life. In hostile territory without any allies, I was able to demonstrate my solid fundamental grasp of actual code they really used, and that I would be expected to help maintain, despite having gotten it wrong.
> 
> So, really, the idea is to present code and ask what it does. **ultrafilter** and **Punoqllads** did a good job of presenting that type of question.
> 
> I (obviously) don’t have the code snippet from my 10 minute debate, but I can probably recreate something close:
> 
> ```auto
> 
> FUNC FUNCT1
> PARA VAR1, VAR2
> DO WHIL LEN(VAR1) > 0
> VAR3 = VAR2
> FOR VAR4 = 1 TO LEN(VAR1)
> IF SUBS(VAR1,VAR4,1) = ' '
> IF VAR4 <= VAR2
> VAR3 = VAR4
> ENDI
> ENDI
> NEXT
> IF VAR3 >= LEN(VAR1)
> VAR5 = VAR5 + CHR(13) + VAR1
> VAR1 = ''
> ELSE
> VAR5 = SUBS(VAR1,1,VAR3)
> VAR1 = SUBS(VAR1,VAR3,LEN(VAR1)-VAR3)
> ENDI
> ENDD  
> RETU (VAR5)
> 
> ```
> 
> What does this function do?  
> What parameters do you send it?  
> What can you not send it?

Since I’ve never worked with FORTRAN (which is what this looks like, to my untrained eye), I tried translating this to C++ (hopefully I correctly converted the 1-based indices to 0-based). I’ve also taken the liberty of giving the variables actual names (though keeping the numbers).

```auto

string function(string str1, int offset2)
{
   int iter4;
   int temp3;
   string str5("");

   while(str1.length() > 0)
   {
      temp3 = offset2
      for (iter4 = 0; iter4 < str1.length(); iter4++)
      {
         if (str1[iter4] == ' ')
            if (iter4 < offset2)
               temp3 = iter4;
      }
      if (temp3 >= str1.length() - 1)
      {
// assumption: str5 is treated as empty string if undeclared
         str5 = str5 + chr(13) + str1;
         str1 = ""; // str1.length() now 0, break out of while
      }
      else
      {
         str5 = str1.substr(0,temp3);
         str1 = str1.substr(temp3, str1.length() - temp3);
      }
   }
   return str5;
}

```

Huh, with a small change, this will do word-wrapping (that is, fit a lot of words into a multi-line text box, breaking at a ’ ’ or in the middle of a word if the word is too long). (Change that last str5 assignment to be str5 = str5 + chr(13) + str1.substr(0,temp3)). However, in my translation, at least, the space between two words will get stuck at the beginning of the line in front instead of at the end of the previous line.

Looks like your people need to use better variable names and comments.

Here’s the code with the appropriate fixes to make it a word-wrapper:

```auto

string function(string str1, int offset2)
{
   int iter4;
   int temp3;
   string str5("");

   while(str1.length() > 0)
   {
      temp3 = offset2
      for (iter4 = 0; iter4 < str1.length(); iter4++)
      {
// This line assumes that the string implementation has 
// implemented the [] operator
         if (str1[iter4] == ' ')
            if (iter4 < offset2)
               temp3 = iter4;
      }
      if (temp3 >= str1.length() - 1)
      {
// assumption: str5 is treated as empty string if undeclared
         str5 = str5 + '\r' + str1;
         str1 = ""; // str1.length() now 0, break out of while
      }
      else
      {
         if (str5.length() > 0)
            str5 = str5 + '\r' + str1.substr(0,temp3 + 1);
         else
            str5 = str1.substr(0, temp3 + 1);
         str1 = str1.substr(temp3 + 1, str1.length() - temp3);
      }
   }
   return str5;
}

```

I would definitely test this guy to make sure there are no off-by-one indexing errors. I also don’t think it’ll handle multiple spaces between words very well. I’d also want to add handling for punctuation such as ‘-’.

---

<div class="post-metadata">

**Author:** ![LtningBug](https://avatars.discourse-cdn.com/v4/letter/l/73ab20/32.png) [@LtningBug](https://boards.straightdope.com/u/LtningBug)\
**Post date:** [October 8, 2004, 6:47am UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/51 "2004-10-08T06:47:46Z")

</div>

Also, that was probably a lot lot lot easier to do sitting here on my couch with no time limit and no pressure (except the pressure to look good in front of y’all ;)). Took me 'bout half an hour or so.

---

<div class="post-metadata">

**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\
**Post date:** [October 8, 2004, 6:41pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/52 "2004-10-08T18:41:36Z")

</div>

> [@Punoqllads](#):
>
> Pseudocode (note: assumes that arrays are 1-based, not 0-based):
> 
> ```auto
> 
> Spoilerfied!
> sum = 0
> compare = 0
> 
> for i [1 .. n]
> sum += array*
> compare += i
> end for
> 
> difference = compare - sum
> shift = 0
> odd = difference
> 
> while (0 == (odd & 0x1))
> odd >>= 1
> ++shift
> end while
> 
> sum = 0
> compare = 0
> 
> for i [1 .. n]
> if ((i >> shift) & 0x1)
> compare += i
> end if
> 
> if ((array* >> shift) & 0x1)
> sum += array*
> end if
> end for
> 
> if (compare - sum > 0)
> printline "The omitted value is ", compare - sum, "."
> else
> printline "The omitted value is ", sum - compare + difference , "."
> end if
> 
> ```

Took me a while to understand exactly what you were doing here. I’ve never seen this particular method before. Here’s what I’ve seen:

Let x be the repeated integer and y be the missing integer. Summing all the integers in the array and subtracting n(n+1)/2 gives you x-y. As I said, most people will say this, but differ in what they do next.

Some people will say take the product of the integers in the array and divide by n! to get x/y. Then, solve for x and y. (Of course, computing a number on the order of n! will make it more likely that you’ll get an integer overflow.)

The solution I like is to compute the sum of the squares of the integers in the array and then substract the sum of the squares of the integers from 1 to n, which gives you x^2 - y^2. This works out nicely, because x^2 - y^2 factors into (x-y)(x+y), so you can divide by x-y to get x+y. Knowing x-y and x+y, allows you to solve for x and y easily.

---

<div class="post-metadata">

**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\
**Post date:** [October 8, 2004, 6:42pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/53 "2004-10-08T18:42:43Z")

</div>

[QUOTE=ultrafilter]  
For what it’s worth, **bitwise** ’s question about the array is a special case of a question that I was actually asked when I interviewed with Microsoft.

[QUOTE]

What is the general case?

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 8, 2004, 6:45pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/54 "2004-10-08T18:45:47Z")

</div>

> [@bitwise](#):
>
> What is the general case?

You’re given an array of integers in [1, n], and you have to discover whether any integers are missing.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [October 8, 2004, 7:30pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/55 "2004-10-08T19:30:32Z")

</div>

I’m a little confused about that question, **ultrafilter**. You’re given an array of n integers or some number greater than n? You just have to find if any integers are missing, not just which ones they are?

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [October 8, 2004, 7:36pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/56 "2004-10-08T19:36:12Z")

</div>

Sorry, I should’ve specified that you’re given n integers in [1, n]. And yes, it’s not necessary to say which ones they are.

---

<div class="post-metadata">

**Author:** ![EllisDee](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ellisdee/32/4531_2.png) [@EllisDee](https://boards.straightdope.com/u/EllisDee)\
**Post date:** [October 9, 2004, 11:53pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/57 "2004-10-09T23:53:39Z")

</div>

> [@LtningBug](#):
>
> Since I’ve never worked with FORTRAN (which is what this looks like, to my untrained eye),

No, it’s xbase. Specifically Clipper, but will work in Visual Foxpro as well.

> [@](#):
>
> I tried translating this to C++ (hopefully I correctly converted the 1-based indices to 0-based). I’ve also taken the liberty of giving the variables actual names (though keeping the numbers).

Those are rather large liberties. The variables are purposely given meaningless names to add to the difficulty. Also, you are given a pencil and a piece of paper, and that single piece of paper is the one with the code samples on it. As in, you don’t get to use a code window to plug in meaningful names to make it easier to grasp. You have to understand it as is.

Let me look at your code…

```auto

// assumption: str5 is treated as empty string if undeclared

```

Your assumption is half correct. xBase does not have variable declaration. The line “var5 = var5 + chr(13) + var1” will return an “undeclared variable” error if var5 hasn’t been declared. The only way xBase has to declare variables is by assigning a value. (You can use LOCAL and PUBLIC, but it won’t avoid the not declared error. As I said, there is no variable declaration in xBase.)

> [@](#):
>
> Huh, with a small change, this will do word-wrapping (that is, fit a lot of words into a multi-line text box, breaking at a ’ ’ or in the middle of a word if the word is too long). (Change that last str5 assignment to be str5 = str5 + chr(13) + str1.substr(0,temp3)). However, in my translation, at least, the space between two words will get stuck at the beginning of the line in front instead of at the end of the previous line.

But your fix will cause a “variable undeclared” error every time. However, the original question does indeed have a bug exactly where you pointed it out, but I’d have to spend some time to make it work.

In the original incarnation, the last var5 assignment statement in the program is actually the declaration for var5, which is why var5 doesn’t appear to the right of the equals sign. Given that, there is no simple fix to that bug.

> [@](#):
>
> Looks like your people need to use better variable names and comments.

Are you kidding, or serious? The whole point of the question is to see if the interviewee understands programming logic. If you filled it with comments and meaningful names, joe schmoe off the street could figure it out.

> [@](#):
>
> I would definitely test this guy to make sure there are no off-by-one indexing errors. I also don’t think it’ll handle multiple spaces between words very well. I’d also want to add handling for punctuation such as ‘-’.

Now I know your missing the point. As I said before, this isn’t the actual code I was given. This is code I threw together in about 15 minutes in the “post reply” area. I didn’t use an IDE, I didn’t compile or test it, I just threw it together as an example of the kind of questions people might see.

The intended answers to the three questions were:

1. It wraps text for display in a fixed-space text box, such as a DOS window.
2. The parameters are FullText, LineLength
3. You cannot send it a string less than LineLength characters long.

However, while #3 is true, it depends on a bug that causes the code to return only the last line of text no matter what, which is a pretty big bug. 🙂

I should have added an TRIM(LTRI()) in there to remove leading and trailing spaces, but I didn’t bother because, again, this is not actual code. The actual function (which had real variable names) was used to display a comments memo field in the lower half of a DOS screen.

Regarding hyphens, be careful of the programming trap of overthinking something. Had they put in hyphen checks, I’m sure they would have gotten line wraps on negative numbers, which appeared frequently in the comments memo field. The KISS principle is your friend.

---

<div class="post-metadata">

**Author:** ![EllisDee](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ellisdee/32/4531_2.png) [@EllisDee](https://boards.straightdope.com/u/EllisDee)\
**Post date:** [October 9, 2004, 11:57pm UTC](https://boards.straightdope.com/t/tough-interview-questions/267937/58 "2004-10-09T23:57:31Z")

</div>

> [@LtningBug](#):
>
> Also, that was probably a lot lot lot easier to do sitting here on my couch with no time limit and no pressure (except the pressure to look good in front of y’all ;)). Took me 'bout half an hour or so.

In addition to the lack of pressure and time limit, the fact that you could play with it at a computer substituting variable names probably helped a lot. I would have been curious to see how you would have handled a printout, a pencil, and an empty room.

It took me around 20 mintes to come up with my answer. I think it was “there is a bug in the code.” hehheh. That’s what brought on the debate with their lead programmer.

Good show, though, you did translate it properly.

[Previous page](https://boards.straightdope.com/t/tough-interview-questions/267937.md?page=2)