Basic Drills

HEAD AND TAIL RECURSION Learning Objectives

How to replace a loop with recursion?
What is head recursion?
What is tail recursion?
Differences between head and tail recursion.
Tail recursion call tree
Head recursion call tree

Before you watch the video, do these:

Write a program to print numbers from 1 to 10 using iteration and recursion
Write a program to print numbers from 10 to 1 using iteration and recursion

Watch Video HEAD RECURSION DEMO Learning Objective

In this video, we will see how the activation records are created and destroyed by pushing and popping values for a given recursive call. The work is done when the recursive calls return. Watch Video TAIL RECURSION DEMO Activation Records in the Stack

You will learn how the activation records are created and destroyed in the stack when the values for a given recursive calls are pushed and popped from the stack. In Tail Recursion, the work is done when the recursive calls are made. Watch Video ADDITION USING RECURSION Learning Objectives

How to find base cases?
Problem decomposition
How to determine the size of the problem?
Recursion diagram as a tool to design recursive programs
What to do in the combine step?
How to find the recursive case?
Mathematical representation of recursive function
How choice of reduction affects performance
Recursive rule for efficient solution
Translating mathematical function into recursive code

Before you watch the video:

Write a program to add two integers using recursion

Watch Video MULTIPLICATION USING RECURSION Learning Objectives

How to derive recurrence relation?
How to reassemble the result of subproblems to get the result for original problem?
Improving the efficiency of the recursive solution
How to determine the number of base cases?

Before you watch the video:

Write a program to multiply two integers using recursion

Watch Video DIVISION USING RECURSION Learning Objectives

Using a counter
How to create a trace table
Concrete case analysis using recursion diagram
Reducing the problem size by more than one unit
Recognize implicit counter in recursive code

Before you watch the video:

Write a program to divide two integers using recursion

Watch Video SUMMATION USING RECURSION Learning Objectives

Expressing the problem mathematically
Determine the size of the problem
Using induction in the recursion diagram
Translating recursion diagram into recursive solution
Comparison of iterative and recursive solutions
Recursion call stack
Time and space complexity
Linear recursion

Before you watch the video:

Write a program to sum from 1 to n using recursion

Watch Video ARRAY SUM USING RECURSION Learning Objectives

How data handled by base case affects recursive case
Choosing what to reduce when you have many options
Trace table showing the computations occurring when recursive calls terminate

Watch Video REMAINDER USING RECURSION Learning Objectives

Deriving equation to solve a problem
Time complexity for equation based implementation
Solving the problem by hand (brute force)
Solving the problem by translating manual steps to iterative code
Recognizing nothing to be done in combine step using recursion diagram
Trivial combine step in recursion leads to tail recursion
Comparison of iterative and recursive solution to see how terminating condition maps to base case, result and reduced value are the same in this case

Watch Video EVEN NUMBER USING RECURSION Learning Objectives

Implement without using % operator
Time and space complexity
Iterative Solution (by using multiply and divide)
Recursion diagram
Recursive solution
Fixing stack overflow error
Reduction step
Trivial combine step
Tail recursion
Two base cases
How many base cases are required?
Time and space complexity
Linear recursion

Watch Video POWER FUNCTION USING RECURSION Learning Objectives

Powers of 2 (warmup) Exponentiation operator Implement without using exponentiation operator Iterative solution Product accumulator Powers of a given base Recursive implementation in linear time Size of the problem Base cases Reduce and combine Allow negative integer exponents Problem decomposition Recursive case Relationship between reduction step and base case Function to express recursive case Multiple recursive cases Powers in logarithmic time Handling multiple cases and its effect on recursion diagram Recursive function with multiple recursive cases Direct translation of mathematical function to code

Watch Video SUM DIGITS USING RECURSION Learning Objectives

Extracting right most digit
Chopping off right most digit
Iterative solution
Accumulator variable
Time and space complexity
Recursion diagram
Reduce and combine
Problem decomposition
Recursive solution
Time and space complexity

Watch Video GUESSING GAME Learning Objectives

Guessing Game
Computational complexity
Derive the time complexity

