Data Structure to Maintain Photographs Database
Your job is to build a data structure to maintain a set of photographs. Your photograph database should allow you to insert and search for photographs, as well as to designate some of the photographs as favourites by marking them. In more detail, your data structure should support the following operations:
Insert(x, t, m): inserts photograph x that was taken at time t. If m = 1, then the photograph is marked as a favourite; if m = 0, then it is not a favourite.
Search(t): find the next photograph taken after time t.
NextFavorite(t): find the next photograph taken after time t that is a favourite.
Give a data structure for solving this problem, and explain how it works. For more efficiency, your data structure should be both time and space efficient: more points will be given for more efficient solutions. (Remember that the photographs themselves may be quite large.) Give the performance (i.e., running time) of each operation and the space usage of the data structure. You may assume that at any given time t, your camera has taken at most one photograph x. Describe your solution in words, or very high-level pseudocode. You do not need to provide complete details. You must provide enough detail, however, that your solution is clear.
-
Interview Candidate
- May 28th, 2015
- 3
- 5422
Showing Answers 1 - 3 of 3 Answers
Related Answered Questions
Related Open Questions
Data Structure to Maintain Photographs Database
Insert(x, t, m): inserts photograph x that was taken at time t. If m = 1, then the photograph is marked as a favourite; if m = 0, then it is not a favourite.
Search(t): find the next photograph taken after time t.
NextFavorite(t): find the next photograph taken after time t that is a favourite.
Give a data structure for solving this problem, and explain how it works. For more efficiency, your data structure should be both time and space efficient: more points will be given for more efficient solutions. (Remember that the photographs themselves may be quite large.) Give the performance (i.e., running time) of each operation and the space usage of the data structure. You may assume that at any given time t, your camera has taken at most one photograph x. Describe your solution in words, or very high-level pseudocode. You do not need to provide complete details. You must provide enough detail, however, that your solution is clear.
Related Answered Questions
Related Open Questions