Posts
-
Trie
Because of trie’s implementation is long, we need to use DFS to traverse to find some keys among all keys. It is not often asked in the interview. Here we will only show some basic knowledge.
-
Dynamic Prgoramming
Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.
-
Pattern And Technique
This article is inspired by Smilence Coding Notes
-
Stack And Queue
Stack and Queue are both linear data structure. Both of them can be considered as linked lists with limited reading and writing rights.Therefore, stack and queue’s problems can also be resolved by more powerful list as well.
-
Math Related Problem
Pure math related problems are rarely asked during an interview. That is because an interview is usually testing an interviewee’s problem solving skills. Most math problems are based on some theorems, and those theorems are hard to infer in a short time. Therefore, it is hard to show problem solving skills by resolving a pure math problem. In this article, we will focus on introducing some common used theorems to inspire sparks.
-
Clean Code Practice
Two Ways to Initialize an Array with Default Value
-
Heap
This article is copied from labualdong
-
Linked List
A linked list is composed of multiple
ListNodenodes.ListNodeis an object and it occupies 8 bytes (integervalue4 bytes +ListNodereferencenext4 bytes) in heap memory. Each node is a reference of aListNodeobject. It is similar tonextreference. The node reference saves an address of aListNodeobject in stack memory and occupies 4 bytes as well. -
Prefix Sum
Prefix sum is a simple yet powerful technique that allows to perform fast calculation on the sum of elements in a given range(called contagious segments of array). It often resolves questions relating to array interval.
-
Hashtable
A hash table is a data structure that is used to store key-value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using a good hash function, hashing can work well. Its advantage over other data structures is the average search time for an element is
O(1). -
Quick Sort
Quick Sort is the sort algorithm widely used in Java and many other languages. Its average time complexity is the same as merge sort, but its space complexity is better than merge sort, which is in place. The main thought of partition is often asked in the interview questions.
-
Sort
Main sort algorithms based on 2 number comparison are selection sort, insertion sort, bubble sort, merge sort, and quick sort. Selection sort, insertion sort, and bubble sort’s time complexity are O(n ^ 2). Merge sort, heap sort time complexity are
O(nlogn), and quick sort average time complexity isO(nlogn). The sort algorithm itself is not very often asked during an interview. However, the thought extended from the sort algorithm is widely used. -
Two Pointer
Two-pointer technique is commonly used to solve array, string and linked list problem. It often solves the problem in place. We have classified the two-pointer questions by its templates. The two pointer questions include sliding window, partition(merge sort, quick sort), binary search, fast and slow pointer, and left and right pointer problems. In this article, we will only describe fast and slow pointer, and left and right pointer .
-
Sliding Window
Sliding Window often applies on finding consecutive elements. When we need to find subarray or substring, we shall try sliding window technique first. Its has 2 difficulties, one is how to prove a question can use this technique. The other is how to implement it.
-
Breadth First Search Bfs
BFS is often used to find shortest path on trees or graphs.
-
Depth First Search Dfs
Depth First Search is traversing through a multiple-branch decision tree. The question usually requires all solutions. Since DFS time complexity is O(2^n) or O(n!), tree’s depth can not be very big. DFS is often used to resolve Combination and Permutation problems.
-
Binary Search Tree
Binary Search Tree is one of the commonly used binary tree. Its definition is that all nodes on the left subtree are <= the node, and all nodes on the right subtree are >= the node.
-
Binary Tree
Binary Tree is a data structure extended from linked list data structure. It has the character of inconsecutive data storage , and indirect data access(unlike array’s direct access). It suits to traverse by recursion.
-
Binary Search
Binary Search main thought is decreasing the searching range by half for every loop. Its time complexity is O(logn).
-
Hello World
Hello World! I am a female programmer and a newbie mom. I want to share my experience both as a programmer and as a mom.
subscribe via RSS