CareerCup

Hey, good idea! I would clarify this with the interviewer (I did during the interview) - the data shouldn't be collected in real time. It will be given as the following (though you were supposed to derive this struct in some form or another for the first part of the interview):

Also, just to make life easier, you can assume that all of the data being fed to you is already constrained to one customer of interest. Work with the following structure (assume you are given a list of the following structure):

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;

Well, in that case the algo would be O(N) no more, as in case of input of format you specified, You'd need nlogn time to sort call start time and end time along the timeline. For this case I think the format like

struct
{
  uint32_t user_id;
  enum {ACTION_START_CALL, ACTION_END_CALL} action;
}

would be better. The satellite would have to log these actions into simple file, each new action would be simply appended to the end of file. Then processing would require traversal of this file from start to end i.e. linear time again :)