Cheat Sheet for Technical Interview

This cheat sheet will help you prepare for a technical interview so you can brush up on key things. In fact, this is the content of the course on computer science without any details.

Basics of data structures

Array

Definition:

• Stores data items based on a sequential index, most often with a zero base.
• It is based on tuples from set theory.
• An array is one of the oldest and most used data structures.

What you need to know:

• The array is optimal for indexing; bad for searching, inserting and deleting (unless you do this at the very end of the array).
• The main variety is linear arrays , or one-dimensional.
  
  • Their size is static, that is, when a linear array is declared, a fixed size is specified.
• Dynamic arrays are similar to linear ones, but they reserve space for additional elements.
  
  • When a dynamic array is populated, its contents are copied into a larger array.
• Two-dimensional arrays have two indices x and y, like grids or nested arrays.

Efficiency ("O" large) :

• Indexing: linear array - O (1), dynamic array - O (1).
• Search: linear array - O (n), dynamic array - O (n).
• Optimized search: linear array - O (log n), dynamic array - O (log n).
• Insertion: linear array - not allowed, dynamic array - O (n).

Linked list

Definition:

• Data is stored in nodes pointing to other nodes.
  
  • A node contains one data item and one link (to another node).
  • A linked list connects nodes with each other using links from one node to another.

What you need to know:

• The linked list is designed to optimize insertion and deletion. Slowly working when indexing and searching.
• A doubly linked list contains nodes that reference previous nodes.
• A ring link list is a simple link list whose tail (last node) refers to the head (first node).
• The stack is usually implemented using linked lists, but can also be created from arrays.
  
  • Stacks are LIFO data structures ( last in, first out ).
  • The head of the linked list underlying the stack is the only place to insert and delete items.
• Queues can also be implemented using a linked list or array.
  
  • Queues are FIFO data structures ( first in, first out ).
  • The queue is a doubly linked list in which elements are removed from the head and added to the tail.

Efficiency ("O" large):

• Indexing: linked list - O (n).
• Search: linked list - O (n).
• Optimized search: linked list - O (n).
• Insert: the linked list is O (1).

Hash table

Definition:

• Data is stored as key-value pairs.
• Hash functions take a key and return output corresponding only to that key.
  
  • This process is called hashing : a one-to-one mapping of input and output data to each other.
  • Hash functions return unique in-memory addresses for the data.

What you need to know:

• Hash functions are designed to optimize search, insert, and delete.
• Hash collisions are situations where, for two different inputs, a function returns the same output.
  
  • This problem is common to all hash functions.
  • Often it is solved by increasing the hash tables to a huge size.
• Hashes are important for associative arrays and indexing databases.

Efficiency ("O" large):

• Indexing: hash tables - O (1).
• Search: hash tables - O (1).
• Insert: hash tables - O (1).

Binary tree

Definition:

• A binary tree is a data structure in which each node has a maximum of two children.
  
  • Child elements are left and right.

What you need to know:

• Trees are designed to optimize the list and sort.
• A degenerate tree is an unbalanced tree. If it is completely one-sided, then it is, in fact, a linked list.
• Trees are relatively easy to implement compared to other data structures.
• Used to create binary search trees .
  
  • The binary tree decides which direction to go to the child node by comparing keys.
  • The key of the left child node is smaller than that of the parent.
  • The key of the right child node is larger than that of the parent.
  • There can be no duplicate nodes.
  • In connection with the foregoing, such a tree is more often used as a data structure than a binary tree.

Efficiency ("O" large):

• Indexing: binary search tree - O (log n).
• Search: binary search tree - O (log n).
• Insert: binary search tree - O (log n).

Search

Search wide

Definition:

• Search in width is an algorithm that searches by tree (or graph), looking through the levels starting from the root.
  
  • The algorithm finds all nodes of the current level, usually moving from left to right.
  • During this process, it registers all the child nodes associated with the nodes at the current level.
  • Upon completion of the search at the current level, the algorithm moves to the leftmost node of the next level.
  • The last rightmost node of the lowest level is analyzed.

What you need to know:

• A wide search is optimal for a search on a tree whose width exceeds the depth.
• While walking on the tree, the algorithm stores information about it in the queue.
  
  • Due to the use of a queue, this search method consumes more memory than a search in depth.
  • The queue uses memory to store pointers.

Efficiency ("O" large):

• Search: search wide - O (| E | + | V |).
• E is the number of edges (faces?).
• V is the number of vertices.

Depth search

Definition:

• Depth search is an algorithm that searches the tree (or graph), first in depth, starting from the root.
  
  • The algorithm goes through the tree, moving between the levels along the left child nodes, until it reaches the bottom.
  • After completing the passage along the branch, the algorithm goes back, looking through the right child nodes of this branch. And, if possible, selects the left-most of the nodes located to the right of the previous route.
  • Having finished viewing the entire branch, the algorithm proceeds to the node located to the right of the root, and again goes along the left child nodes to the very bottom.
  • The last analysis of the rightmost node (located to the right of all its predecessors).

What you need to know:

• The algorithm is optimal for searching the tree, whose depth exceeds the width.
• The algorithm uses a stack.
  
  • Since the stack is a LIFO structure, it does not need to keep track of node pointers; therefore, less memory is consumed than with a wider search.
  • When the algorithm can not go further on the left side, it begins to analyze the stack.

Efficiency ("O" large):

• Search: depth search - O (| E | + | V |).
• E is the number of edges (faces?).
• V is the number of vertices.

Comparison of searches in width and in depth

