-
An airline keeps track of ticket booking, flights and such. Airports have unique
airport codes, flights have unique flight numbers and airplanes have unique
identifiers. For each task below, suggest a suitable data structure from the following
options: Stack, List, Set, Map, Tree, Graph, Queue.
Storing which plane each flight uses.
Suggested data structure:
- Map where keys are flight numbers and values are airplane IDs.
- Only one value per flight.
-
An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.
Keeping track of which flights serve meals and which do not.
Suggested data structure:
A set of flight numbers, containing the flights where meals are served.
-
An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.
Storing a phone number for each booking on all flights, and the order in which
they were booked.
Suggested data structure:
- A list of phone number/flight number pairs. New bookings are added last
- in the list to record the order of bookings.
- The same number can book
- many tickets.
-
An airline keeps track of ticket booking, flights and such. Airports have unique airport codes, flights have unique flight numbers and airplanes have unique identifiers. For each task below, suggest a suitable data structure from the following options: Stack, List, Set, Map, Tree, Graph, Queue.
Storing known airports and all flights between them.
Suggested data structure:
- A directed graph where nodes are airports and edges are flights.
- Allows finding routes involving multiple flights efficintly.
-
Here is a program that wants to learn names and numbers.
The method requstUserInput() lets the user to enter a line of text.
ArrayList.add(x) adds x last in the list.
ArrayList.indexOf(x) uses linear search to find the first index of x, or -1 if x is not in the list.
Suggest a more suitable data structure than lists. Do you think it would improve
the complexity of any operations? Motivate your answers.
- This is a typical case where a map should be used.
- This will replace both
- lists with a single map from strings to strings.
- Instead of indexOf, get is used
- and instead of two adds, use a single put.
- Since indexOf is a linear search,
- using for instance a hash map instead would be a significant speedup.
-
- Node a = g.newNode("a");
- Node b = g.newNode("b");
- Node c = g.newNode("c");
- Node d = g.newNode("d");
- g.addEdge(a, 8, c);
- g.addEdge(a, 4, d);
- g.addEdge(c, 1, d);
- g.addEdge(b, 6, d);
-
For a part of a simple application that handles authenticated users, suggest a
suitable data structure for each task from the following options: Stack, List, Set,
Map, Tree, Graph, Queue.
Write what the elements/keys/values/nodes/edges etc.
are. Also write a short motivation for each choice (for instance which operations
become efficient, where are duplicates allowed/prevented, etc).
Storing the last login time for each user.
Suggested data structure:
- Map where keys are user id's and values are times.
- Only one value per user and they can be updated quickly
- on each login.
-
For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).
Storing the user ID's of the last ten logins into the system.
Suggested data structure:
- A linked list/queue of user id's. Each login adds a new id
- to the front and drops one from the back of the list.
- Constant time operation.
-
For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).
Keep track of which users have administrative privileges.
Suggested data structure:
- A set of user id's. No duplicates and quick lookup.
- Ordering is not needed.
-
For a part of a simple application that handles authenticated users, suggest a suitable data structure for each task from the following options: Stack, List, Set, Map, Tree, Graph, Queue. Write what the elements/keys/values/nodes/edges etc. are. Also write a short motivation for each choice (for instance which operations become efficient, where are duplicates allowed/prevented, etc).
For each user, which other users have been marked as ”blocked” or ”trusted”.
Suggested data structure:
A directed graph where nodes are user-id's and edges represent blocking/trusting.
|
|
