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:

I2luY2x1ZGUgPGlvc3RyZWFtPgoKc3RydWN0IExpc3ROb2RlIHsKaW50IHZhbDsKTGlzdE5vZGUqIG5leHQ7Ckxpc3ROb2RlKGludCB2YWx1ZSkgOiB2YWwodmFsdWUpLCBuZXh0KG51bGxwdHIpIHt9Cn07Cgpib29sIGhhc0N5Y2xlKExpc3ROb2RlKiBoZWFkKSB7CmlmIChoZWFkID09IG51bGxwdHIgfHwgaGVhZC0+bmV4dCA9PSBudWxscHRyKSB7CnJldHVybiBmYWxzZTsKfQoKTGlzdE5vZGUqIHNsb3cgPSBoZWFkOwpMaXN0Tm9kZSogZmFzdCA9IGhlYWQ7Cgp3aGlsZSAoZmFzdCAhPSBudWxscHRyICYmIGZhc3QtPm5leHQgIT0gbnVsbHB0cikgewpzbG93ID0gc2xvdy0+bmV4dDsKZmFzdCA9IGZhc3QtPm5leHQtPm5leHQ7CgppZiAoc2xvdyA9PSBmYXN0KSB7CnJldHVybiB0cnVlOwp9Cn0KCnJldHVybiBmYWxzZTsKfQoKTGlzdE5vZGUqIGZpbmRDeWNsZVN0YXJ0KExpc3ROb2RlKiBoZWFkKSB7CmlmIChoZWFkID09IG51bGxwdHIgfHwgaGVhZC0+bmV4dCA9PSBudWxscHRyKSB7CnJldHVybiBudWxscHRyOwp9CgpMaXN0Tm9kZSogc2xvdyA9IGhlYWQ7Ckxpc3ROb2RlKiBmYXN0ID0gaGVhZDsKYm9vbCBoYXNDeWNsZSA9IGZhbHNlOwoKd2hpbGUgKGZhc3QgIT0gbnVsbHB0ciAmJiBmYXN0LT5uZXh0ICE9IG51bGxwdHIpIHsKc2xvdyA9IHNsb3ctPm5leHQ7CmZhc3QgPSBmYXN0LT5uZXh0LT5uZXh0OwoKaWYgKHNsb3cgPT0gZmFzdCkgewpoYXNDeWNsZSA9IHRydWU7CmJyZWFrOwp9Cn0KCmlmICghaGFzQ3ljbGUpIHsKcmV0dXJuIG51bGxwdHI7Cn0KCnNsb3cgPSBoZWFkOwp3aGlsZSAoc2xvdyAhPSBmYXN0KSB7CnNsb3cgPSBzbG93LT5uZXh0OwpmYXN0ID0gZmFzdC0+bmV4dDsKfQoKcmV0dXJuIHNsb3c7Cn0=

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

The 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 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 function:

I2luY2x1ZGUgPHN0cmluZz4KCmludCBiaW5hcnlUb0RlY2ltYWwoY29uc3Qgc3RkOjpzdHJpbmcmIGJpbmFyeSkgewppbnQgZGVjaW1hbCA9IDA7CmludCBwb3dlciA9IDE7Cgpmb3IgKGludCBpID0gYmluYXJ5Lmxlbmd0aCgpIC0gMTsgaSA+PSAwOyBpLS0pIHsKaWYgKGJpbmFyeVtpXSA9PSAnMScpIHsKZGVjaW1hbCArPSBwb3dlcjsKfQpwb3dlciAqPSAyOwp9CgpyZXR1cm4gZGVjaW1hbDsKfQ==

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

The function initializes two variables, and . keeps track of the calculated decimal value and 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 , starting from the last character () and decrementing 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 by adding . After that, we update by multiplying it by 2 to consider the next bit position.

Finally, we return the calculated 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, , of length . Your task is to find the maximum sum of any contiguous subarray within .

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-

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCmludCBtYXhTdWJhcnJheVN1bShzdGQ6OnZlY3RvcjxpbnQ+JiBudW1zLCBpbnQgbikgewppbnQgbWF4U3VtID0gbnVtc1swXTsKaW50IGN1cnJlbnRTdW0gPSBudW1zWzBdOwoKZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpIHsKY3VycmVudFN1bSA9IHN0ZDo6bWF4KG51bXNbaV0sIGN1cnJlbnRTdW0gKyBudW1zW2ldKTsKbWF4U3VtID0gc3RkOjptYXgobWF4U3VtLCBjdXJyZW50U3VtKTsKfQoKcmV0dXJuIG1heFN1bTsKfQ==

