DSA

Question 1

Recursion Laws

Answer 1

1. Must have a base case (to stop recursion)
2. Must change it’s state and move towards the base case (create sub problems)
3. Must call itself recursively

Question 2

Greedy algorithim

Answer 2

Imagine you’re at a buffet. A greedy approach to filling your plate would be to always pick the nearest food item to you until your plate is full, without worrying about whether you’re choosing a balanced meal or if you’ll have space for dessert.

A greedy algorithm, in the world of computer science, works in a similar way. At every step, it makes the most “immediate” or “local” best choice, without considering the broader implications for future steps. It’s like thinking, “What’s the best thing I can do right now?” and doing it, without worrying about the rest of the process.

For the “Find Balanced Strings” problem (i.e. “LRLLRRLR”), The greedy choice here is deciding immediately, for each character, whether to pop or push based on the current state of the stack. We don’t look ahead to see if this choice will create more balanced strings or fewer in the long run. We just act based on what looks best at that moment.

Question 3

Python Heap and Properties

Answer 3

Python has a min-heap

import heapq
nums = [10,5,4,5]
heapq.heapify(nums) # Will still be a list, just ordered as a tree
heapq.heappop(nums) # returns smallest num
heapq.heappush(nums, 5)