Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
I like the way you have visioned the states. But there are a few more things to consider :
1) Use case : Alarms can be set to recur daily/weekly/ or on specific days of each week. So the AlarmSetState need not be a called manually always. Your clock class can take care of it. As soon as a AlarmEndState is captured from the user, the recurring states can be checked to automatically call the AlarmSetState with the next recurring instance. (you can argue here that an alarm can be snoozed till the next recurring instance is crossed (in which case alarm end state will not be caught and recurring instance alarm will not be set). Either you can add all the recurring instance till 1 year as separate alarms, or in the beginning of each day (assuming lowest recurring interval is 1 day) add the recurring instances from each alarm for that day.
2) The future java task needs to be owned and handled by the clock class as it will sort all the java tasks set by multiple alarms and know which one to execute first. maybe you can use a heap here to know which one needs to go first. Or use a simpler DS is number of alarms you think will be less.
3) You failed to mention that AlarmBuzzState will NOT be a manual action and will be taken by the java task.(or the clock). So the clock picks up the top of heap and when the time comes triggers AlarmBuzzState.
A min heap should do the job with each elements contains the message ( to alarm) and time should be the key to create min heap.
It can easily support snooz operation as well by removing and inserting the node with new time in the heap.
Min heap is great, but complex unless implemented by the language in question is a lot of work. How many alarms does one need? 10, 15, 2000? Remember that many data structure perform well at scale, but at small values suck hard compared to stupid simple implementations. The average individual will have 2 or 3 alarms set. A simple vector that you scan on a timer every second should suffice. Simple to implement. Simple to maintain. Simply works.
Every second, scan all alarms (assuming 1~20 less than a millisecond), and if any hit make some noise!
Can we Design it in Object Oriented way?
Following are some of the objects to design Alarm cloack -
- Clock
- Time - contains hours, min and date
- hour
- minute
- Date
- Format
- Alarm - contains hours, min and date
- User
A user can set different Alarms.
All the alarms (set by user) can act as observer and Time would be the subject.
As soon as time of any alarm hits, corresponding ring function would be called.
Functionality required for an alarm clock to be useful are :
1) Should display current time when user starts the application and options to add new alarms and view previously set alarms
2) Setting alarm sub functions
- set time (can include military time as well)
- set music to be played when alarm goes (this could be provided a default value + custom music that user might want to add)
- adjust volume settings
- frequency of alarm (daily/weekly/specific days of week)
- snooze options (time interval to snooze for could have default value and should allow changes as well), snooze option should be enabled or disabled by the user itself.
- allow the user to add labels or reminders with alarms
Data Structures:
The time for the alarm should be put in an array and a corresponding count according to the frequency of the alarm should be attached to each alarm. Flag can also be used to differentiate one-time and regular alarms.
For the ease of user, the alarms should be displayed in increasing order of time and date i.e. the alarm that will go next should appear first.
Tests :
- When the user tries to set up more than one alarm for the same time, show a proper message saying add reminders or labels to the previously set alarm.
- The device clock should be synchronized with that of the application.
For any design question - one should first understand all the use cases.
- Algorithmy October 28, 2014for this question, let us simplify and consider the following use cases
1.) user can see the current time on the clock
2.) user can set/update the alarm (time, sound, ipod etc) for the clock
3.) clock needs to sound the alarm at the right time
4.) user can snooze/end the alarm.
In this problem, choosing an datastructure is not a big problem. The question might be around how you would design an alarm clock either object-oriented (or) system wise.
Classes:
Clock (Time (can use Calendar object), setTime(), getTime(), list of Alarm objects <Arraylist>)
Alarm (Time (can use Calendar object), setState(IAlarmState), call the right doAction() depending on value of AlarmStateEnum)
AlarmStateEnum - set, buzz, snooze, end
IAlarmState --> doAction()
AlarmSetState implements IAlarmState ==> doAction can call an scheduled future java task to buzz the alarm.
AlarmEndState implements IAlarmState ==> doAction can cancel the scheduled future java task or end the buzzing alarm
AlarmBuzzState implements IAlarmState ==> doAction is an function that will play the sound
AlarmSnoozeState implements IAlarmState ==> doAction will call the clock to cancel the scheduled future java task and create a new one with the snoozed time.\
Please let me know any feedback or input.