|
Pretend you work for a phone company. At your company .......
Microsoft Interview Questions and Answers
(Continued from previous question...)
109. Pretend you work for a phone company. At your company .......
Question:
Pretend you work for a phone company. At your company, you have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. (After asking clarifying questions I received the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts, answer part 2 of this question in such a way as to maximize revenue).
What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct).
Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory like I did, it can be done in O(n)).
Edit: Your solution should not be real-time. The data has already been collected and you need to work with it.
maybe an answer:
Use hash table with key being user id and value an object like {int count, max_count} then on each new call I'd increase "count" for calling user and update max_count if count became more than it. On hangup I just decrease count. On 24 hour boundary hashtable is dumped and users are billed according to that data. O(n) runtime and O(n) memory
typedef struct phone_call {
unsigned user_id; /* arbitrary since all data being fed is for one customer */
unsigned int start_time;
unsigned int call_length;
} phone_call;
(Continued on next question...)
Other Interview Questions
| 