Q1: https://leetcode.com/problems/missing-number
Proposed two solution for Q1 by using arithmetic progression sum and second solution with mark and sweep type of algorithm.
Q2: How will you solve above if the array is sorted 0,1,2,4
Proposed second one for simple binary search.
Interview finished before time and yet they said NO. sometimes its just not the algorithm.
补充一个面经：
Interviewer was very nice and pleasant.
First 5 minutes: general chit/chat.
Coding :
Given a list of names (LastName, FirstName) and an input param (“xyz”), return a list of all the names where either the first or last name start with that entry parm.
Then we moved on to calculating the Big O. Initially mine was O(n) (simple loop); then he asked me if I could make it better, I suggested sorting the array once and then binary which would be O(log n) (just the lookup, not the sorting, that would still be n.
Then he asked me what I prefer, I explain the binary approach, as we could sort the array with a nightly job so lookup times are faster; he seemed satisfied with the answer.
Then we moved on to some behavioural questions; accomplishment at work, we dug deep into it, I used the STAR format, he wanted technical details, I think I did okay.
Quite surprised that I got asked a not so hard question; now I wonder if that was actually a bad thing.
也报一个挂经
社招 猎头联系的
电话面试，一个小时。上来问了一下工作的问题，十分钟后进入zho问的是LRU
需要用linkedHashMap或者orderdict来实现，不然比较难写完
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up:
Could you do both operations in O(1) time complexity?
上来就直接最优吧，用linkedhashmap