Onsite
Round 1: Given a sorted n-size array, there are k elements have been changed i.e. [1, 3, 5, 6, 4, 2, 12] (it might be changed from [1, 3, 5, 6, 7, 8, 12] with k = 2). Important to know is that k is unknown and k is much smaller than n. The task is to re-sort the entire array.
The interviewer wants O(n) solution. I bombed this one. In the end, the interviewer kind of fed the solution to me. What he suggested: a. break the array into two: one sorted array and one unsorted array e.g. [1, 3, 5, 12] and [6, 4, 2]. This takes O(n) b. Sort the unsorted array. This takes O(klogk) c. Merge two sorted arrays. This takes O(n). Because k is very small, so in the end O(n) + O(klogk) ~= O(n).
Round 2: First describe a situation you missed a deadline and what you have learnt from it. Then coding question: Card has 4 attributes (color, count, shading, shape), each attribute can have value 0, 1 or 2. 3 cards are considered as a set if for each attribute, 3 cards either have the same value or have different value from each other. For example:
card1 (2, 0, 1, 2), card2 (1, 0, 0, 1) and card3(0, 0, 2, 0) are 1 set.
card1(2, 0, 1, 2), card2 (1, 1, 0, 1) and card3(0, 1, 2, 0) are not 1 set.
- write a boolean function with 3 cards as input. This function returns true if they are 1 set, otherwise returns false.
- Now given a collection of cards, return true if there is a set of cards exsits, otherwise return false. The interviewer wants O(n^2) solution.
Round 3: Given an array i.e. [1, 2, 3, 5, 6, 7, 8] and a value k i.e. 3. If there is a subarray with length of 2k satisfies a sequence [a, a + 1, a + 2 ... a + k - 1, b, b + 1, b + 2... b + k - 1]. Return the beginning index of this subarray. So with given array [1, 2, 3, 5, 6, 7, 8] and k = 3, it can return 0 as [1, 2, 3, 5, 6, 7] satisfies the sequence requirement. If with given array [1, 3, 5, 6, 7, 8] and k = 3, it return -1 as there is no such subarray exsits.
Round 4: a CPU task is defined as Task(id, queued_time, exec_time). Id is the task's id; queued_time is the time when the task joins the queue; exec_time is the time needed to execuate the task. Given a collection of CPU tasks return the order of task ids thats been executed by one-core evil CPU. For example (1, 2, 2), (2, 5, 15), (3, 5, 10) would return 1, 3, 2. The reason is that at 2nd second, task#1 joined the queue and it's the only one in the queue. It's been executed first. At 4th second, task#1 is finished. CPU is in idling state. At 5th second, task#2 and task#3 joined the queue. CPU will first execute task#3 as task#3 has smaller exec_time. At 15th second, task#3 is finished. Task #2 is still in the queue. Task#2 will be execuated. So the order of execuation is 1, 3, 2.
Round 5: standard behaviral questions.
Overall it was a very good experience to have regardless of the result. All are pretty standard. All interviewers are there to help you instead of making you feel bad.