Uber 2020 Summer Intern timeline和面经

coding 1: binary search 找到第一个和最后一个
coding 2: * Example - Input - A gave B 10$, B gave A 20 $, A gave B 5 $, C gave A 3 $
Output - B gave A 5 $, C gave A 3 $.

  • Key thing is to use map of map datastructure.

Given 3 singly linked list, find all triplets (a, b and, c) one from each list s.t. a+b+c = target.

*Space O(1)

  • Idea - sort first 2 list ascending and 3rd decending, pick one element from 1st list, then for that element find new target by subtracting it from actual target. Then start from first element from 2nd and 3rd list.
  • If sum of first elements of 2nd and 3rd element ( s ) is less than new target, then move pointer of 2nd list,
  • if s greater than new target, then move pointer of 3rd list,
  • if equal then print it.
  • Not allowed to use C++ STL for list. Have been asked to write everything on our own. Defining structure of linked list, sort the list ( which includes merge sort, merge, middle element, etc.) , then perform the above mentioned logic.