[Interview type questions] Task sequence arragnement

Given a task sequence and the cool down time(k), rearrange the task sequence such that the execution time is minimal.

Solution:

 public static void main(String[] args) {
  char[] task = findBestTaskArrangement(String.valueOf("AAABBB").toCharArray(), 2);
  System.out.println(task);
  System.out.println("Total time: " + computeTatalTaskTime(task, 2));
  // ABABAB
  // Total time:8
 }
 
 public static char[] findBestTaskArrangement(char[] tasks, int k) {
  int n = tasks.length;
  Map<Character, Integer> map = new HashMap<>();
  for (char task : tasks) {
   map.put(task, map.getOrDefault(task, 0) + 1);
  }

  PriorityQueue<Task> queue = new PriorityQueue<>(new Comparator<Task>() {

   @Override
   public int compare(Task a, Task b) {
    return b.frequency - a.frequency;
   }
  });

  for (Map.Entry<Character, Integer> entry : map.entrySet()) {
   queue.offer(new Task(entry.getKey(), entry.getValue()));
  }
  
  tasks = new char[n];
  int i = 0;
  while (!queue.isEmpty()) {
   int c = 0;
   List<Task> nextRoundTask = new ArrayList<>();
   while(c++ < k && !queue.isEmpty()) {
    Task task = queue.poll();
    task.frequency--;
    // Locate the next empty slot
    tasks[i++] = task.id;
    if (task.frequency > 0)
     nextRoundTask.add(task);
   }
   for (Task task : nextRoundTask) {
    queue.offer(task);
   }
  }

  return tasks;
 }

 // helper class
 public static class Task {
  char id;
  int frequency;

  Task(char i, int f) {
   id = i;
   frequency = f;
  }
 }

 public static int computeTatalTaskTime(char[] tasks, int k) {
  HashMap<Character, Integer> taskLastTimeMap = new HashMap<>();
  int currTime = 0;
  for (char task : tasks) {
   if (taskLastTimeMap.containsKey(task)) {
    int exceptedTime = taskLastTimeMap.get(task) + k + 1;
    if (exceptedTime > currTime) {
     currTime = exceptedTime;
    } else
     currTime++;
   } else {
    currTime++;
   }
   taskLastTimeMap.put(task, currTime);
  }
  return currTime;
 }

[Interview type questions] MinQueue

Leetcode had a question about min stack, but there is no question about min queue. In this article, I wrote a simple one for min queue.

Solution:

 public static void main(String[] args) {
  MinQueue queue = new MinQueue();
  // Input 3 -> 1 -> 4 -> 2
  queue.offer(3).offer(1).offer(4).offer(2);
  //  0 0 0 1 1 1
  while(queue.isEmpty() == false) {
   System.out.println(queue.getMin());
   queue.poll();
  }
  // Output should be 1 -> 1 -> 2 -> 2
 }
 
 static class MinQueue {
  private Queue<Integer> mQueue = new LinkedList<>();
  private Deque<Integer> mMinDeque = new ArrayDeque<>();
  
  MinQueue offer(int val) {
   int min = val;
   while(!mMinDeque.isEmpty() && mMinDeque.getLast() > val) {
    mMinDeque.pollLast();
    min = val;
   }
   int size = mQueue.size() - mMinDeque.size();
   for (int i = 0; i <= size; i++) {
    mMinDeque.addLast(min);
   }
   mQueue.offer(val);
   return this;
  }
  
  int poll() {
   mMinDeque.poll();
   return mQueue.poll();
  }
  
  boolean isEmpty() {
   return mQueue.isEmpty();
  }
  
  int getMin() {
   return mMinDeque.peek();
  }
 }       

Given a million points (x, y), give an O(n) solution to find the k's points closest to (0, 0).

Use quick select/partial sorting to resolve.
Solution:

 static class Point {
  int x;
  int y;

  public Point(int x, int y) {
   this.x = x;
   this.y = y;
  }

  public double getDistFromCenter() {
   return Math.sqrt(x * x + y * y);
  }
 }

 public static void main(String[] args) {
  Point[] points = new Point[7];
  points[0] = new Point(0, 0);
  points[1] = new Point(1, 7);
  points[2] = new Point(2, 2);
  points[3] = new Point(2, 2);
  points[4] = new Point(3, 2);
  points[5] = new Point(1, 4);
  points[6] = new Point(1, 1);
  int k = 3;
  qSelect(points, k - 1);
  for (int i = 0; i < k; i++) {
   System.out.println("" + points[i].x + "," + points[i].y);
  }
  // Output will be
  //        0,0
  //        1,1
  //        2,2
 }

 // in-place qselect and zero-based
 static void qSelect(Point[] points, int k) {
  int l = 0;
  int h = points.length - 1;
  while (l <= h) {
   int partionInd = partition(l, h, points);
   if (partionInd == k) {
    return;
   } else if (partionInd < k) {
    l = partionInd + 1;
   } else {
    h = partionInd - 1;
   }
  }
 }

 static int partition(int l, int h, Point[] points) {
  // Random can be better
  // int p = l + new Random.nextInt(h - l + 1);
  int p = l + (h - l) / 2;
  int ind = l;
  swap(p, h, points);
  Point comparePoint = points[h];
  for (int i = l; i < h; i++) {
   if (points[i].getDistFromCenter() < comparePoint.getDistFromCenter()) {
    swap(i, ind, points);
    ind++;
   }
  }
  swap(ind, h, points);
  return ind;
 }

 static void swap(int i, int j, Point[] points) {
  Point temp = points[i];
  points[i] = points[j];
  points[j] = temp;
 }