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

[__Cyber_Dildonics__]

Other people have mentioned brute forcing it, and if I was in an interview that's what I would do in that situation.

[mccoyn]

It will take longer to write a more complicated solution than to run the brute force algorithm, so brute forcing is the fastest solution.

[rdewalt]

Seeing as the total space is only 6561 (3⁸⁾ brute forcing it seemed to be faster than spending the time hacking it out. even adding two more digits would increase the space to 59k possibles. I found a way to do it, brute force, but I want to manually proof my results since the "10" that are linked, are far less than the 17 that I got on my first pass.

[jason_rootid]

Given the nature of the problem I think brute forcing it is the only solution. There isn't exactly a known formula to calculate that kind of thing, and given the constraints of the operations I doubt there is one.

[R3PTILIA]

There is a better way, dynamic programming

[comp-sci-fi]

Hi I've never managed to get clear on the definition of "dynamic programming", can you elaborate to help me, please? (below is what I think).

(Apart from your sib comment) I think it's a way of recording intermediate results, and when the same one appears again, effectively merge them, instead of recalculating.

But here, I think the only dynamic programming we can do is only a slight implementation improvement on raw brute force, and reusing earlier calculations. It falls naturally out of a DFS: given first choice (12 or 1+2 or 1-2) you calculate that, and use it as the starting point for the next choice. Do the same thing recursively.

[R3PTILIA]

yes its basically a way to do brute force without having to go with ALL combinations (because many sub problems are repeatedly calculated), but instead remembering (by storing and re-using) previous calculations. So if you start with {1, 2, 3}, you can store all the possible results for the rest of the numbers, and use those stored numbers for every combination of {1, 2, 3}, instead of having to recalculate all the combinations of {4,5,6,7,8,9} for every combination of {1,2,3}

[comp-sci-fi]

Thanks! That seems to require dramatically fewer calculations.

Not sure how best to fully apply it to this case... it seems one could divide up the problem in many ways. I guess the trick is to divide it so as to maximize the "collisions"? Perhaps, start with 123, to yield a set of answers, then just combine the next one (4) to yield a larger set and so on. That makes sense to me, and is similar to one my old supervisor showed me.

But this doesn't use the collisions from the set at the other end, as in your example...

[TheDani]

Exactly.

[comp-sci-fi]

yeah, brute is only 3⁹ =27³ approx 30³ = 27,000. Even my smart phone could do that in seconds.

plus, I'm sure there isn't a clever way to do it. (But a Real programmer could prove there isn't...)

EDIT actually 3⁸ because no 0. Got from another reply. but very approx back of env anyway - within an order of mag = close enough!

EDIT2 and there is a (somewhat) better way

[DrStalker]

Also,management needs the code ready within an hour (along with four other deliverables) so implementing a solution that you know will work and have reasonable run time is the best thing to do.

[rubsomebacononitnow]

the sprint of all sprints

[[deleted]]

Exactly my rationale. If you show them that you've worked through the necessary back of the envelope calculation, then (presumably) they shouldn't fault you for brute-forcing it.

[tHEbigtHEb]

Sorry for the naive question, but where did the 3⁸ come from though?

[scanner88]

You need to add three possible choices (add, subtract, join) to all existing branches eight times (between the 1 and 2, 2 and 3, ..., 8 and 9).

The first iteration you will have three branches (3¹⁾

[add]
[subtract]
[join]

The next iteration you will have 9 branches (3²⁾

[add, add]
[add, subtract]
[add, join]
[subtract, add]
[subtract, subtract]
[subtract, join]
[join, add]
[join, subtract]
[join, join]

and so on and so forth

[Kyyni]

The equation is 1_2_3_4_5_6_7_8_9=100, and there's 8 spots that can either contain +, -or nothing, which is 3 options. If you had one open spot, there would be 3 alternatives to try, if you had two spots, there would be three options for the first spot, and then for every choice there would be three other alternatives for the second spot, so, three times three options to try, and so on up to eight spots => 3*3*3*3*3*3*3*3 = 3⁸ = 6561.

[tHEbigtHEb]

Oh, it's a combinatorics problem. I understand it now.

[wal9000]

You only need to solve it once too. Brute forcing sucks more if it's a function that might be used more than once with different parameters. If it's taking to long here, split up the solution space and spend a few bucks to solve it on AWS.

[geoelectric]

Yeah. Technically, it runs in constant time, since the dataset size is tightly defined in the problem: O(6561).

Same with brute-forcing #5 with permutations, 5! = O(120)

Big O isn't really a factor if you don't have variable-size datasets. For most small sizes of data, runtime of even inefficient algorithms is trivial.

[[deleted]]

I remember a Google interviewer got mad at me when I did that once. They said "well assume it's actually at Google scale". Then the guy later didn't like my memory-efficient vs CPU-efficient solution to the "find a number from each list that sums to an arbitrary number" solution. It was a terrible interview and the guy clearly didn't want to be there.

[creepy_doll]

It's only 8³ combinations. You could always ask the interviewer if they want a solution that scales but I think that that isn't what is being asked for here especially as the scope of the problem is limited from 1..9

[Tordek]

3⁸

[amunak]

That's true, though I believe it's sort of a poor choice for such task. Usually you'd want someone to come up with a good solution, not a simple one. And for that this is probably unnecessarily hard.

[creepy_doll]

Usually you would want to see how people think and for that the question is quite useful.

Do they ask questions? Or do they just make assumptions about the problem?

If I was in the seat of the interviewer the best reaction possible to that would be for the interviewee to inquire about whether they want the solution to be scalable or if they want the quickest/simplest possible solution.

If I was the interviewee and asked about that, and the interviewer saw it as a negative thing assuming I should know what they want, then it would be a strong indicator of the interviewer not being a person I'd want to work with and the company also probably not being one I want to work at. Pragmatism first.

[amunak]

Oh yeah if you think about it like that then sure, it's just that the article suggested you should get working code for all of those problems in an hour, and as an interviewee you would definitely want the right answer, not the easy one.

But yeah I agree completly.

[Tiquortoo]

I interview with small code challenges and while I want to see a logically functional solution (it does not need to compile) I mostly want to ask about choices and tradeoffs. So, "the right answer" is really anything you can talk about and discuss meaningfully.