In this card, we are going to help you understand the general concept of Binary Search.

A tree is a frequently-used data structure to simulate a hierarchical tree structure.

Hash Table is a data structure which organizes data using hash functions in order to support quick insertion and search.

In this card, we are going to introduce another data structure - Linked List.

Similar to the array, the linked list is also a linear data structure. Here is an example:

We may access a random element by index in Array. However, we might want to restrict the processing order in some cases.

Array is one of the fundamental blocks in data structure. Since a string is just formed by an array of characters, they are both similar. Most interview questions fall into this category.

PRIORITY QUEUES

A priority queue, like a dictionary, contains entries that each consist of a key and an associated value. However, whereas a dictionary is used when we want to be able to look up arbitrary keys, a priority queue is used to prioritize entries. Define a total order on the keys (e.g. alphabetical order). You may identify or remove the entry whose key is the lowest (but no other entry). This limitation helps to make priority queues fast. However, an entry with any key may be inserted at any time.

ROOTED TREES

A tree consists of:

• a set of nodes.
• a set of edges that connect pairs of nodes.

A tree has the property that there is exactly one path (no more, no less) between any two nodes of the tree. A path is a sequence of one or more nodes, each consecutive pair being connected by an edge.

The Dynamic Connectivity Problem

Goal: Given a series of pairwise integers connectedness declarations, determine if two integers (or items) are connected. Two operations:

STACKS

A stack is a crippled list. You may manipulate only the item at the top of the stack. The main operations: you may push a new item onto the top of the stack; you may pop the top item off the stack; you may examine the top item of the stack. A stack can grow arbitrarily large.