Data structures

What is a linked list?
What is the structure like?
See my first post.

What is the complexity of finding a specific element in a linked list?
Hint: It's O(n).
• An excellent answer will discuss implementation, structure, operational complexity of common operations, and examples of usage.
• A good answer will discuss an example implementation or usage, but will fail to include internal details or complexity analysis.
• A poor answer would be not knowing about linked lists or confusing them with another data structure.

Compare a linked-list to a vector.
Hint: A vector is a single contiguous memory block containing all the elements whereas a linked list is made up of several memory blocks (elements) linked together through the "next" pointer. Access to an element of the array can be made directly in O(1) but in a list, to find the n^th element, you must iterate over the previous n elements, therefore the complexity is O(n). An array is fixed in size so to extend it you must reallocate a different memory block and copy all the existing data to the new allocated block; in a linked list you can simply add a new element which is linked to the last element, so it's much faster.
• An excellent answer will discuss the implementation differences, different pattern of memory usage and access, and mention some use cases where one is more appropriate than the other.
• A good answer will discuss the implementation differences and elaborate on some examples.
• An acceptable answer will merely mention the access time differences.
• A poor answer will make a technical mistake or not know one or both data structures.

What is a hash table? What is it used for?
Hint: The following description applies for all questions about maps. A hash table is a structure which uses hash functions to store and read items. When a key-value pair is inserted, the key is transformed through a hash function into an integer which represents the index in an array where the key-value pair will be stored. Because of this hash function, the insertion and deletions are O(1) in complexity. Therefore, most hash tables are implemented using an array. Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the array can be allocated once with the optimum size and never resized. If hash collisions occur, one usual solution is to store a list of items at each index in the array. This list will contains key-value pairs for which all the keys have the same hash value.
• An excellent answer will describe an O(1) read and write data structure with scaling memory usage and give several examples of where it is useful (e.g. caching, lookup tables with irregular keys).
• A good answer will describe an O(1) read and write data structure and give an example of where it is useful.
• An acceptable answer will mention constant-time access.
• A poor answer will give the access time as something other than constant-time, or confuse it with a tree or other structure.

How can a Map data structure be implemented? (By following the question regarding hash tables, this should be a gimme.)
• An excellent answer will cite at least the hash table-backed and the tree-backed implementations and note the different performance characteristics of each, possibly mentioning that the tree-backed implementation can provide some features not available in a hash-backed implementation (e.g. sorting).
• A good answer will cite both hash table and tree implementations.
• An acceptable answer will cite either the hash table or tree implementation.
• Being unable to answer this question is unacceptable.

What is a binary tree?(This question follows the Map question to allow people who forgot non-hash table solutions to realize and revise their omission. It is good for candidates who only mentioned the hash table implementation of a map to point out that a tree is also an alternative implementation after this question is asked.)
• An excellent answer will describe a binary tree as distinct from a ternary or general tree, and will note that a binary search tree or balanced tree are distinct sub-categories of the generic binary tree.
• A good answer will describe a generic tree where every node has no more than two children and will cite the O(log N) access time where N is the depth/height of the tree.
• An acceptable answer will describe a tree where every node has no more than two children.
• A poor answer will respond by describing a binary search tree or a non-binary tree, and will not respond to gentle hinting or prodding back to the specific question that was asked.

What is the operational complexity of inserting an element into a hash table?
• An excellent answer will correctly cite O(1) complexity and then consider details include about cases in which a collision occurs and common methodologies for resolving hash collisions (i.e. chaining, linear or quadratic probing, secondary hash functions, etc.) are needed.
• A good answer will cite O(1) complexity but will not include collision considerations.
• A poor answer will be incorrect.

How is a hash table implemented?
• An excellent answer will discuss selecting a hashing algorithm, dividing the address space into buckets and tuning the number of buckets to the use-case, hash collisions and bucket overflow/conflict resolution (possibly mentioning several strategies for dealing with collisions), dynamic resizing of the hash table, and might even discuss performance optimizations and interactions with hardware caching.
• A good answer will note the use of a hashing algorithm on the keys and an array or vector of buckets, and will identify hash collisions as a problem and may cite at least one method of dealing with them. The candidate will be able to answer a follow-up about dynamic resizing.
• An acceptable answer will mention an array of buckets and using a hashing function on the key to index into the array.
• A poor answer will be technically incorrect or impossible, or will be for a different data structure than a hash table.
What is the operational complexity of (various operations) on a binary tree?If the candidate already answered this as part of the first phone screen, this question may be skipped. It may also be asked to ensure the candidate is consistent in responding correctly.


What is operational complexity?
Hint: These notations describe different kinds of bounds on asymptotic growth rates. Search the web. You really should know what they all mean, if you want to work at GOOGLE.
• An excellent answer will distinguish between Big Oh, Big Omega, and Big Theta notations and describe each in detail, including how they relate to measures of run-time and space trade-offs.
• A good answer will describe Big Oh notation and how it relates to run-time of algorithms and common operations of abstract data types (ADTs).
• A poor answer will include vague or incorrect ideas regarding Big Oh notation and usage.

What is the operational complexity of inserting an element into a linked list? (Asking a clarifying question about singly-linked lists versus doubly-linked lists is unnecessary in this case, but clarifying requirements is always a good thing.)
• An excellent answer will correctly cite O(N) and note the edge cases such as empty lists and the beginning/ending of the list.
• An acceptable answer will correctly cite O(N).
• A poor answer will be incorrect.