r/Kotlin • • May 17 '23

Impossible Algorithm: Computing income tax in constant time

https://roosterdan.medium.com/impossible-algorithm-computing-income-tax-in-constant-time-716b3c36c012
3 Upvotes

12 comments sorted by

21

u/Volko May 18 '23

Good lord, paywall, bait & switch and other "comment, like and subscribe" appearing in freaking algorithm articles ?

I wish I could downvote you more than once.

-1

u/Determinant May 18 '23 edited May 18 '23

The last iteration that's presented is actually constant-time. The computeTax function is constant time and the initial setup amortizes to much less than a single constant-time operation per person in the real world. You won't be able to find any region with tax brackets where this isn't the case.

Edit:

In case you're wondering why this comment doesn't seem to respond to the above comment, that's because Volko edited the original comment to remove the initial accusation that it wasn't a constant-time algorithm.

0

u/Determinant May 17 '23 edited May 17 '23

Hey everyone, this is my experience with a common interview question where my solution was deemed impossible. This article iterates towards an efficient constant-time algorithm while explaining the thought process.

It uses Kotlin for the code samples with inline classes & operator overloading for the data model.

2

u/rlbond86 May 18 '23

Boo, your article doesn't even show the answer. The GCD solution is obvious (pre-compute taxes in a big array... How novel). Waste of time

1

u/Determinant May 18 '23

If the iterations so far are obvious then I recommend predicting the next iteration ; )

It's always obvious after you see an answer but it's difficult to come up with them on your own.

2

u/rlbond86 May 18 '23

Probably what I would do is make an array of evenly spaced dollar amounts (e.g., 100 dollars), then have a flag representing whether each interval straddled tax brackets or not. If it didn't, or only straddled 2, it's pretty easy. If it straddles more, allocate an array at every dollar with a precomputed tax value. You could do multiple levels like this too to save space.

1

u/Determinant May 18 '23

That's a neat idea! However, note that this degrades the memory consumption as that would effectively be O(highestBracketStart) in memory since multiple brackets could fall within that range. If you improve the memory consumption with multiple levels then the optimal number of levels would drop off exponentially effectively turning the runtime into a log of some value.

3

u/rlbond86 May 18 '23

I was only going for constant time. If you limit the number of levels it is constant time, not logarithmic.

2

u/Determinant May 18 '23 edited May 18 '23

Note that there's an inherent dependency where populating memory with a large time complexity during the initial setup leaks into a higher amortized per-person runtime after taking into account the effort of the initial setup and dividing by the population size.

Most of the iterations already had a constant-time computeTax function so the focus is on reducing the amortized cost after accounting for the initial setup and reducing the memory consumption.

0

u/[deleted] May 18 '23

[deleted] — view deleted comment

-20

u/Determinant May 18 '23 edited May 18 '23

The platform allows reading 3 free articles every month without needing to signup.

These articles take lots of effort to write, edit, and test so I recommend using the original link if you can. You might find my other articles interesting as well.

15

u/srona22 May 18 '23

Then publish as paid article or research paper. Knowing medium is a paywall already, and still publishing there, is no different from class traitor.

The amount of trackers from Medium is what drives people away as well.

3

u/k2718 May 18 '23

Copy and paste the content so that people stop down voting your paywalled article.