• Choose a search type according to the size and shape of the tree.
  
  • For wide, small trees use a wide search.
  • For deep, narrow trees, use depth search.

Nuances:

• Since wide search uses queues to store information about nodes and their children, it may take up more memory than is available on your computer. (But you hardly have to worry about it.)
• If you use depth-first search on a very deep tree, the algorithm may go too far down. Read more about it here .
• Search wide - cyclic algorithm.
• Search in depth is a recursive algorithm.

Efficient sorting

Merge sort

Definition:

• Comparing data using a sorting algorithm:
  
  • The entire data set is divided into at least two groups.
  • Pairs of values ​​are compared with each other, the smallest is moved to the left.
  • After sorting within all pairs, the left values ​​of the two left pairs are compared. Thus, a group of four values ​​is created: the smallest - on the left, the largest - on the right.
  • The process is repeated until only one set is left.

What you need to know:

• This is one of the fundamental sorting algorithms.
• The data are divided into as small sets as possible, which are then compared.

Efficiency ("O" large):

• The best sorting option: merge sorting - O (n).
• Medium sorting option: merge sorting - O (n log n).
• The worst sorting option: merge sorting is O (n log n).

Quick sort

Definition:

• A sorting algorithm based on a comparison.
  
  • The entire data set is divided in half by selecting the middle element and moving all those smaller than it to the left.
  • Then the same procedure is performed iteratively with the left side until only two elements remain. As a result, the left side will be sorted.
  • Then all the same is done with the right side.
• This algorithm is preferred to use in computing system architectures.

What you need to know:

• Although “O” is large here it has the same values ​​(and in some cases it is worse) as many other sorting algorithms, but in practice this algorithm often works faster, for example, the same merge sort.
• The data will be consistently divided in half until they are completely sorted.

Efficiency ("O" large):

• Best Sort: Quick Sort - O (n).
• Medium Sort: Fast Sort - O (n log n).
• The worst sorting option: quick sort is O (n ^ 2).

Bubble Sort

Definition:

• A sorting algorithm based on a comparison.
  
  • Iterates from left to right, comparing the values ​​inside each pair and moving the smallest to the left.
  • The process is repeated until no value can be moved.

What you need to know:

• The algorithm is very simple to implement, but the least effective of all three described here.
• Comparing the two values ​​and moving the smallest to the left, the algorithm moves one position to the right.

Efficiency ("O" large):

• Best Sort: Bubble Sort - O (n).
• Medium sorting option: bubble sorting - O (n ^ 2).
• The worst sorting option: bubble sorting is O (n ^ 2).

Comparison of merge sorting and quick sorting algorithms

• Quick sorting in practice is often more efficient.
• Merge sorting immediately divides the data set into the smallest possible groups, and then restores the set, incrementally sorting and enlarging the group.
• The quick sort sequentially divides the set by the mean value until it is sorted recursively.

The main types of algorithms

Recursive algorithms

Definition:

• As follows from the definition, this algorithm calls itself.
  
  • Recursive script - when a conditional statement is used to start recursion.
  • The baseline scenario is when a conditional statement is used to interrupt recursion.

What you need to know:

• Stack level too deep and stack overflow.
  
  • If, during the operation of the recursive algorithm, you encounter one of the above, it means that you have spoiled everything.
  • This means that the baseline script was never launched due to errors, or the problem was so serious that your memory ran out before the recursion was interrupted.
  • Knowing whether you can achieve the baseline scenario is an integral part of the proper use of recursion.
  • Such algorithms are often used when searching in depth.

Iterative Algorithms

Definition:

• An iterative algorithm is an algorithm that is called repeatedly, but a limited number of times. Each call is a separate iteration.
  
  • Often used for incremental traversal of a data set.

What you need to know:

• Usually, iterations are represented as cycles, for , while and until expressions.
• Iteration is a single pass through the data set.
• Such algorithms are often used to process arrays.

Comparing recursiveness and iteration

• It is difficult to distinguish recursiveness from iteration, since both are used to implement each other. But:
  
  • Recursiveness is usually more expressive and easy to implement.
  • Iteration consumes less memory.
• Functional languages tend to use recursiveness (for example, Haskell).
• Imperative languages tend to use iteration (for example, Ruby).
• More information can be obtained from the post on Stack Overflow .

Pseudocode for traversing an array (which is why iteration is used for this)

  |  ----------------------------------|---------------------------------- recursive method (array, n) | iterative method (array) if array[n] is not nil | for n from 0 to size of array print array[n] | print(array[n]) recursive method(array, n+1) | else | exit loop | 

Greedy

Definition:

• Greedy algorithms are called, choosing only the information that meets certain criteria.
• The greedy algorithm contains five main components:
  
  • The candidate set, on the basis of which the solution is created.
  • A selection function that decides which best candidate will be added to the solution.
  • The justification function (feasibility function), which decides whether a candidate can contribute to the decision.
  • Objective function (objective function), which assigns a value to a solution or a partial value.
  • The solution function (solution function), which signals that we have found a complete solution.

What you need to know:

• Greedy algorithms are used to find the optimal solution to this problem.
• They are usually applied to data sets in which only a small portion of the processed information gives the desired result.
• Often greedy algorithms can help in reducing the “O” of a large other algorithm.

Pseudo-code greedy algorithm for finding the biggest difference between two numbers in an array

 greedy algorithm (array) var largest difference = 0 var new difference = find next difference (array[n], array[n+1]) largest difference = new difference if new difference is > largest difference repeat above two steps until all differences have been found return largest difference 

This algorithm does not need to compare with each other all the differences, which saves us a whole iteration.