Learn and practice the Merge Intervals and K-way Merge patterns to solve coding interview problems.

Educative-77 in C++: Accelerate Your Coding Interview Prep

Many information processing and decision-support problems require us to merge information coming from multiple sources to build up a global picture of a situation before making some business decisions. This module will help us understand and deploy two common coding patterns used to merge lists of structurally homogeneous data to solve hard problems that we encounter, for example, in scheduling, social media applications, and I/O algorithms.

Fusion

What's the minimum number of units of time if the following values are given as input?

Tasks = [A, A, A, B, B, C, C]

n = 1

What’s the minimum number of units of time if the following values are given as input?
Tasks = [A, A, A, B, B, C, C]
n = 1

Choose the correct final schedule if the following values are given as input.

Tasks = [D, A, F, B, G, E, C]

n = 5

Choose the correct final schedule if the following values are given as input.
Tasks = [D, A, F, B, G, E, C]
n = 5

What's the minimum number of units of time if the following values are given as input?

Tasks = [A, A, C, C, C, B, E, E, E]

n = 2



What’s the minimum number of units of time if the following values are given as input?
Tasks = [A, A, C, C, C, B, E, E, E]
n = 2

Task Scheduler 

Task Scheduler

int LeastInterval(const std::vector<char>& tasks, int n) {
 
 // Replace this placeholder return statement with your code
 return 0;
}

Help me debug only the function Task Scheduler . . I don't need the corrected code.I don't want explanations or code review. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Don't give me the corrected code. . If yes, then Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Your current task is to review only the LeastTime function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function LeastTime. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, Answer the following questions: Is the Knowing What to Track pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function LeastTime. While calculating time complexity, include the time complexity of built-in C++ functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function LeastTime. While calculating space complexity, include the space complexity of built-in C++ functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The Answer should be to the point and in a few lines

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        def least_time(tasks, n):
    
            frequencies = {}

            for t in tasks:
                frequencies[t] = frequencies.get(t,0) + 1

            frequencies = dict(sorted(frequencies.items(), key=lambda x:x[1]))
            max_freq = frequencies.popitem()[1]
            idle_time = (max_freq - 1) * n

            while frequencies and idle_time > 0:
                idle_time -= min(max_freq - 1, frequencies.popitem()[1])
            idle_time = max(0, idle_time)

            return len(tasks) + idle_time




        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = [] 
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(least_time(self.__inputs[0] , self.__inputs[1]))

        if json.dumps(least_time(self.__inputs[0] , self.__inputs[1])) == json.dumps(self.__actual_outputs[0]):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result






#include <iostream>
#include <vector>
#include "main.cpp"

int driver(std::vector<string>& s, int n) {
 // Convert vector of strings to array of characters
 vector<char> charArray(s.size());
 for (int i = 0; i < s.size(); i++) {
 charArray[i] = s[i][0];
 }


 int res = LeastInterval(charArray, n);
 return res;
}

task_scheduler.yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : ['A','A','B','B']
    - 2 : 2
    output: 
    - 1 : 5
  - name: "testcase 2"
    inputs:
    - 1: [A, A, A, B, B, C, C]
    - 2: 1
    output:
    - 1 : 7
  - name: "testcase 3"
    inputs:
    - 1: ['S','I','V','U','W','D','U','X']
    - 2: 0
    output:
    - 1 : 8
  - name: "testcase 4"
    inputs:
    - 1: ['A','K','X','M','W','D','X','B','D','C','O','Z','D','E','Q']
    - 2: 3
    output:
    - 1 : 15
  - name: "testcase 5"
    inputs:
    - 1: ['A','B','C','O','Q','C','Z','O','X','C','W','Q','Z','B','M','N','R','L','C','J']
    - 2: 10
    output:
    - 1 : 34

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 def is_valid_1d_array(arr):

 if arr == None:
 return False
 if not isinstance(arr,list):
 return False
 if any(x==None or isinstance(x,bool) for x in arr):
 return False
 return True





 from string import ascii_uppercase
 LETTER_BANK=list(ascii_uppercase)
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not isinstance(self.__inputs[0],list):
 self.store_result ("input 1 should be a list", ValidationFunction.FAIL)
 elif not is_valid_1d_array(self.__inputs[0]):
 self.store_result ("Invalid input array", ValidationFunction.FAIL)


 elif not isinstance(self.__inputs[1],int):
 self.store_result("input 2 should be an integer", ValidationFunction.FAIL)

 elif not (0 <=self.__inputs[1] <= 100):
 self.store_result("'n' should be in the range [0,100]", ValidationFunction.FAIL)
 
 elif not all(isinstance(x,str) for x in self.__inputs[0]):
 self.store_result("Input array should contain only english alphabet characters", ValidationFunction.FAIL)
 

 elif not all(x in LETTER_BANK and type(x)==str and len(x)==1 for x in self.__inputs[0]):
 self.store_result("'tasks' should contain only single uppercase English letters", ValidationFunction.FAIL)

 elif not (1 <= len(self.__inputs[0]) <= 10**3):
 self.store_result("Length of the input array should be between 1 and 10^3", ValidationFunction.FAIL)

 

 
 else:
 self.store_result("", ValidationFunction.PASS)

Merge Intervals

K-way Merge

Conclusion

Task Scheduler

Statement

Examples

Understand the problem

Figure it out!

Try it yourself