• Original address: github.com/kdn251/inte…
• The Nuggets translation Project
• Translator: The king invites moon Bear
• Proofreader: PhxNirvana, square root of three
• This link is used to see if there are any differences between the translation and the English version (if you don’t see readme.md change, that means the translation is up to date).

Interviews

Personal guide to Software Engineering Technical Interviews.

Maintainer – Kevin Naughton Jr.

Other language versions

• English

directory

• Online practice
• Online interview programming
• The data structure
• algorithm
• An operation
• Algorithm complexity analysis
• Video tutorial
• The interview books
• Computer Science and Technology Information
• File structure

Online practice

• LeetCode
• Virtual Judge
• CareerCup
• HackerRank
• CodeFights
• Kattis
• HackerEarth

Online interview programming

• Gainlo
• Refdash

The data structure

Linked List

• A linked list is a linear collection of nodes. Each Node can point to other nodes with Pointers. It is a data structure that contains multiple nodes and can be used to represent sequences.
• Unidirectional linked list: A linked list in which the node points only to the next node and the last node points to null.
• Bidirectional linked list: where each node has two Pointers p and n, such that P points to the previous node and N points to the next node; The n pointer to the last node points to null.
• Circular list: A list in which each node points to the next node and the last node points to the first node.
• Time complexity:
  • Index:O(n)
  • Search:O(n)
  • Insert:O(1)
  • Removed:O(1)

Stack

• A stack is a collection of elements that contains two basic operations: push, which pushes elements onto the stack, and POP, which removes the top element.
• Follow LIFO.
• Time complexity:
• Index:O(n)
• Search:O(n)
• Insert:O(1)
• Removed:O(1)

Queue

• A queue is a collection of elements that contains two basic operations: the enqueue operation is used to insert elements into the queue, and the dequeeu operation is used to remove elements from the queue.
• Follow the first in, first out (FIFO) principle.
• Time complexity:
• Index:O(n)
• Search:O(n)
• Insert:O(1)
• Removed:O(1)

Tree

• Trees are undirected, connected acyclic graphs.

Binary Tree

• A binary tree is a tree data structure in which each node contains at most two nodes: the left and right child nodes.
• Full binary tree: Each node in the tree contains only 0 or 2 nodes.
• Perfect Binary Tree: Each leaf node ina Binary Tree has two child nodes of the same height.
• Complete binary tree: the number of nodes on each layer reaches the maximum except for the last layer; Only a few nodes on the right are missing at the last layer.

Binary Search Tree

• A binary search tree (BST) is a special binary tree in which the value in any node is greater than or equal to the value stored in the left subtree and less than or equal to the value stored in the right subtree.
• Time complexity:
  • Index:O(log(n))
  • Search:O(log(n))
  • Insert:O(log(n))
  • Delete:O(log(n))

Trie

• Dictionary trees, also called cardinality trees or prefix trees, can be used to store dynamic collections of strings or associative arrays of search trees. Nodes in the tree do not store their associated keys directly, but rather where the node is mounted in the tree determines its associated keys. All children of a node have the same prefix, and the root of the entire tree is an empty string.

Fenwick Tree

• Tree array, also known as Binary Indexed Tree, is represented as a Tree, but essentially implemented as an array. Subscripts in an array represent vertices in the tree, and the subscripts of each vertex’s parent or child nodes can be obtained by bitwise operations. Each element in the array contains the sum of the interval values of the predicted values, which are also updated as the whole tree is updated.
• Time complexity:
  • Interval evaluation:O(log(n))
  • Update:O(log(n))

Segment Tree

• A segment tree is a tree data structure used to store intervals or segments. It allows you to quickly find the number of occurrences of a node in several segments.
• Time complexity:
  • Interval query:O(log(n))
  • Update:O(log(n))

Heap

• A heap is a special tree-based data structure that satisfies certain characteristics. The key values of all parent nodes in the heap meet the same sorting conditions. More precisely, heaps can be divided into maximum heap and minimum heap. In the maximum heap, the key value of the parent node is always greater than or equal to the value of the child node, and the maximum value of the whole heap is stored at the root node. In the minimum heap, the parent node’s key value is always less than or equal to that of its children, and the minimum value of the entire heap is stored at the root node.
• Time complexity:
  • Access:O(log(n))
  • Search:O(log(n))
  • Insert:O(log(n))
  • Removed:O(log(n))
  • Remove Max/min:O(1)

