The data structure

Data structures are abstractions of data elements and their relationships in real problems. Commonly used data structures are represented by linear tables, which can be divided into sequential lists and linked lists.

Common data structures

Before studying algorithms, you must understand some common data structure concepts.

  • Stack: A special concatenated form of abstract data type that can be implemented by linked lists or arrays that Push and Pop data through the Top pointer on the stack, characterized by LIFO.

  • Queue: A linear FIFO list, usually implemented with linked lists and arrays, that can only be inserted at the back or rear and deleted at the front.

  • Array: A data structure consisting of a collection of identical elements, stored in a contiguous memory cell, whose storage address can be calculated based on the element’s index.

  • Linked list: A series of nodes, each containing arbitrary instance data and one or two links to the location of the next/previous node.

  • Tree: Data structures that implement abstract data types, such as binary trees and Huffman trees.

  • Graph: represents the relationship between objects, the basic research object of graph theory.

  • Heap: a special tree data structure in computer science. It is also a special binary tree.

  • Hash table: according to the key (key) to directly access memory storage location of a data structure, through calculation of a key value of the function, will be required to query data is mapped to a table in a position to access records, mapping function is called a hash function, storage array of records is called a hash table (hash function and hash conflict is to realize the hash table is the most important two link).

algorithm

An algorithm is an accurate and complete description of a solution to a problem.

Arithmetic operations

To perform various operations, a computer provides a basic set of functional operations:

  1. Arithmetic operations: addition, subtraction, multiplication and division;
  2. Logical operations: and, or, not;
  3. Comparison operation: greater than, less than, equal to, not equal to;
  4. Data transfer: input, output, and assignment.

Important index of algorithm analysis

  1. Time complexity: indicates the time required by the algorithm, that is, the time cost of the algorithm.
  2. Space complexity: A measure of how much secondary storage an algorithm needs to run.

Algorithmic interview questions

After introducing the theory, we can start to practice. Many of the following algorithm topics can be found in the book Sword Finger Offer. This article and the topics involved are for reference only. Some reference codes are provided in some titles of this article. For the complete reference code, please click here.

  • Arithmetic operation

    1. Prime Numbers
      • Natural numbers greater than 1, which can only be divisible by 1 and itself (1 is not considered), the reference implementation of prime number judgment is as follows:
    bool isPrime(unsigned n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false; }}return true;
}
Copy the code
    1. Number of ugly
      • The number of positive integers divisible only by 2, 3 and 5. 1 is the first ugly number. The reference implementation of ugly number determination is as follows:
      bool isUgly(int n) {
    if (n >= 1) {
        while (n % 2 == 0) {
            n = n / 2;
        }
        while (n % 3 == 0) {
            n = n / 3;
        }
        while (n % 5 == 0) {
            n = n / 5;
        }
        if (n == 1) {
            return true; }}return false;
}
Copy the code
    2. Fibonacci numbers
      • Starting with 0 and 1, the following number is the sum of the first two numbers. Reference implementation is as follows:
      long long fibonacciSequence(unsigned n) {

    int result[] = {0, 1};
    if (n < 2) {
        return result[n];
    }
    long long firstValue = 0;
    long long secondValue = 1;
    long long sum = 0;
    for(int i = 2; i < n; I++) {sum += firstValue + secondValue; firstValue = secondValue; secondValue = sum; }return sum;
}
Copy the code

  • The sorting

    1. Bubble sort (average complexity O(n^2) and stable)
      • Determine a minimum value for each trip, the minimum value up, the reference implementation is as follows:
      void bubbleSort(int *a, int len) {
    if (a == nullptr || len < 1) {
        return;
    }
    for (int i = 0; i < len-1; i++) {
        for (int j = 0; j < len-1-i; j++) {
            if(a[j] > a[j+1]) { swap(a[j], a[j+1]); }}}}Copy the code
    2. Selection sort (average complexity O(n^2) and stable)
      • Select a number and compare it one by one with the rest of the numbers. If the number is smaller than this number, the switch is implemented as follows:
      void selectSort(int *a, int len) {
    if (a == nullptr || len < 1) {
        return;
    }
    for (int i = 0; i < len - 1; i++) {
        for (int j = i+1; j < len; j++) {
            if(a[i] > a[j]) { swap(a[i], a[j]); }}}}Copy the code
    3. Insertion sort (average complexity O(n^2) and stable)
      • From the beginning, select a number to compare with the previously sorted number, insert the number into the appropriate position, reference implementation is as follows:
      void insertSort(int *a, int len) {
    if (a == nullptr || len < 1) {
        return;
    }
    for (int i = 0; i < len; i++) {
        for (int j = i+1; j > 0; j--) {
            if(a[j] < a[j-1]) { swap(a[j], a[j-1]); }}}}Copy the code
    4. Quicksort (average complexity O(nlogn) unstable)
      • The core implementation is to select a number as a reference value, put the value greater than the value on the right, the value less than the value on the left, and finally put the value in the left and right split position, the recursive reference implementation is as follows:
      void IVSort::quickSort(int *a, int len) { // step 1
    if (a == nullptr || len < 1) {
        return;
    }
    quickSortImp(a, 0, len-1);
}

