Interview Questions

Design a algorithm for printing a book........

Microsoft Interview Questions and Answers

(Continued from previous question...)

120. Design a algorithm for printing a book........

Question:
Design a algorithm for printing a book, since the pages in a book are binded, the page number changes if we add more pages. what is the data structure you can use best and why?


maybe an answer:


Think about adding pages randomly to the book either at the end or in the middle.. suppose there are 20 pages and we insert an extra page after 15 so the ordering of page 15-20 changes to 16-21. Is binary search tree or Linked list an option in such case? what about eliminating duplicates and reordering the pages? if it is just about adding more pages at the end is it easier in BST (lgn) and it takes O(1) in Linked list (adding to the tail), max heap also sounds good.

Let us say page nos
1 2 3 4 5
add a new page at stating of the book, then you have to modify all page nos .

1 2 3 4 5 6
Adding a new page at the starting of the book ,time complexity O(n). you have added n new pages at the staring then total time complexity O(n^2 ).

(Continued on next question...)

Other Interview Questions