Amazon Interview Question
Applications DevelopersCountry: India
Interview Type: Phone Interview
This would be off by 1 (1 less):
i.e:
07-01-1992
ERROR
07-02-1992
ERROR
Now this will only count the first error if we take it from 07-01-1992 to 07-02-1992, not only that, it will fail if there is no error that start / end date.
If we want to maintain a dynamic set of records, a still better approach would be to use a balanced BST. The BST would have date as the 'key' field and should be augmented with a 'errorCount' field that maintains the count of errors seen on a given date.
1. As the input file is scanned, insert/update errorCount field of the appropriate key in the BST
2. To find the errorCount in a given range, use a modified version of rank() operation that adds up the errorCount fields is the subtrees.
- Daya May 14, 2013