40+ Uber Interview Questions (2024) For Engineers With Detailed Answers

Ans. To check if a given linked list contains a cycle, we can use Floyd's cycle-finding algorithm, also known as the "tortoise and hare" algorithm. This algorithm uses two pointers, a slow pointer, and a fast pointer, to traverse the linked list.

Here is the approach to detecting a cycle in a linked list:

1. Initialize two pointers, slow and fast, pointing to the head of the linked list.
2. Move the slow pointer one step at a time and the fast pointer two steps at a time.
3. If the fast pointer encounters a null node, it means there is no cycle in the linked list, so we can return false.
4. If the fast pointer and the slow pointer meet at some point, it indicates the presence of a cycle in the linked list.
5. To find the starting node of the cycle, reset the slow pointer to the head of the linked list and keep the fast pointer at the meeting point.
6. Move both pointers one step at a time until they meet again. The node at which they meet will be the starting node of the cycle.

Here's the C++ implementation:

          #include 

struct ListNode {
int val;
ListNode* next;
ListNode(int value) : val(value), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}

ListNode* slow = head;
ListNode* fast = head;

while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) {
return true;
}
}

return false;
}

ListNode* findCycleStart(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}

ListNode* slow = head;
ListNode* fast = head;
bool hasCycle = false;

while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) {
hasCycle = true;
break;
}
}

if (!hasCycle) {
return nullptr;
}

slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}

return slow;
}
      

The hasCycle function checks whether a given linked list contains a cycle using Floyd's cycle-finding algorithm. It returns true if a cycle is found and false otherwise.

The findCycleStart function finds the starting node of the cycle in a linked list. It first uses Floyd's algorithm to determine if a cycle exists. If a cycle is found, it resets the slow pointer to the head and moves both pointers one step at a time until they meet again at the starting node of the cycle. Finally, it returns the starting node or nullptr if no cycle is present.

You can use these functions to check for a cycle in a linked list and find the starting node if a cycle exists.

Q5. You are given a binary integer represented as a string. Your task is to implement a function that converts the binary integer to its decimal representation.

Note: The solution should convert the binary integer to its decimal representation using the base-2 to base-10 conversion. The binary integer can have leading zeros and can be of any length.

Constraints:

• The binary integer represented as a string will contain only '0' and '1' characters.
• The length of the binary integer will not exceed 10^5.

Ans. To convert a binary integer to its decimal representation, we can iterate over the binary string from left to right and calculate the decimal value using the base-2 to base-10 conversion.

Here's the C++ implementation of the binaryToDecimal function:

          #include 

int binaryToDecimal(const std::string& binary) {
int decimal = 0;
int power = 1;

for (int i = binary.length() - 1; i >= 0; i--) {
if (binary[i] == '1') {
decimal += power;
}
power *= 2;
}

return decimal;
}
      

The binaryToDecimal function takes a string binary as input, representing the binary integer, and returns the decimal representation as an integer.

The function initializes two variables, decimal and power. decimal keeps track of the calculated decimal value and power represents the power of 2 in the base-2 to base-10 conversion.

We iterate over the binary string from right to left using the variable i, starting from the last character (binary.length() - 1) and decrementing i until it reaches 0. Within each iteration, we check if the current character is '1'. If it is, we add the corresponding decimal value to decimal by adding power. After that, we update power by multiplying it by 2 to consider the next bit position.

Finally, we return the calculated decimal value, which represents the decimal representation of the given binary integer.

This approach converts the binary integer to its decimal representation by traversing the binary string and accumulating the decimal value based on the base-2 to base-10 conversion.

Q6.You are given an array of integers, nums, of length n. Your task is to find the maximum sum of any contiguous subarray within nums.

Note: The maximum subarray sum is obtained by selecting a contiguous subarray with the largest sum.

Constraints:

• 1 <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

Ans. Arrays are a very common topic that all engineering candidates must be aware of when appearing for an Uber interview. The solution for this question is-

          #include 
#include 

