https://www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1/
Binary Search
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}Breadth First Search (BFS) vs Deep First Search (DFS)
There are two search algorithms exist for binary tree: breadth-first search (BFS) and depth-first search (DFS).
The best way to understand them is visually
BFS search nodes level by level, starting from the root node. Then checking its children. Then children for children and so on. Until all nodes are processed or node which satisfies search condition is found.
DFS behave differently. It checks all nodes from leftmost path from the root to the leaf, then jumps up and check right node and so on.
For classic binary trees BFS implemented using Queue data structure (LinkedList implements Queue)
public BinaryNode<T> bfs(Predicate<T> predicate) {
Queue<BinaryNode<T>> queue = new LinkedList<>();
queue.offer(this);
while (!queue.isEmpty()) {
BinaryNode<T> node = queue.poll();
if (predicate.test(node.data)) return node;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return null;
}public BinaryNode<T> dfs(Predicate<T> predicate) {
Stack<BinaryNode<T>> stack = new Stack<>();
stack.push(this);
while (!stack.isEmpty()) {
BinaryNode<T> node = stack.pop();
if (predicate.test(node.data)) return node;
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return null;
}
Source: http://mishadoff.com/blog/dfs-on-binary-tree-array/
Dijkstra’s shortest path algorithm
A* Algorithm: It is an extension of Edsger Dijkstra’s 1959 algorithm. A* achieves better performance by using heuristics to guide its search.
What’s the difference between a Graph and a Tree?
A tree is a special type of graph, i.e., a minimal graph, where there is only one path between two vertices.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (swapped == false)
break;
}
}Insertion Sort
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}K’th Smallest/Largest Element in Unsorted Array
Quick Select: This is an optimization. If QuickSort is used as a sorting algorithm in first step. In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
Given a sorted array and a number x, find the pair in array whose sum is closest to x
1) Initialize a variable diff as infinite (Diff is used to store the
difference between pair and x). We need to find the minimum diff.
2) Initialize two index variables l and r in the given sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = n-1
3) Loop while l < r.
(a) If abs(arr[l] + arr[r] - x) < diff then
update diff and result
(b) Else if(arr[l] + arr[r] < x ) then l++
(c) Else r--Code:
// Prints the pair with sum closest to x
void printClosest(int arr[], int n, int x)
{
int res_l, res_r; // To store indexes of result pair
// Initialize left and right indexes and difference between
// pair sum and x
int l = 0, r = n-1, diff = INT_MAX;
// While there are elements between l and r
while (r > l)
{
// Check if this pair is closer than the closest pair so far
if (abs(arr[l] + arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = abs(arr[l] + arr[r] - x);
}
// If this pair has more sum, move to smaller values.
if (arr[l] + arr[r] > x)
r--;
else // Move to larger values
l++;
}
cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r];
}