Algorithms Bootcamp (算法训练营)

Fundamentals Time Complexity name complexity description example constant \(1\) statement add two numbers logarithmic \(\log n\) divide in half binary search linear \(n\) loop find the max ...

Arrays and Strings The array questions and string questions are often interchangeable. The time complexity to delete or insert an element at index i without resizing is O(n - i). Instead of deleting/inserting an entry (which requires shifting entries), consider overwriting it. When operating on 2D arrays, use parallel logic for rows an...

List An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list. Insert Delete GetRandom O(1) Design a data structure that supports all following...

Stacks & Queues Facts of Stack A stack uses LIFO (last-in first-out) ordering. That is, as in a stack of dinner plates, the most recent item added to the stack is the first item to be removed. It uses the operations: push(item), pop(), peek(), and isEmpty(). Stacks are often useful in certain recursive algorithm. Sometimes you need ...

Graphs & Trees & Heaps A graph is a set of vertices and a collection of edges that each connect a pair of vertices. A tree is an acyclic connected graph. A disjoint set of trees is called a forest. A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree. A spanning fore...

Sorting Let’s go through a number of sorting algorithms first: Bubble Sort | Runtime: O(n^2) average and worst case. Space: O(1). Selection Sort | Runtime: O(n^2) average and worst case. Space: O(1). Insertion Sort | Runtime: between O(n) and O(n^2). Space: O(1). More efficient than above simple sort. To begin, the left...

Hash Tables A hash table is a data structure that maps keys to values for highly efficient lookups, inserts and deletes (average O(1 + n/m) time complexity). This is a simple implementation by using an array of linked lists and a hash code function: First, use a hash function to compute the hash code from the key, which will usually be an ...

Dynamic Programming Dynamic programming (DP) is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems (that is, the repeated calls). You then cache those results for future recursive calls. All recursive algorithms can be implemented iteratively (still use cache), although sometimes the code to do so is m...

Recursion Recursion is a good choice for search, enumeration, and divide-and-conquer. If you are asked to remove recursion from a program, consider mimicking call stack with the stack data structure. Use recursion as alternative to deeply nested iteration loops. For example, recursion is much better when you have an ...

Parallel Computing Concurrency is when two or more tasks can start, run, and complete in overlapping time periods. Parallelism is when tasks literally run at the same time, eg. on a multi-core processor. Parallel computation has become increasingly common. Laptops and desktops come with multiple processors which communicate through shared memo...

Object-Oriented Design A class is an encapsulation of data and methods that operate on that data, which reduces the conceptual burden of writing code, and enable code reuse, through the use of inheritance and polymorphism. A design pattern is a general repeatable solution to a commonly occurring problem, or it is a description...

In an interview, when someone asks a system design question. You should have a conversation in which you demonstrate an ability to think creatively, understand design trade-offs, and attack unfamiliar problems. You should sketch key data structures and algorithms, as well as the technology stack (programming language, libraries, OS, hardware, an...

Database Topics Indexing An index is a data structure, mostly a B-tree which is time efficient (lookup, deletion, insertion) can all be done in logarithmic time, also it’s sorted inside, helpful for range lookup: like find out all of the employees who are less than 40 years old. An index stores the value of indexed column, an...

Prime Numbers A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. Every positive integer can be decomposed into a product of primes that is unique up to ordering. For example: 84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * …

Honors Questions This chapter contains problems that are more difficult to solve. Many of them are commonly asked at interviews, albeit with the expectation that the candidate will not deliver the best solution. Also categorized with other similar questions to give you an overall ideas around this topic.

Collect a list of java code snippets those are tricky and brilliant. Split a paragraph to words // Print words and ignore space and punctuations. StringBuilder word = new StringBuilder(); for (char c : paragraph.toCharArray()) { if (Character.isLetter(c)) { word.append(c); } else if (word.length() > 0) { System.out.println(word); ...