## Uber Interview Questions

- 0of 0 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.

- 2of 2 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.

- 0of 0 votes
Given an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesn’t exist for i, 1 should be printed.

- 0of 0 votes
Given a character limit and a message, split the message up into annotated chunks without cutting words as, for example when sending the SMS "Hi Sivasrinivas, your Uber is arriving now!" with char limit 25, you should get

["Hi Sivasrinivas,(1/3)", "your Uber is arriving(2/3)", "now!(3/3)"]

- 0of 2 votes
Serialize & Deserialize a binary tree

- 0of 2 votes
Add a third dimension of time to a hashmap , so ur hashmap will look something like this - HashMap<K, t, V> where t is a float value. Implement the get and put methods to this map. The get method should be something like - map.get(K,t) which should give us the value. If t does not exists then map should return the closest t' such that t' is smaller than t. For example, if map contains (K,1,V1) and (K,2,V2) and the user does a get(k,1.5) then the output should be v1 as 1 is the next smallest number to 1.5

- 0of 0 votes
Design a ride sharing application