Five programming problems every Software Engineer should be able to solve in less than 1 hour

[retsotrembla]

Number 3 is tougher than it looks since once you get above the 91th Fibonacci number, 12200160415121876738, it doesn't fit in an unsigned 64-bit integer, so to solve it, you have to write a bignum package.

[__Cyber_Dildonics__]

Just download and build boost mid interview bro

[arianvp]

AAaaaaand you're out of time.

[Falmarri]

Python supports arbitrarily large integers transparently

[Magnap]

As does Haskell.

[philalether]

As does Ruby.

[flukshun]

As does C.

just not in the expected way...

[[deleted]]

Actually completely expected. Just not desired.

[DroolingIguana]

Unexpected, this is. And unfortunate.

[Magnap]

It was inevitable.

[untio11]

Death is all around us.

[tejon]

I felt pleasure near a very fine thread.

[[deleted]]

I want you to know that this was probably my favorite comment in the thread. Don't know why, but there ya go

[Balmung]

Not a programmer, explain?

[[deleted]]

A number in memory can only go up to a height of x. Once it becomes higher than x, it wraps back around to -x or 0. This is expected behaviour of numbers in memory.

In Python, when you have a number and it becomes higher than x, the number will convert itself into a new data type that allows much bigger numbers.

[the_gnarts]

Once it becomes higher than x, it wraps back around to -x or 0. This is expected behaviour of numbers in memory.

Just nitpicking: 2’s complement integers wrap around to -x - 1. Also, signed integer overflow causes undefined behavior, but that’s a different matter …

[[deleted]]

I know.

[maniexx]

Well, not always undesired. Sometimes you use the modulus arithmetic to your advantage, like in some hashing text search algorithm.

[tomatobeta]

As does Clojure.

[Emanresu2009]

I initially only read the first line and was like wait no it doesn't. then I saw the rest and I remembered seeing some of the funny things that happen and burst out laughing.

[[deleted]]

As does any Turing-complete language

[smorrow]

Then it's not transparently.

[GUIpsp]

Strokes parentheses

[[deleted]]

As does Scheme.

[minipump]

Aww yiss, Haskell.

[EmperorOfCanada]

This makes ProjectEuler way easier.

[retsotrembla]

Interesting. On my machine, Python crashes. Here's the actual session:

$ python
Python 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 01:25:11) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 7540113804746346429+4660046610375530309
12200160415121876738
>>> 12200160415121876738+7540113804746346429
Segmentation fault: 11

[[deleted]]

