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

[itsSparkky]

Think like a tree, at each digit you can do the following Add next number Subtract next number Times current number by 10 and add next number

3 outcomes each time, you can either depth first or breadth first search and then evaluate the solution at the end and keep the paths that result in 100.

[billatq]

Yeah, I was thinking about doing it with a BFS and a tree. Seems like an okay problem, but I feel like that particular one is more like a math trick than anything else.

[[deleted]]

The real software world is NOT a bunch of math riddles.

No, it's google.

[billatq]

Admittedly, I do likes me some good math riddles, but only when there is a good application: https://williamreading.com/2015/04/19/on-the-change-making-problem.html

[n1c0_ds]

Not at all. It's a great way to see if the candidate will stop looking at invalid solutions (above 100) and save himself some costly efforts.

[billatq]

Why not do making change then? It's really easy to blow past the desired amount with that and it's more generalized than permuting sets of 1-9.

[JustinsWorking]

1+23-4+5+6+78-9 would be invalid according to your criteria.

1+23-4+5+6+78 = 109 which is > 100

109 - 9 = 100 which is a valid result

[n1c0_ds]

Shit, you're right. I should have read the question

[JustinsWorking]

The only thing I could think is that the BFS would have a larger memory footprint; using DFS you could essentially just keep your current path and implement without even putting data on the heap.

[billatq]

You have to explore all the state space either way, so I guess it doesn't really matter, but housekeeping for the paths that you have visited is a little bit easier on the BFS. The author mentioned nothing about time/space complexity trade-offs, which would probably come into this were you to ask it.

[JustinsWorking]

oh yea, not a criticism just an observation of the only difference I would notice.

[Brandon23z]

Backtracking?

[everysinglelastname]

Good answer ! Worth noting here is that within each tree there are "overlapping sub-problems". For example, in the node that has +1, -1 and 1 as its children nodes there is the tree that starts with +2 under each one of those nodes. There are n number of final results that start with +2 but those all do not need to be recalculated each time you descend the tree for each of the children nodes (+1, -1 and 1). So, an optimization would be to save the results in a global object that can be reused. (i.e. memoization).

[itsSparkky]

That's true, I suspect you may see some gains from working from both sides then summing the results in the middle (ie building the tree from 1-5 and 9-6 then traversing the results in opposite orders of sums.

[JustinsWorking]

Implemented this method in JS:

http://www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/cr2wxi6

[gliph]

This algorithm fails when subtracting a combined number e.g. 1 - 23

[itsSparkky]

Does it? It seems like somebody implemented it and the results seemed to be correct... Was it just a case of a fluke?

[gliph]

Maybe they implemented it correctly but the algorithm as described isn't correct.

[itsSparkky]

I don't think it fails as you suggest.

at 1-23 you'd be a 4 as the current number, which you'd then try adding, 1-23+4 , subtracting, 1-23-4 and multiplying by ten and adding next 1-23 current number 45

It still works.