This time complexity is found in many common algorithms. Understanding how we derive this time complexity when something is repeatedly divided by half is critical to analyze the time complexity of algorithms.

Watch Video SQUARE ROOT USING RECURSION Learning Objectives

Iterative solution
Recursive solution using a wrapper function
Comparison of iterative and recursive function
Using bisection to improve performance

Watch Video REVERSE STRING USING RECURSION Learning Objectives

Recursive solution
Multiple options in reduction step
Combine step requires language builtin function
Performance implications of concatenating strings
Iteration solution using inplace modification of string
Using two pointers
Recursive solution with string inplace modification
Using a wrapper function

Watch Video PALINDROME USING RECURSION Learning Objectives

Problem size
Multiple base cases
Using two pointers
Comparison with reverse a string problem
Problem decomposition and its relationship to base cases
Recursive solution

Watch Video PRINT DIGITS IN REVERSE USING RECURSION Learning Objectives

Size of the problem
Base case
Problem decomposition
Recursion diagram: Reduction and combination
Recursive solution

Prerequisites : Head and tail recursion, Add digits

Watch Video FIND LARGEST NUMBER USING RECURSION Learning Objectives

Problem decomposition
Recursion diagram
Combine step is a custom function
Reducing by half
Recursive function
Two recursive calls
Recursive solution
Comparison of two versions

Watch Video CONTAINS DIGIT USING RECURSION Learning Objectives

Problem Statement
Program interface
Assumption on input
Linear recursive algorithm
Recursion diagram
Tail recursive algorithm
Short circuit evaluation
Relationship between base cases and recursive case
One base case vs Two base cases
Time complexity
Similar problem

Watch Video EQUAL STRINGS USING RECURSION Learning Objectives

Define the Interface (input and output)
Base case
Size of the problem
Linear recursive algorithm
Recursion diagram
Problem decomposition
Boolean function
Recursive solution
Tail recursive algorithm
Short circuit evaluation
Recursion diagram
Comparison of linear and recursive solution

Watch Video FACTORIAL USING RECURSION Learning Objectives

Problem definition
Mathematical representation
Translating mathematical function to recursive code
Recurrence relation
Deferred operation
Subproblem with reduced argument
Minimizing base cases
Iterative solution
Product accumulator
Factorial call trace
Factorial call and return table
Pending multiplication direction
Stack growth
Time and space complexity
Comparison of iterative and tail recursive solution

Watch Video FIBONACCI USING RECURSION Learning Objectives

Problem Statement
Recursive solution
Two base cases
Two recursive calls
Recursive call tree
Redundant calculations
Binary Tree - Level and number of nodes
Binary Tree - Total number of nodes
Binary recursion runtime
Improving performance by dynamic programming
Time and space complexity
Iterative solution
Time and space complexity

Watch Video LINEAR SEARCH Learning Objective

We will work through linear search algorithm and see three different solutions using recursion. You will see a tail recursive implementation. Watch Video BINARY SEARCH USING RECURSION Learning Objectives

Binary Search
Problem decomposition
Base cases
Time complexity of binary search
Walkthrough of the code (method parameters, base cases and recursive cases)

Watch Video TREE TRAVERSALS USING RECURSION Learning Objectives

How to decompose the tree traversal problem?
How to find the base case and the recursive cases?
How to traverse a binary search tree inorder, postorder and preorder?

Watch Video TREE DEPTH USING RECURSION Learning Objectives

How to calculate the depth of a tree?
Base case
Recursive case
Recursive diagram
Recursive solution

Watch Video SEARCHING IN BINARY SEARCH TREE Learning Objectives

Introduction - Covers the basic concepts of a Binary Search Tree
Implement search using recursion
Size of the problem
Base cases
Problem decomposition
Recursive cases
Recursive solution
Time complexity

Watch Video INSERT OPERATION IN BINARY SEARCH TREE USING RECURSION Learning Objectives

Introduction
Interface
Size of the problem
Base case
Code Walkthrough

Watch Video MERGESORT USING RECURSION Learning Objectives

