## Uber Interview Questions

- 0of 0 votes
In a Binary maze with 0 and 1, 0 is the valid cell to which we can travel and 1 means that the cell is blocked. Given source and destination. We have to find-

1. IF path exists, if yes, find shortest path.

2. If we are given a chance to toggle single cell from 1 to 0 , which cell you will toggle so that you will surely get the shortest path.

- 0of 0 votes
Design a system like HackerRank/Codechef.

- 0of 0 votes
Design a concurrent hashmap.

Please point me to the link if this has been discussed before.

They wanted design with code snippet of the classes.

- 0of 0 votes
Given lat long of cabs in a city(lat long keeps changing)

Implement a function getNearby(lat1,long1) which returns all cabs in a circle of radius R from lat1,long1.

Which datastructure will u use?

FollowUp qs: Hows it implemented using a database like MySQl or Postgres.

- 0of 0 votes
You have two arrays of strings, words and parts. Return an array that contains the strings from words, modified so that any occurrences of the substrings from parts are surrounded by square brackets [], following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still more than one such part, then choose the one that appears first in the string.

Example

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"], the output should be

findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

While "Watermelon" contains three substrings from the parts array, "a", "mel", and "lon", "mel" is the longest substring that appears first in the string.

- 2of 2 votes
Convert a string with digits into a literal representation of the number like: 1001 to one thousand one

- 0of 0 votes
Find the Kth most Frequent Number in an Array.

Example:`arr[] = {1, 2, 3, 2, 1, 2, 2, 2, 3} k = 2 Result: 3 Because '3' is the second most occurring element.`

Follow up: What if the array is extremely large?

- 0of 0 votes
`A text file contains {candidateID,voterID} details of an ongoing voting. Read this file in real time and report top 5 candidates. Also report a fraud if a Voter tries to vote twice or try to vote more then one candidate. Assume that the database is offline.`

- 0of 0 votes
Design a data structure that supports 3 below operations

1. GetNextId() : It returns the auto incremental next id. i.e 1 then 2 then 3 then 4

2. Acknolwdge(int i) : receives the acknowledgement of the id that was sent by GetNextId

3. GetIdLevel() : It returns the minimum id that has not been acknowledged

- 0of 0 votes
There is a primary machine and a secondary(backup machine). Write a program to sync files from primary to backup machine

- 1of 1 vote
Given two list of unsorted intervals V1 and V2 write 2 functions 'OR ' and 'And' to return a new list

OR Function (union of list ): Input V1 = (2,4) (6,8) (1,3) V2 = (7,9) (2,5)

output = (1,5) (6,9)

And function : This will be intersection function and will return intersection of the lists

- 2of 2 votes
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4].

Return its length: 4.

Your algorithm should run in O(n) complexity.

- 1of 1 vote
Generate all possible matched parenthesis, given n left parenthesis and right parenthesis needs to be matched.

- 0of 0 votes
Create a data structure that stores integers, let then add, delete. It also should be be able to return the minimum diff value of the current integers.

That is,

min_diff = minimum ( | x_i - x_j | )

Example:

-1,3,4,10,11,11

min_diff = 0

-1,3,4,10,11,14

min_diff = 1

- -7of 7 votes
aa

- 2of 2 votes
4/5 Round at Uber

Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.

For a 2X2 matrix with

/\

\/

The matrix split into 5 pieces - the diamond in middle and the four corners. Return 5 as the answer.

5/5 Round at Uber

Design Excel.

- 1of 1 vote
2/5 Round at Uber

Bar raiser - Behavioral questions. Coding: Find if a set of meetings overlap. Meeting has a starttime and an endtime with accuracy to minute. All meetings take place in the same day. Do this in O(n) time.

3/5 Round at Uber

Coding: Subset sum. Follow-up: Optimize the solution.

- 0of 0 votes
1/5 Round at Uber

Manager : Behavioral questions. Basic system design concepts. Publish/subscribe model. Discussion on Uber architecture.

- 2of 2 votes
Uber

1. Mirror Binary Tree

2. String pattern matching

The matching should cover the entire input string (not partial).

The function prototype should be:

bool isMatch(String str, String pattern)

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa","a{1,3}") → true

isMatch("aaa","a{1,3}") → false

isMatch("ab","a{1,3}b{1,3}") → true

isMatch("abc","a{1,3}b{1,3}c") → true

isMatch("abbc","a{1,3}b{1,2}c") → false

isMatch("acbac","a{1,3}b{1,3}c") → false

isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true

In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} -> a occurs 1 or 2 times.