void quickSortImp(int *a, int start, int end) { // step 2
    if (start >= end) {
        return;
    }
    int index = quickSortImpCore(a, start, end);
    if (index > start) {
        end = index-1;
        quickSortImp(a, start, end);
    }
    if(index < end) { start = index+1; quickSortImp(a, start, end); Int *a, int start, int end) {step 3 int index = start + 1; // The first value is chosen by defaultfor (int i = index; i <= end; i++) {
        if (a[start] > a[i]) {
            if(index ! = i) { swap(a[index], a[i]); } ++index; } } --index; swap(a[start], a[index]);return index;
}
Copy the code

  • To find the

    1. Dichotomy (split half search, average complexity O(logn))
      • Through the left and right indexes, constantly reduce the search area, applicable to the sorted sequence, the reference implementation is as follows:
      bool binarySearch(int *a, int len, int target) {
    if(a ! = nullptr && len > 0) { int start = 0; int end = len - 1;while (start < end) {
            int mid = (start + end)/2;
            if (a[mid] > target) {
                end = mid-1;
            }else if (a[mid] < target) {
                start = mid + 1;
            }else {
                return true; }}}return false;
}
Copy the code

Due to the large number of codes, the length is too long and inconvenient to read. The reference codes for the following topics are not posted, please click here if necessary.

  • string

    1. String flip
    2. String to number
    3. String substitution

  • An array of

    1. Find the number of repeats
    2. Find a two-dimensional array
    3. Rotate the smallest number in the array
    4. More than half of the numbers appear in the array
    5. The KTH largest number in the array
    6. The number of occurrences of a number in an ordered array
    7. Adjust the odd bit to precede the even bit

  • The list

    1. Deleting a Node
    2. Deleting duplicate Nodes
    3. The penultimate KTH node
    4. Intermediate nodes
    5. Entrance to the node
    6. Reverse a linked list
    7. Merge two linked lists
    8. The first common node of two linked lists

  • The tree

    1. Sequential traversal (recursive and non-recursive)
    2. Middle order traversal (recursive and non-recursive)
    3. Post-order traversal (recursive and non-recursive)
    4. Build a binary tree according to the preorder and middle order
    5. Build a binary tree according to middle order and post order
    6. The next node to be traversed in
    7. Flip the binary tree
    8. The depth of the tree
    9. Binary Search Tree (BST)
    10. Prints the binary tree from top to bottom

conclusion

For the friend that work in the programming, data structure and algorithm is the basis of the programming (here is the web and iOS), is also a lot of big interview questions, familiar with algorithm is not only to cope with the interview, the solution of the algorithm questions will help us improve code execution efficiency and rich the train of thought to solve the problem, are necessary for prevention and treatment of alzheimer’s disease, Hope to take as needed, in addition: if you have a better solution, welcome to study and exchange.

PS: The reference code given in this article is not necessarily the best answer, and the above code is based on the Xcode environment, and provides some simple Test Case, not completely covered, you can write your own Case Test, if you find any Bug, please contact me through Sina “Joelixy_” and GitHub. I will correct it as soon as possible, thank you!