Thursday, April 10, 2014

Find the appropriate data structure

Lets see if you have solutions to the standard problems. Lets define the suitable data structures.

Guess the data structues between the 2 data structures provided (in italics).
  1. Operations are Insert, DeleteMax, and DeleteMin.
    balanced tree or sorted doubly-linked list
    The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n).
  2. Operations are Insert and FindMedian.
    (The median is the item m such that half the items are less than m and half are greater than m.)
    red-black trees or sorted array
    You can use two red-black trees plus an additional variable to hold the median, one red-black tree for items less than the median and one for items greater than the median. When you insert, you can keep track of the median by moving items from one tree to the other. With this scheme, Insert takes O(log n) time and FindMedian take O(1) time. The sorted array takes O(n) time for Insert.
  3. You have a dictionary containing the keywords of the Pascal programming language.
    ordered array or red-black tree
    In this situation the ordered array is best. Both data structures take time O(log n) to find an item. An ordered array takes longer to insert or delete, but we don't expect to be creating or destroying keywords, so there shouldn't be any insertion or deletion. The ordered array is simpler to program and takes less space.
  4. You have a dictionary that can contain anywhere from 100 to 10,000 words.
    unordered linked-list or red-black tree
    The red/black tree is better, since the operations require O(n) time for the linked-list and O(log n) time for the red/black tree. For 10,000 words this could certainly be significant.
  5. You have a large set of integers with operations insert, findMax, and deleteMax.
    unordered array or Hashtable
    Neither data structure is good for this problem. An unordered array is slightly better since it has less overhead and it's easier to program.



Post a Comment