Introduction
Time complexity
Size of the problem
Base case
Recursive case
Recursion diagram
Recursive mergesort code
Problem decomposition diagram
Runtime cost
Size of the problem
Recursive case diagram
Problem decomposition
Recursive merge code
Runtime cost

Watch Video MERGE FUNCTION in MERGESORT Learning Objective

We will trace through the merge function used in Mergesort algorithm to learn how the combine step works in a recursive way. Watch Video REMOVE DUPLICATES Learning Objectives

Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the new length of the array.

Input: [2, 3, 3, 3, 6, 9, 9]

Output: 4

The first four elements after removing the duplicates will be [2, 3, 6, 9]. The time complexity of the algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

The algorithm runs in constant space O(1). Watch Video REMOVE WHITESPACES (ITERATIVE SOLUTION) Learning Objective

Given a null terminated string, remove any white spaces (tabs or spaces). Removing all the white spaces.

The runtime complexity of this solution is linear and the memory complexity of this solution is linear. Watch Video QUICKSORT USING RECURSION Learning Objectives

Introduction
Problem decomposition
Recursive diagram
Recursive quicksort code
Inplace quicksort code
Runtime cost analysis

Watch Video QUICKSELECT USING RECURSION Learning Objectives

Introduction
Size of the problem
Base case
Recursive case
Tail recursive function
Runtime cost

Watch Video ASCENDING ORDER USING RECURSION Learning Objectives

Input
Output
Size of the problem
Base case
Problem decomposition
Recursive solution
Time complexity
Cost

Watch Video MAJORITY ELEMENT USING RECURSION Learning Objectives

Problem statement
Goal
Assumption
Output
Size of the problem
Base cases
Recursive cases
Recursive diagram
Concrete example #2
Reassemble function
Occurrences code
Majority code
Time complexity

Watch Video LONGEST PALINDROME SUBSTRING USING RECURSION Learning Objectives

Introduction
Size of the problem
Base case
Problem decomposition
Recursive solution for palindrome
Problem decomposition diagram
Recursive solution for longest
Runtime

Watch Video PERMUTATION OF STRING USING RECURSION Learning Objectives

Introduction
Recurrence relations for permutations
Problem statement
Permutation possibilities
Subproblems
Problem decomposition
Subproblem
Interface
Base case
General structure
Swap diagram
Recursive solution

Watch Video BASE CONVERSION - DECIMAL TO BINARY USING RECURSION Learning Objectives

Introduction
Size of the problem
Base case
Recursive case
Concrete instance analysis
Mathematical function
Recursive solution : Decimal to binary

Watch Video GENERIC DECIMAL TO BASE CONVERSION USING RECURSION Learning Objectives

Problem : Generic Decimal to Any Base
Example
Reduction diagram
Problem decomposition diagram
Size of the problem
Base case
Recursive case
Problem decomposition
Reassemble solutions
Recursive code: Convert any decimal to a given base b

Watch Video FIRST OCCURRENCE OF A NUMBER USING RECURSION Learning Objective

We will see how to use recursion diagram to break down the problem into recursive case and solve the problem of finding the index of the first occurrence of a number in a given array. Watch Video COUNT VOWELS USING RECURSION Learning Objective

In this video, we will see how to count vowels in a string by using recursion. Watch Video SQUARE A NUMBER USING RECURSION Learning Objective

You will learn how to square a number using recursion. Watch Video AVERAGE USING RECURSION Learning Objective

What do we do when we cannot decompose a problem into smaller self-similar problem? How can we decompose the given problem into different problems and still use recursion to find the solution? Watch Video STAIRCASE CLIMBING USING RECURSION Learning Objective

We will analyze the staircase climbing problem and derive recurrence relation that can be used to write code. We will decompose the problem into smaller problems and systematically analyze to come up with the mathematical function. Watch Video STRING SIZE USING RECURSION Learning Objective

Learn how to compute the length of a string using recursion. Watch Video SPELL CHECKER Learning Objective

This is Google coding question that I got. Recursion is used to find the solution to this problem. Prerequisite: You must have watched the video on computing average. It shows how index is passed as parameter to a method so that we can use it to traverse an array or string. Watch Video BUBBLE SORT USING RECURSION Learning Objective

