Naveen
BAN USER
Comments (3)
Reputation 20
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
3
of 3 vote
Use LinkedList and HashMap, map is needed to keep the track of node in linkedlist.
1. Create -> add node to both linkedlist and map O(1)
2. Retrieve -> get the reference of the node in list using map and return the node. O(1)
3. Update -> get the reference of the node in list using map and update it in the list O(1)
4. Delete -> get the reference of the node in list using map and delete it from the both linkedlist and map O(1)
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
My previous below solution gives only number of elements needed without even traversing the array.
Minimum floor(Log(N))+1 elements will be needed to make all 1 to N numbers using ADD operation.
2^0 = 1 (if N<=1 then required number of elements is 0+1 = 1)
2^1 = 2 (if N>=2 & N<=3 then required number of elements is 1+1 = 2)
2^2 = 4 (if N>=4 & N<=7 then required number of elements is 2+1 = 3)
2^3 = 8 (if N>=8 & N<=15 then required number of elements is 3+1 = 4)
2^4 = 16 (if N>=16 & N<=31 then required number of elements is 3+1 = 4)
Here is solution what numbers need to be added to the array.
1. add 1 at index 0 in solutionArray
2. if 1 is already there in inputArray then just increment the index of inputArray.
3. loop while solutionArray[solutionIndex]*2 < N
4. check if next element in inputArray is less than current solutionIndex value * 2.
if(true) then copy the element from inputArray
else add solutionIndex value * 2 in the solution array.
- Naveen August 09, 2015