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

Summation - Using Recursion

You can now easily write the code to add numbers up to a given number.

Head and Tail Recursion

How to teach coding the right way

It would be great if you spend some more time to highlight how you digested the problem and formulated the solution.

It would be good for me to learn about your thinking process so that I can replicate the same pattern or reason about the problem in a similar way.

Apart from that, it would be awesome to go through the process of writing the code. It might help folks like me to understand the flow and how you are solving the problem.

It would be better if you go through problem and write solution step by step with your thought process as you already don't know solution in spite of copy and paste. Otherwise internet has all solution of all problems.

YouTube Comment

I have trouble with implementing and understanding recursive solutions on data structures like Trees (I understand and can implement simple recursion). I tried practicing and solving problems but I feel like I'm missing something.. Any tips specifically for that?

Create a New Post Type in Jekyll

Create a directory called _stories.

Update _config.yml file:

collections:
  stories:
    output: true

Create a story.html file in the _layouts directory.

---
layout: default
---

{{ title }}

{{ content }}

Page

---
layout: story
title: Story Title Goes Here
description: "The story description text goes here"
---

Create a stories.html page in the site root to act as the index page for the stories.

{% for item in site.stories %}
 

{{ item.title }}

  {{ item.description }}
  {{ item.title }}
{% endfor %}

Making a Good Last Impression

What to do in the last 5 minutes, in order to leave a good impression?

You need to remember this is a Two-Way interview. If you're good, I will need to sell you on the company because you could have multiple competing offers. So, I usually have a little spiel prepared to explain why it's so great to work at my company, that I'd love to give. If you can get me to try to sell you on joining the company, my mindset is already being altered towards bringing you in.

Your questions are the last impression that you make. If you have no questions, it indicates that perhaps you're not all that interested in the role.

Q&A doesn't need to last long -- 2 minutes is plenty. Just a quick, Hey before we end this, can I ask you a question?"

- What makes you want to work here?
- What are the primary challenges of your current team?

Share a quick comment about how you've also faced similar challenges. End with "Thanks for sharing, it was a pleasure talking to you and that was an interesting question. I enjoyed tackling it."

It is a great chance to learn about something interesting regarding their stack or internal processes, such as:

- How do they run their CI/CD pipeline?
- How does requirements go from conceptual phase to production?
- How do they deal with critical production issues?
- Do engineers debate and have an active voice on requirements prioritization, and functional requirements?
- How much test coverage do they have for their products?
- How does the company embrace innovation?
- Do the engineers have a chance to research and apply technologies that improve the product?

If you are not just looking for a place to get bills paid, it is really important to match the company's internal processes and goals with your career goals.

Researching a Company

What you should know about the company when researching it?

- Mission Statement
- All their products or at least the product area you're applying to
- What are they working on / new innovation
- What kind of culture they have, so you can mimic it
- What interview questions they ask