Stack growth and multi-source BFS

Questions 1 to 5 of 8

1. 1. A stack built on an array that doubles its capacity, starting from empty, gets 1000 pushes. How many items does it copy in total?

   Type a number.

2. 2. A stack whose capacity grows by one slot each time it is full, starting from empty, gets 10000 pushes. How many items does it copy in total?

   Type a number.

3. 3. Why does doubling make a push cost constant time on average, even though one push can copy every item?

   Each push copies exactly one item, so the copies never add upThe total number of copies over n pushes stays below 2n, so the average is about one copy per pushThe array never grows after the first 16 pushesDoubling makes pop copy the items back, which balances the cost
4. 4. In multi-source BFS, why are all the start cells put into the queue before the loop begins?

   So the queue holds one cell at a time and the bounds check is skippedSo the queue can be read once per minuteSo every start's ripple begins at distance 0 together, and each cell takes the distance of its nearest startSo the answer is the sum of the distances from all the starts
5. 5. In minutesToRot, the number of cells to process in a minute is read once at the start of that minute. What goes wrong if it is read again on every step of the inner loop?

   The loop would skip the first rotten orange in the queueThe grid would be copied and the original would changeThe function would return -1 for every grid that has rotten orangesOranges that rot during the minute would be processed in the same minute, so the answer would come out too small