Twitter Interview Question Software Engineers
Country: United States
public int getTotalWaitTime (String s, int k){
int total = 0 ;
HashMap<Character,Integer> map = new HashMap<> ();
for (int i = 0 ; i < s.length() ; ++i) {
if (!map.containsKey(s.charAt(i))) {
map.put(s.charAt(i), i);
total++;
} else {
total += k - (i - map.get(s.charAt(i)) - 1) + 1 ;
map.put(s.charAt(i), i);
}
}
return total ;
}
In java. O(n) runtime complexity and O(t) memory where T is the wait time
public static int getRunTime(char[] tasks, in waitTime){
if(tasks == null){
throw new NullPointerException();
}
LinkedHashMap<Character, Integer> charToExecTime = new LinkedHashMap<Character, Integer>();
int time = 0;
for(char c : tasks){
//compute the timing for each task
Integer lastTime = charToExecTime.get(c);
if(lastTime != null && lastTime + waitTime > time){
time = lastTime + waitTime;
}
charToExecTime.put(c, time);
time++;
//clear out the unnecessary tasks
ArrayList<Character> remove = new ArrayList<Character>();
for(Entry<Character, Integer> entry : charToExecTime.entrySet()){
if(entry.getValue() >= time){
remove.add(entry.getValue());
}
else{
break;
}
}
for(Character c : remove){
charToExecTime.remove(c);
}
}
return time;
}
public static int delayedTasks(String[] tasks, int k) {
Map<String, Integer> waitMap = new HashMap<>();
int totalTime = 0;
for (String task : tasks) {
// Time waited at the task latest occurrence
Integer occurrenceTime = waitMap.get(task);
if (occurrenceTime != null) {
// Time difference since the last occurrence
int timePassed = totalTime - occurrenceTime;
// Difference compared to the given delay threshold
int waiting = k - timePassed;
if (waiting > 0) {
totalTime += waiting;
}
}
// Linear time increase
totalTime++;
waitMap.put(task, totalTime);
}
return totalTime;
}
I think this might work.
public static int runningTime(char[] tasks, int k){
if(tasks.length==0){
throw new IllegalArgumentException("No tasks declared");
}
Map<Character,Integer> runningTasks = new HashMap<>();
int currentTime = 0;
for(char t : tasks){
if(runningTasks.containsKey(t)){
while((runningTasks.get(t)-currentTime)>=0){
currentTime++;
}
}
runningTasks.put(t, currentTime+k);
currentTime++;
}
return currentTime;
}
O(n) space and O(n) time
public static int runningTime(char[] tasks, int k){
if(tasks.length==0){
throw new IllegalArgumentException("No tasks declared");
}
Map<Character,Integer> runningTasks = new HashMap<>();
int currentTime = 0;
for(char t : tasks){
if(runningTasks.containsKey(t)){
while((runningTasks.get(t)-currentTime)>=0){
currentTime++;
}
}
runningTasks.put(t, currentTime+k);
currentTime++;
}
return currentTime;
}
public int days(String letters,int k){
Map<Character,Integer> hashmap=new HashMap<Character,Integer>();
char[] letter=letters.toCharArray();
int sum=0;
for (int i=0;i<letter.length;i++){
if (hashmap.containsKey(letter[i])){
if (sum-hashmap.get(letter[i])<k){
sum=sum+k+1-(sum-hashmap.get(letter[i]));
}
else
sum=sum+1;
}
else
sum=sum+1;
hashmap.put(letter[i], sum);
}
return sum;
}
#include <bits/stdc++.h>
using namespace std;
int countTime(string s, int k){
int n = s.size(), cnt = 0;
int a[26];
memset(a, -1, sizeof a);
for (int i = 0; i < n; i++){
int pos = s[i] - 'A';
if (a[pos] == -1) a[pos] = cnt++;
else{
if (a[pos] + k < cnt) a[pos] = cnt++;
else {
cnt += k - ((cnt-1) - a[pos])+1;
a[pos] = cnt -1;
}
}
}
return cnt;
}
int main(){
cout << countTime("ABCD", 3) << endl;
cout << countTime("ABAD", 3) << endl;
cout << countTime("AAAA", 3) << endl;
cout << countTime("ABCACBDA", 4) << endl;
return 0;
}
For 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)
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)
#include <stdio.h>
#include <stdbool.h>
#include <queue>
#include <map>
std::queue<char> history_queue;
std::map<char,bool> history_map;
void my_enqueue(char c) {
history_queue.push(c);
history_map[c]=true;
printf(" %c", c);
}
void my_dequeue() {
char c = history_queue.front();
history_queue.pop();
history_map[c]=false;
}
int computeRuntime(const char *tasks, int cooldown) {
/* queue */
int output=0;
while (!history_queue.empty())
my_dequeue();
for (int i=0; i<cooldown; i++)
my_enqueue('_');
while (*tasks) {
if (history_map[*tasks]) {
my_enqueue('_');
} else {
my_enqueue(*tasks);
tasks++;
}
output++;
my_dequeue();
}
printf("\noutput=%d\n", output);
return output;
}
int main() {
const char *b = "AAABCABC";
computeRuntime(b, 2);
const char *a = "ABCABC";
computeRuntime(a, 3);
}
root ~/temp/test ./a.out
_ _ A _ _ A _ _ A B C A B C
output=12
_ _ _ A B C _ A B C
output=7
#include <stdio.h>
#include <stdbool.h>
#include <queue>
#include <map>
std::queue<char> history_queue;
std::map<char,bool> history_map;
void my_enqueue(char c) {
history_queue.push(c);
history_map[c]=true;
printf(" %c", c);
}
void my_dequeue() {
char c = history_queue.front();
history_queue.pop();
history_map[c]=false;
}
int computeRuntime(const char *tasks, int cooldown) {
/* queue */
int output=0;
while (!history_queue.empty())
my_dequeue();
for (int i=0; i<cooldown; i++)
my_enqueue('_');
while (*tasks) {
if (history_map[*tasks]) {
my_enqueue('_');
} else {
my_enqueue(*tasks);
tasks++;
}
output++;
my_dequeue();
}
printf("\noutput=%d\n", output);
return output;
}
int main() {
const char *b = "AAABCABC";
computeRuntime(b, 2);
const char *a = "ABCABC";
computeRuntime(a, 3);
}
root ~/temp/test ./a.out
_ _ A _ _ A _ _ A B C A B C
output=12
_ _ _ A B C _ A B C
output=7
#include <stdio.h>
#include <stdbool.h>
#include <queue>
#include <map>
std::queue<char> history_queue;
std::map<char,bool> history_map;
void my_enqueue(char c) {
history_queue.push(c);
history_map[c]=true;
printf(" %c", c);
}
void my_dequeue() {
char c = history_queue.front();
history_queue.pop();
history_map[c]=false;
}
int computeRuntime(const char *tasks, int cooldown) {
/* queue */
int output=0;
while (!history_queue.empty())
my_dequeue();
for (int i=0; i<cooldown; i++)
my_enqueue('_');
while (*tasks) {
if (history_map[*tasks]) {
my_enqueue('_');
} else {
my_enqueue(*tasks);
tasks++;
}
output++;
my_dequeue();
}
printf("\noutput=%d\n", output);
return output;
}
int main() {
const char *b = "AAABCABC";
computeRuntime(b, 2);
const char *a = "ABCABC";
computeRuntime(a, 3);
}
root ~/temp/test ./a.out
_ _ A _ _ A _ _ A B C A B C
output=12
_ _ _ A B C _ A B C
output=7
We can use a hashtable to record last complete time of every task:
- uuuouou September 14, 2015def getCompleteTime(tasks, waitBetweenRepeatedTask): time = 0 # clock record = {} # record[t] represents last time t is done for t in tasks: if t in record and time - record[t] < waitBetweenRepeatedTask: # wait the cooldown time = record[t] + waitBetweenRepeatedTask # execute t time += 1 # update record record[t] = time return time # tests tasks = [1, 2, 3, 4] k = 3 print(getCompleteTime(tasks, k)) tasks = [1, 2, 1, 4] k = 3 print(getCompleteTime(tasks, k)) tasks = [1, 1, 1, 1] k = 3 print(getCompleteTime(tasks, k)) tasks = [1, 2, 3, 1, 3, 2, 4, 1] k = 4 print(getCompleteTime(tasks, k))