10+ Uber Software Developer Intern Interview Questions and Answers

Determine the minimum number of operations to connect a graph by shifting edges between disconnected vertices.

• Use a disjoint set union (DSU) data structure to keep track of connected components.

• Count the number of connected components in the graph.

• The minimum number of operations required is equal to the number of connected components minus 1.

Implement a function to update an array based on XOR queries.

• Create an empty array to store the elements.

• Iterate through each query and update the array accordingly.

• Use bitwise XOR operation to update the elements.

• Ensure to handle both types of queries - insert and XOR operation.

Find the minimum time required to rot all fresh oranges in a grid.

• Use Breadth First Search (BFS) to simulate the rotting process of oranges.

• Track the time taken to rot all oranges and return -1 if any fresh oranges remain.

• Handle edge cases such as empty grid, no fresh oranges, or no rotten oranges.

• Update the status of adjacent fresh oranges to rotten oranges in each iteration.

Reschedule at most K presentations to maximize gap without overlap.

• Iterate through presentations and calculate the gaps between them

• Sort presentations by end time and reschedule K presentations to maximize gap

• Return the longest gap achieved

Determining the winner of a game where two players take turns to remove stones from a pile based on certain rules.

• Implement a recursive function to simulate the game where each player makes the optimal move.

• Check if the current player can take any stones, if not, the other player wins.

• Return 'Ale' if 'Ale' wins, otherwise return 'Bob'.

Find indices of local minima and maxima in an integer array.

• Iterate through the array and compare each element with its neighbors to find local minima and maxima.

• Consider corner elements separately by comparing with only one neighbor.

• Return the indices of local minima and maxima in a 2-D list.

Rearrange elements in an array based on the K-th bit being 0 or 1.

• Iterate through the array and separate elements based on the K-th bit being 0 or 1.

• Maintain the relative order of elements within each group.

• Combine the two groups to get the final rearranged array.

• Time complexity can be optimized to linear time by using bitwise operations.

• Example: For ARR = {1, 2, 3, 4} and K = 1, output should be {2, 4, 1, 3}.

Given an array and an integer, return all subsets that sum to the given integer.

• Use backtracking to generate all possible subsets of the array.

• Keep track of the current subset and its sum while backtracking.

• If the sum of the subset equals the target sum, add it to the result.

• Recursively explore both including and excluding the current element in the subset.

• Sort the elements in each subset to ensure increasing order of index.

Calculate total unique paths from top-left to bottom-right corner of a matrix by moving only right or down.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell.

• Initialize the first row and first column with 1 as there is only one way to reach them.

• For each cell, the number of unique paths is the sum of paths from the cell above and the cell to the left.

• Return the value in the bottom-right cell as the tot...read more

Find the minimum number of dice throws required to reach the last cell on a 'Snake and Ladder' board.

• Use Breadth First Search (BFS) algorithm to find the shortest path on the board.

• Create a mapping of each cell to its corresponding row and column on the board.

• Consider the presence of snakes and ladders while calculating the next possible moves.

• Handle the case where the last cell is unreachable by returning -1.

• Optimize the algorithm by using a queue to keep track of the cells ...read more