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.
With that change, the program will run fine. The pointer is never dereferenced.
[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.
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.
Pseudocode (note: assumes that arrays are 1-based, not 0-based):
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
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:
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?
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.
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).
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:
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 ‘-’.
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.
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.
[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?
You’re given an array of integers in [1, n], and you have to discover whether any integers are missing.
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?
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.
No, it’s xbase. Specifically Clipper, but will work in Visual Foxpro as well.
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…
// 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.)
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.
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.
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:
- It wraps text for display in a fixed-space text box, such as a DOS window.
- The parameters are FullText, LineLength
- 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.
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.