Question

Safaricom service provider has assigned you a task in their software section to design an application that can be used by wholesalers to buy their products. Your duty is to implement the data structure which can be used to store the inventory of the warehouse containing the products. The data structure should be able to add a product with an associated code indicating its likelihood to spoil, remove a product that is most likely to spoil, and return the overall number of products in the inventory.

i.          Describe the data structure you would use and give reasons.

ii.         With reference to algorithms, explain the terms time efficiency and space efficiency.

iii.        Describe a non-linear data structure. Give examples and operations in which you might perform on such a structure.         

Answer 1

i.

The data structure that will ber good for this purpose would be linked list.

linked list is dynamic in nature and it does not wastes memory (unlike an array where size has to be fixed beforehand) and also does not overflows (provided RAM is large enough). it takes O(n) space where n is the number of items.

For the purpose of the question , we will store the inventory in linked list form with the elements sorted in increasing order of their likeliness of getting spoiled.

to remove the item that is most likely to spoil we just remove the first element of the linked list. It takes O(1) time.

to add an item we iterate over the linked list from start to end and put the item in correct place.the correct place is defined its likelihood of getting spoiled. It takes O(n) time

to return number of elements in inventory we maintain a count variable. it is incremented by 1 everytime an inventory is added and decreased by 1 everytime an item is removed. it takes O(1) time

iii.

A non linear datastructure for this problem would be max-heap (assuming higher code value= higher likelihood of gettinng spoiled). it also takes O(n) space

to remove the item that is most likely to spoil we just remove the root of the heap. but removing the root would break the heap and in order to restore the heap we call HEAPIFY() which take O(log(n))

Insertion in a Heap takes log(n) time.

to return number of elements in inventory we maintain a count variable. it is incremented by 1 everytime an inventory is added and decreased by 1 everytime an item is removed. it takes O(1) time