Crack the Coding Interview

Given two integer arrays, X[] and Y[] of size m and n, write a program to find intersection of these two arrays. The intersection is a list of common elements present in both arrays. Suppose m > n, all array elements are distinct and intersection elements can be in any order. Note: This is an excellent problem to learn problem solving using various approaches.

There is a staircase of n steps, and you can climb either 1 or 2 steps at a time. Write a program to count and return the number of unique ways to climb the nth stair. The order of steps taken matters. Note: Climbing stairs is an excellent problem to learn dynamic programming approach and application of the Fibonacci series in problem-solving.

Given an array of integers sorted in ascending order, write a program to find the first and last occurrence of a given element. Our goal should be to design an algorithm with O(log n) time complexity. Note: This is an excellent question to learn problem-solving using binary search. Here we need to apply binary search twice to solve this problem.

The head pointer of a linked list is given, write a program to remove the Nth node from the end of the linked list and return its head. In other words, when the node is traversed from the end we have to delete the Nth node from there. Note: This is an excellent problem for beginners to learn problem solving using two pointers in a linked list.

Sorting algorithms like merge sort, quicksort, insertion sort, heap sort, etc., determine sorted order based on comparison operations. We call such algorithms comparison sort. The tightest lower bound on the number of comparisons performed by comparison based sorting is O(nlogn). In this blog, we have used a decision tree model to prove this.

Divide and conquer is a recursive problem solving approach in data structure and algorithms that divides a problem into smaller subproblems, recursively solves subproblems, and combines subproblem solutions to get the solution of the original problem. So, there are three steps of the DC method: divide, conquer and combine.