Coding interview
Topic: Coding interview
Interviewer: Cissy chen
Interviewee: YingYing
Level: L5 (Senior)
Sign Up Form:
Job refer and wechat group:
https://commitway.com/job-refer
QRCode
Coding Interview Presentation
Today: we will cover 1 phone interview question (easier) + 1 onsite interview question (harder)
Unsorted array
Length of longest subarray
Subarray includes contiguous elements
For non-contiguous elements, it’s called “subsequence”
This question is on contiguous element
Example [7, 2, 3, 1, 5, 8, 9, 6]
Linear scan from left to right
Scan 7
Scan 2
len=1
max=1
Scan 1
Len=1
max=1
Scan 5
len =2
max=5
Scan 8
len=3
max=8
Scan 9
len=4
max=9
Scan 6
O(N)
====
Interviewee E
Alternative (naive) solution
Use 2 for loops, with start and end, and decide if the result is ascending
O(N^3)
=====
[7:26]
Interviewee William
Dynamic programming
Use historical result to continue to compute
M[i] = the length of the current subarray
Global max
Dynamic programming
Find the basis
Find the induction rule
What to return
You don’t need M[i] (length of the current running subarray)
This should complete within 3 minutes
Should we code and explain at the same time?
You don’t need to code and explain at the same time
1: demo and agreement on working solution
2: focus on coding
3: some portion: you can explain part of your code
William’s code:
Max update at the end of the subarray
Improved efficiency
But sacrificed readability;
Public static int solution(int[] arr) {
If (arr == null || arr.length = 0) {
Return null;
}
Int max = 0;
Int len = 1;
For (int i = 1; i < arr.length; i++) {
If (arr[i] > arr[i-1]) { // check whether equality can be treated as ascending
len++;
} else {
Max = Math.max(max, len)
Len = 1;
}
}
Max = Math.max(max, len)
Return max;
}
====
We have a number of envelopes with widths and heights given as a pair of integers (w,h).
One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you russian doll? (put one inside another)
Note:
Rotation is not allowed
William
Are we getting the input as array of array, or array of object (with width and height as fields)?
Define input and output
Anna:
Interviewee should define the input.
Remember: it’s not leetcode
Output?
William: int
William:
Sort first
Based on width or height
Anna:
Actually based on width or height?
E:
Can 3,3 enclose 3,1?
===
Anna:
What’s the most brute-force?
Recursion, no preprocessing
Do you need to try other ways?
N^N
Sort
Sort based on width
After sort, you don’t have to need to go backward
N!
Should I write sort?
Arrays.sort()
Collections.sort()
Lambda expression. A comparator
You can use (e1, e2) -> integer.compare(e1[0], e2[0])
Or new Comparator
Should I use Integer.compare or subtract?
Integer.compare is better
If we have already sorted by width
We need to find longest subsequence using height element
5 can be connected with 2, 3, or 1
What is M[i]?
If this element is the tail, the length of the longest subsequence
Now need to correct the [2] under [1]
Now change it to [1]
Closed interval vs open interval
Still need global max
Base case:
M[0] = 1
Induction rule
M[i] represents the length of longest ascending subsequence that ends at a[i]
M[i] = if any a[j] that < a[i]
If no such j
max(M[j]) + 1
If M[i] is the same, then can throw away the previous element that is larger
Lowest_ending[1] = 1
Lowest_ending[2]=3
…
We can prove that the above array is an ascending order
Use binary search to find the max element that is smaller than the height
===
Sort by width, then sort by height in reverse
This makes sure that longest subsequence will not get into the situation where the width is the same
10 minutes or so
You can use DFS, recursion (with memorization).
Can use DP
First question can be longest subsequence
Can you map the 2nd question into a longest subsequence?
3+1
理论，实践，设计
===
Dynamic program
Derive the result based on the historical result of smaller problem
How to optimize