Programming Interview Problems

[key78]

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?

Returns the largest sum of contiguous integers in the array
Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8

Reverse a string without the use of a temporary variable.


Any ideas welcome.

 

[BillLeeLee]

Are there any time/space constraints on these problems?

Like having to do the first one in O time and space? If not, one way would be to sort the array (like through mergesort or quicksort) and then iterate through it to find the duplicate, but that is O(n log n).

edit: some stuff cut

 

[444]

Interesting problems... I must say I did not know the answer, but the All Powerful Google did:
How to reverse a string without a temporary var:
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_21008644.html

 

[mikeblas]

Sorting takes way too long. There's a solution that runs in O(n/2) average, O worst case.

Returns the largest sum of contiguous integers in the array
Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8

This question doesn't match the answer. The largest sum of contiguous integers is 5, because the only two contiguous integers are 2 and 3. Did you mean adjacent? Then the answer might be -10, since -10 has a larger magnitude than 8.

These are very easy questions; they're about as hard as I'd ask in a phone screening. If you'd like to take guesses, that would be great; we can help you with your progress--otherwise, I can't see how this is different than a homework problem.

 

[doh]

first one:

int ints[999999] = { ... };
int b[999999] = {};
int i;
for (i=0;i<1000000;i++)
{
  b[ints[i]] += 1 
  if (b[ints[i]] > 1)
  {
    duplicate_num(ints[i])
    break;
  }
}

2nd one:

int ints[6] = { -10, 2,3,-2,0,5,-15 };
int s,sum = ints[0] + ints[1];
int i,j;
for (j = 1; j<4;j++)
  for(i = j+1;j<5;i++)
  {
    s=ints[j]+ints[i];
    if (s>sum)
      sum=s;
  }

that should work


for the last one:

<?php
$str = "Hello World";
$reversed = strrev($str);
?>

Oh, was there a language constraint...?

 

[BillLeeLee]

Sorting takes way too long. There's a solution that runs in O(n/2) average, O worst case.


This question doesn't match the answer. The largest sum of contiguous integers is 5, because the only two contiguous integers are 2 and 3. Did you mean adjacent? Then the answer might be -10, since -10 has a larger magnitude than 8.

The way I understand it, it sounds like it's asking for an algorithm to find the contiguous subset of the array that gives the largest sum, and 8 would be correct if you take the subset {2, 3, -2, 0, 5}.

 

[mikeblas]

The way I understand it, it sounds like it's asking for an algorithm to find the contiguous subset of the array that gives the largest sum, and 8 would be correct if you take the subset {2, 3, -2, 0, 5}.

Oh, the largest continuous subset? Yeah, could be that. That's a more interesting problem.

 

[nonameo]

me = fail

 

[svet-am]

Interesting problems... I must say I did not know the answer, but the All Powerful Google did:
How to reverse a string without a temporary var:
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_21008644.html

that methods SOUNDS great at first, until you think about float. If you're using a short for example, and you've got this currently:

a = 1
b =  0xFFFF

then this example doesn't cut it since b = a + b will cause overflow. even if the short is unsigned, it'll cause wraparound. Then you have to start doing datachecking on all of the data and it quickly gets a lot more complicated than it sounds at first.

 

[nonameo]

anyone figure out #2? I hacked and hacked away at it and I started to come up with something that involved finding the largest negative number and splitting the array into 2 there, and checking it... but it deadended with some issues. The only other thing I can think of is to iterate through each possible subarray and compare the results.

 

[mikeblas]

Each possible subarray makes it O(n^2). There's an O solution based on dynamic programming.

 

[doh]

O solution for #2 for arbitrary length int arrays

#include <stdio.h>

int main() {

  int arr[10] = {-10,2,5,5,10,6,2,-3,-5,-10};
  int i, sum;

  sum = arr[0] + arr[1];

  for (i = 1;i<(sizeof(arr) / sizeof(int)) - 1;i++)
    if (arr[i]+arr[i+1] > sum)
      sum=arr[i]+arr[i+1];
  printf("High Sum: %d\n",sum);

  return 0;
}

 

[Lord of Shadows]

Well jebus, I wrote a whole thing and accidently hit the back button. =(

Anyway, I was under the impression that you needed to find a continous subset with the largest sum (in your case 2,5,5,10,6,2 : 30) for that one. Programming that in O would make my head explode (and if they wanted an O answer in an interview I dont think I would want to work there.) ;o)

