Uber Interview Questions

Math

Excel Sheet Column Number

  • 26 base
  • Need to check overflow

Excel Sheet Column Title

  • There's no representation of 0
  • Tricky part is how to handle 27
  • We can decrement n by one before any calculation
  • so 27 will be (27-1) % 26 = 0, (27-1)/26 = 1

Roman to Integer

  • Take symbol one by one from starting str.size()-2
  • If current value of symbol is greater than or equal to the value of next symbo, then add this value to the sum
  • Else subtract this value from the sum

Happy Number

  • Evaluate square sum
  • Similar to check cycle in linked list
  • Use fast pointer and slow pointer

Fraction to Recurring Decimal

Bit Manipulation

Power of 2

  • n > 0 && !(n & (n-1))

Power of 4

  • Check is power of 2
  • And num-1 is divisible by 3
  • !(num & (num - 1)) && (num - 1) % 3 == 0

Array

Spiral Matrix

  • Use dir to indicate direction 0,1,2,3

  • Use rLow, rHigh and cLow, cHigh to mark range

  • Group Shifted

  • Meeting Room
  • Number of islands
  • 3Sum Smaller
  • Merger Intervals
  • Insert Intervals

1 1 1 2 2 1 1 3 3 3 那么岛屿1的面积是5 岛屿2的面积是2 岛屿3的面积是3 所以输出5

String

Reverse Words in a String

  • How to handle leading and trailing empty space
  • How to handle space in between
  • We can reverse each word and then reverse the string
  • Or we can use a stack to push and pop

One Edit Distance

  • Clarify what is one edit, add, remove, modify
  • Iterate through 0 to min(s.size, t.size)
  • Find the first index where s[i] != t[i]
  • Consider three cases
  • If t.size == s.size then compare the rest substr
  • Else compare s.substr(i+1) == t.substr(i+1)

  • Or s.substr(i) == t.substr(i+1) based on length

  • Reorganize String

Anagram

Valid Anagram

  • Using hash table or array of 256 to store string a
  • Iterate through b to check if characters match

Group Anagrams

  • We need to use a hash map unordered_map to store each group
  • We will use a sorted version of each anagram as the key
  • There are two ways to find the sorted anagram for each word
  • The first one is to use sorting, then check if key exist
  • The second one is to use array to count each character in word, then iterate through the array to get the sorted key.

Palindrome

Valid Palindrome

  • Consider only alphanumeric chars and case insensitive
  • While loop to find the next valid index

Palindrome Permutation

  • Determin if a permutation of the string can form palindrome
  • We can count the number of odds occurances chars in one pass, if there's more than one, then return false

Palindrome Pairs

Hash Table

Two Sum

  • User hash table to store the element and its index
  • Iterate through the vector and search if target exist in hash table.

Word Pattern

  • Use two hash table to check if both words following the pattern

Valid Sudoku

  • User three two dimentional array to save the state
  • row[9][9] = {0}, col[9][9] = {0}, sub[9][9] = {0}

  • Iterate through every item on board, and figure out the row, column and its sub board index, then update corresponding array

  • Encode and Decode TinyURL

Linked List

Reverse Linked List Recursion

  • We divide the list into two part, the head and the rest.
  • Reverse the rest list and get the new head node
  • The old head node still points to the tail of the sorted list
  • Then we update tail's next pointer to head, head's next pointer to NULL.

Reverse Linked List Iteration

  • We need three pointer prev, cur, next
  • While cur is not null, we keep updating those three pointer

Swap Nodes in Pairs

  • Divide the list into two part, pair of nodes and the rest
  • Recursively swap the right part and get the new head
  • Update the pair and new head

Copy List with Random Pointer

Stack

Min Stack

  • Using two stack, one to store all elements, one to store min values.
  • To-Do: O(1)

Exclusive Time of Functions

  • We need stack to save function call, we just need to store the id and timestamp
  • We also create a vector of size n to store the exclusive time of each function
  • Iterate through the logs, extract the id, start or end, timestamp
  • If it's the start of a function, we update the current function's exclusive time if there's any, then push the new function
  • If it's the end of a function, we update the current function's exclusive time, then update the previous function's timestamp if there's any.

Asteroid Collision

  • We can just use vector instead of stack
  • Iterate through the input vector
  • Use while loop to check if the asteroid will collide with the previous one
  • If the two asteroids are of the same size, we pop the previous one and set current asteroid size to 0
  • If asteroid moving left is larger, we pop the previous one
  • If asteroid moving right is larger, we set asteroid size to 0
  • After the while loop, if the asteroid is not zero, we push it back

Search in Rotated Sorted Array

  • Check which half is sorted
  • If left half is sorted (arr[left] < arr[mid]), check if element is located in left half
  • Else right half is sorted, check if element is located in right half

Find Minimum in Rotated Sorted Array

  • The idea is to find the unsorted half
  • If arr[left] < arr[right], it means there's no rotation in the range, we can directly return arr[left]
  • If arr[left] < arr[mid], then second half is not sorted, and min value is located there.
  • Otherwise, the first half is not sorted and the min valus is located in first half.

Binary Tree

Maximum Depth of Binary Tree

  • Using recursion to find the maximum of left and right subtree

