• Recently I am seeking for 2017 summer software engineering intern therefore I accumulated some OA experience and dicide to post them once all.

### LiveRamp

1. Given 4 numbers(0-9) and asked you find the largest combination that represents a time, e.g. 5, 9, 3, 2 after combination should return "23:59", input type is four int and output is string. It mentioned that you needn’t consider the time complexity but just the correctness.
2. Given an unordered array represents series of students’ heights. You should resort them to gain the ascending(allow equal) sequence. return the minimum number of students you have to adjust in original array to reach your final goal. It requires maximum time complexity is O(nlogn)

#### Solution

1. loop in loop for 4 times, in the last loop check they can formed a time or not and update the return result if necessary
2. Sort the array and find the first and last different height compared with original sequence. return their difference

1. A SQL question but I don’t remember that right now. It’s said that Twitter OA questions are related with your resumes.
2. Given a m*n matrix and you have to start from left-up unit and your goal is to reach at the right-bottom unit. Rule is that you can go from (1)left unit to right unit(horizon) or (2)upper unit to lower unit(vertical) or (3)left-up unit to right-down unit(diagonal) for one step once a time. Asked how many different routes to finish your goal
3. Given a sentence like "Twitter is a good company", but once a time you can just handle k characters. Asked the maximum number of words you can handle with such a constraints, e.g. in "Twitter is a good company" and given k=4 your program should return 2 with respect to "is a"

#### Solution

1. To be remembered
2. Dynamic programming
3. Sliding window to keep a deque

1. Give a string, find the number of its distinct substring which is a palindrome, e.g. absb should return 4 which are "a", "b", "s", "bsb"

#### Solution

1. loop from the start character to the end character, at each iteration choose current character as the center and expand char by char to side to find all the palindromes with center as current character

### Coursera

1. [Multiple Choice]Choose the operation has the time complexity of O(1)
2. [Multiple Choice]Given an array, if pick the midian is O(log n), how about the worst time complexity of quick sort
3. An infinite dimension matrix, each time given a coordinate (m,n) and all the units within 0<= x <= m and 0<= y <= n will increments by 1. return the number of the unit have the maximum value after applying all the coordinates
4. Given an unordered array, and an integer k, find the minimums of all the subarrays with length k, and finally return the maximum of all these minimums

#### Solution

1. To be remembered
2. To be remembered
3. Just find the minimum x and minimum y among all the given coordinates and return (x+1)*(y+1)
4. Loop from the start to the end-k. Track a sliding window with a deque(size may not necessarily be k, may be less than k) whose first element is current window’s minimum value.

### Hulu

1. Hangman), give an API that you can call and you have 3 times for wrong guess(the char you guessed doesn’t appear in given setence) for each Hangman round. If 3 wrong tolerant times run out, you will fail current round and go for next round. Try your best to improve your accuracy in 6-hour OA

#### Solution

1. No correct answer for this problem I think, just break through the limit of yourself.