As for the other questions, I would sort and search for the number list, brute force the subset thing (and implement a better solution if I ever figured one out dont care to think for one now) And Im sure my solutions to the string are cheating. (print it out backwars? use the null terminator as a variable?)

Edit: Just read dohs first set of programs, surprised I didnt think of the number list one. (Duplicating everything in memory is something I would try to avoid normally) Oh and btw, how do I view the experts exchange thing, asks me for a subscription? (Maybe I should look a little more into the site) --amazing how long I've been avoiding expert exchange answers because I thought it was subscription only =P

 

[mikeblas]

O solution for #2 for arbitrary length int arrays

Well, I'd hope any solution didn't use a hard-coded array length. What you've provided works fine for consecutive pairs of integers, but doesn't tell us about sums over larger groups.

I think the goal of the string reversal question is to demonstrate that the candidate knows the XOR identity trick. If someone asked me that question, I'd code the program in assembler -- I think I have an air-tight argument that a register isn't a "temporary variable".

 

[sharpenyourteeth]

here is my solution to the reverse string problem. i'm assuming my first and last variables aren't considered temporary variables since they're not holding a character from the string or anything.

#include <iostream>
#include <string>
using namespace std;

void reverse_string(string& x)
{
     int first = 0;
    int last = x.length() - 1;

	while (first < last) 
	{
		x[last] += x[first];
		x[first] = x[last] - x[first];
		x[last] -= x[first];
	
		first++;
		last--;
	}

	
}
void main()	
{

   string x("backwards");
   reverse_string(x);
   cout << x << endl;
}

 

[Shadow2531]

here is my solution to the reverse string problem. i'm assuming my first and last variables aren't considered temporary variables since they're not holding a character from the string or anything.

#include <iostream>
#include <string>
using namespace std;

void reverse_string(string& x)
{
     int first = 0;
    int last = x.length() - 1;

	while (first < last) 
	{
		x[last] += x[first];
		x[first] = x[last] - x[first];
		x[last] -= x[first];
	
		first++;
		last--;
	}

	
}
void main()	
{

   string x("backwards");
   reverse_string(x);
   cout << x << endl;
}

I'm not certain the following isn't buggy, but you could take your example and do it like this:

#include <iostream>
#include <string>

using namespace std;

void reverse( string& s ) {
    for ( string::iterator first = s.begin(), last = s.end(); first < --last; ++first ) {
        *last += *first;
        *first = *last - *first;
        *last -= *first;
    }
}

int main() {
    string x("abcdefg");
    reverse(x);
    cout << x << endl;
}

 

[Fryguy8]

In the first problem, do we know how many elements are in the array?

For example is it an array of 10,001 elements, 1 through 10000 and then an extra one? If so, just sum the array (O), and then subtract n(n+1)/2 where n is 10000. The difference will be the value of the extra number.

If this is not guaranteed, and the size of the array is n, where n < 10000 then you are forced to be o(n^2) because you have to compare every element to every other element. The best answer would be to do a linear insertion sort that stops if it meets a match while finding the right spot:


The other problems are painfully trivial, except for reversing w/o a temp variable, which is easy but hard to explain. It's also easier in languages with true pointers (ie, not java).

 

[doh]

In the first problem, do we know how many elements are in the array?

For example is it an array of 10,001 elements, 1 through 10000 and then an extra one? If so, just sum the array (O), and then subtract n(n+1)/2 where n is 10000. The difference will be the value of the extra number.

Here's an implementation of yours:

#include <stdio.h>


int main()
{
  int arr[10] = { 1,2,2,3,4,5,6,7,8,9 };

  int i,sum=arr[0],bad = -1;
  int cnt = sizeof(arr) / sizeof(int) -1;

  for (i = 0;i< cnt ;sum+=arr[++i]);
  bad = sum - (cnt*(cnt+1))/2;
  printf("Duplicate number: %d\n",bad);
  return 0;
}

It works for even lengths and odd lengths.

 

[mikeblas]

Here's an implementation of yours:

Your loop is a little convoluted, but it does work.

For example is it an array of 10,001 elements, 1 through 10000 and then an extra one? If so, just sum the array (O), and then subtract n(n+1)/2 where n is 10000. The difference will be the value of the extra number.

That's a good observation. When I read the problem, I assumed the array was n in size, and not n+1, so I discarde the sum-of-series solution.

If this is not guaranteed, and the size of the array is n, where n < 10000 then you are forced to be o(n^2) because you have to compare every element to every other element. The best answer would be to do a linear insertion sort that stops if it meets a match while finding the right spot:

