Skip to main content

Recursion - Interview Questions - Question 1

Recursion - Interview Questions - Question 1


If needed, you can read the Recursion Basics first.

Please describe the recursion concept to a 5 years old?

Suggested Answers:

One: Russian dolls. If you open it, then there is "the same" but "smaller" one, until you reach to the most inside one.

Two: Thinking about that you are sitting at the last row of a very large class room. The rows of seats have been defined as starting with the one most close to the front chalkboard (1, 2, 3, ...). The question to ask is which row you are sitting now. 

Your can count it from the first row until to your row; but a different way is that: "if the row number of the one before mine is x, then my row is (x + 1)". Then the same procedure can be run until reaching the first row, which can return 1 easily. Then it can be used to return the row numbers for all the rest rows (including yours).

Comments

Post a Comment

Popular posts from this blog

Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...
Post a Comment
Read more

Binary Search - Example

Binary Search - Example Leetcode 35  Search Insert Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Constraints: 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums contains distinct values sorted in ascending order. -10^4 <= target <= 10^4 Analysis: The array is sorted, so we just need to run a routine binary search. Make a guest first, then based on the guessed result, we can adjust the search range. See the code below: class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size(); while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } return left; } }; If you know t...
Post a Comment
Read more