Sunday, February 4, 2018

Leetcode solution 621 Task Scheduler

Problem Statement 

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
  1. The number of tasks is in the range [1, 10000].
  2. The integer n is in the range [0, 100].
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

  1. Array is not sorted, could it be sorted?
  2. Task is a finite set, 26 maximum. 
  3. It is about extreme value (min value in this case), can Dynamic Programming (DP) be applied?
  4. DP seems cannot be applied here, it is very hard to come up with a mathematical induction function, even though there is a solution by coming up with a math formula, but it is very hard to come up with this in a real interview session.  
  5. Can we do any binary search hear, nope
  6. Hmm... it seems maybe we can be greedy here, doing it in a round robin way. Schedule the largest job first, then 2nd largest job, then 3rd largest job until the internal is met. Note, we have to always apply the largest job as soon as possible, for example, if we have a test case [A, A, A, A, A, B, C, D, E] and interval n is 2, if we are doing strict round robin, it would be A, B, C, D, E, A, idle, idle, A, idle, idle, A, idle, idle, A -> 15 cycle, where we should really apply A as soon as possible, so it becomes A, B, C, A, D, E, A, idle, idle, A, idle, idle, A -> 13 cycle.

Solutions

Sort after every iteration 

Given the greedy sort, we want to always apply the largest job first, so we should sort the jobs first (job name does not matter), after meeting the interval requirement, sort the array again and repeat by applying the largest job first, then 2nd largest etc.

Use priority queue (max heap) 

Instead of sorting after every iteration, we can use a max heap to always pop out the largest element, and instead of sort O(NlgN) on every iteration, it will just be O(lgN) to heaptify, even though N is fixed 26 on size.

References

Monday, January 15, 2018

Leetcode solution 162 Find Peak Element

Problem Statement 

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Problem link

You can find the detailed video tutorial here:

A few edge cases to think about

  • Null array, one element array 
  • Strictly increasing array 
  • Strictly decreasing array 
  • Array with all same element (won't happen in this case)

Here is an example:


Code Sample

A few follow up
  • Use first and last element as negative infinite (Solution: just skip the first and last then)
  • There could be same elements and they can be equal. (Solution: same thing, just need to change your comparison logic in this case)

References

  • https://www.youtube.com/watch?v=NFvAD5na5oU
  • https://www.tangjikai.com/algorithms/leetcode-162-find-peak-element
  • https://leetcode.com/problems/find-peak-element/solution/