Use the right tool for the job:
In my first interview out of college I was asked the change counter problem:
Given a set of coin denominations, find the minimum number of coins required to make change for a given number. IE for USA coinage and 37 cents, the minimum number is four (quarter, dime, 2 pennies).
I implemented the simple greedy algorithm and immediately fell into the trap of the question: the greedy algorithm only works for "well-behaved" denominations. If the coin values were [10, 9, 1], then making 37 cents would take 10 coins in the greedy algorithm but only 4 coins optimally (10+9+9+9). The "smart" answer is to use a dynamic programming algorithm, which I didn't know how to do. So I failed the interview.
But you only need dynamic programming if you're writing your own algorithm. It's really easy if you throw it into a constraint solver like MiniZinc and call it a day.
[...] Lots of similar interview questions are this kind of mathematical optimization problem, where we have to find the maximum or minimum of a function corresponding to constraints. They're hard in programming languages because programming languages are too low-level. They are also exactly the problems that constraint solvers were designed to solve. Hard leetcode problems are easy constraint problems. Here I'm using MiniZinc, but you could just as easily use Z3 or OR-Tools or whatever your favorite generalized solver is.
[...] Now if I actually brought these questions to an interview the interviewee could ruin my day by asking "what's the runtime complexity?" Constraint solvers runtimes are unpredictable and almost always slower than an ideal bespoke algorithm because they are more expressive, in what I refer to as the capability/tractability tradeoff. But even so, they'll do way better than a bad bespoke algorithm, and I'm not experienced enough in handwriting algorithms to consistently beat a solver.
[...] Most constraint solving examples online are puzzles, like Sudoku or "SEND + MORE = MONEY". Solving leetcode problems would be a more interesting demonstration. And you get more interesting opportunities to teach optimizations, like symmetry breaking.
(Score: 2, Insightful) by pkrasimirov on Thursday November 20, @03:04PM (9 children)
If you go to a job interview for programmer and they ask you such question, leave. We are no longer in the 1960s or 1970s, or even 1980s.
(Score: 4, Insightful) by Mojibake Tengu on Thursday November 20, @03:41PM
I'd rather ask the programmer job applicant to solve the said problem in C++ templates, as an abstraction. That fits the century well.
I can do that in any decent macroassembler with pure macros. For me, a pure macro means it calculates everything at compile time, emits no code.
Yes it's not 1980s, but the current regular incompetent schoolboys are quite incapable to think about algorithms for themselves.
Not that the managers hiring them are any better.
Without specialized tools, they are completely useless.
Rust programming language offends both my Intelligence and my Spirit.
(Score: 5, Insightful) by JoeMerchant on Thursday November 20, @04:07PM (2 children)
It's an interesting point... on the one hand, solving such problems in day to day work almost never happens directly, nobody is going to give you a problem like "what's the smallest number of coins to make $0.37 when your denominations are 10, 9 and 1?" and if they did, a little internet research would quickly give you good solutions - optimal if you care to spend a minute doing the research.
On the other hand, how you approach such things, how you communicate with colleagues about your thinking processes, does come up many times a day, unless you're a paid hermit. Also, such situations reveal a lot about your attitudes and interactions with authority, dealing with ridiculous bureaucratic BS and so many other common aspects of paid work.
🌻🌻🌻🌻 [google.com]
(Score: 2) by pkrasimirov on Friday November 21, @10:49AM (1 child)
> how you approach such things, how you communicate with colleagues about your thinking processes
That is a very valid reason for such questions, however that was not the case in TFA:
> ... I didn't know how to do. So I failed the interview.
In a previous field-related job they had a question "You have to install [something] at customer site and it's scheduled at 18:00 on Friday. You are there but the door is locked and nobody is responding on the customer phone, what do you do?"
(Score: 2) by JoeMerchant on Friday November 21, @02:31PM
There's the reason you are given why you failed the interview (these tests are great for that, almost everybody fails, so it's almost always a potential "valid" reason), then there's the real reasons you don't get an offer.
Anywhere I have ever been, the hiring process involves a closed door, cameras and microphones off, meeting where the decision makers ask each other "what do you think?" All kinds of illegal, immoral, and generally unacceptable reasons are thought and expressed in some way or another during those meetings, and when the result of those meetings is a consensus: Yes, or more often: No. They give that verdict back to HR and HR crafts the "we're so sorry" letter that is fully legally compliant, and reflective of the public image that the company is attempting to project.
This is why DEI is (was, will probably be again someday) based on actual staffing demographics. Nobody has successfully legislated a way to control the hiring decision process, but when upper management knows that a diverse workforce leads to free money? That does tilt the scale.
🌻🌻🌻🌻 [google.com]
(Score: 0) by Anonymous Coward on Thursday November 20, @04:25PM
From what I heard, Google was infamous for still pulling that shit in the 00s.
I supect the hiring process is different now that there are no longer people in
the loop at all and they just want techno-parrot correctors who are measured
by the volume of slop they produce.
(Score: 1) by khallow on Thursday November 20, @10:48PM
I came up with a bespoke answer inside of five minutes. While that might not be fast enough for the job interview, I'd be able to give a good answer. Start with the above greedy algorithm as your first guess, ordered largest to smallest. Then systematically replace coins with smaller ones in a lexigraphic pattern until you either find better combinations or get to coins so small that you can't possibly find a better solution. For the [10,9,1] coins to make up 37 cents: Start:
10 10 10 1 1 1 1 1 1 1 [10]
10 10 9 1 1 1 1 1 1 1 1 nope
10 9 9 9 [4] better
10 9 9 1 ... nope
9 9 9 1...nope
At this point, one can't find a further pattern that uses only 4 coins - too many 1 cent coins have to be used and we stop.
To summarize, we're doing partitions of 37 cents in lexographic order and have several tricks that keep us from having to search all the possible partitions.
Depending on the job's requirements and tasks, that might be a good skill to demonstrate. But it's sure not just for 40+ years ago.
(Score: 1) by fen on Friday November 21, @03:43AM (2 children)
Your ego is showing.
(Score: 3, Touché) by pkrasimirov on Friday November 21, @02:49PM (1 child)
In your comments in other articles you often see ego. Is it possible that you are projecting?
(Score: 0, Offtopic) by fen on Saturday November 22, @08:52PM
Ego is the ultimate taboo. It's not sex, or even money. Everything comes down to ego. Every thought anyone has ever had.
(Score: 4, Insightful) by VLM on Thursday November 20, @03:54PM (2 children)
Minizinc looks cool I've bookmarked it to fool around with because it looks fun.
WRT "Use the right tool for the job" my work life has been a strange might of very high level architecture and very low level EE/embedded stuff. The problem is awful.
The company will never break even on paying for the worlds most complicated and elaborate partially debugged algo vs "just shove a few more coins in the dispenser".
The next problem, also business related, is the company almost certainly CANNOT afford a bug, the simplest most reliable algo must be used, so do the greedy algo. Imagine the staggering cost to the company if there were even the most microscopic bug that lost a quarter from the till every 1000 transactions or even worst failed to dispense and the state regulators went in attack dog mode on the retailer who's lawyers do in attack dog mode on the change dispenser mfgr, an unimaginably dumb business risk to take. What would it cost to verifiably destroy all the bad eeprom code and install all new? Or spend $10K on hyper elaborate tiresome and error prone testing of the elaborate algo. May as well declare bankruptcy and give up now.
The programmer isn't hired to implement beautiful math but to logistically belch out the proper number of coins. The number of combos is incredibly small my modern memory standards and risk tolerance around money is very low so precalculate it all and ship it in a binary lookup table. The entire table for a cash register would cost about one zillionth the memory of a five cent microcontroller or even less of the beast that'll run an IRL cash register.
Its focusing efforts on the wrong problem. Its easy to generate piles of coins adding up to a specific value. Its hard to define business rules like "no matter what never emit 19 nickels if everything else is out and they ask for 95 cents" or "never try to emit coins while the loading slot is open and the human fingers are in there" or "sound an alarm if someone is probably trying to steal coins but don't sound an alarm if they're probably not" Good luck with those hard problems.
Really, the purpose of interview questions like that is threefold. Can you babble at all or did you fake your entire resume and experience, just don't say anything too stupid. Whats your thought process and communication style when you have a "real" problem at work and I gotta help you. How will you react when management is moronic as usual and sends you ten memos about changing TPS report headers please don't pull a weapon on me at least during the interview. They don't really care about the math problem.
Someone tried to fizzbuzz me one time and I told him "he he yeah I know what a modulus operator is" and he marked that as successfully completed and we spent the time talking about higher level stuff the trials and tribulations of database normalization (essentially everyone with SUPER access to a DB knows what codd normal form is almost intuitively, like almost genetic instinct, but business drones seem mystified at the very concept, you can't expect much from folks who think Excel is the worlds best database management system).
(Score: 2) by VLM on Thursday November 20, @03:58PM
What the hell some kind of predictive text spell checker bullshit is F-ing my stream of consciousness typing. I did not change anything so my browser must be F-ing me. Great. Its gonna be a long day...
(Score: 0) by Anonymous Coward on Wednesday November 26, @01:09PM
Most real world problems and decent solutions to them usually look nothing like those "Computer Science" stuff. Except for some cases, in which case nowadays there's stuff like search engines and AI which will quickly find relevant algorithms...
FWIW I've rarely seen any of the model answers to those questions include decent comments, logging, signal and error handling. 🤣
And when something goes wrong years later when the original coder has left, comments and logging etc might be worth much more than how clever the algorithm was.
(Score: 3, Interesting) by DannyB on Thursday November 20, @04:06PM (7 children)
I did it in Java. It's fast. It looks for all possible solutions. It does not have a GUI interface. The puzzle has to be put into the source code.
It's not that I was doing anything new. I just wanted to scratch that particular itch.
Puzzle to solve:
1 . . | 2 . 8 | . . 9
. 8 . | . . . | . 3 .
. . 7 | . 1 . | 2 . .
------+-------+------
4 . . | 1 2 3 | . . 6
. . 2 | 4 5 6 | 9 . .
6 . . | 7 8 9 | . . 4
------+-------+------
. . 6 | . 4 . | 8 . .
. 2 . | . . . | . 7 .
9 . . | 8 . 2 | . . 1
Solving...
Solution #1. Found in 0 days 00:00:00.006.
245 boards examined so far.
1 6 5 | 2 3 8 | 7 4 9
2 8 4 | 6 9 7 | 1 3 5
3 9 7 | 5 1 4 | 2 6 8
------+-------+------
4 7 9 | 1 2 3 | 5 8 6
8 3 2 | 4 5 6 | 9 1 7
6 5 1 | 7 8 9 | 3 2 4
------+-------+------
7 1 6 | 3 4 5 | 8 9 2
5 2 8 | 9 6 1 | 4 7 3
9 4 3 | 8 7 2 | 6 5 1
Solution #2. Found in 0 days 00:00:00.001.
287 boards examined so far.
1 6 5 | 2 3 8 | 7 4 9
2 8 4 | 9 6 7 | 1 3 5
3 9 7 | 5 1 4 | 2 6 8
------+-------+------
4 7 9 | 1 2 3 | 5 8 6
8 3 2 | 4 5 6 | 9 1 7
6 5 1 | 7 8 9 | 3 2 4
------+-------+------
7 1 6 | 3 4 5 | 8 9 2
5 2 8 | 6 9 1 | 4 7 3
9 4 3 | 8 7 2 | 6 5 1
2 total solutions found.
304 total boards examined.
Total time 0 days 00:00:00.113.
Done.
Puzzle to solve:
1 2 . | 3 . . | . . .
4 . . | . . . | 3 . .
. . 3 | . 5 . | . . .
------+-------+------
. . 4 | 2 . . | 5 . .
. . . | . 8 . | . . 9
. 6 . | . . 5 | . 7 .
------+-------+------
. . 1 | 5 . . | 2 . .
. . . | . 9 . | . 6 .
. . . | . . 7 | . . 8
Solving...
Solution #1. Found in 0 days 00:00:00.565.
219,509 boards examined so far.
1 2 5 | 3 7 4 | 8 9 6
4 7 9 | 6 1 8 | 3 2 5
6 8 3 | 9 5 2 | 7 1 4
------+-------+------
7 1 4 | 2 6 9 | 5 8 3
5 3 2 | 7 8 1 | 6 4 9
9 6 8 | 4 3 5 | 1 7 2
------+-------+------
8 9 1 | 5 4 6 | 2 3 7
2 5 7 | 8 9 3 | 4 6 1
3 4 6 | 1 2 7 | 9 5 8
1 total solutions found.
975,208 total boards examined.
Total time 0 days 00:00:02.382.
Done.
For some odd reason all scientific instruments searching for intelligent life are pointed away from Earth.
(Score: 4, Interesting) by zocalo on Thursday November 20, @04:26PM (1 child)
Remember, a given problem should ideally be both solveable using nothing but logic and only have a single valid solution. Without looking at Simon's code, I've worked out a methodology to solve many of the problems in that set that I could easily turn into a solver, but how to write a generator that I can be certain always meets both those criteria for some of the puzzles in the collection I've tackled still eludes me unless I brute force it. Creating a solveable puzzle is usualy pretty easy, ensuring the solution for a given start point is also unique without resorting to brute force however...
UNIX? They're not even circumcised! Savages!
(Score: 2) by DannyB on Friday November 21, @03:35PM
I have been considering venturing into building a puzzle generator. I've read some material on the subject. It is pretty clear that you need a solver to build a generator. Generally, Sudoku puzzles should have only one possible solution.
One problem is that there is less published material about generators than there is about solvers and other Sudoku related topics. People with puzzle generators are typically using them for profit making game apps on people's phones, or on web sites. So some people who have the knowledge about this topic, do not publish, but keep their know-how secret.
For some odd reason all scientific instruments searching for intelligent life are pointed away from Earth.
(Score: 0) by Anonymous Coward on Thursday November 20, @06:14PM (1 child)
But does it run with less 1Tb of RAM?
(Score: 2) by DannyB on Friday November 21, @03:38PM
As far as I know, it doesn't use a ridiculous amount of ram. My machine has only 32 GB.
The more important point is that it is fast.
Fast is always (usually) more important than memory.
You can always buy more memory. But no amount of money can buy back lost time.
For some odd reason all scientific instruments searching for intelligent life are pointed away from Earth.
(Score: 3, Interesting) by Ingar on Thursday November 20, @06:37PM (2 children)
I wrote a sudoku solver in C++ when I was still commuting by train. It only finds a single solution,
but it has a gui and it was a fun exercise to kill some time.
There are sudokus designed specifically to annoy brute-force algorithms. I remember doing some interesting optimizations,
like randomizing the order of the cells to be solved. There's also an option to try and find a solution using the constraint rules
only.
Here's a fun one:
9 . . 1 . 4 . . 2
. 8 . . 6 . . 7 .
. . . . . . . . .
4 . . . . . . . 1
. 7 . . . . . 3 .
3 . . . . . . . 7
. . . . . . . . .
. 3 . . 7 . . 8 .
1 . . 2 . 9 . . 4
My apologies for the formatting, I can't seem to force fixed-width text.
Love is a three-edged sword: heart, soul, and reality.
(Score: 3, Informative) by Anonymous Coward on Friday November 21, @03:05AM
Use <ecode> and </ecode> and don't include any blank lines. (There's a bug where an empty line will turn off the fixed width, even without the </ecode> )
here :
You can also just use <code> and it will be fixed width without looking quoted. Same deal with the empty lines though.
9 . . 1 . 4 . . 2
. 8 . . 6 . . 7 .
. . . . . . . . .
4 . . . . . . . 1
. 7 . . . . . 3 .
3 . . . . . . . 7
. . . . . . . . .
. 3 . . 7 . . 8 .
1 . . 2 . 9 . . 4
(Score: 2) by DannyB on Friday November 21, @03:48PM
I have thought about building a GUI, or some type of front end.
Three possibilities:
1. A desktop app in Java using Swing UI so that it can run on any desktop platform. In 2004 I wrote a small Mandelbrot explorer, and I happened to be using Windows when I wrote that. It ran on my Linux system at home. Ten years later in 2014 when I got the first model of Raspberry Pi (512 MB, one core, including Java in the Raspbian OS), I was able to take my compiled binary and run it on the Pi which had a different processor (ARM) and a different OS (Linux).
2. An Android app. I've done this before (a toy "asteroids" game in 2010). Build an Android app and use my solver, since it's already written in Java, making it ideally suited to build into an Android app.
3. A web app. Build a Java Servlet that plugs into any servlet container, Apache Tomcat, Jetty, etc.; much like how an android app plugs into any android phone. The beauty of this is that the compiled web app would drop right into any compliant servlet container on anything from a Raspberry Pi up to an IBM mainframe.
For some odd reason all scientific instruments searching for intelligent life are pointed away from Earth.
(Score: 0) by Anonymous Coward on Thursday November 20, @04:51PM
but I HATE solving puzzles,
especially ones involving a non-intuitive "trick"
(Score: 1) by khallow on Thursday November 20, @05:02PM (2 children)
(Score: 2) by VLM on Thursday November 20, @05:33PM (1 child)
One of my fellow contractors suggested it was cool to get rid of the penny but why not skip past that, even skip past metric conversion, and go full on binary. We both enjoy sci fi worldbuilding type books. You could carry more than a quarter million bucks with just a handful of 24 or fewer binary coins. That many denominations would be a PITA but its still a cool idea.
I one upped him by suggesting Euler's constant for the larger coins instead of base 2, it is about two and would make a much funnier to think about currency system. Obviously the primary design criteria when designing a currency system is what's funnier. Assuming the coinage supports cents, a heptaeuler coin would be worth about $11. A heptabinary coin "a seven bit coin" would only be worth about a buck and a quarter (well, exactly $1.28). You'd need a deci-binary coin ($10.24) to express about as much money as a mere heptaeuler coin ($10.95).
If you replaced paper money with euler's constant coins and used binary coins to replace trad American USA coinage, that crossover between systems would be problematic as a FiveEuler aka QuintEuler coin would be worth about a buck fifty which is more than a SevenBit aka SeptaBinary coin ($1.28) so the 5 would be worth more than the 7 and even worse there would be two 5, 6, and 7 coins.
I also thought it would be funny to name my binary coins "bit-coins" but that name is already taken LOL
(Score: 2) by pkrasimirov on Friday November 21, @09:24AM
If they want to force everyone into credit cards, they can do just that.
(Score: 2) by bzipitidoo on Friday November 21, @03:42AM (1 child)
What do you mean "you only need dynamic programming if you're writing your own algorithm"?? What's so hard about dynamic programming, pray tell? It's a very common algorithmic technique, and, last I heard, algorithms are still core Computer Science.
(Score: 1) by khallow on Friday November 21, @03:59AM
(Score: 3, Insightful) by ElizabethGreene on Friday November 21, @01:46PM
/self, remind me ask grok about dynamic programming algorithms and constraint solvers
Step 0 of learning about a thing is knowing thing exists, with the rare exception edge case of inventing or discovering something novel.
(Score: 2) by VanessaE on Saturday November 22, @04:21AM (1 child)
Naturally, I didn't read the article 😉 but this kind of problem seems super easy to solve. Everyone who's ever worked retail has had to learn how to count-out a customer's change, and you can do it almost exactly the same way in a program, and it should work equally well with "poorly behaved" denominations...
Someone check my logic:
1. Initialize a running value, set equal to the amount you want to match.
2. Initialize an array of coin counts to all zeros, with one entry per denomination.
3. Determine the highest denomination of (a single) coin that's less than or equal to the running value.
4. Subtract that coin's value from the running value.
5. Update the relevant entry in the coin count array
6. If the running value is greater than 0, loop back to (3).
7. If the running value is less than 0, decrement the last coin's count and print an appropriate error message
8. Exit the loop, skim through the array and print the resulting coin counts.
Incidentally, this is similar to how one does integer division in assembly on a CPU that has only add, subtract, and bitwise shifts/rolls.
(Score: 1) by khallow on Saturday November 22, @05:15PM
Greedy approach yields: 3 ten cents and 7 one cents. Optimal is a 10 cent and 3 nine cents. 10 coins versus 4 coins.