Arjan
BAN USERYou need:
1) HashTable
2) Doubly LinkedList
Each entry will have the key mapped to a struct that includes {data, prev, next} via hashmap
You also need 2 placeholder pointers: MostRecent and LeastRecent (I call them hi and lo)
When you insert entries, link the 'hi' entry to the newest entry and vice versa. update the 'hi'
When you fill up the cache (ie the array/hashmap capacity) then:
1) if you get a new data entry request (cache-miss), put it in place of 'lo' entry, and update the next and prev pointers (using hi.prev and lo.next) Update 'hi' ofcourse.
2) if you get a previously entered data request (cache hit) then goto that entry (use hashmap's O(1) access) and update the prev and next pointers for that entry (using entry.prev and entry.next, hi.next) update 'hi'
Good God, this is much easier to explain on paper.
Use a Hash_map of size k.
Now hash the first k values into this map, and anytime you try to insert a duplicate, return the answer (check if value already present, if not then insert; because most hash maps will not report duplicate insertions)
Once you have mapped this initial set of k values, iterate over the rest of the elements by:
1) remove the value from the map that was at the beginning of your k-window (you may keep a pointer/index to this location and increment the location in every iteration)
2) map the next value in the array (again, you can keep a pointer/index to the current 'end' of the k-window
3) like above, check if duplicate, else keep iterating
Space: O(k) {using hash map of size k)
Time: O(n) {iterating over all the elements of array only once! }
Edge cases: think of how you can take care of the end: your k window will start skrinking so you must be careful of keeping track of the 'end' index
Test cases: arrays of size: 0, 1, k-1, k, k+1, k*2; arrays with no dups, with dups at the edges of array; with continuous dups (2 4 4 4 4 4 3); array with only dups (4 4 4 4 4)
RepChariserMachado, Android test engineer at ABC TECH SUPPORT
Hey, I am Charisar. And I'm working in Stratpro as a meeting director and it's been 3 years ...
RepHenryBrown, Associate at A9
I am an experienced budget analyst skilled at researching and consolidating financial and budget information. I am taught record keeping ...
On a higher level, you could talk about browser cookies, and the fact that the yelp.com server will (1) run some code like python to find information about your profile (2) which will eventually call into some database to get some information like how many friends, reviews, does this person have, whats his favorite location, etc (3) maybe to get your profile photo (if not already cached by the browser) will talk to some key value store to get photos, (like amazon AWS)
- Arjan July 29, 2015then you can ask the interviewer which part would he like more details on... I think its meant to be a conversation.