int maxSubarraySum(std::vector& nums, int n) {
int maxSum = nums[0];
int currentSum = nums[0];

for (int i = 1; i < n; ++i) {
currentSum = std::max(nums[i], currentSum + nums[i]);
maxSum = std::max(maxSum, currentSum);
}

return maxSum;
}
      

The solution uses Kadane's algorithm to find the maximum sum of any contiguous subarray within the given array nums. It initializes two variables: maxSum and currentSum. The maxSum variable keeps track of the maximum sum found so far, and the currentSum variable stores the sum of the current subarray being considered.

The algorithm iterates through the array starting from the second element. For each element, it calculates the maximum between the current element itself and the sum of the current element and the previous subarray sum (currentSum + nums[i]). This step determines whether it is better to start a new subarray from the current element or to continue the existing subarray. The currentSum is updated accordingly.

After updating the currentSum, the algorithm compares it with the current maximum sum (maxSum). If the currentSum is greater, it becomes the new maxSum.

Finally, when the iteration is completed, the function returns the maximum sum found, which represents the maximum sum of any contiguous subarray within nums.

Q7. You are given a 2D array of integers with dimensions m x n. Implement a function that finds the maximum value in the array and its corresponding row and column indices.

Constraints:

• The 2D array matrix will have at least one element.
• The dimensions of the matrix, m and n, will not exceed 100.

Ans. To find the maximum value in a 2D array along with its corresponding row and column indices, we can iterate over the entire array and keep track of the maximum value and its indices.

Here's the C++ implementation of the findMaxValue function:

          #include 
#include 

std::pair<int, std::pair<int, int>> findMaxValue(const std::vector<std::vector>& matrix) {
int m = matrix.size();
int n = matrix[0].size();

int maxVal = matrix[0][0];
int rowIndex = 0;
int colIndex = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] > maxVal) {
maxVal = matrix[i][j];
rowIndex = i;
colIndex = j;
}
}
}

return std::make_pair(maxVal, std::make_pair(rowIndex, colIndex));
}
      

Q8. You are given an array of non-negative integers of size n. Your task is to implement a function to find the maximum possible sum of a subarray with the constraint that no two elements in the subarray are adjacent.

Note: The solution should find the maximum sum of a subarray with the constraint that no two elements in the subarray are adjacent. The subarray can be of any length, including 0.

Constraints:

• The array nums can contain up to 10^5 non-negative integers.
• Each element in nums is a non-negative integer not exceeding 10^4.

Ans. To find the maximum possible sum of a subarray with the constraint that no two elements in the subarray are adjacent, we can use dynamic programming to build a table of subproblem solutions.

Here's the C++ implementation of the maximumNonAdjacentSum function:

          #include 
#include 

int maximumNonAdjacentSum(const std::vector& nums) {
int n = nums.size();

if (n == 0) {
return 0;
}

int incl = nums[0];
int excl = 0;

for (int i = 1; i < n; i++) {
int temp = std::max(incl, excl);
incl = excl + nums[i];
excl = temp;
}

return std::max(incl, excl);
}
      

The maximumNonAdjacentSum function takes a vector of non-negative integers nums as input and returns the maximum possible sum of a subarray with the constraint that no two elements in the subarray are adjacent. The function first checks if the input vector is empty. If it is, it returns 0 since there are no elements to consider. Then, it initializes two variables, incl and excl, to keep track of the maximum sum, including the current element and excluding the current element, respectively. We start by considering the first element of the vector. Next, we iterate over the remaining elements of the vector, updating the incl and excl values accordingly. At each step, we compare the maximum sum obtained by including the current element (current element + previous excl) with the maximum sum obtained by excluding the current element (previous incl or excl). We update incl and excl accordingly. Finally, we return the maximum value between incl and excl, which represents the maximum possible sum of a subarray with the given constraint. The dynamic programming approach allows us to efficiently compute the maximum sum by considering the adjacent element constraint and avoiding redundant calculations.

Q9. You are given a grid of size m x n, where each cell represents a possible position. You can only move either down or right at any point in time. The goal is to find the number of unique pathways from the top-left cell to the bottom-right cell of the grid.

Note: The solution should count the number of unique pathways by considering only the allowed movements (down and right) and finding all possible paths from the starting cell to the destination cell.

