Triplet Sum to Zero

Remove Duplicates

Square Sorted Array

Two Pointers

Words Concatenation

Smallest Window containing Substring

String Anagrams

Permutation in a String

Longest Subarray with Ones after Replacement

Longest Substring with Same Letters after Replacement

Number of Encodings

Missing Positive Integer

Serialize and Deserialize Binary Tree

Products Except Self

Two Sum

Non Repeat Substring

Fruits and Baskets

Find the kth Smallest Number

Merge Sort using Recursion Trace

Merge Ordered Lists using Recursion

Longest Palindrome Substring Trace

Generate Subsets of Three Characters

Search in Binary Search Tree

N Queens Problem

Generate Permutations of String

Generate Permutations of String

Tail Recursion Demo

Longest Substring with K Distinct Characters

Smallest Subarray with a Given Sum

Maximum Sum Subarray of Size k

Average Subarrays of k Elements

Anagram

Reverse Sentence

Merge k Sorted Linked List

First Recurring Letter using Recursion

Reverse Linked List

Selection Sort using Recursion

Size of Linked List

Invert Tree using Recursion

Balanced Parenthesis using Recursion

Replace Negative using Recursion

Reverse Array using Recursion

LRU Cache

Remove Tabs from String using Recursion

Remove Adjacent Duplicates in a String using Recursion

Lexicographic Merge of Strings using Recursion

Balanced Tree using Recursion

Clarification Questions

Strings, Arrays and Numbers

• How many elements can be in the array?
• How large can each element be? If it’s a string, how long? If it’s a number, what is
the minimum and maximum value?
• What is in each element? If it’s a number, is it an integer or a floating point? If it’s a string, is it single-byte or multibyte (unicode)?
• If the problem involves finding a subsequence, does “subsequence” mean that the elements must be adjacent, or is there no such requirement?
• Does the array contain unique numbers or can they be repeated (this is sometimes relevant)?

Grids/Mazes

• For problems where some actor (e.g. a robot) is moving in a grid or maze, what moves are allowed? Can the robot move diagonally (hence 8 valid moves), or only horizontally/vertically (hence only 4 valid moves)?
• Are all cells in the grid allowed, or can there be obstacles?
• If the actor is trying to get from cell A to cell B, are cells A and B guaranteed to be
different from each other?
• If the actor is trying to get from cell A to cell B, is it guaranteed that there’s a path between the two cells?
  Copyright © 2014 HiredInTech

Graphs

• How many nodes can the graph have?
• How many edges can the graph have?
• If the edges have weights, what is the range for the weights?
• Can there be loops in the graph? Can there be negative-sum loops in the graph?
• Is the graph directed or undirected?
• Does the graph have multiple edges and/or self-loops?

Return Values

• What should my method return? For example, if I’m trying to find the longest subsequence of increasing numbers in an array, should I return the length, the start index, or both?
• If there are multiple solutions to the problem, which one should be returned?
• If it should return multiple values, do you have any preference on what to return? E.g. should it return an object, a tuple, an array, or pass the output parameters as input references? (This may not be applicable in languages allowing you to return multiple values, e.g. Python)
• What should I do/return if the input is invalid / does not match the constraints? Options may be to do nothing (always assume the input is correct), raise an exception, or return some specific value.
• In problems where you’re supposed to find something (e.g. a number in an array), what should be returned if the element is not present?

Manhattan Paths

Euclid's Algorithm

Bubble Sort using Recursion

Spell Checker

String Size using Recursion

Staircase Climbing using Recursion

Average using Recursion

Square a Number using Recursion

Count Vowels using Recursion

First Occurrence of a Number using Recursion

Generic Decimal to Any Base Conversion using Recursion

Base Conversion - Decimal to Binary using Recursion

Permutation of String using Recursion

Longest Palindrome Substring

Majority Element using Recursion

Ascending Order using Recursion

Quick Select using Recursion

Quick Sort using Recursion

Mergesort using Recursion

Insert Operation in BST using Recursion

Searching in a Binary Search Tree

Stitching Videos Using FFMPEG

1. On Mac 10.13.6 (17G12034). To install ffmpeg:

brew install ffmpeg

2. Create the stitch.txt with files to be stitched. The command needs a slight modification to avoid silent video:

ffmpeg -f concat -safe 0 -i stitch.txt -c:v copy adjacent-duplicates-f.mp4

Tree Depth using Recursion

Tree traversals using Recursion

Binary Search using Recursion

Problem Solving Tools

The three important problem solving tools are:

1. Data Models
2. Data Structures
3. Algorithms

Data models are abstractions used to describe problems. Graphs is an example of a data model.

Use abstractions to formulate solutions to problems. For example, graphs are a way to model data and provide data abstraction to manipulate data effectively to solve problems.

Data structures are programming language constructs used to represent data models. For example, built-in abstractions such as structs and pointers. This can be used to construct data structures to represent complex abstractions such as graphs.

Algorithms are techniques used to obtain solutions by manipulating data as represented by the abstractions of a data model, by data structures or by other means.

Linear Search using Recursion

Fibonacci Sequence

Factorial Using Recursion

Equal Strings using Recursion

Contains Digit using Recursion

Find Largest Number Using Recursion

Print Digits in Reverse using Recursion

Palindrome using Recursion

Reverse String using Recursion

Square Root using Recursion

Guessing Game

Sum Digits using Recursion

Power Function using Recursion

Questions on N Queens Problem

1. Why matrix is inefficient?
2. How is recursive calls made in preorder traversal of the tree?
3. How to generate all of the permutations and all of the subsets of n distinct elements?
4. Print all of the subsets of the elements in a list. Input: [a, b, c]
5. Which part of the code does backtracking?
6. What does the solution space tree look like?
7. Why it is DP? Does it satisfy optimality? Subproblem?
8. When to use backtracking?
9. How call stacks are called with for loop? What is returned?
10. What happens when we backtrack?
11. How to determine the base case?
12. What is the time complexity?
13. What is the space complexity?
14. What data structures to use?
15. How to check if a position is in a diagonal?
16. How to identify a backtracking problem?
17. When do we stop making choices?
18. When does the undo happen? (only when the choice is invalid?)
19. How many wrapper functions do we need? What parameters are needed?
20. What are the subproblems?

Even Number using Recursion

Remainder using Recursion

Array Sum using Recursion

Summation using Recursion

Division using Recursion

Multiplication using Recursion

Addition using Recursion

Mastering Recursion Course Outline for Module 1

## 1. Head and Tail Recursion

- 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

## 2. Addition

- 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

## 3. Multiplication

- 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?

## 4. Division

- 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

## 5. Summation

- 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

## 6. Array Sum

- 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

## 7. Modulo

- 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

## 8. Even

- Without using % operator
- Time and space complexity
 - Iterative Solution
    - 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

## 9. Exponent

- 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

## 10. Sum Digits

- 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

## 11. Guess a Number Game

- Game
- Computational complexity
- Derive the time complexity

## 12. Square Root

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

## 13. Reverse a String

- 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

## 14. Palindrome

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

## 15. Print digits in reverse

- Prerequisites : Head and tail recursion, Add digits
- Size of the problem
- Base case
- Problem decomposition
- Recursion diagram: Reduction and combination
- Recursive solution

## 16. Find largest

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

## 17. Contains Digit

- 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

## 18. Equal Strings

- 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

## 19. Factorial

- 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

## 20 Fibonacci

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

Head and Tail Recursion

Division using Recursion

Outline

• 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

Multiplication using Recursion

Add Numbers Using Recursion