先报一下timeline
申请-内推的[10月6日]
接到电话-10月16日
预定第一轮-10月30日
预定第二轮-11月18日[结束第一轮之后]
拿到-11月26日
第一轮：
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.