We will use recursion and learn how bubble sort algorithm works. We will see a code demo that shows what happens at the end of each scan of the array. You will see two pointers, leader-follower pointers in action and how the indexes for them are handled when they reach the end of the list. We compare and swap to bubble up the largest element in each scan of the array. Watch Video EUCLID’S ALGORITHM Learning Objectives

Problem statement
Example
Mathematical Function
Call trace
Recursive code
Efficient version

Watch Video MANHATTAN PATHS USING RECURSION Learning Objectives

Problem statement
Constraint
Size of the problem
Base cases
Problem decomposition
Manhattan path function
Time and space complexity

Watch Video BALANCED TREE USING RECURSION Learning Objective

How do you check if a tree is balanced or not using recursion? You must have already watched the Depth of a Tree video before watching this video. Watch Video LEXICOGRAPHIC MERGE OF STRINGS USING RECURSION Learning Objective

We will work through a problem where the input is two strings that is sorted, we need to merge them into one string in alphabetical order. Watch Video REMOVE ADJACENT DUPLICATES IN A STRING USING RECURSION Learning Objective

We will see how to remove adjacent duplicates in a string using recursion. Watch Video REMOVE TABS FROM STRING USING RECURSION Learning Objective

We will work through the problem of removing tabs and white spaces from a given string using recursion. Watch Video LRU CACHE Learning Objective

Design and implement a LRU cache with get and put with O(1) time complexity. We will solve this problem and look at the code and walkthrough the diagrams to clarify how the cache works in different scenarios. This is a frequently asked question by companies like Amazon and Adobe. Watch Video REVERSE ARRAY USING RECURSION Learning Objective

You will learn how to reverse an array by using recursion. The problem is a good example of how to process the output of the subproblem. It answers the question: Where do we need to append the intermediate result to the output of the subproblem. It also illustrates during the return of the recursive calls, we form the result. Watch Video REPLACE NEGATIVE USING RECURSION Learning Objective

In this video we will see how to replace all negative numbers with 0 by using recursion. Watch Video BALANCED PARENTHESIS USING RECURSION Learning Objective

Write a recursive program to check if a given array has parenthesis that matches opening and closing brackets. Watch Video INVERT TREE USING RECURSION Learning Objective

We will see how easy it is to invert a tree using recursion. In less than 4 minutes you will learn how to invert a tree and never forget it for the rest of. your life. Watch Video SIZE OF LINKED LIST USING RECURSION Learning Objective

How to calculate size of linked list by using iteration and recursion. Why you need to minimize the number of base cases in recursion? Watch Video SELECTION SORT USING RECURSION Learning Objective

In this video, we will see how to implement selection sort algorithm to sort a given array in ascending order using recursion. Watch Video REVERSE LINKED LIST USING RECURSION Learning Objective

We will see how to reverse a linked list using recursion. The key idea needed to solve this problem is understanding about the returning phase of the recursive calls. This is the power of recursion. It is as if you are able to go back in time using a time machine. The state of those variables are preserved and you can reverse the links.

Iteration does not have the returning phase and does not have that power. This is the key to solving other problems such as reversing a stack without using any additional data structures or difficult problems like N Queens and Generating Permutations. Watch Video FIRST RECURRING LETTER USING RECURSION Learning Objective

We will see how to solve the first recurring letter in a string problem using Set data structure and recursion. Watch Video MERGE K SORTED LINKED LIST Learning Practice

We will see how to merge k sorted linked list using recursion. Watch Video REVERSE SENTENCE Learning Objective

Reverse words in a sentence. Time complexity is linear and space complexity is constant in this solution. We will modify the string in place. Watch Video ANAGRAM Learning Objective

We will find a solution for anagram problem that is linear in time complexity and constant in space. Watch Video AVERAGE SUBARRAYS OF K ELEMENTS Learning Objective

This video will show how to use sliding windows to solve calculating average of subarrays of size k using sliding window. Watch Video MAXIMUM SUM SUBARRAY OF SIZE K Learning Objective

