Pregunta de entrevista de Arista Networks
Implement queue using two stacks. Implement stack with push(), pop(), getMin() [ each in O(1) time]. How do you implement linux file system?, what data structures do you use?, write code to create file, folder and delete file, folder and search for a file, folder. How do you think the android contacts search is implemented? what data structure do you use? some questions on trees. syntax of printf function in c. How does free() function in c knows the amount of memory it needs to deallocate? no questions from dp are asked. If you are good at C, C++ and data structures you can easily crack the interview.
Respuesta de la entrevista
Anónimo
- queue with 2 stacks: pushes always go to stack A. pops are always from stack B. whenever stack B is empty (and only when it's empty!), pop all elements from A into B. push will be O(1), and pop will be amortized O(1) - stack with getMin, all O(1): use 2 stacks. push and pop normally using stack A. only push to B when the new element being pushed to A is less or equal the top of B (or B is empty). only pop from B when the top is equal the element being popped from A. all O(1), nothing amortized - linux fs: it sure looks like a tree, but how to code this? i dunno, should i know the syscalls/disk API structure to answer this? damnnn - android contacts: a trie, since usually the app only finds prefixes, or aho corasick for more flexible/less accurate results (it finds substrings) - printf: printf(const char* fmt, ...), it's a C's variadic function. use the va_args C constructs to retrieve the args from the call stack - free: memory blocks usually have a fixed-size data structure in their beginning with their metadata (a memory overhead), so the lib subtracts this size from the given pointer and casts to the appropriate type