Uber
10+ Kanneganti and Associates Interview Questions and Answers
Q1. Minimum Operations to Connect a Graph
You are given a graph with 'N' vertices labeled from 1 to 'N' and 'M' edges. In one operation, you can shift an edge from being between two directly connected vertices to b...read more
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.
Q2. XOR Query Problem Statement
Assume you initially have an empty array called ARR
. You are required to return the updated array after executing Q
number of queries on this array.
There are two types of queries to...read more
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.
Q3. Meeting Rescheduling Challenge
Ninja is tasked with organizing a meeting in an office that starts at time ‘0’ and ends at time ‘LAST’. There are ‘N’ presentations scheduled with given start and end times. The p...read more
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
Q4. Rotting Oranges Problem Statement
You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:
- 0 - representing an empty cell
- 1 - representing a fresh orange...read more
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.
Q5. Game of Stones Problem Statement
Two players, 'Ale' and 'Bob', are playing a game with a pile of stones. Your task is to determine the winner if both play optimally.
Rules of the Game:
1. On each turn, a player...read more
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'.
Q6. Find Indices for Local Minima and Maxima
Given an integer array arr
of size N
, your task is to determine all indices of local minima and local maxima within the array. Return these indices in a 2-D list, where ...read more
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.
Q7. Sort By Kth Bit
Given an array or list ARR
of N
positive integers and an integer K
, your task is to rearrange all elements such that those with the K-th
bit (considering the rightmost bit as '1st' bit) equal to...read more
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}.
Q8. Return Subsets Sum to K Problem Statement
Given an integer array 'ARR' of size 'N' and an integer 'K', return all the subsets of 'ARR' which sum to 'K'.
Explanation:
A subset of an array 'ARR' is a tuple that c...read more
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.
Q9. Total Unique Paths Problem Statement
You are located at point ‘A’, the top-left corner of an M x N matrix, and your target is point ‘B’, the bottom-right corner of the same matrix. Your task is to calculate the...read more
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
Q10. Snake and Ladder Problem Statement
Given a 'Snake and Ladder' board with N rows and N columns, where positions are numbered from 1 to (N*N) starting from the bottom left, alternating direction each row, find th...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
Q11. Changes on graph structure
Changes on graph structure involve adding, removing, or modifying nodes and edges.
Adding a new node to the graph
Removing an existing node from the graph
Modifying the weight of an edge in the graph
More about working at Uber
Interview Process at Kanneganti and Associates
Top Software Developer Intern Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month