SDE - 1

Use sliding window: Maintain a window over the string that expands and shrinks based on the count of normal characters.

Track normal characters: Keep a count of normal characters in the current window.

Expand the window: Move the right end of the window forward, including one character at a time.

Shrink when needed: If normal characters exceed k, move the left end forward until the window is valid again.

Update maximum length: After each adjustment, check if the current window is the longest valid substring so far.

Continue till end: Repeat expanding and shrinking until the entire string is processed.

Result: The maximum length recorded is the answer.

Understand the problem: Maximize profit by selecting non-overlapping jobs.

Sort jobs by end time to make it easier to find compatible jobs.

Use a DP array where each entry stores maximum profit including that job.

Find last non-conflicting job for each current job using binary search.

Apply recurrence: Maximum profit = max(current job + profit till last non-conflict, profit till previous job).

Fill DP for all jobs to accumulate maximum profit step by step.

Return the last DP value as the maximum achievable profit.

The problem is asking for the minimum cost to connect all cities, which is equivalent to finding a Minimum Spanning Tree (MST) of the graph.

First, we treat each city as a node and each road with a repair cost as a weighted edge.

We sort all edges by their repair cost in ascending order, so we can always pick the cheapest available connection first.

We then use Kruskal’s algorithm (or Prim’s) to add edges one by one, making sure no cycles are formed while connecting the cities.

To check for cycles efficiently, we can use a Union-Find (Disjoint Set) data structure.

We keep adding the smallest cost edge that connects two disconnected components until all cities are connected.

Finally, the sum of the selected edges’ costs gives the minimum total cost to repair roads and connect all cities.

Two-Pointer Approach – Initialize two pointers, one at the start and one at the end of the array.

Calculate Area – At each step, calculate the area as min(height[left], height[right]) * (right - left) and keep track of the maximum area seen so far.

Move Pointers Strategically – Move the pointer pointing to the smaller height, because moving the larger height cannot increase the area.

Repeat Until Pointers Meet – Continue moving pointers and updating the maximum area until the two pointers meet.

Return Result – The maximum area tracked is the answer.

Tip 1: Name each one of ACID properties.
Tip 2: Explain theory.
Tip 3: Give example.

To insert a node in a Binary Search Tree (BST), start at the root and compare the new value with the current node’s value. If it is smaller, move to the left subtree; if larger, move to the right subtree. Repeat this process recursively (or iteratively) until you find a null position where the new node can be inserted. Once inserted, the BST property is maintained: left child < parent < right child.

Level order traversal visits nodes of a tree level by level from top to bottom. We typically use a queue to keep track of nodes at the current level. Start by enqueuing the root, then repeatedly dequeue a node, process it, and enqueue its left and right children if they exist. Continue this process until the queue is empty, which ensures all levels are visited in order.

Start at the root and compare the values of the two target nodes (p and q) with the root.

If both values are smaller than root, move to the left subtree; if both are larger, move to the right subtree.

When one value is on the left and the other is on the right (or one equals the root), the current root is the LCA.

Treat the array freshness[] as a row of baskets and the window of size k as the current selection of baskets.

Use a deque to keep track of indices of baskets that could be the maximum freshness in the current window.

Iterate through each basket from left to right. For each basket, remove indices from the front of the deque if they are out of the current window.

Remove indices from the back of the deque if their freshness is less than the current basket, because they can never be the maximum while this basket is in the window.

Add the current basket’s index to the deque. The basket at the front of the deque is the maximum freshness for the current window.

Continue this process for all baskets, recording the maximum freshness for each window of size k.