Problem-Solving Techniques and Patterns

Question 1

Explain the Two Pointers Technique.

Answer 1

Technique: Uses two pointers which could move towards each other or in the same direction to iterate through the data structure (array or linked list) to solve problems.

Applications: Find a pair in an array that sums up to a target value, reverse an array, remove duplicates from a sorted array.

Question 1

What is the Sliding Window Technique?

Answer 1

Concept: The Sliding Window technique involves creating a window that can either grow or shrink in size as it slides over data structures like arrays or strings to capture sub-elements.

Classic Problems: Maximum sum of any contiguous subarray of size ‘k’, smallest subarray with a given sum, longest substring with ‘k’ distinct characters.

Question 2

What is the Top K Elements Pattern?

Answer 2

Concept: This pattern deals with problems that ask to find a set of ‘K’ elements out of a collection that meet certain criteria.

Techniques: Often solved using a Heap or the Quick Select algorithm to efficiently find the required elements.

Example Problems: Find K largest (or smallest) elements in an array, K closest points to the origin.

Question 3

How to create a sliding window in a list?

Answer 3

end - start + 1

Question 4

What is Pigeon-hole principle?

Answer 4

• This principle states that if you have more items (pigeons) than containers (pigeonholes), at least one container must hold more than one item.
• In the scenario, think of the n possible unique numbers as pigeonholes and the n + 1 elements in the array as pigeons. Since there are more elements (pigeons) than possible unique values (pigeonholes), at least one number must be duplicated.
• This principle guarantees the existence of at least one duplicate in the array.

Question 5

How do you reverse a singly linked list in Python?

Answer 5

To reverse a singly linked list, you need to change the direction of the pointers. Iterate through the list and, for each node, switch its next pointer to point to the previous node.

def reverseLinkedList(head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Shorter version:
head.next, head, prev = prev, head.next, head

Question 6

What property does the in-order traversal of a Binary Search Tree (BST) demonstrate, and how does it relate to the elements’ order?

Answer 6

The in-order traversal of a Binary Search Tree (BST) demonstrates the property of producing the elements of the tree in a sorted ascending order. This traversal method visits the left subtree first, then the current node, and finally the right subtree.
Due to the BST’s inherent property where the left child is less than the parent node, and the right child is greater than the parent node, in-order traversal naturally processes the nodes in their increasing value order.
This characteristic makes in-order traversal especially useful for operations that require sorted data, such as searching for a specific value or printing all values in order.