Hashing

• Hashes can map data of arbitrary length to data of fixed length. A hash function returns the hash value, and if two different keys get the same hash value, this phenomenon is called a collision.
• Hash Map: A Hash Map is a data structure that establishes relationships between keys and values. A Hash Map can use Hash functions to convert keys into subscripts in buckets or slots to optimize the search speed for target values.
• To solve collision
  • Separate Chaining: In Chaining, each bucket is independent of each other and contains a list of indexes. The time complexity of the search operation is the sum of the bucket search time (fixed time) and the traversal time of the list.
  • Open Addressing: In Open Addressing, when a new value is inserted, it is determined whether the hash bucket corresponding to that value exists, and if so, the next possible location is chosen according to some algorithm until an address is found that is not yet occupied. The open address method also means that the position of an element is not always determined by its hash value.

Graph

• A graph is an abstract data type consisting of a many-to-many relationship between data elements and a set of basic operations.
  • Undirected Graph: An Undirected Graph has a symmetric adjacency matrix, so that if there is an edge from node U to node V, then there is an edge from v to u.
  • Directed Graph: The adjacent matrix of a Directed Graph is asymmetric, i.e. the presence of edges from u to V does not mean that edges from V to u must exist.

algorithm

The sorting

Quick sort

• Stability: no
• Time complexity:
  • Optimal time:O(nlog(n))
  • Worst time:O(n^2)
  • Average time:O(nlog(n))

Merge sort

• Merge sort is a typical divide-and-conquer algorithm, which continuously divides an array into two parts, sorts the left and right subarrays respectively, and then merges the two arrays into a new ordered array.
• Stability:
• Time complexity:
  • Optimal time:O(nlog(n))
  • Worst time:O(nlog(n))
  • Average time:O(nlog(n))

Bucket sort

• Bucket sort divides an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue sorting using bucket sort recursively).
• Time complexity:
  • Optimal time:Ω (n + k)
  • Worst time:O(n^2)
  • Average time:Θ (n + k)

Radix sort

• Radix sort is similar to bucket sort in that it splits an array into a finite number of buckets. However, instead of sorting each bucket individually, it directly merges the buckets.
• Time complexity:
  • Optimal time:Ω (nk)
  • Worst time:O(nk)
  • Average time:Θ (nk)

Graph algorithm

Depth-first search

• Depth-first algorithm is an algorithm that traverses child nodes first rather than backtracking.
• Time complexity:O(|V| + |E|)

Breadth-first search

• Breadth-first search is a graph traversal algorithm that preferentially traverses neighbor nodes rather than child nodes.
• Time complexity:O(|V| + |E|)

A topological sort

• Topological ordering is a linear ordering of nodes of a directed graph. If there is an edge from u to V, the subscript of U is considered to precede v.
• Time complexity:O(|V| + |E|)

Dijkstra algorithm

• Dijkstra algorithm is used to solve single-source shortest path problems in directed graphs.
• Time complexity:O(|V|^2)

Bellman – Ford algorithm

• Bellman-ford algorithm is an algorithm to calculate the shortest path from a single source point to other nodes in a weighted graph.
• Although the algorithm is more complex than Dijkstra’s algorithm, it is suitable for graphs containing negative edges.
• Time complexity:
  • Optimal time:O(|E|)
  • Worst time:O(|V||E|)

Floyd – Warshall algorithm

• Floyd-warshall algorithm can be used to find the shortest path of any node in acyclic weight graph.
• Time complexity:
  • Optimal time:O(|V|^3)
  • Worst time:O(|V|^3)
  • Average time:O(|V|^3)

Prim algorithm

• Prim algorithm is a greedy algorithm for calculating minimum spanning tree in weighted undirected graphs. In other words, Prim algorithm can extract the minimum cost subset of edges connecting all nodes in the graph.
• Time complexity:O(|V|^2)

Kruskal algorithm

• Kruskal algorithm is also an algorithm to calculate the minimum spanning tree of graphs, and the difference with Prim is that graphs do not need to be connected.
• Time complexity:O(|E|log|V|)

An operation