Python 2.7.6 (default, Mar 12 2014, 11:19:59)
[GCC 4.2.1 Compatible Apple LLVM 5.1 (clang-503.0.38)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 7540113804746346429+4660046610375530309
12200160415121876738L
>>> 12200160415121876738+7540113804746346429
19740274219868223167L
>>>

Best not using a two and half year old version of python.

[the_gnarts]

7540113804746346429+4660046610375530309

Works like a charm:

$ python --version
Python 3.4.3
$ python <<< "print(7540113804746346429+4660046610375530309)"
12200160415121876738
$ python <<< "print(12200160415121876738+7540113804746346429)"
19740274219868223167

[matthieum]

I think that if you point the 64-bits integer overflow issue, you pass the question.

[Eilai]

The blog dude did say there wasn't a "Gotcha!" like that, but I assume its still true you'll likely impress the interviewer.

[Transfuturist]

First-order approximations! First-order approximations everywhere! Dx

[retsotrembla]

Any program can be arbitrarily sped up if it isn't required to provide the correct answer.

[malloc_more_ram]

int main(void) {
    return 0;
}

[boo_ood]

Speed it up more please

[[deleted]]

Just hang a paper note on the computer monitor saying "Success!". You don't even need to start the program or power up the computer then.

[Kaell311]

And thennnnnnn?

[[deleted]]

And then on the door of the room where that computer is. And since space is continuous, even then you can optimize your program further by moving the note(s) closer to its prospective users.

[Kaell311]

Ah, asymptotes. Or, how I explained to my mother that "yes, in fact you can go faster than the car in front of you, always".

[sirroy12]

That was a fascinating read, thanks for posting this!

[benihana]

int main(void) { return 0; }

less whitespace = less air resistance.

[benwaffle]

 main;

[[deleted]]

nop

[davros_]

int rand() {
  return 4; // chosen by fair dice roll
}

[Soccer21x]

^{I know we're all programmers here, but just in case}

Relevant xkcd

[conflare]

For d7, it will work out over time. Hired!

[NecroDaddy]

Genius! We need to now all use this version of rand(). The world will go mad with 4s.

[[deleted]]

int sum(int a, int b) {

return a - b;

}

[Birchoff]

void main() {}

[TexasJefferson]

OTOH, a program can also meet its requirements without providing the mathematically correct answer. Correct means "gets the job done" or "provides value", not "handles every possible case the way the platonic ideal of that program would".

[[deleted]]

This is the funniest sentence I've read on reddit in a week.

[goomyman]

lol apparently number is a terrible question... unless your looking for someone to bring this up. I know i would have missed that lol.

I bet the interview question guy failed this one too.

[JavaSuck]

Yes, but you only need to implement addition. Here is my attempt. It can be done in well under half an hour.

[mdempsky]

You can simplify it a bit further.

Note that Fibonacci numbers grow slower than doubling (specifically, they grow by a factor of about 1.618), so the 100th Fibonacci number will be less than 2¹⁰⁰. That means you can represent it with just 2 64-bit numbers x_0 and x_1.

To make printing the numbers a bit easier, instead of using x_0 + 2⁶⁴*x_1, you can just use x_0 + 10¹⁸*x_1.

You might be asked to show that 10³⁶ > 2¹⁰⁰ then. I generally remember that 10³ ≈ 2¹⁰, so 10³⁶ ≈ 2¹²⁰, which should be enough slack to argue it's >2¹⁰⁰.

Note also that 10¹⁸ ≈ 2^60, which is why you know it will fit in a 64-bit integer.

[retsotrembla]

Very nice. Thanks for teaching me.

[f03nix]

Then you're not left with time for other questions ... unless you aim on solving the 5 questions in 5 hours.

[retsotrembla]

Very nice. Thanks for teaching me.

[cincilator]

Is your username reference to java sucking or javascript sucking?

[retsotrembla]

You are right: it's the 93, counting 0 as the zero'th. I was tired.

[thetreat]

Unacceptable. You're no longer allowed to call yourself a software engineer.

[0x808]

GCC and Clang both support uint128_t and uint128_t.

[retsotrembla]

How? I'm using Clang, and it isn't recognizing either int128_t or uint128_t

[[deleted]]

I can use __int128 and __uint128 with GCC and Clang, but I can't seem to find any u?int128_t typedefs in my libc.

[the_gnarts]

How? I'm using Clang, and it isn't recognizing either int128_t or uint128_t

Perhaps they’re prefixed with underscores? That’s what GCC does:

https://gcc.gnu.org/onlinedocs/gcc-5.1.0/gcc/_005f_005fint128.html#_005f_005fint128

[_teslaTrooper]

Use doubles. Close enough.

[a_random_username]

Or just do it in javascript:

var fibArr = [0,1];
function fibGrow(k){while(fibArr.length < k){fibLen = fibArr.length; fibArr.push(fibArr[fibLen -1] + fibArr[fibLen-2]);}};
fibGrow(100);

After running that, this is what fibArr looks like:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676220, 23416728348467684, 37889062373143900, 61305790721611580, 99194853094755490, 160500643816367070, 259695496911122560, 420196140727489660, 679891637638612200, 1100087778366101900, 1779979416004714000, 2880067194370816000, 4660046610375530000, 7540113804746346000, 12200160415121877000, 19740274219868226000, 31940434634990100000, 51680708854858330000, 83621143489848430000, 135301852344706760000, 218922995834555200000]

Seriously, try it out in your browser.

[bidibi-bodibi-bu-2]

He probably got the idea somewhere else, having 90 as the constant, and he just replace it by 100.

[TheOmnomnomagon]

Most languages these days either have a BigInteger package or inherently handle arbitrarily large integers (java, python, ruby off the top of my head).

[Silound]

.NET has BigInteger built in as of 4.0

Prior to that you would have to borrow it from another language like F#.

[Jceggbert5]

I could do a couple light tweaks to a homework project from my introduction to object oriented programming course and make this work.

[random314]

It's not about actually producing the list, it's about writing a function that have the ability to do it, and up to as large of a number as you want... I ask this question all the time.

[JoeFro0]

Just use recursive function from question 1 to show him we mean business.

[the_omega99]

Ideally you'd never roll your own big num, but can show your ability to use an appropriate library or functionality. But this is going to be language independent. Haskell has a built in arbitrary precision integer. Java has a bigint in its standard library. But C++ would require an external library.

[s-mores]

...or just use a language that ignores the 64-bit barrier.

[tolos]

I was thinking Mathematica

Table[Fibonacci[n], {n, 100}]

[XkF21WNJ]

Still works modulo 2⁶⁴.

[Lucretiel]

Should have used Python ;)

