Data structures question.. A sawmill company maximizes its revenues by tracking
ID: 3581950 • Letter: D
Question
Data structures question..
A sawmill company maximizes its revenues by tracking each log individually. They want to perform the following queries as quickly as possible using a reasonable amount of memory. You can use a different data structure for each query. given a unique log ID number, display information about the log e.g. size, weight, wood specie, origin, current destination, end destination, etc. each log undergoes a sequence of processing and is transformed into several boards with their own characteristics. Given a unique log ID, what is the quickest way to list all the boards it was transformed into? given a unique board ID, how can one find out which log it came from? a furniture needs a specific number of boards to be further processed. Given the requirements for the furniture as number of boards and species, how do we quickly find out the closest location having these boards? Assume each log has a location, all boards stay at the same location as their parent log, and the furniture factory location is known. In addition, assume all data is known at the time of the query i.e. do not solve the dynamic version of the question that involves transportation times. each log is assigned a quality index from 0 (low) to 100 (oustanding). Custom orders have specific requirements of using a log with at least a given quality. Given a custom order, how would you select the logs to fulfill it? Assume logs are continuously brought to the sawmill. For each question, explain in plain English what data structure you suggest, the time-complexity to answer the question (separate pre-processing time from query time), whether it is worst-case, expected, or averaged time complexity, and enough explanation in plain English of your algorithm to justify the complexity.Explanation / Answer
1. Given a unique ID, we have to go through all the available logs to find out the given log ID. Each log can be stores in an array. If there are N logs available, we need to loop through all the logs to find the given log.
The time complexity for this would be O(N). This has an expected time complexity.
2. We can use an array to hold all the logs and boards. The first processing will take O(log N*N) since we have to go through all the logs and create boards. Once this is done, we have to again go through the boards and display the board information.
3. We can loop through the arrays of all the boards. Each board will be conatining the log ID associated with it. Through this we can get to know the information about the log. This will again take O(log N*N) since this will be looping though the array of boards and then the array of logs.
4. The array can be sorted in the acsending order of locations from which the nearest location can be taken.
This will take O(log N) complexity
5. We can loop through the array of logs and find out the logs with exact quality and display all of them. This will have O(log N) complexity.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.