Home > Reflections | ⏮️ ⏭️
2024-06-04
🏋️ Practice
Problem statement
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array
nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.You may imagine that
nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.You must write an algorithm that runs in
O(log n)time.
🪞 Reflections
- I’m not happy with the solution below
- More importantly, I think there’s a strategic error here
- When planning, I didn’t really settle on a solution that I had much confidence in
- I decided to try implementing it and just hope for the best
- But it turned out poorly, as I’d expected it would
- In general, I don’t think it’s a good strategy to attempt to implement a fuzzy plan that I’m not confident in
1. It seems like when I do, it doesn’t turn out well. This is more of a trend than an isolated incident.
2. But what to do instead?
3. Why is it fuzzy?
4. How can I make it less fuzzy without implementing it?
5. In this case, I had a hunch that it wouldn’t work, and eventually found a test case to confirm that hunch.- That’s better than not finding the bug, and allowed me to find a hacky workaround, but it wasted a lot of time.
6. If I caught the bug during a test case, maybe I can try testing the “fuzzy” algorithm “manually” before implementing it in code. - This would at least save the time required to implement a wrong solution
- And it may be more difficult to modify a wrong solution than it is to implement a correct solution from scratch
- That’s better than not finding the bug, and allowed me to find a hacky workaround, but it wasted a lot of time.
- In an interview context, if I’m not confident in my plan, I should probably engage with the interviewer rather than attempt to implement and hope for the best.
1. At least this way I may get a hint and some help constructing a better plan. - Even without a hint, testing the algorithm manually before implementing the code seems like an improvement.
- But maybe there’s something even better.
1. I’m not quite sure what that is, but there’s an idea that makes me think there’s a better way:
2. In general, testing is not a good strategy for improving quality.
3. We can, of course, test the output of a process and discard the results that don’t meet our quality bar.
4. But a better approach is to improve the process in order to reduce the variation in the outputs.
5. Note: This idea comes from my understanding of W Edwards Deming’s writing.
6. So in this case, rather than test a fuzzy algorithm and then reject it when it doesn’t work, how can I improve the process of generating an algorithm in the first place?- Note: if I test the algorithm and find that it doesn’t work, I’m going to have to do this anyway, so we may as well save some time and skip the testing step until we have an algorithm we’re confident in.
7. So this is my new challenge:
- Note: if I test the algorithm and find that it doesn’t work, I’m going to have to do this anyway, so we may as well save some time and skip the testing step until we have an algorithm we’re confident in.
🤔 How can I generate higher quality algorithms without relying on testing?
To be continued…
My first solution
/* return index of any peak element
Notes:
- peak element is strictly greater than neighbors
- out of bounds is always less than in bounds
- Must run in O(log(n))
- neighbors are never equal
Thoughts:
- O(log(n)) time means we can't
- scan the whole array - O(n)
- sort the array - O(n*log(n))
- O(log(n)) makes me think of binary search...
- but the array isn't sorted...
- so I don't think binary search would be effective
- if we scan left to right
- in the worst case all elements are increasing
- so we'd do O(n) work before finding the peak
- however, we could detect a monotonic increase like that with binary search
- is the last element higher than the middle element?
- Maybe a binary search can help
- if we're searching for elements that are higher or lower than some other element
- what are we searching for?
- a change in direction
- thinking this through
- look at first element: A
- check last element: Z
- is Z greater than A?
- if so, there must be an increase between A and Z
- if Z is the last element and the element prior is less than, we have a solution
- if Z is less than A, there must be a decrease between A and Z
- if the element after A is less than A, we have a solution
- but I think we need to not just check neighbors
- I think this will work, but I don't have it fully fleshed out yet
- continuing
Binary Search plan:
1. Read first element A
2. Read last element Z
3. If A < Z, Z might be a peak
a. Check the midpoint M
b. if M < Z, Z might be a peak
c. continue binary searching
d. if M > Z, M might be a peak... which way do we search now?
i. check the midpoint between M and Z (MZ)
ii. if MZ < M, continue narrowing toward M
iii. if MZ > M, continue narrowing toward MZ
4. If A > Z, A might be a peak
a. Check the midpoint M
b. if A > M, A might be a peak
c. continue binary searching
Gist:
1. binary search
2. always assume the largest number seen is a peak
3. binary search toward the peak to narrow that window
I'm not 100% sure this will work, but it seems worth a try.
[22:00] Done planning
[33:50] Done with initial implementation
[1:16:35] Submitted: wrong answer
*/
function findPeakElement(nums: number[]): number {
// 1. nums=[1]
// 2. nums=[1,2]
// 3. nums=[1,2,3,1]
// 4. nums=[1,3,2,1]
// 5. nums=[1,6,5,4,3,2]
for (let l = 0, r = nums.length - 1; true;) {
let L = nums[l]
// 1. L=1
// 2.1 L=1
// 2.2 L=2
// 3.1 L=1
// 3.2 L=3
// 3.3 L=3
// 4.1 L=1
// 4.2 L=2
// 4.3 L=2
// 5.1 L=1
// 5.2 L=4
// 5.3 L=4
// 5.4 L=4
let R = nums[r] // <- uncaught bug: used R instead of r as index
// 1. R=1
// 2.1 R=2
// 2.2 R=2
// 3.1 R=1
// 3.2 R=1
// 3.3 R=3
// 4.1 R=1
// 4.2 R=1
// 4.3 R=2
// 5.1 R=2
// 5.2 R=2
// 5.3 R=3
// 5.4 R=4
if (l === r) {
if (l === 0) {
if (nums.length > 1 && nums[l + 1] > L) return l + 1
else return l
// 1. return 0
}
if (r === nums.length - 1) {
if (((r - 1) >= 0) && nums[r - 1] > R) return r - 1
else return r
// 2.2 return 1
}
if ((nums.length > (l + 1)) && nums[l + 1] > L) {
// 2nd fix: rightward linear scan
while ((nums.length > (l + 1)) && nums[l + 1] > nums[l]) {
l = l + 1
}
return l
}
else if ((l > 0) && nums[l - 1] > L) {
// fix: linear scan leftward
while (l > 0 && nums[l - 1] > nums[l]) {
l = l - 1
// 5.4.1 l = 1
}
return l
// 5.4 return 1
// 4.3 return 1
// 5.4 return 2 <- wrong answer
// we're only searching for a peak effectively in one direction
// I think we need to search left more than 1 space over
// ideally, we'd binary search leftward at this point
// though maybe a linear scan at this point would still be good enough
// how do we binary search leftward after finding our right boundary?
// we may need to keep track of our prior left side
// I'm going to start with a linear leftward scan here to check for correctness
// I don't actually expect this to be O(log(n)) but it'll at least give confidence
// that we're on the right track.
// Also, we're 1:11 in at this point and I'm getting tired.
}
else return l
// 3.3 return 2
}
if (L <= R) {
l = Math.ceil((l + r) / 2)
// 2.1 l=1
// 3.1 l=2
// 4.1 l=2
// 5.1 l=3
} else {
r = Math.floor((l + r) / 2)
// 3.2 r=2
// 4.2 r=2
// 5.2 r=4
// 5.3 r=3
}
}
}; Round 2
I took a break, then came back and thought about the problem for a while, sketching some ideas with paper and pen.
I eventually convinced myself of an algorithm, then sat down to solve the problem again.
Here are the results:
/* return index of any peak element
I've been thinking about this and think I have a good strategy now.
high level plan:
- maintain left & right boundaries & candidate peak
- candidate peak is always the largest value I've seen
- check next value based on which boundary is further from the peak
- if the new value is higher, its our new candidate peak; adjust the boundary we moved away from to be our previous peak
- if the new value is lower, it's a new boundary
- repeat until both boundaries equal the candidate peak
[4:22] done planning
[12:58] done writing initial implementation
[39:52] done testing, fixing bugs, submitted, success on first try
Bugs found during testing:
- Needed to adjust boundaries by an additional 1 to avoid infinite loop
- needed to swap Math.floor vs Math.ceil to guarantee search progress in the correct direction
*/
function findPeakElement(nums: number[]): number {
// 1. nums=[1]
// 2. nums=[1,2]
// 3. nums=[2,1]
// 4. nums=[1,3,2,1,0]
let p = 0
for (let l = 0, r = nums.length - 1; l !== r;) {
// 2.1 l=0 p=0 r=1
// 3.1 l=0 p=0 r=1
// 4.1 l=0 p=0 r=4
// 4.2 l=0 p=2 r=4
// 4.3 l=0 p=1 r=2
// 4.4 l=1 p=1 r=2
const P = nums[p]
// 2.1 P=1
// 3.1 P=2
// 4.1 P=1
// 4.2 P=2
// 4.3 P=3
// 4.4 P=3
if (p - l >= r - p) {
// search left
const m = Math.floor((l + p) / 2)
// 4.2 m=1
// 4.3 m=0
const M = nums[m]
// 4.2 M=3
// 4.3 M=1
if (M >= P) {
r = p
// 4.2 r=2
p = m
// 4.2 p=1
} else {
l = m + 1
// 4.3 l=1
}
} else {
// search right
const m = Math.ceil((p + r) / 2)
// 2.1 m=1
// 3.1 m=1
// 4.1 m=2
// 4.4 m=2
const M = nums[m]
// 2.1 M=2
// 3.1 M=1
// 4.1 M=2
// 4.4 M=2
if (M >= P) {
l = p
// 2.1 l=0
// 4.1 l=0
p = m
// 2.1 p=1
// 4.1 p=2
} else {
r = m - 1
// 3.1 r=0
// 4.4 r=1
}
}
}
return p
// 1. return 0
// 2. return 1
// 3. return 0
// 4. return 1
};