5 ms·

> 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 quest

• Foy 14y ago
  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.
• Someone 14y ago
  As with all such questions, it attempts to test (creative) thinking. Also as with (almost) all such questions, knowledge can prevent that. For this example, 1/3, in binary, is 0.0101010101… From there, writing out the long multiplication will give hints towards a solution. Untested, so likely erroneous: uint n = 12356; uint result = 0; while( n > 0) { n >>= 2; result += n; // cheating } If you do not want to cheat, write a function that computes x minus 1 using but twiddling, and add a loop.
  • aristidb 14y ago
    The result is off by 1. :) Not bad though!
    • Retric 14y ago
      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.
  • qntm 14y ago
    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: 0 + 3923085.75 = 3923085.75 + 980771.4375 = 4903857.1875 + 245192.859375 = 5149050.046875 + 61298.21484375 = 5210348.26171875 + 15324.5537109375 = 5225672.81542969 + 3831.13842773438 = 5229503.95385742 + 957.784606933594 = 5230461.73846436 + 239.446151733398 = 5230701.18461609 + 59.8615379333496 = 5230761.04615402 + 14.9653844833374 = 5230776.01153851 + 3.74134612083435 = 5230779.75288463 + 0.935336530208588 = 5230780.68822116 + 0.233834132552147 = 5230780.92205529 + 0.0584585331380367 = 5230780.98051382 + 0.0146146332845092 = 5230780.99512846 + 0.0036536583211273 = 5230780.99878211 + 0.000913414580281824 = 5230780.99969553 + 0.000228353645070456 = 5230780.99992388 ... which eventually reaches the correct answer for any desired degree of accuracy. But using "N >>= 2", you get: 0 + 3923085 = 3923085 + 980771 = 4903856 + 245192 = 5149048 + 61298 = 5210346 + 15324 = 5225670 + 3831 = 5229501 + 957 = 5230458 + 239 = 5230697 + 59 = 5230756 + 14 = 5230770 + 3 = 5230773 + 0 = 5230773 which is out by 8.
    • tzs 14y ago
      This can be fixed by keeping track of some of the spillage. Here's a solution using this approach that works for 32-bit unsigned integers: def badd(A, C): while C != 0: t = A & C A = A ^ C C = (t << 1) & 0xFFFFFFFF return A def div3(ah): qh = 0 ql = 0 al = 0 while ah != 0: al = (al >> 2) & 0x0000FFFF al = badd(al, (ah & 0x3) << 14) ah = ah >> 2 qh = badd(qh, ah) ql = badd(ql, al) if ql & 0xFFFF0000: qh = badd(qh, ql >> 16) ql = ql & 0xFFFF if ql > 0x8000: qh = badd(qh, 1) return qh
• madrox 14y ago
  The answer to your question is in a previous HN link: http://raganwald.posterous.com/i-dont-hire-unlucky-people http://raganwald.posterous.com/i-dont-hire-unlucky-people 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.
  • Tloewald 14y ago
    Of course this was given as an example of how NOT to select engineers.
  • jakejake 14y ago
    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!
• kevhsu 14y ago
  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!)
  • Shenglong 14y ago
    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?
    • kevhsu 14y ago
      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.
• bunderbunder 14y ago
  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.
  • toomuchcoffee 14y ago
    The point of such questions is to test the person's problem-solving skills. As if you're qualified to tell one way or another.
    • crusso 14y ago
      As if you're qualified to tell one way or another. I hope you appreciate the irony of you sarcasm.
  • toomuchcoffee 14y ago
    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.
    • bunderbunder 14y ago
      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?"
• tzs 14y ago
  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.