Little problem(s) July 2022

[pier4r]

(07-05-2022 03:41 PM)Thomas Klemm Wrote:  

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL?

I must admit that I don't know the details, but I assume that POS has to check every entry to find the position.
The worst case is if we search for an entry that is absent.

Yes somehow I managed to mix POS with GET in my mind (I hope GET is O(1) with lists in userRPL, now I start to have doubts).
(thank you to Albert Chan as well!)

But then we cannot really lie to the interviewer can we? That is also the interesting part of those problems solved with the calculator capabilities, one doesn't exactly have all the tools (data structures or methods) needed.