Interviewer explained a bit about Technical Screening round, like how he wants structure the interview,
Q1: ~ approach : 4 min ~coding : 5min ~complexity : 1-2 min
Given an array of integers, return the position of the maximum element. If the maximum element occurs multiple times, use a random number generator to choose one of the positions uniformly at random.
// I asked few questions
I walked through how i want to solve it.
Sol 1 : I gave simple map based solution which holds element and position, he was not happy.
Sol 2 : linear time and no extra space.
Q2 ~approach : 5 min ~coding : 15min ~complexity : 5 min
You are given N integer intervals [a_i, b_i] on the real axis, and the absolute value of the coordinates is bounded by M. Determine a point that belongs to the maximum number of intervals. Point x belongs to the interval [a, b] if a <= x <= b.
// This one was confusing, so asked few dumb questions
I read question again, explained what I understood.
Sol 1 : sort intervals and then look for point x that is present in most of the intervals, he was not happy
Sol 2 : Instead of sorting, determine start and end of all of the intervals combined, then use PriorityQueue which is sorted based on count for point x seen on intervals. He asked me to implemented
Walked through run time and space complexity. Everything was okay till I said queue.poll() will take o(1) time. instead of o(log(m))
//--------------------//
Feedback came positiive, moving to Virtual Onsite, next week.