The solution uses Kadane's algorithm to find the maximum sum of any contiguous subarray within the given array . It initializes two variables: and . The variable keeps track of the maximum sum found so far, and the 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 (). This step determines whether it is better to start a new subarray from the current element or to continue the existing subarray. The is updated accordingly.

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

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

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 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 function:

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHV0aWxpdHk+CgpzdGQ6OnBhaXI8aW50LCBzdGQ6OnBhaXI8aW50LCBpbnQ+PiBmaW5kTWF4VmFsdWUoY29uc3Qgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4mIG1hdHJpeCkgewppbnQgbSA9IG1hdHJpeC5zaXplKCk7CmludCBuID0gbWF0cml4WzBdLnNpemUoKTsKCmludCBtYXhWYWwgPSBtYXRyaXhbMF1bMF07CmludCByb3dJbmRleCA9IDA7CmludCBjb2xJbmRleCA9IDA7Cgpmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewpmb3IgKGludCBqID0gMDsgaiA8IG47IGorKykgewppZiAobWF0cml4W2ldW2pdID4gbWF4VmFsKSB7Cm1heFZhbCA9IG1hdHJpeFtpXVtqXTsKcm93SW5kZXggPSBpOwpjb2xJbmRleCA9IGo7Cn0KfQp9CgpyZXR1cm4gc3RkOjptYWtlX3BhaXIobWF4VmFsLCBzdGQ6Om1ha2VfcGFpcihyb3dJbmRleCwgY29sSW5kZXgpKTsKfQ==

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 can contain up to 10^5 non-negative integers.
• Each element in 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 function:

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCmludCBtYXhpbXVtTm9uQWRqYWNlbnRTdW0oY29uc3Qgc3RkOjp2ZWN0b3I8aW50PiYgbnVtcykgewppbnQgbiA9IG51bXMuc2l6ZSgpOwoKaWYgKG4gPT0gMCkgewpyZXR1cm4gMDsKfQoKaW50IGluY2wgPSBudW1zWzBdOwppbnQgZXhjbCA9IDA7Cgpmb3IgKGludCBpID0gMTsgaSA8IG47IGkrKykgewppbnQgdGVtcCA9IHN0ZDo6bWF4KGluY2wsIGV4Y2wpOwppbmNsID0gZXhjbCArIG51bXNbaV07CmV4Y2wgPSB0ZW1wOwp9CgpyZXR1cm4gc3RkOjptYXgoaW5jbCwgZXhjbCk7Cn0=

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 and 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 function:

I2luY2x1ZGUgPHZlY3Rvcj4KCmludCB1bmlxdWVQYXRocyhpbnQgbSwgaW50IG4pIHsKc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gZHAobSwgc3RkOjp2ZWN0b3I8aW50PihuLCAwKSk7CgovLyBCYXNlIGNhc2U6IFRoZXJlIGlzIG9ubHkgb25lIHdheSB0byByZWFjaCBhbnkgY2VsbCBpbiB0aGUgZmlyc3Qgcm93IG9yIGZpcnN0IGNvbHVtbgpmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewpkcFtpXVswXSA9IDE7Cn0KZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspIHsKZHBbMF1bal0gPSAxOwp9CgovLyBGaWxsIHRoZSB0YWJsZSBieSBzdW1taW5nIHRoZSBudW1iZXIgb2Ygd2F5cyBmcm9tIHRoZSBhYm92ZSBjZWxsIGFuZCBsZWZ0IGNlbGwKZm9yIChpbnQgaSA9IDE7IGkgPCBtOyBpKyspIHsKZm9yIChpbnQgaiA9IDE7IGogPCBuOyBqKyspIHsKZHBbaV1bal0gPSBkcFtpLTFdW2pdICsgZHBbaV1bai0xXTsKfQp9CgovLyBSZXR1cm4gdGhlIG51bWJlciBvZiB1bmlxdWUgcGF0aHdheXMgdG8gcmVhY2ggdGhlIGJvdHRvbS1yaWdodCBjZWxsCnJldHVybiBkcFttLTFdW24tMV07Cn0=

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 function:

I2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3N0cmVhbT4KCnN0ZDo6c3RyaW5nIHNpbXBsaWZ5RGlyZWN0b3J5UGF0aChjb25zdCBzdGQ6OnN0cmluZyYgcGF0aCkgewpzdGQ6OnN0YWNrPHN0ZDo6c3RyaW5nPiBkaXJlY3RvcnlTdGFjazsKCi8vIFNwbGl0IHRoZSBwYXRoIGJ5ICcvJwpzdGQ6OnN0cmluZ3N0cmVhbSBzcyhwYXRoKTsKc3RkOjpzdHJpbmcgZGlyZWN0b3J5Owp3aGlsZSAoZ2V0bGluZShzcywgZGlyZWN0b3J5LCAnLycpKSB7CmlmIChkaXJlY3RvcnkuZW1wdHkoKSB8fCBkaXJlY3RvcnkgPT0gIi4iKSB7CmNvbnRpbnVlOyAvLyBJZ25vcmUgZW1wdHkgb3IgY3VycmVudCBkaXJlY3RvcnkgIi4iCn0gZWxzZSBpZiAoZGlyZWN0b3J5ID09ICIuLiIpIHsKaWYgKCFkaXJlY3RvcnlTdGFjay5lbXB0eSgpKSB7CmRpcmVjdG9yeVN0YWNrLnBvcCgpOyAvLyBHbyBiYWNrIHRvIHRoZSBwYXJlbnQgZGlyZWN0b3J5ICIuLiIKfQp9IGVsc2UgewpkaXJlY3RvcnlTdGFjay5wdXNoKGRpcmVjdG9yeSk7IC8vIFB1c2ggdmFsaWQgZGlyZWN0b3J5IG5hbWVzIG9udG8gdGhlIHN0YWNrCn0KfQoKLy8gQ29uc3RydWN0IHRoZSBzaW1wbGlmaWVkIHBhdGgKc3RkOjpzdHJpbmcgc2ltcGxpZmllZFBhdGg7CndoaWxlICghZGlyZWN0b3J5U3RhY2suZW1wdHkoKSkgewpzaW1wbGlmaWVkUGF0aCA9ICIvIiArIGRpcmVjdG9yeVN0YWNrLnRvcCgpICsgc2ltcGxpZmllZFBhdGg7CmRpcmVjdG9yeVN0YWNrLnBvcCgpOwp9CgpyZXR1cm4gc2ltcGxpZmllZFBhdGg=

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

The function first initializes an empty stack 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 of length , where represents the parent node of node in the tree. The root of the tree is denoted by , and its value is set to .

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

The array 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 represents a valid tree by following these steps:

1. It initializes a list to keep track of the number of children each node has.
2. It iterates through the array 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.