C _Interviews - RicoJia/notes GitHub Wiki

========================================================================

Basic Prep

======================================================================== amazon interview prep:

ipad charged
backup computer, sleep time changed. have

========================================================================

DFS

========================================================================

In most cases, DFS is implemented in a recursive way. But there are also for-loop equivalents.
- But for either implementation, the first step of designing a DFS is to figure out the output sequence of each iteration then how to call the same process.
- Don't worry too much about copy, etc. Implement it!
number of islands. Just like your Fun Project. Use DFS. Note that in each DFS iteration, you're going to find a complete patch.

Dynamic Programming

The very definition is to use previous knowledge to compute a current value. So the key is to think how to build your way to each step.
- A typical problem is the 0-1 knapsack problem. And it can be easily implemented as a 2D array
- Key idea for DP: Sometimes, even though the problem asks to go for one specific value, you might be able to build your sub-problems by going from 0 to that value.
- Actually, for the classic knapsack problem, you can use an 1d array to solve the problem, bottoms up
```
int knapsack(int val[], int wt[], int n, int W)
{   //val[] are values, wt[] are weights, n is the number of items, W is target weight. 
    int dp[W+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0; i < n; i++) 
        for(int j=W; j>=wt[i]; j--)
            dp[j] = max(dp[j] , val[i] + dp[j-wt[i]]);
    return dp[W];
}
```
- Reason why this algorithm works:
  1. knapsack requires you to be able to - keep best values of their corresponding weights as they are if your current weight is higher.
    - your max value will be max(old_value(target_weight), item_value+old_value(target_weight - item_weight))
  2. bottom up approach allows you to: - not touch best values if your current weight is higher (j>=wt[i]) - allows you to read old_value(target_weight), dp[j] and old_value(target_weight - item_weight)), (dp[j-wt[i]])), since this is bottom up approach.

Backtracking

permutation and combination both can be expressed as DFS.
Back tracking
- tricky: let the base do the final work. clean up after yourself

========================================================================

BFS

========================================================================

Distance To the Nearest 0

Problem you can use a queue and keep adding and popping nodes to achieve BFS. The rationale is similar to the DP solution
- which is: you will get the right result after evaluating by getting the best of multiple passes.
- In 1D case, in each pass you evaluate 1 by starting from the 0 on the left/on the right. This is same as DP, which evaluates from 0 on the left & on the right as well.
stack
- push() not push_back()
- top()
- pop()
- BFS: push neighbors onto stack, then move on.

========================================================================

Graph Problems

========================================================================

build a lookup table, a "status_board", then do DFS and flip signs like in here
- Traversing thru a tree is similar to DFS, you do dfs on each node, and you store the status of each node in an array. DFS can return the "rest of the total cost" to you, so make use of that.
- Better method is required. See here

Distance To the Nearest 0

Not so good solution Problem
```
[011111011]
```
- You just need two passes to find the minimum value from one direction: left to right: [0,1,2,3,4...0, 1,2], right to left:[0,1,2...3,2,1,0,1,2]
- Rationale is you get the min from both directions, which is to improve based on what you have.
- In the 2D case, you can check left, up, then right, down. But this is not so good, as you will have to treat cells on the edge separately, and depending on if there have been 0 at all.
Generic Solution - multi-source BFS
1. so you start from all the 0s, update their neighbors, then search from those neighbors, to update their neighbors.
2. A queue can make the search depth under control: you push all 0 positions first, then 1st layer neighbors, then 2nd layer neighbors.
3. Push cells to the queue if their cell values are changed.

Topological Sort

https://leetcode.com/problems/course-schedule-ii/ Used in Software IDE build system, apt-get (packaging tool)

Bi-partition Problems:

If a problem asks you to classify two types of nodes, and adjacent nodes cannot be in the same color, then it's bi-partition. 1. The solution is:
1. build a FULL edge list (half edge list is you only have node 1 -> node 2, but not node 2 -> node 1. ). A full edge list can gurantee all connected nodes are traversed,, while a half edge list cannot. E.g, 0 -> 5, 5->2.
2. Use DFS for this problem. Otherwise, there will be too bugs for you to consider!!
3. Therefore, we are able to traverse thru all connected nodes from one DFS pass. This makes sure that we can start with a random color every time we want to color our pallet, since they're not connected.
  - Corner case: empty edge list.

