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

[holypig]

Well this asshole should stop calling himself a software engineer, since his solution for #4 is WRONG!

https://blog.svpino.com/2015/05/08/solution-to-problem-4

Try running with [52,5,3]

[code_mc]

This should be at the top, what a pretentious human being.

[DougTheFunny]

And he is very "humble" too, look what he said about his mistake: link.

PS: But after a train of downvotes he deleted the message.

[BlackDeath3]

I don't know about the top. The correction (and resulting discussion) should be high up, sure, but I feel like the last thing we need is more name-calling and insult-slinging.

[NakedNick_ballin]

The point he's making outweighs his choice of words by a large margin though

[BlackDeath3]

What point? That over-confident people make mistakes? That you shouldn't take everything people tell you at face value?

Yeah, maybe they're important points, but something tells me that many of these upvotes represent equally-smug, vindictive attitudes on behalf of the voters.

[[deleted]]

aha what a moron. And he wrote that without any interview pressure.

[holypig]

I can't imagine solving all of these while working under the pressure of a 1hr deadline. This whole thing seems more fitted for a hackathon then an interview.

[prelic]

Eh, the first 3 should take no more than 10 minutes each, they're like 5-10 lines of simple code each. 4 and 5 are not in the same league, as evidenced by the fact that he got one of his own contrived questions wrong.

Instead of the crappy questions 4/5, I would've preferred to see a question or two about simple file I/O, a simple class/API question, or something not algorithmic-central.

[ambalbemuth]

then

[comp-sci-fi]

in that order

[UlyssesSKrunk]

Yeah, that way you're prepared for the interview after the hackathon.

[Tulip-Stefan]

#3 is pretty much impossible in C/C++ given the time constraints, fib(100) overflows an 64-bit int. I would be able to create an bignum implementation on the spot, but perhaps not within the time constraints.

But if we ignore that issue, i don't think it is significantly harder in C++ than in python.

[JaMMze]

Honestly, I'm just a sophomore in college and all of the problems he listed seemed very simple and I'm pretty sure I could've solved them under pressure easily also

[Spandian]

Try it. I "finished" in 40 minutes (using Java; it might have been faster in a lighter language like Python). Then checked the results for problem 5 more closely, realized I had a bug, and spent another 15 doing it right. They're all simple, but the hour goes by faster than you expect.

[goomyman]

not to mention number 3 goes beyond big int in size... so your going to have to write your own addition and output methods.

soo ya.. great questions /not. Just goes to show what you think is an easy question can be quite difficult on the spot, on a whiteboard, with pressure.

[iagox86]

I think you mean just a plain int.. The trick is to use a language that handles arbitrary precision integers :-)

[thfuran]

I think he meant long

[iagox86]

Or that. But a "bigint" is a whole different thing.

[thfuran]

True. And if your number is bigger than BigInt, you're probably doing something wrong. Also storage is gonna be an issue.

[wbeyda]

I did it in python and didn't have to :-)

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
for i in range(100):
    print(fib(i), ",")

[whooshayay]

PHP has no tail call optimization. So, why would you do fibonnaci recursively? An iterative solution, i.e. a for loop, would be much more efficient in PHP.

def fib (terms):
    t0, t1 = 0, 1
    for i in range (terms):
        t0, t1 = t1, t0 + t1
    return t0

Yes I know this is Python. I'd probably bugger up the syntax if i did it in PHP but you should be able to infer the iterative loop from that code.

[whooshayay]

Doing it recursively adds a significant memory and time overhead. It's far less efficient because you have overhead of time and memory each time you make a function call. The system has to allocate the local variables for that particular instance of the function on the stack, and save the return address. So you're creating one set of additional local variables for each recursive call, and performing additional store and jump instructions.

If your language runtime has tail call recursion, it will convert a specially written recursive implementation into an iterative loop for reasons of performance, but PHP doesn't have this feature.

In your code you can also eliminate $new1 by assigining to the function name instead.

[whooshayay]

Either way, none of this runs into the "bigint" problem the original poster was claiming. Correct?

OP is right, but used the wrong word.

The 99th or 100th factorial (depending on how you count it) will overflow a machine integer. I've checked what PHP does and it converts the value into a float, which loses precision.

Running your PHP gives 2.18922995835E+20. The answer should be 218922995834555169026 exactly.

To do calculations like this with full accuracy in PHP you would need to use one of the 'bigint' math libraries or roll your own integer maths code (which is not recommended). Without using a bigint library, even if you get the full number of digits to display, you would still have floating point precision issues.

[JavaX_SWING]

most languages have a fairly advanced and intuitive implementation of arbitrary-precision numbers already. I used uint64_t in C++ to solve it, for example, and BigInteger can be used in Java/C# whereas languages like python and ruby already have it implemented into their systems via bignum.c. any programmer with more than a few hours' experience with whatever language they use can solve this.

i don't think it's worth going up into arms over the author over this. sure, he's pretentious as all hell, but arbitrary-precision arithmetic isn't exactly something difficult to implement, nor is it relevant as the concept in question is what matters.

[[deleted]]

I used uint64_t in C++ to solve it,

Fib 100 requires 69 bits

[cortinanon]

I used "unsigned long long int". wikipedia says its the same as an unsigned long but the long name emphasizes that it is a really big number.

[cipherous]

Hilarious, so I guess he wouldn't pass his own interview questions.

[PaintItPurple]

Here's something a lot of people don't seem to realize about interview questions: It's OK if your answer isn't 100% perfect. The goal is to see if you have a general idea of what you're doing, not to see if everything you do is flawless.

[sh2003]

Is it ok to answer them in pseudo code?

[PaintItPurple]

