SDE - 1

This problem can be efficiently solved using Kadane's algorithm.
Approach:
1. Initialize two variables max_so_far and max_ending_here to 0.
2. Traverse the array and for each element, do the following:
Add the element to max_ending_here.
If max_ending_here is negative, set it to 0.
If max_ending_here is greater than max_so_far, update max_so_far.
3. Return max_so_far.

There are multiple ways to solve this problem. I solved it using Union Find. Other approaches can be BFS and DFS.
Approach:
1. Initialize a parent array, which stores the parent of each element in the grid. Initially, all elements are set to -1, which means they have no parent.
2. We then iterate over the grid and union neighboring elements that are part of the same island. If two elements are adjacent and both contain the value '1', we union them together in the parent array.
3. Finally, we count the number of disjoint sets in the parent array. Each set represents an island.

We can solve this problem using a heap-based approach. Since STL was not allowed I had to create heap manually. We can maintain a min-heap of size k, where each element in the heap is the first node of one of the k lists. We can then repeatedly extract the minimum element from the heap, add it to the merged list, and replace it with the next node in the corresponding list.

Approach:

1. Create a min-heap of size k.
2. Push the first node of each linked list into the heap.
3. While the heap is not empty, extract the minimum node from the heap, add it to the merged list, and replace it with the next node in the corresponding list (if it exists).
Repeat step 3 until the heap is empty.

We can solve this problem using dynamic programming. We can define dp[i][j] to be the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

We can then fill in the dp array using the following recurrence relation:

if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Sure! Here's a problem statement, a solution approach with pseudocode, and corner cases to consider for the "Longest Common Subsequence" problem:

Problem Statement
Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example:

vbnet
Copy code
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Solution Approach
We can solve this problem using dynamic programming. We can define dp[i][j] to be the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

We can then fill in the dp array using the following recurrence relation:

less
Copy code
if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

The base case for the dp array is dp[0][j] = dp[i][0] = 0 (i.e., the longest common subsequence of an empty string and any other string is 0).

The answer to the problem is stored in dp[m][n], where m and n are the lengths of text1 and text2, respectively.

Printing LCS:
Traverse the 2D array starting from dp[m][n]. Do following for every cell dp[i][j] 
If characters (in X and Y) corresponding to dp[i][j] are same (Or text1[i-1] == text2[j-1]), then include this character as part of LCS. 
Else compare values of dp[i-1][j] and dp[i][j-1] and go in direction of greater value.

Tip 1: Identify the requirements: The first step is to identify the requirements of the parking lot system from your interviwer. This might include things like the number of parking spots, the types of vehicles that can park, the pricing model, and the payment methods accepted.
Tip 2: Choose appropriate data structures: Choose appropriate data structures to represent the different components of the system. For example, you might use a hash table to represent the parking spots, or a priority queue to manage the payment system.
Tip 3: One can read System Design by Alex Yu for popular system design questions

Apparoach:

1. Modify the input list: We modify the input list nums by adding two 1's at the beginning and end of the list, since balloons outside the range of [i, j] have a value of 1 when they are burst.

2.Define the subproblem: We define the subproblem as finding the maximum coins that can be obtained by bursting balloons in the range [i, j]. The final solution is the maximum coins that can be obtained by bursting balloons in the range [0, n-1].

3. Use dynamic programming: We define a 2D array dp where dp[i][j] represents the maximum coins that can be obtained by bursting balloons in the range [i, j] (inclusive). We fill in the array dp in a bottom-up fashion using the following recurrence relation:

dp[i][j] = max(dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]) for all k in range(i, j+1)

Here, k represents the last balloon to be burst in the range [i, j]. We consider all possible choices of k and take the maximum.

4. Handle edge cases: If the input list is empty, return 0.