Serialize and Deserialize Binary Tree

  • We can use pre order to encode and decode the tree.
  • We can use '.' or '#' to mark null node
  • String stream would be helpful when manipulating the string
  • We can also use level order to solve this

Binary Search Tree

Delete Node in a BST

  • Replace the target node with it's inorder successor.
  • First we need to find the target node.
  • Then we need to consider three cases:
  • If target node has no child, we can simply remove the node
  • If target node has only one child, we can use its child to replace itself.
  • If the target has two children, replace the node with its in order successor and delete the successor node recursively.

Inorder Successor

  • Do an inorder traversal, use a flag to mark target node is found.
  • We can use stack to save parent nodes.
  • And the next node is its in order successor.

Binary Search Tree Iterator

  • Using stack to store inorder traversal nodes
  • The next element will be on the top in stack

Kth Smallest Element in a BST

  • We can use the property of inorder traversal
  • We can also use divide and conqur to solve this, we can easily get the number of nodes in left subtree, and compare it with k.

Serialize and Deserialize Binary Search Tree

  • There's no difference than serialize and deserialize binary search tree.

Heap and Priority Queue

  • Find K Pairs with Smallest Sums

Top K Frequent Words

  • We can use a hash table to cound the number of each words.
  • Then we insert each word with its number of occurences into a priority queue.
  • We sort the each element by it's occurences. We can start pop k elements from the queue.

Top K Frequent Elements

  • The idea is quite similar to bucket sort.
  • We count the frequence of each word in hash table first
  • Then we create a bucket of size N+1, the index represent the count of each word
  • Then we iterate through the hash table, and insert word in bucket.

Merge K Sorted Linked Lists

  • First we push all head node to priority queue
  • While the queue is not empty, we keep poping node from the queue.
  • We also need a dummy head and current pointer.
  • Each time we pop a node from queue, we need to push its next node to queue if it exists.

Trie

Implement Trie

  • We can use array or hash table to store child pointers
  • To search for word, we need to add flag in each node to mark the end of word.

Replace Words

  • We can use trie to store each word in dictionary
  • Then we can use istringstream to extract word from sentence
  • To replace word with shortest root, we just need to search for the shortest prefix.

Add and Search Word

  • We can use trie to store and search for each word
  • To search pattern lik "..a", we need to do a dfs

BFS and DFS

Employee Importance

  • Use hash table to search employee by id
  • To avoid cycle in dfs we use hash table or set to save visited employee
  • Then we use dfs to find the importance sum

Flood Fill

  • We can use dfs to change all neighbors color
  • We don't need a visited array in this problem
  • If the pixel is the new color, that means we don't need to continue

01 Matrix

  • We create a array of directions to help updating neighbor nodes
  • Push all 0 as start position to queue
  • Mark all 1 as INT_MAX
  • Start updating neighbors of nodes in queue.
  • If neighbor node's value is larger, then we update its value and push it to the queue
  • Repeat this until the queue is empty

Shortest Distance from All Buildings

Graph

Course Schedule

Clone Graph

Backtracking

Generate Parentheses

  • We can use two variable to indicate the current number of open and close parentheses.
  • We also need to pass the current string which represents the current state
  • The termination condition is when the current string size is equal to 2*n, n is the number of pairs
  • We only add bracket when we know it will remain a valid sequence.
  • We can do this by keeping track of the number of open and close brackets we have placed so far.
  • We only add open bracket when its less or equal than n.
  • We only add close bracket when its less than open brackets

Letter Combinations of a Phone Number

  • First we need to create a vector containing strings represented by number from 0 to 9
  • We use a vector to store the previous words combination.
  • For each new digit, we pop one word from the vector each time, and push the new word the vector.
  • We need to save the size of the vector first, just like level order traversal

Combination Sum

  • First we need to sort the input array
  • For backtracking, we need to pass the candidates and target
  • We also pass the start index and previous choice vector to represent the current state
  • The termination case is when the target is less than 0
  • When target is equal to zero, we push the vector to result vector
  • When target is larger, we try all the combinations start from the start index.

Subsets

  • We don't need to sort the input array
  • We can push an empty vector to the result vector first
  • Iterate through the input vector
  • Append the number to all subsets in vector and push it back to result vector
  • We need to remember the size of the current vector first

Factor Combinations

Dynamic Programming

House Robber

Word Break

Best Time to Buy and Sell Stock

Longest Palindromic Subsequence

Design

LRU

  • Cause we need to insert and remove frequently, we can use a doubly linked list.
  • Insert and remove in doubly linked list is O(1)
  • To search in O(1) time, we can use a hash table to store the position of each element.
  • For get() operation, if key exists in list, we can use cache.splice(cache.begin(), cache, m[key]) to remove element from cache and insert it at the front, then return the value.
  • For set() operation, if the key exist, we just update the value and move it to the front.
  • If it doesn't exist, first we need to check if cache is full, if so we need to remove the last element from hash table and list, then we insert the new key value pair and update the hash table.

Insert Delete GetRandom O(1)

  • To support insert, search and delete, we can use hash table
  • To get random element in O(1), we can use use vector
  • The hash table stores the value and its positon in vector
  • To remove an element, we get the postion from hash table, swap it with the last element in vetor, and remove it from both.

Logger Rate Limiter

Rate Limiter

results matching ""

    No results matching ""