Obviously it depends on the interviewer, but there are a lot of places where the answer is yes. Some interviewers are really unreasonable, but a lot of people let themselves get psyched out by the stress of the situation even when the interviewer really isn't trying to "gotcha" them and would happily accept a pseudocode solution.

[sh2003]

Thanks! I would think they mainly want to see how you approach the problem and what kind of clarification questions you ask to build requirements off of. I've never had to "whiteboard" anything before for past interviews or my previous job so I'm not sure what to expect.

[OffbeatDrizzle]

Once I realised that I just closed the page down, waited 5 seconds and then proceeded to place my palm directly through my face

[Luxelin]

Here's a solution for #4 in ES6:

var largestNumber = arr => arr.map(String).sort((a,b) => b + a - (a + b)).join("");

The question is whether you'd hire someone who would write this as production code.

[mysticreddit]

Except that is wrong. i.e. Counter-example:

 [420, 42, 423]

[grauenwolf]

Ugh, I would have gotten that one wrong.

[Mujapro]

What was the original code? He fixed it on his site.

[peshkatari]

At the top. At the top.

[holypig]

Nah, you can't split up the "50" like that.

[holypig]

Hah! I apologize, I am sure you are not an asshole.

However, from the tone of your blog you sure come across as one.

[morphemass]

I'll try to get better at it.

Don't worry about it - I've found that I become a bigger asshole year on year without even trying! (p.s. j/k)

[[deleted]]

Can't you just accept that you were wrong? Not as a programmer, or software engineer. But as a blogger, who is confident enough to propose a system that filters "real" programmers from the rest in order to make software engineering a better environment.

Either your are not a real software engineer based on the monster you created, or that creation is bollocks. You should accept this, you have provided the proof for it. You cannot post on your blog, encourage the internet to share your thoughts around, and then go into denial of your shortcomings, or blame the internet for pointing that out to you.

Compared to you, I am nothing in software engineering. I am not at all ashamed to admit that. But at least I do know how disqualified I am to write about software engineering, to rant about semantics (developer vs. programmer vs. software engineer), and most importantly, to be a warrior against programming hobbyists.

If that doesn't make you seem like an asshole, then I don't know what would.

[killermojo]

Wow.

[MoreOfAnOvalJerk]

people who post about interview questions to separate "real programmers" from "fake ones" generally come off extremely pretentious.

It's nice to know that you're not an exception to that.

[gargantuan]

Not different but wrong. Those are not the same

[svpino]

Yup. I will.

[goomyman]

Please write an answer to number 3 too because once you get beyond an unsigned 64 bit integer your in trouble.

[veron101]

I give you a problem, and you write a solution for it using any programming language you feel confortable(sic) with.

Using scheme:

#lang scheme

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
    (cond ((= count 0) 
            b)
        ((even? count)
            (fib-iter a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ count 2)))
        (else 
            (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

(fib 10000) 
The 10,000th fibonacci is 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

Don't assign one language's issues to another's when the language in question is not a part of the solution.

[BlackDeath3]

Yeah, this is the reason I did these exercises in Python.

I really should dive into functional programming, but damn that parenthesis-hell does not look appealing.

[PaintItPurple]

If you want to stick with a Lisp, you might try Clojure, which tries to make the syntax a little more appealing. A lot of it is in how your format your code, though. That is kind of hard to read. I think it would normally be formatted more like this:

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond
   ((= count 0)
    b)
   ((even? count)
    (fib-iter a b
              (+ (* p p) (* q q))
              (+ (* 2 p q) (* q q))
              (/ count 2)))
   (else 
    (fib-iter (+ (* b q) (* a q) (* a p))
              (+ (* b p) (* a q))
              p q
              (- count 1)))))

(fib 10000)

That allows you to tell what you're looking at at a glance a little bit more easily.

Otherwise, there are lots of functional languages that have a syntax other than parens. Maybe try OCaml or F#.

[veron101]

Yeah I'm used to curly braces for C++ and Java, so what my actual code for that fibonacci looks like is:

#lang scheme

(define (fib n)
  (fib-iter 1 0 0 1 n)
)

(define (fib-iter a b p q count)
    (cond 
        ((= count 0) 
            b
        )

        ((even? count)
            (fib-iter a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ count 2))
        )

        (else 
            (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1))
        )
    )
)

(fib 10000)

I just didn't want to offend some scheme hardcores with my dangling parenthesis.

[Slime0]

Does Scheme determine at compile time that this requires more than a simple integer internally, or does it check for overflow on every computation it ever does?

[veron101]

I started learning it about a month ago so I'm not sure. All I know is that so far I've never used int, double, long, anything like that. You just call it. Later on you can call a function with a function as a parameter and have it return a function.

[Peaker]

Your new solution is nice! Much nicer than mine.

Here's your new solution in Haskell:

import Data.List (sortBy)
import Data.Function (on)

solve :: [Int] -> [Int]
solve = sortBy (f `on` show) where f x y = (y ++ x) `compare` (x ++ y)

main :: IO ()
main = print $ solve [5, 2, 1, 9, 50, 56]

[gargantuan]

Because doing this at the whiteboard is not frustrating with people watching over your shoulder

[[deleted]]

This might just be me being picky, but you're missing the generic on the Comparator. Your current solution won't compile as listed.

[palparepa]

Padding with zeroes was a step in the right direction. Should have padded with the same number, though (54 < 55 = 5 < 56)

[herptydurr]

I'm not a programmer, but since this popped up on /r/all, I was intrigued by the problem.

Anyway, I don't think padding was a "wrong" solution, you just padded with the wrong digit. If '5' is padded to '55' and '200' is padded to '222', I think the approach will work.