• Bitwise computing is the technique of operating at the bit level. Proper bitwise computing can help us achieve faster computing speed and smaller memory usage.
• Test position K:s & (1 << k)
• Set bit K:s |= (1 << k)
• Position k zero:s &= ~(1 << k)
• Switch the k bit value:s ^= ~(1 << k)
• 2 times:s << n
• Divided by 2:s >> n
• Intersection:s & t
• And set:s | t
• Subtraction:s & ~t
• exchangex = x ^ y ^ (y = x)
• Extract lowest set bit;s & (-s)
• Extract lowest unset bit;~s & (s + 1)
• Exchange value: x ^= y; y ^= x; x ^= y;

Algorithm complexity analysis

O said

• The big O is used to indicate the upper limit of an algorithm, often to describe the worst case.

Small said O

• The little O is used to describe the asymptotic upper bound of an algorithm, but the two are tighter.

Big Ω said

• The large ω is used to describe the asymptotic lower bound of an algorithm.

Small omega said

• Little Omega Notation is used to describe the lower bounds of a particular algorithm, though not necessarily close.

Theta Θ said

• Theta Notation is used to describe the bounds of a deterministic algorithm.

Video tutorial

• Data Structures
• UC Berkeley Data Structures
• MIT Advanced Data Structures
• Algorithms
• MIT Introduction to Algorithms
• MIT Advanced Algorithms

The interview books

• Competitive Programming 3 – Steven Halim & Felix Halim
• Cracking The Coding Interview – Gayle Laakmann McDowell
• Cracking The PM Interview – Gayle Laakmann McDowell & Jackie Bavaro

Computer Science and Technology Information

• Hacker News
• Lobsters

File structure

