AMTS

Step 1: I first discussed the problem with the interviewer and clarified that the graph could contain negative edge weights, so algorithms like Dijkstra’s would not work correctly.

Step 2: I decided to use the Bellman-Ford algorithm, which works for graphs with negative edge weights and can also detect negative cycles.

Step 3: I initialized the distance of all nodes to infinity and set the distance of the source node to 0.

Step 4: I relaxed all edges V−1 times (where V is the number of vertices). For every edge (u, v), if dist[u] + weight < dist[v], I updated dist[v].

Step 5: After performing V−1 relaxations, I ran one more iteration over all edges to check whether any distance could still be reduced.

Step 6: If any distance was updated in this extra iteration, it meant that a negative-weight cycle existed in the graph.

Step 7: Finally, I returned the shortest distances from the source node to all other nodes or reported the presence of a negative cycle.

Step 1: I first considered solving the problem using recursion by exploring all possible paths from the starting cell.

Step 2: I realized that many subproblems were repeating, which would make the recursive solution inefficient.

Step 3: I then applied Dynamic Programming using a DP table, where dp[i][j] represents the minimum cost to reach cell (i, j).

Step 4: I initialized the first row and first column based on cumulative costs.

Step 5: For each cell, I calculated the minimum cost using:
dp[i][j] = cost[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Step 6: The value at dp[m-1][n-1] gives the final minimum path cost.

Step 1: I first clarified that the graph is a DAG, which allows the use of topological ordering.

Step 2: I performed topological sorting of the graph using DFS or Kahn’s algorithm.

Step 3: I initialized all distances to negative infinity and set the source distance to 0.

Step 4: I processed the nodes in topological order and relaxed all outgoing edges.

Step 5: For each edge (u, v) with weight w, I updated:
dist[v] = max(dist[v], dist[u] + w).

Step 6: After processing all nodes, the distance array contained the longest path from the source to all other nodes.

Step 1: I first clarified that the task is to find all the shortest transformation sequences between the begin word and the end word.

Step 2: I converted the word list into a hash set so that lookups could be done in constant time.

Step 3: I used Breadth-First Search (BFS) starting from the begin word because BFS guarantees the shortest path in an unweighted graph.

Step 4: For each word, I generated all possible words by changing one character at a time and checked whether the new word existed in the dictionary.

Step 5: I maintained a mapping of each word to its previous words to reconstruct the shortest paths later.

Step 6: Once the end word was reached in BFS, I stopped expanding further levels and started reconstructing all paths using backtracking.

Step 7: Finally, I returned all the shortest transformation sequences obtained from the backtracking process.

Step 1: I first understood that land is added dynamically, and after each addition, we must calculate the number of islands.

Step 2: I used the Union-Find (Disjoint Set) data structure to efficiently manage connected components.

Step 3: Initially, the grid contained only water, and the island count was zero.

Step 4: Whenever a new land position was added, I treated it as a new island and increased the island count.

Step 5: I checked its four neighboring cells (up, down, left, right).

Step 6: If any neighbor was already land, I performed a union operation to merge the islands and reduced the island count.

Step 7: After processing the neighbors, I recorded the current island count.

Step 8: Finally, I returned the list containing the island count after each land addition.

Tip 1: Start by identifying functional and non-functional requirements such as scalability, latency, and availability.

Tip 2: Design a high-level architecture including components like load balancers, API servers, databases, caching systems, and message queues.

Tip 3: Discuss optimizations like feed generation strategies (fan-out on write vs. fan-out on read), caching, database sharding, and CDN usage to handle large-scale traffic.