> This question has been asked in an Oracle interview.
I don't usually sit on the side of fence that complains about "write a function that does X" style questions in interviews, but I can't see how this is useful at all.
This just seems like one of those things that you either know off the top of your head, or you don't. If you asked me to derive the addition operation using only bit level operators, I might be able to come up with it, but it'd probably take me much longer than an interview allows. But to come up with divide is just not going to happen.
So if you don't know the answer off the top of your head, what use is this question?
Hello candidate. Please state in reverse alphabetical order every algorithm you have memorized. For completeness, provide an implementation of each algorithm on this sheet of paper.
I had the same idea. The problem is that shifting the bits to the right results in decimal points falling off the end, which is actually a big deal because they add up to something substantial (i.e. more than 1) by the end of the sum.
If N = 15692343, the result should be 5230781. Using "N /= 2", you get:
Yea, but you can correct for that. Because it's always going to be close but low. So just1 add number to it's self twice and if that's low add 1, repeat as needed.
PS: Or because there is no need for it to be fast just start with zero keep adding 1 until 3x+3 > n.
Disclaimer: I have 1 semester left of undergrad, so I've only done internship interviews so far. These are just my intuitions from visualizing myself as a senior engineer trying to hire competent engineers and whatever interview experience I have as a candidate.
During a technical interview, my experience is that it's best to talk to your interviewer and interact with them as you solve the problem. Usually you will get a nudge in the right direction, and you'll find the problem is not nearly as daunting as your initial impression.
Even if you don't end up getting the question right, the interviewer can get a positive impression based on your problem-solving approach and how well you communicate your thought process.
This really isn't as difficult of a question as you think, especially in an interactive environment (interview) as opposed to noninteractive (pencil and paper test). I would not be surprised to see this question on a test for sophomores or even 2nd semester freshmen in ECE here at UIUC. Not that everyone would get it right... But that's the point of tests and interviews anyway.
Finally, keep in mind that based on this question, the position the interview was for probably required some decent low-level understanding. If you find it daunting, it's probably not a position you would have interviewed for anyway, so you wouldn't have to worry about it. (Basing this on the statement that deriving addition with bit-logic would only be a "maybe" for you. This knowledge would be a given for most Computer Engineers or Electrical Engineers. I hope neither of those was your discipline of choice. No offense!)
This is definitely a second-year programming question, and I'd reasonably expect a second year CS student to solve it - as that's when you start learning about bitwise operations.
The question is, would graduated programmers work with bitwise operations? Or, even worse, programmers who haven't been to school, but still do good work?
I seriously doubt this question would be asked during an interview for any position that didn't involve a good deal of low-level knowledge. If you're hiring a hardware engineer or a systems engineer, why wouldn't you hire the one that understands what actually happens inside of a computer at a very basic level?
The people that are questioning the validity of this question are not in the target audience. This definitely falls more towards the Electrical and Computer Engineering end of the spectrum than CS.
When I ask questions like this in interviews, I am never expecting the interviewee to give the correct answer. In fact, if they could rattle it off right away it would be disappointing, and mean I'd have to try and figure out some other question I don't think they know the answer to.
The point of such questions is to test the person's problem-solving skills. What's being observed is how they go about trying to crack open the problem. As well as how they react to being thrown a curveball - do they roll up their sleeves and get to work, or do they stammer and freeze up under the pressure?
Secondarily, their working knowledge is also being tested, since if they pass the first two parts of the test then they should end up demonstrating some of that knowledge as they start working their way into the problem.
But I'm not interested in sitting around waiting for a correct solution. Just waiting long enough to get an answer to the questions I had. None of which are the same as the question I asked.
do they roll up their sleeves and get to work, or do they stammer and freeze up under the pressure?
Which, BTW, correlates more with whether they had seen that particular problem or not before (i.e. had subjected themselves to the tedious and soul-crushing task of prepping for interviews like this) than with any "intrinsic" problem-solving ability.
Perhaps. Though in my experience it seems to correlate better with whether someone enjoys a good brain-bender or not. Frankly, I'd prefer not to hire the kind of person who spends time doing cram sessions on compendiums of interview questions. If I get the impression that they're mostly operating on that particular kind of book smarts rather than working knowledge, then they're probably going to lose out to someone who didn't give me that impression.
And yeah, I am starting to think that problem-solving ability is at least somewhat intrinsic, to the extent that it has more to do with a person's temperament than anything else. It's certainly not the kind of thing I've ever seen much success in training someone to do. It seems to be the difference between initially reacting with, "Hmm, that's funny, I wonder why that happened," and "Ughh no no how do I make it stop!?"
If it were workable, I think a stellar interview question might be, "Do you find jigsaw puzzles more enjoyable with or without a picture?"
Because the answer might give some insight into a person's personality. Which is a the main thing a good interview is supposed to try and probe. If you make it that far then they should already have good reason to believe you've got the necessary skills.
So, in a sense, you're right. It's a good question because their is no correct answer. An interviewer who's asking many questions that have correct answers is an interviewer who didn't exercise due diligence during the pre-interview process.
Say you have 50 people, all of whom are capable of doing the job. You have to whittle that number down somehow. Might as well find a problem only 1 in 50 could answer.
Problem being that in programming you don't have 50 candidates to choose from. At the moment things seem to greatly favor the candidates rather than employers.
As a programmer I really like this, but as somebody who hires programmers it makes things difficult!
As others have noted, they probably are interested in how you approach the problem, not whether or not you can actually solve it. Just fire off a few ideas and outlines of how they would work. Here's what comes to mind (I had not seen this problem before) (I'm assuming the target number we are trying to divide by 3 is a non-negative integer of N bits, where N is fixed...e.g., a C unsigned int or something like that):
1. Implement addition at the bit level. Here's an example for 16-bit numbers:
def badd(A, C):
while C != 0:
t = A & C
A = A ^ C
C = (t << 1) & 0xFFFF
return A
That's actually all I need, because I could no do something like make two counters in a loop, both starting at 0. The first counter goes up by 1 each iteration, the second by 3. Stop when the second counter exceeds the target number, and return the first counter.
2. The solution in #1 can be greatly speed up, while keeping the same basic idea. Hard code in a table that contains decreasing powers of two in the first column, and the second column is 3 times the first column.
Now the loop starts at 0, and has two counters, but also has an index into the table. The first counter goes up by the first column at the current table index, the second counter by the second column. When a step would take the second counter past the target number instead of terminating, increment the index into the table.
3. Do division similar to how we would do it by hand. Here is an example for 16-bit numbers:
def div3(A):
m = 0x8000
r = 0
d = 0
while m != 0:
r <<= 1
if A & m:
r |= 1
if r == 0:
q, r = 0, 0
elif r == 1:
q, r = 0, 1
elif r == 2:
q, r = 0, 2
elif r == 3:
q, r = 1, 0
elif r == 4:
q, r = 1, 1
elif r == 5:
q, r = 1, 2
d = (d<<1) | q
m >>= 1
return d
4. Similar to the above, but first replace the if/elif chain with something based on table lookup, and work on more than one bit at a time.
5. Dividing by 3 is the same as multiplying by 1/3. Multiplication can be done by shifting and adding, and I've got adding from #1.
6. Oracle can afford big machines. Just do the whole thing with a big table lookup.
Hmm, what would be a typical experienced, successful programmer's response to this kind of a question if it were asked in, you know, a real-life setting?
"Look at bit-shift operators, and how they work on unsigned integers. Then think & and ^ and how they relate to addition (adders, after all, have to be implemented in terms of elementary operations like those). It's all pretty straightforward from there. Go the whiteboard and walk you through it? Huh? Look, it's an interesting problem, but I've got some regression tests to get straightened out by the end of the day that are like, totally messed up. They were written by some guy we hired on the basis of his ability to solve puzzle problems, but just ended up totally slacking and never tying the ends off of anything he did."
Really now, why should one's response in an interview be any different?
As a hiring manager for the last 15+ years, I would LOVE that kind of response.
That kind of response would save me a tremendous amount of time and enormous headaches dealing with a bad hire. I would thank you for your honesty, ask you a couple of perfunctory questions so it didn't seem too awkward and then let you go on your way in life to be someone else's problem.
Working on real projects that people actually want to pay for means working somewhat on the edge. Things go wrong. There are crunch time when solutions have to be delivered. The last thing I want at those times is to have to depend upon some mommie's special little snowflake who was too self-important to gamely work through some puzzle exercises during an interview for a job he claimed he wanted. That little snowflake will melt every time and leave me and the rest of his team to fend for itself. No thanks.
This should be exactly the kind of out-of-the-box thinking that these questions find. But something tells me the person who asked this question would not have been impressed, which is sad. They probably just want someone who memorized a division implementation in assembly.
That's how brain-teaser questions usually stump me - because I impose some limitation that doesn't exist. The question had pretty specific limitations, but the amount of resources wasn't one of them. To me the answer is valid. If the interviewer wanted to see an implementation of a division function they could have just said "please implement a division function"
Tangentially related: although you're probably suggesting trisecting an edge with origami folds (which is straightforward), the mention of dividing by three using physical methods reminded me of the classic trisecting-an-angle problem, which apparently is also solvable with origami folds [1], even though it isn't solvable with compass and straightedge [2].
Yup - they're the same thing... you trisect the angle from the corner, and end up with an edge neatly in thirds.
Surprised me when I found it too - neat stuff, paper.
n = 12345 # your input
s = ''.zfill(n) # fill as many zeroes
while len(s)>3: s=s[3:] # trim 3 zeroes each time
print 'divisible by 3' if len(s)==3 else 'nop'
If I had a dollar for every time in the 12 or so years I have written code as a profession, I have needed to implement tricks such as this I would have...
1 dollar.
I get that a company wants to hire smart people who can problem solve and think outside the box, but it doesn't really represent reality. I think if you had someone who wrote code like that you would have a maintenance nightmare since most people don't write code like that.
Of course not all situations are like mine. I write a few layers of abstraction away from the hardware, and live mostly in the managed code world. A low level/embedded systems developer may need to know these things.
It is a question about binary arithmetic. If you understand how computers work, you can get the solution. If you understand the divide and conquer approach, you can make a fast and efficient solution.
Why would it be a maintenance nightmare?! It is arithmetic with one input and one output! If an organization cannot validate that, they have no chance of making good software.
I disagree. This sort of thing is an exception, and not a rule. I would much rather a developer knows their framework, knows design patterns, separation of concerns, and most importantly writing clean code. As I said before, for enterprise applications, this sort of thing is rarely if ever necessary to know. Having someone who likes to bit twiddle just because they find it interesting is not always good for writing a solid maintainable code base.
An team can certainly make a lot of progress using the skills you list. But that is not sufficient to solve tough problems. You really do need at least a few people who understand things like memory hierarchies, Bloom filters, statistics, etc. To find these people you have to interview for them.
Y1=X1+X0+carry =X1+Y0 or X1+Y0+1 (extra bits of carry are in Y0)
Y2=X2+X1+X0+carry=X2+Y1 or X1+Y1+1 (extra bits of carry are in Y1)
The key is that in the above, there is only ever a single bit being carried between bit pairs, as the "01" pattern in 1/3 base 2 limits how carries propagate.
Here's a partial solution, which only works fro a few trivial cases (eg 2^N) since I haven't accounted for the possability of a single bit carry. For a full solution, maybe a conditional is required and an additonal logic operation or two to perform an increment on a pair of bits?
div3(int x)
{
int y=0;
while(x)
y ^= (x>>=2)
return(y)
}
Can anyone complete it?
Edit: formatting. Beats me how to do fixed width properly.
Edit: Oops. In the time it took me to write this qntm got there first!
I read the stack overflow. So someone at Oracle is dumb enough to want to reimplement / and/or wants to see if a future hire is dumb enough to be intimidated by a manager into doing something dumb (dumb like, say, reimplement /)
OK my solution is connect to a postgres sql DB server and something very much like "SELECT WIDTH_BUCKET(389, 999, 0, 333);" and the result will be something like 129. width_bucket asks for a sample, the highest bucket, the lowest bucket, how many buckets, and tells you which bucket to dump the sample into. You know, for histograms and stuff like that. So you make the largest bucket max_int or 999 in this easy scenario, and the number of buckets precisely 1/3 the number of buckets or 333 in this easy case, and postgres database will figure out the number of the bucket to stick your sample into, which coincidentally happens to numerically match 1/3 the sample.
Its possible Oracle has a function similar to width_bucket from postgres, but I have no idea because a Oracle license costs about 10 times the value of my house so I can't afford it, probably because they pay people to reimplement /.
Another fun way to attack this problem would be to go all trig on them and try to convince them its impossible to divide by 3 because you can't trisect an angle using classical greek construction techniques. Then you hit them with galois theory as relates to solving cubic equations, until their brains bleed and/or you get the job and/or removed by security. This stuff is all 200 years old, or so, but you'll still find cranks who think they can trisect angles using classical greek construction techniques. Maybe being smart enough to understand that overqualifies the applicant from working at a place that things reimplementing / is a wise use of brain power.
Is anyone else disappointed that the best answer (the standard div() function) was passed over in favor of massively inefficient bit-twiddling wankery?
If n < 0 record sign and invert. (If we can't use unary "-" then just use two blocks of code).
Set dividend to 0.
Loop against n, incrementing loop index by 3.
Increment dividend by 1 per loop iteration.
Invert dividend if we inverted n.
Dividend is your answer (or add the remainder to a more precise floating point result).
No bit twiddling. Small RAM footprint. Obviously correct. (This is really just an unoptimized version of the "clever" solution.)
For Oracle though -- create a database of numbers and their thirds and then lookup the answer.
On every microprocessor I have seen, increment has a different assembler instruction (e.g. INC) than add (e.g. ADD), so it is reasonable to say they are different.
fread and fwrite do their thing on N chunks of M bytes each, and fread returns the number of chunks that it managed to read. So the write writes 1 chunk of `number' byte each, then the read reads `number' chunks of `divisor' bytes each (obviously this value will be larger than the number of bytes in the file). And by returning the number of `divisor'-byte chunks needed to read a file of `number' bytes in size, you get your answer.
This just goes to prove that fread and fwrite are the biggest pile of crap.
He writes "number" bytes into a temporary file and then, starting from the beginning, re-reads them in blocks of "divisor" bytes each. "fread" returns the number of full blocks read from the stream.
Simple Perl solution, using string/numeric coercion. Don't think there's anything here you couldn't do in C. Uses a 30-item lookup table. I've made it round, rather than adding precision logic for recurring 3s...
I don't usually sit on the side of fence that complains about "write a function that does X" style questions in interviews, but I can't see how this is useful at all.
This just seems like one of those things that you either know off the top of your head, or you don't. If you asked me to derive the addition operation using only bit level operators, I might be able to come up with it, but it'd probably take me much longer than an interview allows. But to come up with divide is just not going to happen.
So if you don't know the answer off the top of your head, what use is this question?