How do you guys come up with such an algorithm
You state &quot;O(1) complexity to find the minimum value&quot;, but usually without further qualification, that refers to time, not space. With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value&#x27;s minimum entry.<p>In this case, the big clue is that O(1) means that there must be somewhere &quot;constant&quot; to look for the solution. In a stack, there&#x27;s only one practical place to look in O(1) time. (In principle, &quot;the second element&quot; is always O(1) as well, as long as it is <i>always</i> the second unconditionally, but there&#x27;s no clear reason to add that condition.) Since that place is incorrect, you&#x27;re going to have to add one. Then it&#x27;s only a matter of per-element, or per-stack, and from there it won&#x27;t take long to work it out.<p>Larger O() factors imply a larger possibility of places to look and possible things to compute.<p>Not that I ask these questions in interviews anyhow, but I think a case could be made that&#x27;s not <i>entirely</i> an unreasonable question. (Albeit weird for a QA position, unless you&#x27;re going to be literally testing underlying APIs. Any UI-level QA position this is massive overkill for.) That is at least in the ballpark of problems I do solve all the time. I am always adding fields to things for faster lookup or something, even if I&#x27;m not implementing a generic stack.<p>The &quot;do it in O(1) space question&quot; can be a trick question, either accidentally or otherwise, if the interviewer isn&#x27;t careful to specify that they want it done for integers specifically. A lot of the clever &quot;pack it in a tighter space&quot; questions revolve around exploiting the properties of integers, and involve having seen uses of XOR or things like that. If they don&#x27;t communicate it&#x27;s integer-only, and the interviewee makes the completely reasonable assumption that &quot;stacks&quot; are meant to be data-type generic (since that&#x27;s how we usually encounter them in the real world), the interviewer has accidentally asked a question which may be effectively impossible. (Which, in <i>principle</i>, means you should further ask your interviewer about it. However it seems the sort of people asking this question are also often inclined to not be that specific or something.) If you are not <i>exceedingly</i> fast on your feet with integer manipulation, in many ways the answer is just that you&#x27;ve done enough of these to have more-or-less memorized the tricks.<p>Unless this is an interview for a super-constrained embedded job, I would <i>not</i> consider this a good interview question. There&#x27;s a lot of games you can play with the integers specifically, because of their confined range of values and the strong relationships between them, but I almost <i>prefer</i> that you not know them, or that if you do know them that you keep them to yourself. I don&#x27;t <i>want</i> to see that kind of game played in my code without a very good reason. Plus it&#x27;s just memorization.