Uber Interview Questions

 Question: Best Time To Buy Or Sell Stock

Question: Clone Graph

Question: Decode Ways

Question: Exclusive Time Of Functions

Question: Generate Parentheses

Question: Group Anagrams

Question: Group Shifted Strings

Question: Implement Trie

Question: Insert Delete Get Random O(1)

Question: Letter Combinations Of A Phone Number

Question: Maximum Depth Of A Binary Tree

Question: Merge K Sorted Lists

Question: Minimum Window Substring

Question: Min Stack

Question: One Edit Distance

Question: Palindrome Permutation

Question: Regular Expression Matching

Question: Regular Expression Simple

Question: Reverse Linked List

Question: Roman To Integer

Question: Search In Rotated Sorted Array

Question: Subsets

Question: Two Sum

Question: Valid Palindrome

Question: Valid Sudoku

Question: Word Break

Question: Given a regular expression pattern and a string, check to see if pattern matches the string. 

Question: write code to print the matrix from outside to inside. (sprial form)

Question: Given a list of words, find whether a new word is anagram of word in list.

Question: Find the longest word in a grid of random letter, each consecutive letters has to be next to the previous one.

Question: Print all permutations of 3 pair of parens. ()()(), (()()), (())(),,,. etc  

Question: Implementing the substring method

Question: Lowest common ancestor in BST  

Question: Given a restaurant menu and a budget, output all the  possible ways to use up the budget.

(can use modified knapsack solution)

Question: Finding kth smallest element in a BST

Question: Reverse a string

Question: Search and delete nodes in BST. Delete operation is pretty tricky and you should review that.

Question: Implement a rate limiter attribute/decoration/annotation on top of an API endpoint. caps to N requests per minute with a rolling window (implement from scratch / test / compiling + working code)

Question: Reversing a linked list, Reversing linkedlist from ith to mth node,

Question: Implementing a rate limiter for a web service.

Question: Implement a map data structure using a binary search tree. It should have the functions Get, Set, and Size.

Question: Distance between siblings in trees, basic SQL queries

Question: input a list of array [[1, 2, 3], [1], [1, 2]] return the list of array, each array is a combination of one element in each array. [[1, 1, 1], [1, 1, 2], [2, 1, 1], [2, 1, 2], [3, 1, 1], [3, 1, 2]] Followup: each array in the input list is an iterator, which can only be looped once. 

Question: Implement data structure "Map" storing pairs of integers (key, value) and define following member functions in O(1) runtime: void insert(key, value), void delete(key), int get(key), int getRandomKey().  

Question: Given a string A and B, find the smallest substring of A that contains all the characters from B. (implement solution in O(n), keep in mind chars in B can repeat) 

Question: Given a message "one two three four five six seven eight nine", chop it in chunks(no exceed the give buffer size) and print out to the screen. Need to maintain the word and do not chop it off.

I.E.: buffer size is 15

one two three (1/4)

four five six (2/4)

seven eight (3/4)

nine (4/4)  

Ref:http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

Question: please construct a hash map 

Question: Search a target number in a Rotated Sorted Array. How do you find a specific element in a rotated sorted array in one pass?  

Question: Code secret santa

Question: Given a text message and max number of characters, implement how the phone company can represent a given message. 

isMatch(“aa”,”a”) ? false

isMatch(“aa”,”aa”) ? true

isMatch(“aaa”,”aa”) ? false

isMatch(“aa”, “a*”) ? true

isMatch(“aa”, “.*”) ? true

isMatch(“ab”, “.*”) ? true

isMatch(“aab”, “c*a*b”) ? true

Write isMatch()

Question: Heap datastructure

Question: Given a set of sudoku boards, determine whether a board is valid or not. 

