Coding Patterns

Question 1

Sliding Window

Answer 1

Sliding Windows start from the 1st element and keep shifting right by one element and adjust the length of the window according to the problem that you are solving. In some cases, the window size remains constant and in other cases the sizes grows or shrinks.

• The probleminput is a linear data structure such as a linked list, array, or string
• You’reasked to find the longest/shortestsubstring, subarray, or a desired value

Question 2

Two Pointers

Answer 2

Two Pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition. Helps reduce one point n² to n

• It will feature problems where you deal with sorted arrays (or Linked Lists) and need to find a set of elements that fulfill certain constraints
• The set of elements in the array is a pair, a triplet, or even a subarray

Question 3

3. Fast and Slow pointers

Answer 3

Two pointers that move through the array (or sequence/linked list)at different speeds.This approach is quite useful when dealing with cyclic linked lists or arrays.

• The problem will deal with a loop in a linked list or array
• When you need to know the position of a certain element or the overall length of the linked list.

Question 4

4. Merge Intervals

Answer 4

Given two intervals (‘a’ and ‘b’), there will be six different ways the two intervals can relate to each other:

Question 5

5. Reverse Linked List

Answer 5

This pattern reverses one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) will point to the previous node that you have processed. In a lock-step manner, you will reverse the current node by pointing it to the previous before moving on to the next node. Also, you will update the variable “previous” to always point to the previous node that you have processed.

Question 6

5. Reverse Linked List

Answer 6

This pattern reverses one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) will point to the previous node that you have processed. In a lock-step manner, you will reverse the current node by pointing it to the previous before moving on to the next node. Also, you will update the variable “previous” to always point to the previous node that you have processed.

Question 7

In-Order Traversal

Answer 7

In-order traversal means to “visit” (often, print) the left branch, then the current node, and finally, the right branch. When performed on a binary search tree, it visits the nodes in ascending order (hence the name “in-order”).

void inOrderTraversal(TreeNode node) {
if (node!= null) {
inOrderTraversal(node.left);
visit(node);
inOrderTraversal(node.right);
}
}

 4
 / \    2  5    / \   1  3

Question 8

Pre-Order Traversal

Answer 8

Pre-order traversal visits the current node before its child nodes (hence the name “pre-order”).

void inOrderTraversal(TreeNode node) {
if (node!= null) {
visit(node);
inOrderTraversal(node.left);
inOrderTraversal(node.right);
}
}

  1
 / \        2  5    / \   3 4

Question 9

Post-Order Traversal

Answer 9

Post-order traversal visits the current node after its child nodes (hence the name “post order”).

void inOrderTraversal(TreeNode node) {
if (node!= null) {
inOrderTraversal(node.left);
inOrderTraversal(node.right);
visit(node);
}
}

5
/ \
3 4
/ \
1 2