## Uber Interview Questions

- 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

- -4of 4 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

- 0of 0 votes
Given an api which returns an array of chemical names and an array of chemical symbols, display the chemical names with their symbol surrounded by square brackets:

Ex:

Chemicals array: ['Amazon', 'Microsoft', 'Google']

Symbols: ['I', 'Am', 'cro', 'Na', 'le', 'abc']

Output:

[Am]azon, Mi[cro]soft, Goog[le]

If the chemical string matches more than one symbol, then choose the one with longest length. (ex. 'Microsoft' matches 'i' and 'cro')

My solution:

(I sorted the symbols array in descending order of length and ran loop over chemicals array to find a symbol match(using indexOf in javascript) which worked. But I din't make it through the interview, I am guessing my solution was O(n2) and they expected an efficient algorithm.

- 0of 0 votes
Design a hashMap in Java. Implement put, get, remove, resize methods.

- 0of 0 votes
1) Narrate an instance you optimized or improved a software design.

2) Given a chance how would you re-think some of the design aspects?

- 0of 0 votes
Design a Twitter feeds API. How would you actually connect it from a mobile? What happens behind the Twitter network? how do the Trends get published? From where does Twitter get the information for a particular trend(Eg: #Obama, #nfl) and publish it out? What protocol does it use? How do you connect to Twitter API? How does Twitter handle multiple connections?

- 0of 0 votes
1) Describe your most proudest project, least proudest project

2) Most inpiring teammate, what did he do?

3) Most awesome manager? Why was he so good?

- 0of 0 votes
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

- 0of 0 votes
LRU Cache

- 1of 1 vote
WAP to take one element from each of the array add it to the target sum. Print all those three-element combinations.

/*

A = [1, 2, 3, 3]

B = [2, 3, 3, 4]

C = [1, 2, 2, 2]

target = 7

*/

Result:

[[1, 2, 4], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 3, 3], [1, 4, 2], [2, 2, 3], [2, 2, 3], [2, 3, 2], [2, 3, 2], [3, 2, 2], [3, 2, 2]]

- 0of 0 votes
For a given string and dictionary, how many sentences can you make from the string, such that all the words are contained in the dictionary.

// eg: for given string -> "appletablet"

// "apple", "tablet"

// "applet", "able", "t"

// "apple", "table", "t"

// "app", "let", "able", "t"

// "applet", {app, let, apple, t, applet} => 3

// "thing", {"thing"} -> 1

- 0of 0 votes
Given string a and b, with b containing all distinct characters, find the longest common subsequence's

length. Expected complexity O(nlogn).

- 1of 1 vote
Given a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.