Latest DATA STRUCTURE Aptitude Question SOLUTION: 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

• Placement Papers
• /
• DATA STRUCTURE
• /
• Programming
• /
• Technical

DATA STRUCTURE Question Papers:

(#M40151838) DATA STRUCTURE Programming question Keep an EYE

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.

Asked In DATA STRUCTURE aditi yadav (9 years ago)

Solved gaurav Read Solution (4)

Is this Puzzle helpful?   (8)   (1) Submit Your Solution Technical

Read Solution (4) :

Nitish Sharma  (9 years ago)

Use a binary tree of some type (pick your favorite flavor). Each node of the tree would preserve a single photo and a flag indicating if the photo is a favorite. The tree is sorted on the time that the photographs are taken.

Insert(x, t, m): inserts a new tree node at a location 't' containing photo 'x' and flagged favorite = 'm'==1. This operation is O(log n) complexity and takes O(1) memory where n is the number of stored photos

Search(t): do a search for the first node that occurs immediately after 't'. This operation is O(log n) in complexity and O(1) memory where n is the number of stored photos

NextFavorite(t): do a search for the first node with the flag == true and time after 't'. This operation is also O(log n) in complexity and O(1) memory where n is the number of stored photos

For the most part, this is the 90% immediate solution. There are naturally other things that could be done like bucketing chunks of time or maintaining separate trees for the favorites vs all the photos

Is this solution Helpfull? Yes (4) | No   

Manish Pant  (9 years ago)

B+ tree is a data structure that can be used here.

Leaf nodes contain (pointer to photograph stored in memory, time and favorite). and all leaf nodes are connected.

Now for inserting new record it will take O(logn base b) b - order of b+ tree
Search also it takes O(logn base b) Time complexity.

Is this solution Helpfull? Yes | No (4)  

gaurav  (9 years ago) Best Solution

Use a binary tree of some type (pick your favorite flavor). Each node of the tree would preserve a single photo and a flag indicating if the photo is a favorite. The tree is sorted on the time that the photographs are taken.

Insert(x, t, m): inserts a new tree node at a location 't' containing photo 'x' and flagged favorite = 'm'==1. This operation is O(log n) complexity and takes O(1) memory where n is the number of stored photos

Search(t): do a search for the first node that occurs immediately after 't'. This operation is O(log n) in complexity and O(1) memory where n is the number of stored photos

NextFavorite(t): do a search for the first node with the flag == true and time after 't'. This operation is also O(log n) in complexity and O(1) memory where n is the number of stored photos

For the most part, this is the 90% immediate solution. There are naturally other things that could be done like bucketing chunks of time or maintaining separate trees for the favorites vs all the photos.

Is this solution Helpfull? Yes | No (4)  

Hitesh singh   (9 years ago)

Use 2 B-Trees for storing the photo Node indexes based on their timestamp, one tree for favorites and other for non-favorites so search will be
O (Log N), you can search for first immediate node after Timestamp T, this will still be O (log N), insert and remove O(log N) each node of the tree would store a key value which would point to a HashMap which would store the actual photo data (or else retrieve it from a persistent storage).

Is this solution Helpfull? Yes | No   

Please Login to Read Solution.