March 10, 2022
Here is the link.
C# | Design a deque | Review Array - Subarray | 2022 March
March 10, 2022
Introduction
I plan to spend two weeks to prepare for Meta phone screen. I had three onsite interview from Meta in the row from 2019 to 2021, and this time I have to take another phone screen again. I did a few hours research on Leetcode.com, and kept blogging those case study of FB, Google, MSFT interview, and then I found the book through one of sharings. I like to go through those patterns - book chapter: Part VII Problem-patterns, and review all those algorithms. Here is the link of the book. I am reviewing Array - subarray algorithms, here is the list written in the book chapter.
C# | LinkedList | Deque data structure
It is hard for me to review the algorithm using deque. I think that I can do my best, and make sure that deque will work perfectly with test case [3, -2, 5], target = 4.
Time complexity: O(N)
- Using O(N) time to calculate prefix sum;
- C# LinkedList - a deque
- What to remove - PK, remove those ones impossible to be smallest one from the end
- What to remove - PK, remove those ones impossible to be smallest one from the beginning.
- Study the test case [3, -2, 5]
- Read more carefully about discuss post, how deque solve the problem. Here is the link.
Case study: [3, -2, 5], K = 4 | Deque
prefix sum: {3, 1, 6], K = 4, minimum length is 1, start and end index = 2
How to find it?
put index = 0 onto deque
iterate index = 1, deque size is 1, skip;
I think that working on this simple test case is best way to understand the design.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _862_minimum_subarray_at_least_k
{
class Program
{
static void Main(string[] args)
{
var minimumLength = ShortestSubarray(new int[]{3, -2, 5}, 4);
}
/// <summary>
/// code review:
/// 1. Read the book chapter
/// https://github.com/liyin2015/python-coding-interview
/// Part VII Problem-patterns
/// Page 551 algorithm 862
/// 2. Read the discuss post
/// https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/189039/Detailed-intuition-behind-Deque-solution
/// 3. Work on test case and test C# code
/// Time complexity: O(N)
/// </summary>
/// <param name="A"></param>
/// <param name="K"></param>
/// <returns></returns>
public static int ShortestSubarray(int[] A, int K)
{
if (A == null || A.Length == 0)
return -1;
var length = A.Length;
var prefix = new int[length + 1]; // change from length to length + 1 since failed [2, -1, 2]
// using O(N) time to build a prefix sum of the array
prefix[0] = 0;
for (int i = 0; i < length; i++)
{
prefix[i + 1] = prefix[i] + A[i];
}
var shortest = length + 1;
// store index of the array into deque
var linkedList = new LinkedList<int>();
// three operations of deque
// remove_front - it is impossible for the start point
// append_back - it is possible for new start point
// remove_back - it is impossible for the start point
// check current index and first one in dequeue - prefix difference vs K
// test case: [2, -1, 2]
for (int i = 0; i < prefix.Length; i++)
{
var current = prefix[i];
// step 1: Remove from deque - end side
// argue that: what is inside deque? - possible ranges
while (linkedList.Count > 1 && prefix[linkedList.Last.Value] >= current)
{
linkedList.RemoveLast();
}
// step 2: Add to deque
linkedList.AddLast(i);
// step 3: remove from the start of deque
//
while (linkedList.Count > 1 && (current - prefix[linkedList.First.Next.Value] >= K))
{
linkedList.RemoveFirst();
}
// step 4: Compare to shortest range
if (i > 0 && (current - prefix[linkedList.First.Value] >= K))
{
shortest = Math.Min(shortest, i - linkedList.First.Value);
}
}
return shortest == length + 1 ? -1 : shortest;
}
}
}