Constraints:

• The grid dimensions m and n are positive integers.
• The grid can have a maximum size of 100 x 100.

Ans. To find the number of unique pathways from the top-left cell to the bottom-right cell in a grid, we can use dynamic programming to build a table of subproblem solutions.

Here's the C++ implementation of the uniquePaths function:

          #include 

int uniquePaths(int m, int n) {
std::vector<std::vector> dp(m, std::vector(n, 0));

// Base case: There is only one way to reach any cell in the first row or first column
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}

// Fill the table by summing the number of ways from the above cell and left cell
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}

// Return the number of unique pathways to reach the bottom-right cell
return dp[m-1][n-1];
}
      

Q10.You are given a string representing a file directory path. Your task is to simplify the directory path by removing unnecessary "." and ".." symbols.

Constraints:

• The directory path can have up to 10^5 characters.
• The characters in the path are alphanumeric and can include the following special characters: "", ".", "..".

Ans. To simplify a directory path, we can use a stack data structure to keep track of the valid directory names while iterating through the path. We push valid directory names onto the stack and handle special cases for "." and ".." symbols.

Here's the C++ implementation of the simplifyDirectoryPath function:

          #include 
#include 
#include 

std::string simplifyDirectoryPath(const std::string& path) {
std::stack directoryStack;

// Split the path by '/'
std::stringstream ss(path);
std::string directory;
while (getline(ss, directory, '/')) {
if (directory.empty() || directory == ".") {
continue; // Ignore empty or current directory "."
} else if (directory == "..") {
if (!directoryStack.empty()) {
directoryStack.pop(); // Go back to the parent directory ".."
}
} else {
directoryStack.push(directory); // Push valid directory names onto the stack
}
}

// Construct the simplified path
std::string simplifiedPath;
while (!directoryStack.empty()) {
simplifiedPath = "" + directoryStack.top() + simplifiedPath;
directoryStack.pop();
}

return simplifiedPath
      

The simplifyDirectoryPath function takes a string path as input and returns the simplified directory path as a string.

The function first initializes an empty stack directoryStack to store the valid directory names. It then splits the input path using a stringstream and iterates over the resulting directories.

Within the iteration, it checks for special cases. If the directory is empty or ".", it is ignored. If the directory is ".." and the stack is not empty, it means we need to go back to the parent directory, so the top directory is popped from the stack.

For any other valid directory name, it is pushed onto the stack.

Once the iteration is complete, the function constructs the simplified path by popping the directory names from the stack and concatenating them with a "" separator. Finally, it returns the simplified path or "" if the path is empty.

Q11.You are given an undirected tree represented as an array tree of length n, where tree[i] represents the parent node of node i in the tree. The root of the tree is denoted by tree[0], and its value is set to -1.

Write a function that determines whether the given tree is a valid tree or not. Explanation:

The array tree represents the following tree structure:

0
/ \
1 2
/ \
3 4

The tree is a valid tree because it satisfies the following conditions:

1. There are no cycles or loops in the tree.
2. All nodes except the root have exactly one parent.
3. The tree is connected, meaning that there is a path between any two nodes in the tree.

Note: The tree is a valid tree because it satisfies all the conditions mentioned.

Constraints:

• 1 <= n <= 10^4
• -1 <= tree[i] < n

Ans.

def isValidTree(tree):
n = len(tree)
parent_count = [0] * n

for i in range(n):
parent = tree[i]
if parent != -1:
parent_count[parent] += 1

root_count = 0
for count in parent_count:
if count > 1:
return False
if count == 0:
root_count += 1
if root_count > 1:
return False

return True

The solution checks whether the given array tree represents a valid tree by following these steps:

1. It initializes a list parent_count to keep track of the number of children each node has.
2. It iterates through the array tree and increments the count for each parent encountered.
3. After counting the parents, it checks if there is more than one child for any node (excluding the root). If so, it returns False, as a tree cannot have multiple children for a single parent.
4. It also checks if there is more than one root in the tree. If there is, it returns False, as a tree should have only one root.
5. If no invalid conditions are found, it returns True, indicating that the given tree is valid.