Question: Compute a^b (https://leetcode.com/problems/powx-n/discuss/19544/5-different-choices-when-talk-with-interviewers)

Question: Implement a timer using queue.  

Question: You have a sorted array of integers. Find the element where the array index is equal to the value of the corresponding element. Or return that no such element exists. 

Question: You have a dictionary of words. Create a matrix of letters such that each row of the matrix is a word and each column of the matrix is a word. Kind of like a very dense crossword puzzle.  

Question: A file contains strings like abcd 3.0 xyx 4.0 foobar 5.0 return random string but probability should be based on weighted average. Ref:https://softwareengineering.stackexchange.com/questions/150616/get-weighted-random-item

Sol(1)

add as many entries for an item as defined by its weight, shuffle the list and get a random entry

Sol(2)

Calculate the cumulative sums of weights:

intervals = [4, 6, 7]

Where an index of below 4 represents an apple, 4 to below 6 an orange and 6 to below 7 a lemon. Generate a random number n in the range of 0 to sum(weights). Find the last item whose cumulative sum is above n. The corresponding fruit is your result.

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

Question: longest palindromic substring.  

Question: given an integer array, find the number of triplets that have sum more than a particular value.  

Question: Reservoir sampling related problem

Question: valid parenthesis problem

Question: Find if tree is a valid BST  

Question: Number of Islands

Question: Linked List Sum

Question: Rotate matrix

Question: Given the travel time of each customer. Find the driver  with the longest chain of trips ,which means there is always at least one person on the car

Question: implement hashmap, Constant time random access hash implementation

Question: Find and return the first duplicate integer in an array in O(n) time and O(1) space. Assume there will always be at least one duplicated integer in the array. 

for (i = 0; i < arr.length; i++) 

{ 

if (arr[Math.abs(arr[i])] >= 0) 

arr[Math.abs(arr[i])] = -arr[Math.abs(arr[i])]; 

else

System.out.print(Math.abs(arr[i]) + " "); 

}

Question: 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". 

public boolean wordBreak(String s, List<String> wordDict) {

boolean[] dp = new boolean[s.length() + 1];

dp[0] = true;

for(int i = 1; i <= s.length(); i++) {

for(int j = 0; j < i; j++) {

if(dp[j] && wordDict.contains(s.substring(j, i))) {

dp[i] = true;

}

}

}

return dp[s.length()];

}

Question: Given an input string of numbers like 121, find all permutations of that number in the same order for the corresponding letters for each number so 121 => 1 2 1, 12 1, and 1 21 which is ABA, LA, and AT

Question: Sparse vector product. Given two very large sparse vectors, 1. find the data structure to store them 2. calculate the product of them

Question: Given an array of Ints find a maximum sum of non adjacent  elements. for ex. arr = [1,0,3,9,2] then ans would be 10 = 1 + 9 (non adjacent element)

=>http://blog.gainlo.co/index.php/2016/12/02/uber-interview-question-maximum-sum-non-adjacent-elements/?utm_source=glassdoor&utm_campaign=glassdoor&utm_medium=121516

evalexpr(-4 - 3 * 2 / 2 + 4) -> result (float or double)

Question: Ransom note

Question: Median of k unsorted arrays

Question: Design of a task scheduler

Question: Give a list of number, return all subsets of the list.  

Question: Write a power function

Question: How will you find the first and the last occurrence of a number in a sorted list? 

Question: You have an array and you need to partition the array values into buckets so that each bucket sums to an equivalent value. Return a boolean if its possible or not on the array. 

Question: Complexity of Sort Functions  

Question: Given a linked list of length n, and without creating any secondary data structures, how would you find an entry in the linked list in less than n probes?

Question: Write a function that takes a list of "ranges" and returns a list of the minimum number of "ranges" by combining overlapping "ranges".

Question: Given an array of prices how will you gain max profit if you can buy and sell any no of times but you can't buy the next day you sell  

Question: Given a number represented as a linked list, add '1' to it. No extra space, and in liner time.  

Question: What's the time complexity of searching through a sorted Binary Search Tree?