Cycle Detection

You can have 2 methods: topological sort, or building 2 edge lists (one with inbound and one with outbound edges).
- Then, you can start popping edges on one edge list, from all leaf nodes. If there are no edge left at the end, the graph is clear.

Loop detection

BFS is easy. Layer by layer, and there should be an end point, with "in degree"= 0. In degree means number it points to.

DFS's Summary: for every starting node in graph:

1. unexplored -> exploring .... -> (Nothing to explore, end of chain), explored
2. unexplored -> exploring -> explored, done
3. unexplored -> exploring -> ... hit another exploring, loop, false.

Hash Map

if you work with random IDs, do not use std::vector. use std::unordered_map instead. Note that for unordered_map, you shouldn't use .at, but []

========================================================================

Tree

========================================================================

Don't worry about ptrs. But also it might be hard to test them
BST concept is very important: left val < root < right val.
In the real thing debugging a tree is very cumbersome, (your job sometimes is to make a tree, from an array!) but you can debug at least some peripherals.
Binary search: use [left, size - 1]; [left, mid - 1], [mid + 1, right]; return condition: l > r return null.
- Binary Search: use recursion. While loop: exit condition needs to be checked after recursion

Heap

Heap is
```
   10(0)
    /  \
 5(1)  3(2)
/   \
4(3) 1(4)
```
1. Therefore, the root is either larger/smaller than the two children. If you heapify a heap, that's what it is.
2. Say you have an array that represent heap (root = vec[i], left = vec[2*i + 1], right=[2 * i +2]).
3. To heapify, You'll start from the non-leaf nodes (size/2-1), swap them so that the root is the largest.
4. Then, trace down the affected tree.
```
#include <algorithm>
std::make_heap(vec.begin(), vec.end(), [](int a, int b){return a < b; }) //so this is a max heap. 
std::pop_heap() //will pop the first element of a heap, then sort. you need to erase the last element of the vector. 
std::push_heap() //will also sort the heap. 
```
  - std::make_heap does that. O(n) , not O(nlg(n)). for a single heapify operation, it's o(lg(n)).
Heap sort:
pop, sort heap, pop, sort heap ...

========================================================================

Sort

========================================================================

Quick Sort:

std::partition: reorder elements [beg, end), elements satify the predicate will be put left (inside order NOT preserved). returns the first element of the second group.

#include <algorithm>
// Bad Example: 
auto first_it = std::partition(ls.begin(), ls.end(), [&pivot](const int& i){return i < pivot; }); // is first_it the pivot? Not necessarily, because the order of the right-hand side might be screwed up!

So you need to partition on array NOT including the pivot, then splice onto it (for list), or do insert (vector)

move stuff to the left of the pivot and right of the pivot.

# always makes sure to_swap>=pivot. This makes the end a lot easier. 
def partition(self, l, r):
    # this is the tricky part
    # this way we start check from the very beginning, so we can guarantee that s is always >=
    s = l
    c = l
    print( "l: ", l ,", r: ", r)
    while c<r:
        if (self.nums_[c] < self.nums_[r]):
            self.nums_[c], self.nums_[s] = self.nums_[s], self.nums_[c]
            s+=1
        c+=1
    self.nums_[r], self.nums_[s] = self.nums_[s], self.nums_[r]


    # print("after: ", self.nums_[l:r+1], ", pos: ", s)
    return s

Another great answer

def sortArray(self, nums):
    if len(nums) <= 1:
        return nums

    pivot = random.choice(nums)
    lt = [v for v in nums if v < pivot]
    eq = [v for v in nums if v == pivot]
    gt = [v for v in nums if v > pivot]

    return self.sortArray(lt) + eq + self.sortArray(gt)

