Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
I think Lazy deletion should not happen in an array list. The expectation from array list is
Access = O(1)
Insertion/deletion = O(n)
When you delete an element, all the elements to the right have to be left shifted by 1 element . The reason is, again next access to the array list is O(1). If you flag the deleted elements this cannot meet that..
Also I think threshold should always be n (with capacity increment of kn where k is the number of times u exceed the size). However this is implementation dependent.
There is misunderstanding with operation delete(), because its prototype has not index variable, so if we can delete only from the end of an array we can use lazy deletion, else we should shift all elements placed next to the current.
If deletion happens at the end you are decrementing your length. So flagging is not neccessary.
Create an array of size 2n where is n is the size of object[]. If the size grows beyond, 2n/3 ( some threshold T), create a new array of size "3n" and copy the elements from overgrown array.
- AmzFAILFacebookFailMSFTFail January 05, 2012Add will to empty locations of the array while delete will be lazy delete. for each delete request, we should invalidate the data at that location and do not free up memory until there are enough cells that needs to be deleted.
Update should be trival in this case.
Disclaimer: Naive approach. Would love to see some awesome improved answers!