RSS
Technical Interview 2
November 11th, 2010The second version of the technical interview comic. It took me forever to find an interview question that sounded complicated and mathy but was small enough to fit in a panel.
The idea was to make technical interviews sound scary but I think most CSE people will be able to figure this out pretty easily… >>
Oh gosh, this is going to be me in 7 minutes. I love the expressions XD
Of course it’s not 5……….. it’s 42.
Also, good luck Michael. 😛
:/
I loved the hand-drawn comics which added a bit of yourself in it.
me too actually! I’m glad to hear you liked the hand drawn ones.
The only reason I’m doing it digitally is because the newspaper wanted them to look nice and neat >>
his interview question is actually pretty common. Sadly, I was totally stumped when I was asked how to do it in O(n) time with O(1) space. Which company was this?
Yeah, I figured CSE majors would be like “what, that’s not hard at all”, haha. But I had to try to find a question that was mathy/complicated sounding but not chock full of CS jargon.
Umm… I think this was Amazon? Not sure.
so since I’m not doing the newspaper anymore after this quarter, it’s back to handdrawn in a couple weeks XD
Wait a second…WHAT?!?!? Who said YOU could quit The Daily? Are you graduating this quarter, or are the weekly deadlines a bit too much? If it’s the latter case, just talk to the editor — you could publish once every 2 weeks, or publish on a different day of the week. If it’s the former case, well…are you getting a job or going to grad school?
wow…i totally got that question at the career fair. not fun at all but in return i got 2 t-shirts, which made up for it 🙂
yeah, i kinda inferred that.. :/
neat and clean just doesn’t have “you” in it..NOT SAYING UR NOT CLEAN AND NEAT *betty: how is joy neat…*
i’m glad i’ll be able to see your work in it’s original form soon ;o
and if you ever do draw for the newspaper again, is there any way you can artistically have it in so that it’s acceptable for them as well?
I like your comics, but I agree that the digital ones are… not very personal. But you still capture those awesome facial expressions!
Hmm… I wonder if you can submit to M Review. I don’t know if there’s a section that would be appropriate for your work. They (I’m actually editor this year) accept visual art, so maybe. I will ask. If you’re interested, let me know.
The digital ones might not be as “personal”, but I tend to enjoy the nice clean drawings a lot more. Maybe if Joy did digital hand lettering, they would look more personal!
Scan it with an n-bit empty bitfield OR-ing it with 1 left-shifted by the number in the field. NOT the bitfield and its unsigned value is 2^x.
Oops bug, that only works for counting from 0. Counting from 1, subtract 1 from the field’s value before the left-shift.
Actually I suck, the first version was right, but you need n+1 bits in your bitfield.
SPOILER ALERT!!!
Add numbers in array. Subtract this number from the sum of numbers 1 to n. Tada…missing number!
I got this in an interview for a small tech company.
Oh, thats a lot simpler than what I was thinking
My answer would have been WHILE i <= N and have it check i to numbers in the array until it returns a FALSE.
I've been out of school for a while and havent done any coding since then, though, so that might not work
Nope, numbers can be repeated in the question asked here. For instance, if n=5, then the array could be [2,3,4,5,5,5]. Your answer would return -9, which is clearly wrong.
I never actually learned about this stuff, but my (probably extremely inefficient) method would be to make an integer array such that the array contains indexes 1, 2,…n, then iterate through the original array and add 1 to the corresponding key each time the value appears in the original array. After that, iterate through the new array to check which one has value 0.
This would also compensate for the nil which would be present if the array is 0 based or if the array position where the missing number should be is left empty and for the extra number which may be present (since the guy said “present at least once“, not “present exactly once“). Kylee’s method would work if the missing number were replaced with a 0 in the array; otherwise, if the missing number were replaced with a different number then the result would be smaller than the missing number, and if there is a nil then the code would need to include a check to make sure there is no adding of nils.
Woo 4-year-late replies.
What is “n”?
(Please don’t judge I’m in middle school)
No judging here! 🙂 Basically “n” is a placeholder for any number. When the guy in the comic says “1 to n” he’s talking about any range of numbers that start from one… for example, “1 to 10”, or “1 to 200” or “1 to 39489384”.
Put another way, he’s asking Auto to write a computer program that should find a missing number no matter how big or small the range of numbers is.
If you’ve learned algebra in school yet, “n” is sort of similar to “x” or “y” or “z” — it’s just a placeholder for some number.
Hope that made sense! 🙂
This could vary a lot if the array is sorted or not. Admittedly since I looked through the comments, I have figured out a decent method though.
/*We will assume the array has already been passed into the function/method It will be int[] Given for this example*/
int SIZE = Given.length;
int sumG = 0; //this will sum up the values in Given[] minus the repeated number
int sumA = 0; //sums up what the full array should be
int[] store = new int[SIZE]; //if the array is not sorted this will be needed to check for repeats
int storeSIZE = 1;
int[] temp = new int[SIZE]; //to help with sorting
int tempC = 0;
int missingValue;
boolean repeat = FALSE;
store[0] = Given[0];
for(int n = 1; n <= SIZE; n++){
sumA = sumA + n;
if(repeat != TRUE){
for(int m = 0; m Given[n-1]){
tempC = m;
for(int c = tempC; c<storeSize; c++){
temp[c] = store[c];
}
store[m] = Given[n-1];
storeSize++;
for(int c = tempC; c<storeSize; c++){
store[c+1] = temp[c];
}
sumG = sumG + Given[n-1];
}elseif(store[m] == Given[n-1]){
repeat = TRUE;
}
}
if(store[storeSize-1] < Given[n-1] && repeat != True){
store[storeSize] = Given[n-1];
sumG = sumG + Given[n-1];
storeSize++;
}
}else{
sumG = sumG + Given[n-1];
}
}
missingValue = sumA – sumG;
This code was not tested, so I don't have practical proof that it works, but the logic of what I was going for should be sound. Given the parameters that were given, only one number should be potentially repeated in this list, since there is only one number in the sequence missing.