Mar 4, 2016 12:08 AM
(This post was last modified: Mar 4, 2016 12:14 AM by 6577657534735.)
Going to make a weekly challenge thread to help people prepare for in-person whiteboard style data structure and algorithms interview questions. To some these problems will seem rudimentary, but to other beginners they should be a wake up call that data structures and algorithms are a lot more important than learning random language features and the public interfaces of random libraries or APIs.
Problem:
You are a ticket manager at a ski resort. People are constantly entering and leaving the resort.
When they enter they get a ticket with a unique number on it as well as a time they must leave which is one hour from right now.
People can renew their ticket by running to the counter real quick and showing their number to the ticket manager who gives them another hour free of charge (by updating their time they must leave to be an hour from now once again).
But of someone forgets to renew their ticket and is still in at the time they must leave, name is announced on the loudspeaker to get the fuck out of there since they've overstayed their skiing enjoyment welcome, and their ticket number is released back to the manager who sticks it in the pool of potential numbers and can now assign it to a new person who enters at some point in the future.
When people choose to leave they give their ticket to the manager and its number is also returned to the pool of potential numbers to be assigned to future customers.
tl;dr
Explain how to solve this problem i.e. which data structures and algorithms to use to do the following tasks:
There are basically only 3 functions you need to implement that work upon shared data structures. Figure out what the functions are as well as what the shared data structures are.
Keep in mind that this ski resort can lots of people. So you really really really have to optimize for algorithmic complexity and memory usage
Feel free to spitball random ideas. And don't Google the question. Even if you can figure out how to word it in a searchable way you're just cheating yourself out of practice and knowledge.
Good luck!
Problem:
You are a ticket manager at a ski resort. People are constantly entering and leaving the resort.
When they enter they get a ticket with a unique number on it as well as a time they must leave which is one hour from right now.
People can renew their ticket by running to the counter real quick and showing their number to the ticket manager who gives them another hour free of charge (by updating their time they must leave to be an hour from now once again).
But of someone forgets to renew their ticket and is still in at the time they must leave, name is announced on the loudspeaker to get the fuck out of there since they've overstayed their skiing enjoyment welcome, and their ticket number is released back to the manager who sticks it in the pool of potential numbers and can now assign it to a new person who enters at some point in the future.
When people choose to leave they give their ticket to the manager and its number is also returned to the pool of potential numbers to be assigned to future customers.
tl;dr
Explain how to solve this problem i.e. which data structures and algorithms to use to do the following tasks:
- Assign tickets with unique numbers, and an expiration time one hour from now
- Determine which tickets are expired and return their numbers to the pool of potential assignable numbers
- Let users renew their ticket so their expiration time is one hour from now
There are basically only 3 functions you need to implement that work upon shared data structures. Figure out what the functions are as well as what the shared data structures are.
Keep in mind that this ski resort can lots of people. So you really really really have to optimize for algorithmic complexity and memory usage
Feel free to spitball random ideas. And don't Google the question. Even if you can figure out how to word it in a searchable way you're just cheating yourself out of practice and knowledge.
Good luck!