Question

Flipkart | SDE | Coding OA Questions and Solutions | Set - 7

Answer 1

You are given a range [m , n]
Consider them a licence plate number.
For regular customers you use numbers in sequence and for premium customers you can give out number which customer asks for and if its available.
Question is you need to perform both operation in O(1).
How can this be done
for e.g. range is 1000 -> 5000
normal customers: 1000, 1001, 1002, 1003.....
for premium customer: 1111,1221,1122 etc - it can be any number customer wants

 

Which DS to use for this problem, only constraint is time wise it must be O(1)

Comments

Create a DLL with a data field containing values in range m to n.
Create an unordered map to map numbers [m to n] to node addresses.
Front always points next available number.

for each requested number
       if(regular request)
            d=DLL.front.val;
            delete front node
            delete mapping of d to address in unordered map
      else
           if number  exists in map
                   delete corresponding DLL node
                   remove mapping from map
          else
                number not available for allocation