. ├ ─ ─ Array │ ├ ─ ─ bestTimeToBuyAndSellStock. Java │ ├ ─ ─ findTheCelebrity. Java │ ├ ─ ─ gameOfLife. Java │ ├ ─ ─ IncreasingTripletSubsequence. Java │ ├ ─ ─ insertInterval. Java │ ├ ─ ─ longestConsecutiveSequence. Java │ ├ ─ ─ MaximumProductSubarray. Java │ ├ ─ ─ maximumSubarray. Java │ ├ ─ ─ mergeIntervals. Java │ ├ ─ ─ missingRanges. Java │ ├ ─ ─ ProductOfArrayExceptSelf. Java │ ├ ─ ─ rotateImage. Java │ ├ ─ ─ searchInRotatedSortedArray. Java │ ├ ─ ─ spiralMatrixII. Java │ ├ ─ ─ subsetsII. Java │ ├ ─ ─ subsets. Java │ ├ ─ ─ summaryRanges. Java │ ├ ─ ─ wiggleSort. Java │ └ ─ ─ wordSearch. Java ├ ─ ─ Backtracking │ ├ ─ ─ androidUnlockPatterns. Java │ ├ ─ ─ generalizedAbbreviation. Java │ └ ─ ─ LetterCombinationsOfAPhoneNumber. Java ├ ─ ─ BinarySearch │ ├ ─ ─ closestBinarySearchTreeValue. Java │ ├ ─ ─ FirstBadVersion. Java │ ├ ─ ─ guessNumberHigherOrLower. Java │ ├ ─ ─ pow (x, n). Java │ └ ─ ─ SQRT (x). Java ├ ─ ─ BitManipulation │ ├ ─ ─ binaryWatch. Java │ ├ ─ ─ countingBits. Java │ ├ ─ ─ hammingDistance. Java │ ├ ─ ─ maximumProductOfWordLengths. Java │ ├ ─ ─ Java │ ├─ ├─ Bass Exercises - ├─ Java │ ├─ Java │ ├─ Bass Exercises - BinaryTreeLevelOrderTraversal. Java │ ├ ─ ─ cloneGraph. Java │ ├ ─ ─ pacificAtlanticWaterFlow. Java │ ├ ─ ─ RemoveInvalidParentheses. Java │ ├ ─ ─ shortestDistanceFromAllBuildings. Java │ ├ ─ ─ symmetricTree. Java │ └ ─ ─ Java │ ├─ Heavy Metal │ ├─ Heavy Metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ Heavy metal │ ├─ ConvertSortedArrayToBinarySearchTree. Java │ ├ ─ ─ maximumDepthOfABinaryTree. Java │ ├ ─ ─ numberOfIslands. Java │ ├ ─ ─ PopulatingNextRightPointersInEachNode. Java │ └ ─ ─ sameTree. Java ├ ─ ─ the Design │ └ ─ ─ zigzagIterator. Java ├ ─ ─ DivideAndConquer │ ├ ─ ─ expressionAddOperators. Java │ └ ─ ─ kthLargestElementInAnArray. Java ├ ─ ─ DynamicProgramming │ ├ ─ ─ bombEnemy. Java │ ├── Java │ ├─ Flag School. Java │ ├─ Flag School. Java │ ├─ Flag School HouseRobber. Java │ ├ ─ ─ paintFence. Java │ ├ ─ ─ paintHouseII. Java │ ├ ─ ─ regularExpressionMatching. Java │ ├ ─ ─ SentenceScreenFitting. Java │ ├ ─ ─ uniqueBinarySearchTrees. Java │ └ ─ ─ wordBreak. Java ├ ─ ─ HashTable │ ├ ─ ─ BinaryTreeVerticalOrderTraversal. Java │ ├ ─ ─ findTheDifference. Java │ ├ ─ ─ groupAnagrams. Java │ ├ ─ ─ GroupShiftedStrings. Java │ ├─ islandPerimeter. Java │ ├─ loggerRateLimiter MaximumSizeSubarraySumEqualsK. Java │ ├ ─ ─ minimumWindowSubstring. Java │ ├ ─ ─ sparseMatrixMultiplication. Java │ ├ ─ ─ StrobogrammaticNumber. Java │ ├ ─ ─ twoSum. Java │ └ ─ ─ uniqueWordAbbreviation. Java ├ ─ ─ LinkedList │ ├ ─ ─ addTwoNumbers. Java │ ├ ─ ─ deleteNodeInALinkedList. Java │ ├ ─ ─ mergeKSortedLists. Java │ ├ ─ ─ palindromeLinkedList. Java │ ├ ─ ─ PlusOneLinkedList. Java │ ├ ─ ─ the README. Md │ └ ─ ─ reverseLinkedList. Java ├ ─ ─ the Queue │ └ ─ ─ movingAverageFromDataStream. Java ├ ─ ─ The README. Md ├ ─ ─ Sort │ ├ ─ ─ meetingRoomsII. Java │ └ ─ ─ meetingRooms. Java ├ ─ ─ Stack │ ├ ─ ─ binarySearchTreeIterator. Java │ ├ ─ ─ decodeString. Java │ ├ ─ ─ flattenNestedListIterator. Java │ └ ─ ─ trappingRainWater. Java ├ ─ ─ String │ ├ ─ ─ addBinary. Java │ ├ ─ ─ countAndSay. Java │ ├ ─ ─ decodeWays. Java │ ├ ─ ─ editDistance. Java │ ├ ─ ─ integerToEnglishWords. Java │ ├ ─ ─ LongestPalindrome. Java │ ├ ─ ─ longestSubstringWithAtMostKDistinctCharacters. Java │ ├ ─ ─ minimumWindowSubstring. Java │ ├ ─ ─ MultiplyString. Java │ ├ ─ ─ oneEditDistance. Java │ ├ ─ ─ palindromePermutation. Java │ ├ ─ ─ the README. Md │ ├ ─ ─ ReverseVowelsOfAString. Java │ ├ ─ ─ romanToInteger. Java │ ├ ─ ─ validPalindrome. Java │ └ ─ ─ validParentheses. Java ├ ─ ─ Tree │ ├ ─ ─ binaryTreeMaximumPathSum. Java │ ├ ─ ─ binaryTreePaths. Java │ ├ ─ ─ inorderSuccessorInBST. Java │ ├ ─ ─ InvertBinaryTree. Java │ ├ ─ ─ lowestCommonAncestorOfABinaryTree. Java │ ├ ─ ─ sumOfLeftLeaves. Java │ └ ─ ─ ValidateBinarySearchTree. Java ├ ─ ─ Trie │ ├ ─ ─ addAndSearchWordDataStructureDesign. Java │ ├ ─ ─ implementTrie. Java │ └ ─ ─ ├── Exercises for your muscles, exercises for your muscles, exercises for your muscles, exercises for your muscles MinimumSizeSubarraySum. Java ├ ─ ─ moveZeros. Java ├ ─ ─ removeDuplicatesFromSortedArray. Java ├ ─ ─ reverseString. Java └ ─ ─ sortColors.java 18 directories, 124 filesCopy the code

---

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. Android, iOS, React, front end, back end, product, design, etc. Keep an eye on the Nuggets Translation project for more quality translations.