(BQ) Part 2 book "Cracking the coding interview" has contents: Data structures, concepts and algorithms, knowledge based, additional review problems, threads and lock, recursion and dynamic programming, brain teaser, bit manipulation,. and other contents. | Interview Questions VIII Join us at to download full, compilable Java / Eclipse solutions, discuss problems from this book with other readers, report issues, view this book's errata, post your resume, and seek additional advice. Data Structures Interview Questions and Advice 1 Arrays and Strings H opefully, all readers of this book are familiar with what arrays and strings are, so we won't bore you with such details. Instead, we'll focus on some of the more common techniques and issues with these data structures. Please note that array questions and string questions are often is, a question that this book states using an array may be asked instead as a string question, and vice versa. Hash Tables A hash table is a data structure that maps keys to values for highly efficient lookup. In a very simple implementation of a hash table, the hash table has an underlying array and a hash function. When you want to insert an object and its key, the hash function maps the key to an integer, which indicates the index in the array. The object is then stored at that index. Typically, though, this won't quite work right. In the above implementation, the hash value of all possible keys must be unique, or we might accidentally overwrite data. The array would have to be extremely large—the size of all possible keys—to prevent such "collisions." Instead of making an extremely large array and storing objects at index hash (key), we can make the array much smaller and store objects in a linked list at index hash (key) % get the object with a particular key, we must search the linked list for this key. Alternatively, we can implement the hash table with a binary search tree. We can then guarantee an 0(log n) lookup time, since we can keep the tree balanced. Additionally, we may use less space, since a large array no longer needs to be allocated in the very beginning. Prior to your interview, we recommend .