what would you wish to do when you're stuck?
- first is to know how exactly the algorithm works. Coming to realize we need splicing was a big change.
- naming could be more descriptive, we think with names!
- debug with the simplest case: it shouldn't be any simpler,e.g, array with two elements.
- coming back to the basic concepts: "does the iterator point to a different element after std::partition, or list::splice?"
Summary

========================================================================

Misc

========================================================================

String

Odd string and even string for palindrome:
- A Palindrome could be either odd, or even
- Manacher algorithm is really just expanding towards the two ends of a string.

Tips for your career

Make your work public, and advertise it. The validation of your work is important.
Do the work that has a clear market-value goal!!. Then, do well so that people can count on you. That's how you make an impact.

Experiences

Amazon OA19 Max of Mins
Take whiteboard marker, eraser, pens, resumes to avoid las pendejadas. Nobody cares about your performance except for yourself.
Quickselect... The partitioning algorithm is too hard to implement. Try the simple one (heap) first, and mention that in your comment.
- This is because they sometimes just want to see how you think, not exactly how good your code is.
Do not say: can I do DP? Like you're asking for permission. You should discuss alternatives.
Usually, you don't have to worry about overflow. If that happens, use / instead of *, use - instead of +.
complex index arithmatics: consider using [left_index, right_index], and std::find with index-1.
- if indexing going one direction is too difficult, can we go the other way?
remove needs to work with end, then use the new end:
```
end = std::remove(beg, end, val); // Not vec.end()
```
- vector::erase(iterator pos) also exists
- Bidirectional itrs: you can do itr+2.
- std::distance(beg, end)
use the same name as input arg. like target_
int max in python: no int max in python 3. use sys.maxsize
Binary Search - can be used to find k closest O(N), (N + N/2 + ... N/N) leetcode question
- use a random pivot, partition the list into two lists: closer, further
- if closer has less than K elements, try to partition until you get exactly K elements

========================================================================

OOD

========================================================================

Procedure: think of this as a simulator
1. clarify, features
2. High level abstraction
  1. Have an example workflow
3. Interesting principles (solid)
  - Single Responsibility principle (class should just have the specified responsibilities)
  - Open Closed Principle (open for extension, closed for modification)
  - Liskov substitution (child class should do everything base class is already doing)
  - Interface Segregation Principle (no useless interfaces)
  - Dependency Inversion Principle
airport question:
- std::unique_lock::try_lock()
Parking lot - Question
- sln #

========================================================================

Interview Experiences

========================================================================

在职面亚麻基本就是和地理大多数帖子类似上来先是简历问了一下项目和认为挑战难度的地方然后代码

// 1
Q：设计一个打车调度的系统。
Q：编程：给出一个从小到大排好序的整数数组nums和一个整数n，在数组中添加若干个补丁（元素）。
使得[1,n]的区间内的所有数都可以表示成nums中若干个数的和。
返回最少需要添加的补丁个数。

// 2014
https://www.1point3acres.com/bbs/thread-101169-1-1.html

// 3
（2）面试官可能会让你回答 OOP 的四个基本要素、如何定义抽象数据等问题。
（4）OOD 面向对象程序设计。面试官有可能会让你为电梯、停车场或电影院进行面向对象编程。这是需要你能够巧妙地使用类和函数。
（5）解释多态性。面试官可能会让你针对销量top10的产品进行对比，解释多态性的含义。
（6）哈希表。面试官可能会出一道编程题考察你对哈希表的熟悉程度。

Leadership bq: make a decision, help others.第二题因为紧张一开始弄错题了，等我答完了让我重新答了一遍，很尴尬...感觉bq都是大家碰到过的题目，按照亚麻的LP14条准备就好。

C _Interviews - RicoJia/notes GitHub Wiki

Basic Prep

DFS

Dynamic Programming

Backtracking

BFS

Distance To the Nearest 0

Graph Problems

Distance To the Nearest 0

Topological Sort

Bi-partition Problems:

Cycle Detection

Hash Map

Tree

Heap

Sort

Quick Sort:

Misc

String

Tips for your career

Experiences

OOD

Interview Experiences

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️