Amazon Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

time complexity : O(nlogn)

typedef struct node
{
int start;
int finish;
}node;

solution :
{
1. Use the Priority_Queue <node> data structure
by setting the priority of increasing finish time...
// means the one having less end_time will have greater priority;

2. Then pop first node from priority_queue;
and set last_finish=node.finish;

Then pop nodes from priority_queue until Priority_queue is empty...
if(node.start>last_finish)
return NOT_BUSY;

else BUSY in that appointment;

}// end

----question based on activity selection

- v krishna January 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

/// little bit edited and more explained soln of above algo

time complexity : O(nlogn)

typedef struct node
{
int start;
int finish;
}node;

algorithm :
{
1. Use the Priority_Queue <node> data structure
by setting the priority of increasing finish time...
// means the one having less end_time will have greater priority;

2. Then pop first node from priority_queue;
and set last_finish=node.finish;

Then pop nodes from priority_queue until Priority_queue is empty...
if(node.start>last_finish)
{ last_finish=node.finish;
and Doctor is NOT_BUSY in current node appointment
// so appointment is possible
}

else
{
Doctor is BUSY in current node appointment;
// so appointment is not possible in this
}

}// end

----question based on activity selection

- v.krishna1708 January 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution: Go though each interval and check for conflict. O(n).
Another solution use a 2D interval tree to make the queries. O (log n)

- Anonymous January 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not maintain a schedule as a binary tree, where key is the starting point and data is the finish time:

for every new appointment
1. search for the node at which this appointment (node) can be inserted, by start times ... O(log n)
2. get the successor of the pre node ... O(log n)
3. check for conflicts: pre.finish < new.start && new.finish < successor(pre).start ... O(1)
return true if no conflicts, and otherwise

- Anonymous January 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input needed :
1. what is the length of the appointment to be scheduled?
2. What is the last time until which an appointment can be scheduled?

once we have these details, follow these steps:
1. arrange already scheduled appointments in increasing order of start time. O(nlogn)
2. traverse through the list and compute difference between end time and start of successive intervals.
3. an appointment can be scheduled if oneo f the following is satisifed:
a) if the gap between any two successive appointments is greater than or equal to the length of the required appointment
b) if there is enough time left in the day after last appointment to accomodate the new appointment

- anon123 January 12, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More