Software Developer Intern

Step 1: I first understood the definition of a subsequence and tried to list a few subsequences manually for a small example array.

Step 2: I realized that for every element in the array, we have two choices—either include the element in the subsequence or exclude it.

Step 3: Based on this observation, I understood that each element contributes two possibilities, which leads to a total of (2^N) possible subsequences for an array of size (N).

Step 4: Finally, I calculated the result using the formula (2^N) and explained the time complexity and reasoning behind it to the interviewer.

Step 1:
First, I understood the problem and thought about checking every possible substring and verifying if it contains repeating characters. However, this brute-force approach would take O(N³) time, which is inefficient.
Step 2:
I then optimized the idea by generating substrings and checking uniqueness using a set, reducing the complexity to O(N²).
Step 3:
To further optimize, I applied the sliding window technique with two pointers. I maintained a window that expands when characters are unique and shrinks when a duplicate character appears.
Step 4:
I used a set / hash map to track characters currently in the window. When a duplicate character is found, I moved the left pointer forward until the duplicate is removed.
Step 5:
During this process, I continuously updated the maximum length of the window, which represents the longest substring without repeating characters.

Step 1: Understand the structure
The matrix can be viewed as a directed graph:

Each cell is a node.

An edge exists if a neighbor has a greater value.

We need to find the longest path in this directed graph.

Step 2: Avoid brute force
If we start DFS from every cell without optimization, the complexity becomes exponential.
So, we apply DP with memoization.

Step 1: I first understood the problem and identified that it is an optimization problem where we need to find the minimum number of coins required to form a given amount.

Step 2: I realized that this problem can be solved using dynamic programming because the solution for a larger amount depends on the solutions of smaller amounts.

Step 3: I created a DP array where dp[i] represents the minimum number of coins required to make amount i.

Step 4: I initialized dp[0] = 0 because zero coins are required to make amount 0, and initialized the rest of the values with a large number.

Step 5: Then, for each amount from 1 to the target amount, I checked all the coins and updated the DP value using dp[i] = min(dp[i], dp[i - coin] + 1) whenever i - coin is valid.

Step 6: Finally, after filling the DP array, I checked dp[amount]. If it was still a large value, it means the amount cannot be formed, so I returned -1; otherwise, I returned dp[amount].

Step 1: I first understood that the grid can be treated like a graph where each land cell is a node and connected lands form a component.
Step 2: I traversed the entire grid, and whenever I encountered a cell with a value of '1', it indicated the start of a new island.
Step 3: From that cell, I performed a DFS/BFS to visit all connected land cells in four directions (up, down, left, right).
Step 4: While visiting those cells, I marked them as visited (or changed them to '0') so they are not counted again.
Step 5: Every time a new unvisited '1' was found, I increased the island count.
Step 6: After traversing the entire grid, the final count represented the total number of islands.

Tip 1: Start by identifying the main components—URL generation service, a database to store mappings (short URL → original URL), and a redirection service. Discuss how a unique short key can be generated using hashing or Base62 encoding.

Tip 2: Explain the database design, such as a table containing fields like short_url_id, original_url, created_at, and expiry. Mention indexing on the short URL for faster lookups.