Sorting isn't required as there's still an O solution as Doh posted. It can be made 16x more efficient for memory use by packing the flags into bits instead of using a whole integer for each one.

The other problems are painfully trivial, except for reversing w/o a temp variable, which is easy but hard to explain. It's also easier in languages with true pointers (ie, not java).

I don't think your assertion about pointers is true at all. Indexing characters in an array is probably easier to read than pointers. Meanwhile, will you post your "painfully trivial" solution to the second problem, showing the maximum sum of the contiguous subset?

 

[doh]

Your loop is a little convoluted, but it does work.

I was in a weird mood this morning.

 

[Shadow2531]

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?

My interpretation of that is:

An array size of >= 2; (never says how many integers except that one integer is in there twice, so there has to be at least 2.)

1 < allowed integers < 1000000 (It said *between* 1 and 1000000)

So,

int x[2] = { 1, 1 }
int x[2] = { 1000000, 1000000 }
int x[4] = { 3, 3, 2, 2 } ( two integers are in the array twice )
int x[3] = { 3, 3, 3 } (it's in the array 3 times. I assume *total*)

would not satisfy the requirements and

int x[2] = { 2,2 }
int x[2] = {999999, 999999}
int x[5] = { 7, 15, 32, 32, 3 }
int x[5] = {2, 2, 5, 5, 5 ); (Only 1 int that's in there twice. The other is in there 3 times )

would satisfy the requirements.

I'm not saying thats' the desired or correct interpretation. I'm just saying, that's what I get out of it and the problem requires more info to know for sure.

 

[mikeblas]

I'm not saying thats' the desired or correct interpretation. I'm just saying, that's what I get out of it and the problem requires more info to know for sure.

I guess those are all reasonable points and interpretations. key78 has apparently abandoned the thread, so we may never know what they wanted.

At the company where I work, we want to learn how a candidate approaches problems both technically and socially. An important part of solving the problem in an interview is talking through the problem, then. I sometimes ask candidates vague questions in order to push on their communications skills, and their flexability, as well as their design skills.

 

[1tbs4life]

we want to learn how a candidate approaches problems both technically and socially.

So when you give difficult problems to people that you're interviewing, how much importance do you place on the end result (whether a solution was found or not) versus the thought processes they go through when trying to find an answer?

Also, I know you said talking through the problem is important, but how do you or other interviewers handle people that can perform well only when sitting down and thinking quietly? If someone you're interviewing stays still most of the time and is very quiet but thinks up a solution to a tough problem do you overlook their inability to enunciate their thoughts and hire him/her or tell them to take a hike?

I'm pretty sure you work at Microsoft, so I'm guessing you give out a lot of brain teasers. Here's something I've been curious about for a long time: How do you know that people haven't just already heard the problem? There are a ton of books out there filled with solutions to these problems. How do you know that someone hasn't read/heard the solution before and isn't just BSing you the whole way through?

 

[Shadow2531]

I guess those are all reasonable points and interpretations. key78 has apparently abandoned the thread, so we may never know what they wanted.

At the company where I work, we want to learn how a candidate approaches problems both technically and socially. An important part of solving the problem in an interview is talking through the problem, then. I sometimes ask candidates vague questions in order to push on their communications skills, and their flexability, as well as their design skills.

Yeh, my answer to question #1 is, "I need clarification on the requirements of the array and here is why...".

Getting clarification would help decide what the requirments of the array are and whether I need to check to see if the array is valid. From the problem, I assume the array my solution would get would always meet the requirements, but that's a big assumption.

If you're told to do something and you don't know exactly what you're supposed to do, you better be asking or be really good at guessing. If all else fails, you're left with a solution that is based on your interpretation, which can be fine or really undesired.

 

[RedShark]

Here's my solution to the "Returns the largest sum of contiguous integers in the array" problem:

int main(int argc, char* argv[])
{
  const int size = 7;
  int vals[size] = { -10, 2, 3, -2, 0, 5, -15 };
  int sums[size];
  
  sums[0] = vals[0];
  
  for (int i = 1; i < size; i++)
  {
    if (sums[i - 1] + vals[i] > vals[i])
    { sums[i] = sums[i - 1] + vals[i]; }
    else
    { sums[i] = vals[i]; }
  }
  
  int max = -0x7fffffff;
  for (int i = 0; i < size; i++)
  {
    printf ("%d ", sums[i]);
  }
  
  return 0;
}

The output was, for the example: -10 2 5 3 3 8 -7

As mikeblas said, it's a dynamic programming problem. It doesn't actually find the maximum at this point, but adding that functionality would take little work, and the bound on running time would clearly remain O.

Here is another try at it that retains the O runtime bound, and uses only constant extra space:

int main(int argc, char* argv[])
{
  const int size = 7;
  int vals[size] = { -10, 2, 3, -2, 0, 5, -15 };
  int sum;
  int max = -0x7fffffff;
  
  sum = vals[0];
  
  for (int i = 1; i < size; i++)
  {
    if (sum > max)
    { max = sum; }

    if (sum + vals[i] > vals[i])
    { sum = sum + vals[i]; }
    else
    { sum = vals[i]; }
  }
  
  if (sum > max)
  { max = sum; }
  printf ("%d ", max);
 
  return 0;
}

I don't know for sure if these are correct, but they're close Edit: Yeah, -0x80000000 works better for initializing max.

 

[mikeblas]

So when you give difficult problems to people that you're interviewing, how much importance do you place on the end result (whether a solution was found or not) versus the thought processes they go through when trying to find an answer?

Also, I know you said talking through the problem is important, but how do you or other interviewers handle people that can perform well only when sitting down and thinking quietly?
If someone you're interviewing stays still most of the time and is very quiet but thinks up a solution to a tough problem do you overlook their inability to enunciate their thoughts and hire him/her or tell them to take a hike?

It depends on a lot of things.

The interview process is a loop, first off -- the candidate talks to four to eight people, maybe even more. If I don't think something went well, then I can add it to the email and ask the next interviewer to push on it. If three guys in a row don't think the candidate can get through a problem, then they probably aren't a good candidate.

That group approach helps decide if the guy has the yips, is tired from travelling, and so on.

We're also trying to establish the candidate's level. It's not necessarily a hire no-hire decision; if we hire them, what's their job level? Are they really junior, or really senior?

For more junior candidates, they had better be able to code simple stuff completely. Reversing string and finding the missing/duplicated number are things I'd consider must-do. Nobody on one of my teams would need to go away and think quiety about those.

Like it or not, software development is a team sport. If a candidate can't hack it in an inteview, will they be able to help other members of the team? Write good comments or a spec? Explain their design in a review meeting? Meet the war room when their bug has cuased the product to cut a new RC, or slip a beta?

I'm pretty sure you work at Microsoft, so I'm guessing you give out a lot of brain teasers. Here's something I've been curious about for a long time: How do you know that people haven't just already heard the problem? There are a ton of books out there filled with solutions to these problems. How do you know that someone hasn't read/heard the solution before and isn't just BSing you the whole way through?

Personally, I don't like the brain teaser question. (My answer to "Why are manhole covers round?" was always "Because manholes are round.") They're hard to specify, not always easy to concisely communicate, and often irrelevant. Worst, they don't offer enough surface area or depth for discussion. I'd like to think they're on the wane across the company, but I think disciplines other than development end up asking them.

To answer your question, finding a posuer is pretty easy. The books and websites are sometimes wrong, and word of bad answers spreads pretty quickly. They give markers. Asking why always helps -- if they understand the answer, or can handle a chaneg to the problem and still get the explanation right, then they're probably okay. They can't have read every question, and the loop goes on all day. Odds are against them.

I do like to ask estimation questions. I think it's important for engineers to understand scale and estimation. You might propose a solution that takes lots of memory; but if you don't do the math, it might turn out to take a trillion bytes of memory. Well, duh. (See Programming Perals by John Bentley, or How to Solve It by Polya.)

So asking how much water flows out of the Mississippi, or how many cars go up I-5 in a day, all seem reasonable and I wouldn't call them "brain teasers".

 

[mikeblas]

I don't know for sure if these are correct, but they're close Edit: Yeah, -0x80000000 works better for initializing max.

What about INT_MIN? Or setting it to sum, which you initialize from vals[0]? That would also take care of a bug -- you don't handle a list of size 1 correctly.

Otherwise, I think the code is correct; great work!

 

[RedShark]

Yeah, I always forget about those constants. In code like this, when there's no excuse not to make it portable, using INT_MIN would be the way to go. limits.h ftw!

 

[mikeblas]

Actually, I think intializing from sum is the way to go.

 

[RedShark]

Yeah that eliminates the need for the extra if-statement outside the for-loop too.