YOE : 6+
Location : Bay area
Telephonic:
1.) https://leetcode.com/discuss/interview-question/417262/dropbox-phone-screen-permissions-in-a-file-system
They just expect you to save the data as dictionary with parent child relationship and just traverse it to find if the file or directory has the access.
Follow Up: find if the directory's access is redundant. Basically say A has two children B and C. Initially hasAccess = (A, B, C). Now, since A has access then B & C dont need access because they are just Children of A. So, remove B and C and return (A)
Normal space, time complexity discussion
Onsite:
1.) The interviewer started with asking me to access read_acquire(), read_release, write_acquire, write_release.
Using Semaphores. This is the most boring question I have been ever asked in an interview. Mainly because I think unless you are Silberschatz or have really good experience with multithreading(which I don't) or remember the implementation of wait() and signal() it is hard to come up with a solution on the spot. In any case, the interviewers were sweet. They kept helping but after 15 min it almost became a dictation. So, I said I am not interested to interivew. Some(read all) companies take it as a sign of "unwilling to learn" but I was genuinely not interested to write a dictated solution. The interviewer was caught off-guard. He googled for some other question and came up with a very simple question to list all files and directory.
Then they asked how would I implement a feature to find duplicate files. I think this is something you can find somewhere on Leetcode discussion section.
2.) Say you are given a number N, such that N tends to a million. You have to come with a design for this class:
class Number:
def assign():
# Assign a number from 0 to N-1
def release(num):
# return num to be reused.Approach 1: Create two linkedlist. One for Assigned and one for unassigned and do simple O(1) to assign but O(n) operation to release a number. Becuase you will have to find the number in the Linked List. It can be simplied by using a hashmap. But roughly speaking space requirement will be 1 Million * 4 bytes = 4MB (Not including the hashmaps + pointers space)
Approach 2: keep a global variable say count. count will only increase in a strictly increasing manner. Everytime you release put the result back in the a set. and now if you are called acquire() first check the set. If the set is not empty return from there else increment count. Again memory requirement will be 4 MB in worst case.
Approach 3: Create an int array of about 2^15 element. A million = 2^20 and 1 integer = 4 bytes =2^5. dividing the two you get 2^15. That is you want 1024 * 32 elements in the array. Where each bit will represent a flag for a number.
The interviewer said it is too complicated. So, we didn't discuss this further.
Approach 4: Interviewer gave this solution. Create a heap of these N numbers. Then for every subtree rooted at i, save T/F at arr[i] to represent if there is an element available in the subtree or not. I didn't understand the approach but the time was up. As this can solve in O(log n) time and 1 MB memory.
3.) Implement Producer Consumer. Say producers/end users are producing images to be processed. And then consumer is a service that will use these images to process and then discard the images that have been processd.
The interviewer said it is fine to assume that system will not be fault tolerant but then changed her mind later.
My design was end user -> LB/rate limited -> Services -> DB
Now DB, will mark each row as PROCESSING once the consumer service picks a row for processing. And say, now consumer itself crashed so there will be another monitor process that will see that row has been in processing stage for say an hour now. It will reset the row to AVAILABLE.
suggested api /messages {GET, POST} respectively that can take json objects. The interviewer didn't ask much about how would you send the file. As in encrypted? Stream? The main focus eventually became the fault tolerance of the system.
There was some discussion about when will producer send 200 OK response code. Some discussion around fields of the DB.
4.) Behavioral
They asked me to pick a project. Mainly, around who made the decision. Who asked you to do this. Who verified the results etc. What did you learn. When you received/gave negative feedback.
5.) Another call with someone from the team to know more about the team.