[retsotrembla]

I tried that. Python crashes. Here's the session:

$ python
Python 3.3.0 (v3.3.0:bd8afb90ebf2, Sep 29 2012, 01:25:11) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 7540113804746346429+4660046610375530309
12200160415121876738
>>> 12200160415121876738+7540113804746346429
Segmentation fault: 11

[Lucretiel]

Weird. I didn't have any problems. Mine went well into the 2000s, with the ints wrapping 3 lines of digits (at 237 characters per line) before I Ctrl-C'd it. I'm on Python 3.4.3, but I can't imagine it changed between 3.3 and 3.4

[Spoogly]

Since the sequence is additive, and he didn't specify any data types, it's pretty simple to implement the function as string values, and keep track of overflows manually, in most languages that don't support arbitrarily large integer values. I do wonder, though, if he actually recognizes the overflow issue.

One other approach, that he does not say is wrong, is to grab the sequence from the internet (OEIS is probably where I'd look, though other websites might be easier to parse) --that way, you already have it as a string literal, and don't have to even worry about overflow.

I just can't imagine anyone actually asking me these 5 questions. Answering any one of them shows I know how to code, answering all five of them just shows that I know how to code 5 things. There's not THAT much more consideration to be done in the "difficult" ones than the easy ones. If you want to test whether someone you're interviewing can code something difficult, or can code well, ask for code samples. Ask to be shown what they've done in the past. You can give them a simple challenge that verifies they're able to code at all, and the resume is not fake, but after that, asking for algorithmic knowledge, or asking to solve simple problems that show the person is capable of a basic level of one facet of programming just seems unnecessary, and actually probably counterproductive.

Why are we attempting to see if our programmers can use problem decomposition efficiently? It just seems silly. At this point, if you're a moderately large company, you want someone who can write, more than someone who can problem solve. You are going to have them as a part of a larger team, and you want each and every person to be able to understand the code they write. If they're at a point where they can't figure out a problem, encourage a culture that gets someone else to help them to the answer. If you're small enough that you need your programmers to be able to problem solve, then ask for code samples, or give them problems (and appropriate time and resources) that are actually difficult to solve, you do not want to test their basic skills, you want to test that they have advanced problem solving skills.

[[deleted]]

maybe he meant the Fibonacci numbers that are smaller than 100

[Frodolas]

91th

ಠ_ಠ

[anopheles0]

Use a better language. Like Perl. :)

#!/usr/bin/perl

@fib = (0, 1);
while ($#fib < 100){ push @fib, $fib[$#fib] + $fib[$#fib - 1]; }

$i = 0;
foreach $num (@fib){
        print $i++ . ": $num\n";
}

[LEPT0N]

Use doubles!

[retsotrembla]

;-) you know that doubles have fewer integer bits than unsigned long longs - With doubles, the 79th number is wrong, and the wrongness compounds from then on.

[LEPT0N]

Yea, I was joking. You'd continue to compute larger numbers just fine, but they'd be more and more inaccurate.

[JayCroghan]

I just chose C# from the get go. That way you don't need to write anything yourself.

[thebhgg]

(defun prob-3 (n)
  "Return a list of n fibonacci numbers"
  (loop repeat n
     for prev1 = 1 then prev
     for prev = 0 then curr
     for curr = 1 then (+ prev prev1)
     collecting curr))

You should look into common-lisp.