- 0of 0 votes
How to do estimate driver arrival and drop off time?

- 0of 0 votes
How to evaluate that the estimated time (for when the driver arrives and the drop off time) is a good estimate?

- 0of 0 votes
Design classes to represent the following problem and solve the questions 1,2,3

A user might have some outstanding auto loan amount and you have 3 types of offers: personal loan, credit card and auto loan offers. You need to provide the user

with the following details:

1. Send user all the offers to the user

2. Send user all eligible offers (where minCreditScore < userCreditScore < maxCreditScore)

3. Send user all offers which satisfied 2) and where the (userOutStandingLoanAmount < maxOfferedAutoLoanAmount)

personal-loan = [{

"personal-loan": {

"id": 1,

"provider": "Avant",

"term": 36,

"minimumCreditScore": 300,

"maximumCreditScore": 700,

"maximumAmount": 10000

}

}, {

"personal-loan": {

"id": 2,

"provider": "Prosper",

"term": 24,

"minimumCreditScore": 600,

"maximumCreditScore": 700,

"maximumAmount": 5000

}

}]

credit-card=[{

"credit-card": {

"id": 2,

"provider": "CapitalOne",

"minimumCreditScore": 600,

"maximumCreditScore": 700

}

}, {

"credit-card": {

"id": 3,

"provider": "Chase",

"minimumCreditScore": 300,

"maximumCreditScore": 900

}

}]

autoloan = [{

"auto-loan": {

"id": 1,

"provider": "CapitalOne",

"term": 36,

"minimumCreditScore": 300,

"maximumCreditScore": 700,

"maximumAmount": 10000

}

}, {

"auto-loan": {

"id": 2,

"provider": "Blue Harbor",

"term": 24,

"minimumCreditScore": 600,

"maximumCreditScore": 700,

"maximumAmount": 5000

}

}]

- 1of 1 vote
Consider that the driver with one trip want to pick up some peoples in different locations like this:

String[] locations ={

"person1, person2, person3, person4, person5",

" person6, person7, person8, person9",

"person10, person11, person12",

"person13, person14, person15",}

in each location there are different choice, so write a code present all possible way to pick up people in the different locations. you can use every data structure needs.

- 3of 3 votes
Given a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.

e.g.

a relies on b

b relies on c

then a valid sequence is [c, b, a]

- 0of 0 votes
Given input which is vector of log entries of some online system each entry is something like (user_name, login_time, logout_time), come up with an algorithm with outputs number of users logged in the system at each time slot in the input, output should contain only the time slot which are in the input. For the example given below output should contain timeslots

[(1.2, 1), (3.1, 2), (4.5, 1), (6.7, 0), (8.9, 1), (10.3,0)]

/*

[

("Jane", 1.2, 4.5),

("Jin", 3.1, 6.7),

("June", 8.9, 10.3)

]

=>

[(1.2, 1), (3.1, 2), (4.5, 1), (6.7, 0), (8.9, 1), (10.3, 0)]

*/

- 1of 1 vote
Each test file starts with an integer ‘t’ - the number of testcases.

In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].

Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’

Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.

Duplicate strings are not allowed. The final expressions to be counted have to be distinct

As the answer may be large, please output it modulo 1000000007 (10^9+7)

Output one integer per line corresponding to each testcase.

Constraints :

1 <= t <= 20

1 <= n <= 100

0 <= Number of ‘*’ in the input string <= min(n,10)

Sample Input:

2

(*(*)*)

*(*(**)*

Sample Output

5

9

Explanation

The five possible valid solutions are for the first input are :

((()))

()(())

()()()

(())()

(())

The nine possible valid solutions are for the second input are :

(((())))

(()(()))

(()()())

(()())

((()))

()(())

()()()

()()

(())

- 0of 0 votes
Given a string s, return all the palindromic permutations ( without duplicates), of it. Return an empty array if no palindromic combinations can be formed.

- 0of 0 votes
Given a string, determine if a permutation of a string can form a palindrome.

- 3of 3 votes
Given an input string and ordering string, need to return true if the ordering string is present in Input string.

input = "hello world!"

ordering = "hlo!"

result = FALSE (all Ls are not before all Os)

input = "hello world!"

ordering = "!od"

result = FALSE (the input has '!' coming after 'o' and after 'd', but the pattern needs it to come before 'o' and 'd')

input = "hello world!"

ordering = "he!"

result = TRUE

input = "aaaabbbcccc"

ordering = "ac"

result = TRUE

- 0of 0 votes
Implement a data structure to represent this

[1,[2],[[[5]]],6,7,8]. Multi level indirection with in a list