Data Structures
A data structure that follows the Last-In-First-Out principle.
What is a stack?
A sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.
What is quick sort?
The general runtime of a nested loop.
What is O(N^2)?
A linear data structure of ordered elements which are not stored at contiguous memory locations
What is a linked list?
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
This data structure is an easy way of solving the above problem.
What is a hashmap?
A data structure that consists of a finite set of vertices (or nodes) and a collection of edges connecting pairs of vertices.
What is a graph?
An algorithm that starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
What is Depth-First-Search?
The fastest average time complexity of any sorting algorithm.
What is O(n log n)?
A type of data structure in which each internal node is smaller than or equal to its children and can be used for priority queues or sorting.
What is a minheap?
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Example 2:
Input: s = "()[]{}"
Output: true
This data structure is an easy way to solve the above problem.
What is a stack?
The two ways of implementing a queue data-structure.
What are arrays and linked lists?
This sorting algorithm has a best-case time complexity of O(n) when the list is nearly sorted or already sorted.
What is Insertion Sort?
The enqueue and dequeue time of a circular-array based queue.
What is O(1)
1
/ \
2 3
\ \
4 7
/ \ /
5 6 8
This is the depth of this binary tree.
What is 3?
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
This commonly used algorithm is one way of solving the above problem.
What is the two-pointer technique?
A tree in which all the nodes follow the principle that the left sub-tree of a node has a key less than or equal to its parent node's key and the right sub-tree of a node has a key greater than or equal to its parent node's key.
What is a binary search tree?
A type of tree traversal that visits the root node of the subtree first, followed by the left subtree, before finally traversing the right subtree.
What is preorder?
The space complexity (memory used) of the merge sort algorithm.
What is O(N)?
The principle that a queue follows for inserting and removing elements.
What is First-In-First-Out?
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
This commonly used algorithm solves the above problem.
What is sliding window?
One of the two methods of addressing collisions (same key) in hash maps.
What is chaining/open-addressing?
An algorithm is used in Dijkstra's shortest path algorithm to find the shortest paths from a source vertex to all other vertices in a graph with non-negative edge by selecting for the vertex with the smallest distance and updating distances to its neighbors.
The worst case time complexity of a hash map that uses chaining.
What is O(N)?
1
/ \
2 3
\ \
4 7
/ \ /
5 6 8
The inorder traversal of this binary tree.
What is 2, 5, 4, 6, 1,3, 8, 7?
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
This algorithmic technique is needed to solve the above problem because it eliminates repetition for a shorter runtime.
What is dynamic programming?