So, amortized complexity is different than actual complexity. The doubling the size of the array whenever you overflow leads to log(n) performance which isnt constant. What they were looking for was an array of arrays such that each consecutive nested array is double the size of the previous. This way, you get the same number of expected allocations, but you dont ever have to copy data (and therefore inserts are actually constant time). It also has the benefit of being able to consolidate the subarrays into a single one at places where there is time to do so. So, you didnt actually give the question asker what they were asking for.
This answer is the epitome of all of the answers here pointing probably in the wrong direction.
The OP is basically saying any discussion of 'amortization' or anything past something very simple, was completely beyond them.
And your response, like many others here, is gong way off into the weeds, suggesting 'what they were really expecting' etc..
I definitely understand HNers willingness to go into the weeds for no apparent reason, but the lack of social comprehension here is really odd.
The OP has reiterated over and over the social context and yet everyone seems to be happy to dismiss it whilst providing their bit of extraneous extra input.
It goes on like a comedy.
"But they must have been expecting this niche/novel thing way over here in the corner, and well if you didn't get that ..."
It's as though the respondents are validating the poor ability of we techies to establish context.
Any specific requirements in the interview, it would seem, could have been discussed by the interviewer and frankly without providing very specific contextual details, there's no such thing as a 'right answer' because it always 'depends'.
And finally, why anyone would expect specific correct answers instead of a discussion about the constraints is also odd to begin with.
> fairly certain they were looking for a linked list, but I could be wrong
They were probably looking for an answer which went along the lines of a linked list and then what to fix - the ratio of pointer sizes to data (16-item nodes), sorted insert optimizations, the ability to traverse to the 500th element faster etc (skips with pow-10 or a regular skip list etc).
I bombed a similar soft-ball interview question in the past, because I was asked to build out a work item queue using a database in SQL & I got stuck failing to explain why it was a bad idea to use an ACID backend for a queue.
Some constructive feedback from the person who referred me came back as "dude, you just wouldn't let go of the topic and the interviewer gave up on you".
That was definitely true for me, but I remember that feedback more than the actual technical correctness of my opinion.
That was a clear failure of fit in multiple ways, but it didn't matter whether I was right or not, I had failed to persuade someone who would be my team lead on a topic which I had deep knowledge on.
There is a tradeoff between the cost of introducing another component, and the advantages of a perfect component.
If you already have an ACID database at hand, and your queue requirements are not that big, using the database and NOT having to have someone around who knows exactly how Rabbit MQ was set up is better than to require everyone around you to know the piece of specialized software that you happen to be a domain expert on.
Conversely if your needs are demanding enough, then it is best not to let your team discover the hard way why people build dedicated queueing systems.
If you are unable to accept that this tradeoff even exists, then I wouldn't want to be your team lead.
