Facebook Interview Question
Country: United States
Interview Type: Phone Interview
int find_min_intervals(const vector<int>& iv, int cool){
vector<int> out;
int ii = 0;
unordered_map<int, int> hmap;
unordered_map<int, int>::iterator mit;
while(ii < iv.size())
{
mit = hmap.find(iv[ii]);
if(mit == hmap.end())
{
hmap.insert(pair<int, int>(iv[ii], out.size()));
out.push_back(iv[ii]);
ii++;
}
else
{
if(out.size() - mit->second > cool)
{
mit->second = out.size();
out.push_back(iv[ii]);
ii++;
}
else
{
out.push_back(-1);// represents gaps
}
}
}
return out.size();
}
Time is O(n). Space is O(k) k is the number of task.
int[] arr = {1, 1, 2, 1, 2};
int cooldown = 2;
int currentPos = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
int pos = map.get(arr[i]);
if (pos + cooldown + 1 - currentPos > 0) {
for (int k = 0; k < pos + cooldown + 1 - currentPos; k++) {
System.out.print("_ ");
}
currentPos = currentPos + cooldown - 1;
}
}
System.out.print(arr[i] + " ");
map.put(arr[i], currentPos);
currentPos++;
}
System.out.println();
If n is the number of tasks, and k is the cooldown, then we have an O(k) storage and O(n) time solution.
The idea is to slide a window across the array of tasks. We only care about tasks at most k away from identical tasks, so the maximum size of our window can only be k.
As we're sliding the window, if we encounter a new task that already exists in the window, we calculate how much cooldown we'll need before entering this new task into the window (call this calculated value delta).
In order to add this new task into the window, it is easy to understand that we must delete the older but identical task from the window. However, notice that after we add this new task, we need to decide whether to _also_ delete tasks that occur _after_ this deleted task. Turns out we need to delete delta tasks.
To implement this special window, we use just a map and a pointer (b).
# Note: Please use Python 3.6
def solution(a, k):
n = len(a)
if n <= 1:
return n
m = {a[0]: 0}
c = 1
b = 0
for i in range(1, n):
x = a[i]
if x in m:
delta = (k + 1) - (i - m[x])
for p in range(delta + 1):
del m[a[b + p]]
b += delta + 1
c += delta
# Put x in m
m[x] = i
# Increment c
c += 1
# The maximum size of m is k
if len(m) == k + 1:
# Delete the beginning from m
del m[a[b]]
# Increment b
b += 1
### debug ###
# print(f'i: {i}')
# print(f'a[i]: {x}')
# print(f'c: {c}')
# print(f'm: {m}')
# print(f'b: {b}')
# print()
return c
def test_runner(ans, func, *args, **kwargs):
attempt = func(*args, **kwargs)
print(attempt)
assert attempt == ans
a = [1, 2, 3, 1, 2, 1, 4, 5, 1]
k = 3
test_runner(13, solution, a, k)
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = 3
test_runner(9, solution, a, k)
With Python
def calculateTasksCooldown(tasks, wait):
# to calculate the sequence ordering
seq = []
# to keep a record of a task and its weight
record = {}
# initialize time unit counter by 0
time = 0
for t in tasks:
if t not in record:
# add a new task to sequence
seq.append(t)
# add weight of task as per current time
record[t] = time + wait
else:
# if task weight is lapsed
if record[t] == time:
seq.append(t)
else:
# else find the time units needed
delta = record[t] - time
# append "_" to sequence for needed time units
for i in range(delta+1):
seq.append("_")
# also increase the time unit counter
time = time + 1
# after the weight for earlier identical task is lapsed, add next to sequence
seq.append(t)
# update the weight for task in process as per current time
record[t] = time + wait
time += 1
print "Total time: ", time
print "Sequence: " + " ".join(str(item) for item in seq)
if __name__ == "__main__":
calculateTasksCooldown([1,2,2,1,1,2,2], 3)
calculateTasksCooldown(["A", "B", "A", "D"], 3)
public static String coolDownAlt(int[] vals) {
List<Integer> buff = new ArrayList<Integer>();
buff.add(vals[0]); // 1
int c = 2;
String out = vals[0] + " "; // 1
for (int i = 1; i < vals.length; i++) {
System.out.println(out);
boolean isPrinted = false;
while (c > 0) {
if (buff.contains(vals[i])) {
out += " _ "; // 1 _ _
c--;
} else {
buff.add(vals[i]);
out += " " + vals[i];
isPrinted = true;
c--;
if (i < vals.length - 2)
i++;
}
}
if (c == 0) {
c = 2;
if (!isPrinted) {
for(int bi : buff) {
out += " " + bi;
}
}
buff.clear();
buff.add(vals[i]);
}
}
return out;
}
public static String coolDownAlt(int[] vals) {
List<Integer> buff = new ArrayList<Integer>();
buff.add(vals[0]); // 1
int c = 2;
String out = vals[0] + " "; // 1
for (int i = 1; i < vals.length; i++) {
System.out.println(out);
boolean isPrinted = false;
while (c > 0) {
if (buff.contains(vals[i])) {
out += " _ "; // 1 _ _
c--;
} else {
buff.add(vals[i]);
out += " " + vals[i];
isPrinted = true;
c--;
if (i < vals.length - 2)
i++;
}
}
if (c == 0) {
c = 2;
if (!isPrinted) {
for(int bi : buff) {
out += " " + bi;
}
}
buff.clear();
buff.add(vals[i]);
}
}
return out;
}
count the different type of tasks, maintain a vector of number of tasks for the last run. time and space complexity O(tasks)
int neededTime(vector<int>tasks, int cooldown)
{
int slots = 0;
int count = 0;
int n = tasks.size();
for (int i = 0; i < n; i++)
{
if (tasks[i] > count)
count = tasks[i];
}
vector<int> last(count,0);
for (int i = 0; i < n; i++)
{
slots++;
int task = tasks[i]-1;
if (last[task] == 0 || slots - last[task] > cooldown)
last[task] = slots;
else
slots = last[task] = last[task] + cooldown+1;
}
return slots;
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class OptimumScheduler {
public static void main(String[] args){
int testcase[] = {1,1,2,1,2};
int cooldown = 2;
List<Integer> schedule = scheduleMinimizeclockTime(testcase, cooldown);
System.out.println("schedule " + schedule);
}
/**
* Assumptions:
* 1) tasks need to be executed in order
* 2) cooldown is non negative
*/
public static List<Integer> scheduleMinimizeclockTime(int[] tasks, int cooldown) {
Map<Integer,Integer> earliestEligibleStartTime = new HashMap<Integer, Integer>();
int t = 0;
List<Integer> schedule = new LinkedList<Integer>();
for (int task : tasks){
if (earliestEligibleStartTime.containsKey(task)){
int treq = earliestEligibleStartTime.get(task);
while (t < treq) {
schedule.add(-1);
t++;
}
}
schedule.add(task);
earliestEligibleStartTime.put(task, t + cooldown + 1);
t++;
}
return schedule;
}
}
Time is O(n). Space is O(k) k is the number tasks
- T N January 03, 2018public void print_min_intervals(int[] task, int cooldown) { int currentPos = 0; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < task.length; i++) { if (map.containsKey(task[i])) { int pos = map.get(task[i]); if (pos + cooldown + 1 - currentPos > 0) { for (int k = 0; k < pos + cooldown + 1 - currentPos; k++) { System.out.print("_ "); } currentPos = currentPos + cooldown - 1; } } System.out.print(task[i] + " "); map.put(task[i], currentPos); currentPos++; } System.out.println(); }