Given an array of positive numbers and a positive number k, find the maximum sum of any contiguous subarray of size k. Watch Video SMALLEST SUBARRAY WITH A GIVEN SUM Learning Objective

Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists. Watch Video LONGEST SUBSTRING WITH K DISTINCT CHARACTERS Learning Objective

Given a string, find the length of the longest substring in it with no more than K distinct characters. Time complexity is linear and space complexity is linear. Watch Video FRUITS AND BASKETS Learning Objective

Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.

You can start with any tree, but once you have started you can’t skip a tree. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

Write a function to return the maximum number of fruits in both the baskets. Watch Video INSERT INTERVAL Learning Objective

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]

Output: [[1,3], [4,7], [8,12]]

After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7]. Watch Video INTERVALS INTERSECTION Learning Objective

Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.

Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]

Output: [2, 3], [5, 6], [7, 7]

The output list contains the common intervals between the two lists. The time complexity is linear and space complexity is constant. Watch Video FIND THE KTH SMALLEST NUMBER Learning Objective

We will use heap to efficiently find the kth smallest number in a list. We will construct a heap and store the kth smallest number in the root to access the result at the end of the procedure. Watch Video ENHANCED LINEAR SEARCH LINKED LIST Learning Objective

We will implement a linear search in a linked list and enhance by moving the node we find to the beginning of the list to improve the search performance. This is the basics of building an LRU cache. Watch Video LINKED LIST BASICS Learning Objective

We will see how to create a linked list, insert nodes and traverse the linked list. Watch Video LONGEST PALINDROME SUBSTRING TRACE Learning Objective

In this video we will trace all the recursive calls visually and learn how the longest palindrome substring solution works. You will gain a deeper understanding of recursion. Watch Video MAXIMUM ELEMENT IN A LINKEDLIST Learning Objective

We will see how to compute the maximum value in a linked list two different ways by using iteration and recursion. Watch Video SUM OF ALL ELEMENTS IN A LINKEDLIST Learning Objective

We will see iterative and recursive way to add all elements in a linked list. Watch Video MERGE INTERVALS Learning Objective

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Intervals : [[1,4], [2,5], [7,9]]

Output : [[1,5], [7,9]]

Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5]. Watch Video MERGE SORT PERFORMANCE Learning Objective

We will derive the equation for mergesort performance by analyzing the call trace. Watch Video MERGE SORT USING RECURSION TRACE Learning Objective

We will trace the recursive calls of mergesort and demystify recursion so that you understand the magic behind recursion. We will see how the returning phase seems like magic. This is the power of recursion. Iteration does not have an equivalent phase to returning phase of recursion. Watch Video MOVE ZEROES Learning Objective

You must know the right programming construct to use to solve a problem. In this video we will see fast and slow pointers which can be categorized under Two Pointers. If don’t know the right tool to apply when solving a problem, you will have lot of difficulty implementing the solution in your language of choice.

Use Fast Slow Pointers with swap operation results in straightforward code that is correct and performs well. Watch Video NON REPEAT SUBSTRING Learning Objective

Given a string, find the length of the longest substring which has no repeating characters.

We will apply the Sliding Window pattern. We will use dynamic sliding window strategy as seen in Longest Substring with K Distinct Characters video. HashMap is used to remember the last index of each character we have processed. Whenever we get a repeating character we will shrink our sliding window to ensure that we always have distinct characters in the sliding window. Watch Video NUMBER OF ENCODINGS Learning Objective

This problem was asked by Facebook. Given the mapping a = 1, b = 2, … z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message ‘111’ would give 3, since it could be decoded as ‘aaa’, ‘ka’, and ‘ak’. You can assume that the messages are decodable. For example, ‘001’ is not allowed. Watch Video TWO POINTERS Learning Objective

In problems where we deal with sorted arrays (or LinkedLists) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray.

The time complexity of the algorithm will be O(N). Watch Video WORD BREAK Learning Objective

Given a dictionary of words and a large input string, find out whether the input string can be completely segmented into the words of a given dictionary.

The runtime complexity of this solution is exponential, O(2^n), if we use only recursion. With memoization, the runtime complexity of this solution can be improved to quadratic. Watch Video