MAQ Interview Questions
MAQ Software was founded in 2000 as a digital marketing and analytics firm. It has a variety of interests in technology, energy, retail, and healthcare. Artificial Intelligence, Data Analytics, and the Cloud are the three main sectors it serves. "Focus" and "Execution" are the two simple ideas that the company follows for success. MAQ Software has been in partnership with Microsoft for sixteen years and considers itself a Microsoft preferred supplier in data analytics, application development, and data platforms.
It is a great organization for freshers and experienced software professionals. You will gain the skills to learn new things by working in this organization and also the opportunity to gain knowledge from other sources. You will face a bit of pressure, but you will love it as the same will be valuable in your evaluation of other options in the IT industry.
MAQ Recruitment Process
1. Interview Process
MAQ Software conducts a selection process every year to pick new candidates. These selection rounds are as follows:
 Written Test
 Technical Interview
 Technical + HR Interview
The aptitude test in mathematics and coding is difficult, but it is also divided into two parts: basic math and basic coding. This section will be easy to pass, as it will have straightforward questions. Once cleared, you will go for the technical interview and the HR interview once you clear this test.
2. Interview Rounds
 Written Test: The 60 minutes for the written exam is divided into two parts. There is a negative mark on the paper and the aptitude section contains questions from the categories that include percentages, probability, combinations, series, algebra, time, speed, and distance, among others. The arithmetic, profit, and loss questions in the general coding section are from the C, C++, Java, and DS categories. The question paper is straightforward but of medium difficulty. Candidates who pass the written test will be eligible for the next round. The MAQ Software Company may make changes to the test at any time.
 Technical Interview: In these technical interviews, you must demonstrate your employability qualities as well as your technical knowledge in order to pass. You will also be tested on your interpersonal skills and ability to comprehend the questions. Be genuine and knowledgeable when composing your resume. After completing these challenges, you will have to appear for the HR test, and it will be your job to be evaluated your personality.
 Technical + HR Interview: The previous HR rounds were pretty straightforward, although the technical ones were not. He will probably only ask you questions like Why do you want to work for us? and similar questions, although you will still be asked questions like that. You will be successful in the technical interviews after which you have a 95% chance of being hired by MAQ Software, although you will be ready to start work straight away.
MAQ Technical Interview Questions: Freshers and Experienced
1. Rotate the array by k steps to the right, considering the array as nonnegative.
Example 1:
 Input: nums = [1,2,3,4,5,6,7], k = 3
 Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
 Input: nums = [1,100,3,99], k = 2
 Output: [3,99,1,100]
Explanation:
rotate 1 steps to the right: [99,1,100,3]
rotate 2 steps to the right: [3,99,1,100]
Solution:
In the beginning, start with zero and place it in its correct position, then place the original element at x in its correct position. This process will naturally end at the place you started. We must create a sequential order for all the elements. We may obviously put all the elements into a line until we reach the number n.
public void rotate(int[] a, int k) {
int n = a.length, count = 0;
for(int i=0; count < n; i++){
int j = i, tmp = a[j];
do{
int hold = a[ (j+k) % n];
a[ (j+k) % n] = tmp;
++count;
tmp = hold;
j = (j+k) % n;
}while(j != i);
}
}
2. We want to sort the arrays nums inplace so that objects of the same colour are adjacent, with the colours in order red, white, and blue.
To solve this problem, you must use the integers 0, 1, and 2 to represent the colours red, white, and blue, respectively.
Example 1:
 Input: nums = [2,0,2,1,1,0]
 Output: [0,0,1,1,2,2]
Example 2:
 Input: nums = [2,0,1]
 Output: [0,1,2]
Solution:
Consider threepointers low = 0, mid = 0, high = nums.size()  1. The algorithm ensures that at any point, every element before low is 0, every element after high is 2, and every element in between are either 0, 1 or 2. That is, unprocessed. We will use mid to traverse and check the array elements in order that nums[mid] == 0 when nums[low] != 0 and nums[mid] != 1 and nums[mid]++ when mid++.
class Solution {
public void sortColors(int[] nums)
{
int low=0,mid =0,high = nums.length1;
int temp;
while(mid<=high){
if(nums[mid]==0)
{
temp=nums[low];
nums[low]=nums[mid];
nums[mid]=temp;
low++;
mid++;
}
else if(nums[mid]==1)
{
mid++;
}
else if(nums[mid]==2)
{
temp=nums[mid];
nums[mid]=nums[high];
nums[high]=temp;
high;
}
}
}
}
3. What is the difference between JAVA and C++?
C++ uses a compiler, whereas Java uses an interpreter and a compiler. C++ is able to offer both operator overloading and method overloading, whereas Java only provides method overloading. C++ supports new and deleted statements in order to manage objects manually rather than relying on automatic garbage collection, whereas Java has a builtin garbage collection mechanism. A structure can be created in C++ whereas Java cannot.
4. What is BST? Give a reallife example.
A selfbalancing BST (like the AVL and RedBlackTrees) keeps its height constant by balancing itself. These selfbalancing BSTs maintain their heights as Log(n), which is O(log n). Other operations that become Log(n) include searching, inserting, deleting, flooring, Ceiling, Greater, and Lesser, among others. BST also allows data traversal in O(n) time.
A binary search tree is employed to maintain sorted streams of data. For example, we want to maintain the live data in sorted order of prices if we're getting online orders. We would like to know how many items were purchased at a certain cost at any given time. We would also like to know the maximum cost we are approaching. Using a selfbalancing binary search tree, we can implement a priority queue with extractMin() or extractMax(). If we also support both extractMin() and extractMax(), we use a SelfBalancing Binary Search Tree to do both operations O(Log n). A list of the smallest elements on the right, the Smallest Greater Element on the right, and so on are all examples of problems where a selfbalancing BST is suitable.
5. What is ObjectOriented Programming?
In objectoriented languages such as Java and Python, classes and Objects are used to form programs. Polymorphism, encapsulation, abstraction, and inheritance comprise the four major building blocks of OOP. Other programming paradigms, such as procedural programming, include sequences of instructions. Python and Java are multiparadigm languages that allow both OOP and procedural programming. OOP makes programming simpler, quicker, more dynamic, and secure, irrespective of the paradigm you choose. In addition, there is no controversy that OOP makes programming simpler and quicker because it makes programming easier, faster, more dynamic, and more secure. It is a huge reason that Java and Python are the world's most popular programming languages today. It is fairly straightforward to understand these ObjectOriented Programming paradigms, which are crucial to Java and Python or any other objectoriented programming languages.
6. What is Inheritance and what is its purpose of it?
An object that can take on a set of characteristics from other classes of objects is called inheritance in objectoriented programming. These characteristics are commonly instance variables or member functions. A subclass is one that inherits these characteristics from its ancestor. A superclass is one that it inherited. It may also be the case that inheritance is implemented using code language features, but Simula was the first language to do so. Inheritance is used to consolidate and reutilize code. For example, if the objects 'car,' 'truck,' and 'motorcycle' are subclasses of vehicle code can be consolidated into a vehicle superclass. The subclasses receive this code and any future modifications, automatically.
7. Discuss garbage collectors in Java?
It is the job of the garbage collector (GC) in the Java virtual machine (JVM) to delete unused memory when a Java program requests it. Because memory is reclaimed automatically by the JVM, Java application developers are not forced to free memory objects that are no longer being used. The GC operation is based on the assumption that objects used in Java code are shortlived and can be reclaimed immediately after their creation. Because unreferenced objects are automatically removed from the heap memory when GC is running, Java is memory efficient. It is no longer necessary to manually deallocate memory in order to eliminate applicationsystem problems. Because GC eliminates certain types of applicationprogram faults, for example, it significantly reduces or eliminates certain types of problems.
8. Imagine a normal queue (push, peek, pop, and empty) but only need two stacks to implement it. The MyQueue class must support all queue functions (push, peek, pop, and empty). The push() method pushes element x to the front of the queue.
The pop() method returns the front element. The peek() method checks to see if the queue is empty. If it is, the empty() method returns true. If not, the method returns false. The queue is empty if it is not.
Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 1, 1, false]
Explanation:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Solution:
We will implement the push function inside the push function, in which we will first pop the top element off of the main stack and store it in the "temp" variable before calling push2 recursively. Then we will call push2 repeatedly until the main stack becomes empty, at which point we will push the element "x" into it. We will also add the "temp" variable to the main stack while backtracking in the push2 function.
class MyQueue {
public static Stack<Integer> mainStack;
public MyQueue() {
mainStack=new Stack<>();
}
public void push2(int x,Stack<Integer> mainStack)
{
if(mainStack.size()==0)
{
mainStack.push(x);
return;
}
int temp=mainStack.pop();
push2(x,mainStack);
mainStack.push(temp);
}
public void push(int x) {
push2(x,mainStack);
}
public int pop() {
return mainStack.pop();
}
public int peek() {
return mainStack.peek();
}
public boolean empty() {
if(mainStack.size()>0)
return false;
else
return true;
}
}
10. Given the head of a linked list, return the list sorted in ascending order.
Example 1:
 Input: head = [4,2,1,3]
 Output: [1,2,3,4]
Example 2:
 Input: head = [1,5,3,4,0]
 Output: [1,0,3,4,5]
Example 3:
 Input: head = []
 Output: []
Solution
Divide the list into two sublists by using two pointers: fast and slow. Assure that list 1 is equal to or longer than list 2. The condition of a while loop is whether fast is next and whether fast is next. After this while loop, slow will be at the end of list 1.sort list 1 and 2. Merge list 1 and 2.
public class Solution {
public ListNode sortList(ListNode head){
if(head==null  head.next==null)
return head;
ListNode h1=head;
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null && fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode h2=slow.next;
slow.next=null;
h1=sortList(h1);
h2=sortList(h2);
return merge(h1,h2);
}
public ListNode merge(ListNode h1, ListNode h2){
ListNode fakeHead = new ListNode(9);
ListNode cur = fakeHead;
while(h1!=null && h2!=null){
if(h1.val<h2.val){
cur.next=h1;
cur=h1;
h1=h1.next;
}else{
cur.next=h2;
cur=h2;
h2=h2.next;
}
}
cur.next=h1==null?h2:h1;
return fakeHead.next;
}
}
11. You have k eggs and n floors and you know that a floor f is low for 0 = f = n in which any egg dropped at a floor above f will break or one in which an egg dropped at or below f will not break.
You may drop an unbroken egg from any floor (1 = x = n) whether it breaks or not. If it does, you cannot use it again. If it doesn't, you can reuse it in the future. Determine with certainty what floor f is by considering all its possible values of it.
Example 1:
 Input: k = 1, n = 2
 Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Example 2:
 Input: k = 2, n = 6
 Output: 3
Example 3:
 Input: k = 3, n = 14
 Output: 4
Solution
To efficiently solve the problem of dividing a large job into smaller jobs, we must first determine how to partition the job into smaller jobs. For example, a binary search may be used to determine the optimal floor location. However, an easier way to determine the optimal floor location is to recognise that eggs are less likely to be broken in the higher floors, thus the floor location should be chosen to achieve this balance. This is a common procedure to determine the cut point for binary search. You should choose a floor location that minimises the number of moving steps for the higher floors (and maximises the number of moving steps for the lower floors) to provide a stable floor.
class Solution {
private:
vector<vector<int>> moveNum;
public:
int superEggDrop(int K, int N) {
moveNum.assign(K+1, vector<int>(N+1, 1));
for(int i = 1; i <= K; i++){
moveNum[i][0] = 0;
moveNum[i][1] = 1;
moveNum[i][2] = 2;
}
for(int i = 1; i <= N; i++ ) {
moveNum[1][i] = i;
}
return help(K, N);
}
int help(int K, int N){
if(moveNum[K][N] != 1)
return moveNum[K][N];
// the most important thing is to find the cut point
int end = (1 + N) / 2;
int begin = 1;
int cut = (begin + end) / 2;
int diff = help(K1, cut1)  help(K, Ncut);
while(diff != 0 && end  begin > 1) {
if(diff > 0){
end = cut;
cut = (begin + end) / 2;
diff = help(K1, cut1)  help(K, Ncut);
}
else{
begin = cut;
cut = (begin + end) / 2;
diff = help(K1, cut1)  help(K, Ncut);
}
}
int move1 = 1 + max(help(K1, begin1), help(K, Nbegin));
int move2 = 1 + max(help(K1, end1), help(K, Nend));
int move3 = 1 + max(help(K1, cut1), help(K, Ncut));
moveNum[K][N] = min(move1, min(move2, move3));
return moveNum[K][N];
}
};
12. Given a string s, find the first nonrepeating character and return its index. If one is found, return the index. Otherwise, return 1.
Example 1:
 Input: s = "scaler"
 Output: 0
Example 2:
 Input: s = "interviewbit"
 Output: 1
Example 3:
 Input: s = "aabb"
 Output: 1
Solution
A hashmap is not required for this example because you can count the frequency of the English lowercase characters using an array. O(n) time complexity: O(2n) as we traverse the string 2 times (1 to count the letter frequency and 2 to find the letter with frequency = 1). Space complexity: O(26) we use an array of 26 to hold the English lowercase characters' frequency.
class Solution {
public:
int firstUniqChar(string s) {
if (s.empty()) {
return 1;
}
// use an array where we count the frequency of all english lower case characters
int char_freq[26] = { 0 };
for (int i = 0; i < s.size(); ++i) {
//convert char to its ascii code in the range [0,26)
int char_idx = s[i]  'a';
char_freq[char_idx]++; //increase letter frequency
}
// check the letters of the string again from start to end
for (int i = 0; i < s.size(); ++i) {
int char_idx = s[i]  'a';
//if the character has frequency of 1, return its position into string
if (char_freq[char_idx] == 1) {
return i;
}
}
return 1;
}
};
13. Why is Monitoring Java Garbage Collection Important?
Garbage collection can have unpredictable effects on Java app performance. As a result of frequent garbage collection, CPU loads may rise and application processing may slow down. As a result, endusers may experience a slower computing experience. As a result, a memory leak in the Java application can occur. In addition to CPU utilisation, garbage collection can also contribute to increased memory consumption. As a result, the greater garbage collection activity may be observed. Increased CPU utilisation may occur due to CPU overload caused by excessive garbage collection activity. A good Java app performance requires monitoring the GC usage. To achieve high app performance, an adequate GC should be used sparingly. GC usage should be kept to a minimum, typically less than 5% and the amount of CPU usage for garbage collection should be kept as low as possible (this allows application threads to use almost all the available CPU resources).
14. What is JVM and is it's platformindependent?
The Java Virtual Machine (JVM) is a runtime environment for bytecode(.class files) that is run on the Java Platform. The JVM is the platform. It is the JVM that does the work. The Java Virtual Machine (JVM) is responsible for this. Due to its awareness of the various platform characteristics and instruction lengths, JVM makes this possible. The JVM is not platformindependent. Java Virtual Machine (JVM) provides the environment for Java code to run. A file created with Java code is executed by the JVM. Most OSs (operating systems) are not compatible with one another, which means that the end result is dependent on the kernel, and the kernel is different for each OS (operating system). The JVM translates bytecode into machine language so that computers can access the same machine language code, and it actually executes those machinelanguage instructions. Without the JVM, you cannot run a Java program.
15. What are wrapper classes?
Wrapper classes wrap data types in objectlike wrappers, allowing them to be converted to objects. They are used to turn any primitive type into an object in Java. Although they are not objects themselves, they are defined in the language. Thus, it is necessary to convert data types into objects in Java in some circumstances. To demonstrate this, we created a wrapper class that conforms to the structure of only objects.
16. What do you think of the primary memory and the secondary memory?
Main memory is tasked with transferring data from secondary memory to the processor in Dragon Fantasy. RAM and ROM, two of the foremost memories in the system, are used but hard disk and other largesized memories from secondary memory are also utilised. The main memory is straightforward and fast to utilise data from it rather than secondary memory, which requires additional time to utilise data. The main memory is faster to utilise data from than secondary memory, which results in less data being stored in the main memory permanently and more utilising data quicker. Secondary memory data is not stored in the main memory as permanently as RAM data, but only for a certain amount of time in order to achieve optimum performance.
17. What is Reentrancy?
Multi programmed timesharing systems using Reentrant Procedures are useful for retaining a record of activations for subsequent executions of programs. Reentrant Procedures are procedures that must be written so that multiple individuals may share a single copy of the program code during the same period. The program code cannot modify itself, and the local data for each user process must be stored separately. The permanent part is the code, and the temporary part is the pointer to the calling program and local variables used by that program. Each activation is called an execution instance. It executes the code in the permanent part but retains its own copy of local variables/parameters. The temporary part associated with each activation is the activation record. Typically, the activation record is retained on the stack. A reentrant procedure may be interrupted and executed again if it is interrupted.
18. What are the advantages of multiprogramming, and what is it?
An operating system that allows multiple programmes to run on one CPU is known as a multiprogramming operating system. You can discuss key differences between a multiprogramming OS and other systems by highlighting key differences in terms of operation. When you describe a scenario in which you used multiprogramming to benefit from its advantages, you can show your understanding of a system that might be important to the interviewer.
19. You are given an integer array digits as shown, where each digit of the integers represented by an integer value. The digits are from most significant to least significant in lefttoright order.
There are no leading 0's in the large integer. Increment it by one and return the array of digits.
Example 1:
 Input: digits = [1,2,3]
 Output: [1,2,4]
 Explanation:
The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Example 2:
 Input: digits = [4,3,2,1]
 Output: [4,3,2,2]
 Explanation:
The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Example 3:
 Input: digits = [9]
 Output: [1,0]
 Explanation:
The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
Solution
To increase the value of the last index by one, we need to reverse the string and then deal with the carry separately. To reverse the string, we can simply reverse the string. In this case, we can simply make the first index 0 and check the next index. If the next index is also 9, we add one to it until we come across an index with a value other than 9. Increase that value by one. In the case where there are no more than nine indices, we have dealt with it by pushing 1 at the end. Reverse the string again.
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
if(digits[n1]!=9)digits[n1]+=1; //Case when last index not 9
else{ //Case when last index is 9
reverse(digits.begin(),digits.end());
int i=0;
while(i<=n){
if(i==n){digits.push_back(1); //Case when no index has value other than 9.
break;
}
if(digits[i]==9)digits[i]=0,i++;
else{
digits[i]++; //Case when some index has value other than 9.
break;
}
}
reverse(digits.begin(),digits.end());
return digits;
}
return digits;
}
};
20. Given a sorted array of distinct integers, return the index if the target value is found, or if not, the index where the value would be inserted in order. An algorithm with O(log n) runtime must be written to handle it.
Example 1:
 Input: nums = [1,3,5,6], target = 5
 Output: 2
Example 2:
 Input: nums = [1,3,5,6], target = 2
 Output: 1
Example 3:
 Input: nums = [1,3,5,6], target = 7
 Output: 4
Solution
We must be careful if the start is greater than the end, because if this statement is true, we know that the target is NOT FOUND, and we just return the insertion position. Now, let's take a look at what happens if the previous caller was the case mid=start=end. binarySearchInsert(nums, mid+1, end, target), in case 1, the insertion position should be mid+1 (insert target after mid) in case 2, the insertion position should be mid (insert target into mid and shift old mid value afterwards). It is also clear in the next call when start>end that the start should be at the insertion position. But wait, if the target is found, how do you know whether the idx >= 0, if the target is not found, how do you know whether the idx >= 0? To find out the original value when not found, we use a trick to return a negative value. What about the found value? It is 0, so we use another trick to increment the insertion idx before negation.
public class Solution {
public int binarySearchInsert(int[] nums, int start, int end, int target) {
if(start>end)
return (start+1);
int mid = start+(endstart)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]<target)
return binarySearchInsert(nums, mid+1, end, target);
else
return binarySearchInsert(nums, start, mid1, target);
}
public int searchInsert(int[] nums, int target) {
int idx = binarySearchInsert(nums, 0, nums.length1, target);
return idx>=0 ? idx : idx1;
}
}
21. Return the median of the two sorted arrays given two arrays of size m and n, nums1 and nums2, respectively. It is recommended that the runtime complexity be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Solution: When two arrays are combined, the middle element will be the median since it splits the total number of items into two equal halves. However, O(m+n) more space will be needed. However, by taking note of the fact that when merging the arrays, we are only interested in the border elements of the arrays because the arrays are already sorted, this solution may be optimised to operate in const space. As a result, we must determine how many elements from the first array should be chosen to go before the median. The number of elements from the second array that should go before the median may be computed as total elements/2  the number of selected elements from the first array. Additionally, while computing the median, we need to know the values of either just one middle element or two middle elements (if there are even numbers of components) (in case of odd number of elements). So, when conducting a binary search, we will keep track of these values.
Note: Since arrays are already sorted, left values will always be smaller than right values of its own array when merging, i.e. left value of one array with right value of another array.
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if(m > n)
{
return findMedianSortedArrays(nums2, nums1);
}
int l=0, r= m;
int total = m+n+1;
while(l<=r)
{
int fir = l + (rl)/2;
int sec = total/2  fir;
int l1=INT_MIN, l2=INT_MIN;
int r1=INT_MAX, r2=INT_MAX;
if(fir > 0)
{
l1 = nums1[fir1];
}
if(sec>0)
{
l2 = nums2[sec1];
}
if((fir>=0) && (fir<m))
{
r1 = nums1[fir];
}
if((sec>=0) && (sec<n))
{
r2 = nums2[sec];
}
if(l1<=r2 && l2<=r1)
{
if((n+m)%2 == 0)
{
return (max(l1, l2)+min(r1, r2))/2.0;
}
else
{
return max(l1, l2);
}
}
else if(l1> r2)
{
r = fir1;
}
else
{
l = fir+1;
}
}
return 0;
}
};
22. An array of k linkedlist lists is provided to you; each linkedlist is arranged in ascending order. Create one sorted linked list out of the combined linked lists, then return it.
Example 1:
 Input: lists = [[1,4,5],[1,3,4],[2,6]]
 Output: [1,1,2,3,4,4,5,6]
 Explanation:
The linked lists are:
[
1>4>5,
1>3>4,
2>6
]
merging them into one sorted list: 1>1>2>3>4>4>5>6
Example 2:
 Input: lists = []
 Output: []
Example 3:
 Input: lists = [[]]
 Output: []
Solution:
Taken as our initial starting point, k=2. 1>2>3, 2>7>11 The linked list's pointer is then advanced by selecting the least pointer value.
The process for raising k will proceed in the same way. The least number will be arbitrarily selected, and the corresponding pointer will be advanced. The issue is that for k=2, we can simply use the or > sign to determine which number is smaller of the two. However, adopting such an approach will take years to compute if k is huge, let's say 1 million.
To answer this question, we'll need to use a more intelligent data structure. Consider a data structure that can hold all values and provide the lowest value in the shortest amount of time.
A little mound would be preferable.
1. All first pointers from each linked list will be pushed into the heap.
2. We also need to advance that list's pointer.
3. Next, we begin linking all of the smallest nodes to obtain the answer.
Though I've represented heaps in this way for convenience, keep in mind that heaps actually take the form of trees.
struct comp
{
bool operator()(const ListNode* a,ListNode* b)
{
return a>val>b>val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,comp> pq;
for(auto x:lists)
{
if(x)pq.push(x);
}
if(pq.empty())return NULL;
ListNode* result=pq.top();
pq.pop();
if(result>next)pq.push(result>next);
ListNode* t=result;
while(!pq.empty())
{
t>next3e=pq.top();
pq.pop();
t=t>next;
if(t>next)pq.push(t>next);
}
return result;
}
23. Return the updated list after inverting the list's nodes k at a time, starting with the linked list's head. Positive integer k must be less than or equal to the linked list's length.
The remaining nodes should, in the end, remain how they are if the number of nodes is not a multiple of k. Only the nodes themselves may be modified; the list's nodes' values may not be changed.
Example 1:
 Input: head = [1,2,3,4,5], k = 2
 Output: [2,1,4,3,5]
Example 2:
 Input: head = [1,2,3,4,5], k = 3
 Output: [3,2,1,4,5]
Solution:
Similar to reversing a specific area of a linked list, reversing K nodes at a time in a linked list. In order to reverse a specific section of the linked list from m to n, I wrote the method reverse(). Until we get an upper bound that is fewer than the number of nodes in the provided linked list, I used this function again with portions of [i,i+k1], [i+k,i+2k 1], and so on.
class Solution {
public:
ListNode* reverseList (ListNode* head) {
ListNode* newHead = NULL;
ListNode* cur = head;
// add code here to reverse the list
while (cur) {
ListNode* next = cur>next;
cur>next = newHead;
newHead = cur;
cur = next;
}
return newHead;
}
void printList (ListNode* head) {
while (head) {
cout<<head>val<<" ";
head = head>next;
}
cout<<endl;
cout<<endl;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* newHead = NULL;
ListNode* curStart = head;
ListNode* prevEnd = NULL;
// All this below code is going to be in a loop
while (1)
{
// for pointing to the Kth element we need to move ahead k1 times
int rot = k1;
ListNode* curEnd = curStart;
while(rot && curEnd) {
curEnd = curEnd>next;
rot;
}
// this means we are left with the less nodes then k so we don't need to process further
if (curEnd == NULL) {
// just add the remaining list as it is.
prevEnd>next = curStart;
break;
}
// To keep track of next portion of list before breaking the current part.
ListNode* curNext = NULL;
if (curEnd) {
curNext = curEnd>next;
}
// now break current part of the list
if(curEnd) {
curEnd>next = NULL;
}
// reverse current part only
reverseList(curStart);
if (newHead == NULL) {
// since when nothing is processed we need to set the newHead (for first part)
newHead = curEnd;
} else {
// attach this reversed part to "already processed" list
prevEnd>next = curEnd;
}
// update previous end to the end of the currently reveresed part
prevEnd = curStart;
// update the current start to next part of the list which need to be processed next
curStart = curNext;
}
return newHead;
}
};
24. The smallest missing positive integer should be returned from an unsorted integer array called nums. You must build an algorithm that requires constant additional space and runs in O(n) time.
Example 1:
 Input: nums = [1,2,0]
 Output: 3
Example 2:
 Input: nums = [3,4,1,1]
 Output: 2
Example 3:
 Input: nums = [7,8,9,11,12]
 Output: 1
Solution:
Cycle sort is an unstable inplace sorting algorithm that does comparison sorting and is theoretically the least amount of writes to the original array. Regarding the quantity of memory writes, it is ideal. It reduces the amount of memory writes required for sorting (each value is either written once to its right spot or zero times if it is already there). Its foundation is the notion that an array to be sorted may be broken up into cycles. Graphs can be used to represent cycles. If the element at index I must also be present at index j in the sorted array, then we have n nodes and an edge that runs from node I to node j.
Cycle in arr [] = 2, 4, 5, 1, 3.
Cycle in arr [] = 4, 3, 2, 1
We evaluate each cycle individually. We start by thinking about the cycle that contains the first ingredient. We locate the first element's right position and set it at, let's say, position j. We take into account the previous value of arr[j] and determine its proper location. We continue repeating this until all of the components of the current cycle are in their proper positions, meaning that we never return to the cycle's starting point.
As a result, we may cycle sort just the positive items in this question and disregard the negative and zero elements. The element that is not at its predicted index will serve as our response as we proceed through the positive elements. Additionally, our response will be one greater than the greatest positive if all positive factors are at their predicted indices.
class Solution {
public:
int firstMissingPositive(vector<int>& arr) {
//Cycle sort
int n = arr.size();
int i = 0, correct_idx;
while(i < n) {
if(arr[i] == i+1 or arr[i] > n or arr[i] <= 0)
i++;
else {
correct_idx = arr[i]  1;
if(arr[i] != arr[correct_idx])
swap(arr[i], arr[correct_idx]);
else
i++;
}
}
//Find first missing positive
int max = 1;
for(int i = 0; i < n; i++) {
if(arr[i] > 0)
max = arr[i];
if(arr[i] != i+1)
return i+1;
}
return max+1;
}
};
25. Determine how much water a given set of n nonnegative integers representing an elevation map, where each bar's width is 1, can hold after a rainstorm.
Example 1:
 Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
 Output: 6
 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
 Input: height = [4,2,0,3,2,5]
 Output: 9
Solution:
The basic goal is to calculate the total volume of water held above each structure. To perform se, we must identify the buildings on either side of a structure with the maximum height. as in [3, 0, 0, 2, 4] In this instance, the heights of the building with height 3 (the tallest structure to the left of building 2) and building with height 4 determine how much water is present above building with height 2. (i.e the heightest building to the right of 2). Maintaining two arrays to hold the maximum heights of the right and left components is the basic principle. The purpose is served by the arrays with the names maxl and maxr in the solution. Now, to get the volume of water on top of a building, we must first determine the minimum height difference between the structures on the left and right, then deduct that value from the height of the present structure. The quantity of water held beyond 2 is (3  2 = 1) since in the instance of 2, the minimum value between 3 and 4 is 3. This result may be saved in another array, and the total of all the items can then be returned.
class Solution {
public:
int trap(vector<int>& height) {
int trappedWater = 0; // Initialize trappedWater with "0"
int leftMaxHeight = 0, rightMaxHeight = 0; // Initialize leftMaxHeight and rightMaxHeight with "0"
int left = 0, right = height.size()  1; // Initialize left with "0" and right with "size of height array".
// Loop until Left <= right
while (left <= right)
{
// If the height[left] < height[right] then update LeftMaxHeight/TrappedWater from Left side
if (height[left] < height[right])
{
if (height[left] > leftMaxHeight)
leftMaxHeight = height[left];
else
trappedWater += leftMaxHeight  height[left];
left += 1;
}
else // If height[right] > height[left] then will update rightMaxHeight and trappedWater
{
if (height[right] > rightMaxHeight)
rightMaxHeight = height[right];
else
trappedWater += rightMaxHeight  height[right];
right = 1;
}
}
return trappedWater; // return Trapped Water
}
};
26. Return the smallest window substring of s such that every character in t (including duplicates) is contained in the window, given two strings s and t of lengths m and n, respectively.
Return the void string "if there is no such substring." The test cases will be created so that each test case yields a distinct answer. A continuous group of characters within the string is referred to as a substring.
Example 1:
 Input: s = "ADOBECODEBANC", t = "ABC"
 Output: "BANC"
 Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
 Input: s = "a", t = "a"
 Output: "a"
 Explanation: The entire string s is the minimum window.
Example 3:
 Input: s = "a", t = "aa"
 Output: ""

Explanation:
Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Solution:
Use variable count to find the first valid substring from index p to index I then for each I we increase p until it still qualifies as a valid substring, at which time we update the result string.
class Solution {
public:
string minWindow(string s, string t) {
unordered_map < char , int > a;
unordered_map < char , int > b;
for(auto ch: t)
{
a[ch]++;
}
int p = 0;
int mn = INT_MAX;
string mxstr = "";
int count=0;
for(int i =0;i<s.size();i++)
{
watch(i);
watch(p);
b[s[i]]++;
int flag=0;
if(b[s[i]]<=a[s[i]])
{
count++;
}
if(count >= t.size())
{
while(p<i && b[s[p]]>a[s[p]])
{
b[s[p]];
p++;
}
// mn = min(mx, ip+1);
if(mn > ip+1)
{
mn = ip+1;
mxstr = s.substr(p,ip+1);
}
}
}
return mxstr;
}
};
27. An array of prices is provided to you, where prices[i] represents the price of a certain stock on the ith day. Determine the highest profit you can make. You can only execute two transactions at once.
Note: You may not do more than one transaction at once (i.e., you must sell the stock before you buy again).
Example 1:
 Input: prices = [3,3,5,0,0,3,1,4]
 Output: 6

Explanation:
Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 30 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 41 = 3.
Example 2:
 Input: prices = [1,2,3,4,5]
 Output: 4

Explanation:
Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 51 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
 Input: prices = [7,6,4,3,1]
 Output: 0
 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
In the future, we want to determine the highest profit if we have 1, 2, 3, and 2. (buy then sell). Additionally, we're looking for the best movingback profit (sell then buy). A forward array and a reverse array are the results.
 Future maximum profit range: 0. 1 2 2 4.
 Maximum profit array in reverse: 4 3 3 3 0.
Recall that each array represents the maximum profit cumulatively. You can only benefit from the backwards array after locking in the profit from the front array since you can only purchase after you've sold.
In other words, the maximum of forwardArray[i  1] + backWardsArray[i] will be your maximum profit; This means that in the case above, our maximum possible profit array is 3 4 5 2, and our maximum profit in that array is 5.
The formulas ForwardArray[0] + BackwardsArray[1], and ForwardArray[1] + BackwardsArray[2] were used to generate this array.
Additionally, there is a rare circumstance in which the profit on the forward array is significantly greater than on the backwards array. Consider the following two arrays, which are oriented forward and backward.
 In the future: 0 1 2 20 1
 In reverse: 0 0 5 0 0 0
In this instance, there is no benefit to doing F[i1] + B[i] since the profit point of the forward array (20 > 7) outweighs that of any possible forward and backward combination. So, we merely make a single purchase and sale, earning $20.
int maxProfit(vector<int>& prices) {
if (prices.size() == 1) return 0;
int n = prices.size();
vector<int> first_buy_and_sell(prices.size(), 0);
int min_price_so_far = numeric_limits<int>::max();
int first_buy_profit{};
for (int i{}; i < n; i++) {
min_price_so_far = min(min_price_so_far, prices[i]);
first_buy_profit = max(first_buy_profit, prices[i]  min_price_so_far);
first_buy_and_sell[i] = first_buy_profit;
} // Find the maximum profit going forward, and keep a copy of it
int max_price_so_far = numeric_limits<int>::min();
int max_profit{};
for (int i = n  1; i > 0; i) {
max_price_so_far = max(prices[i], max_price_so_far);
max_profit = max(first_buy_and_sell[i],max(max_profit, max_price_so_far  prices[i] + first_buy_and_sell[i  1]));
} // We use two max functions above to account for the edge case detailed above.
return max_profit;
}
28. Partition a string s in such a way that each of its substrings is a palindrome. Return the minimal cuts required to split s into palindromes.
Example 1:
 Input: s = "aab"
 Output: 1
 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
 Input: s = "a"
 Output: 0
Example 3:
 Input: s = "ab"
 Output: 1
Solution: A palindrome is any substring that shares the same centre as a palindrome. If s is a palindrome and letter c serves as the centre, then s[ck,..,c,...,c+k] must also be a palindrome. Finding every palindrome with the last character I and calculating the new minimum number partition at I is all that is necessary to determine the minimum number partition at I if we know the minimum number of partition for s[0,...,i1].
class Solution {
public:
int minCut(string s) {
// if there is only one character in string, then it is already a palindrome, so, return 0
if(s.length()==1)return 0;
//now, we need to check different substrings whether they are pallindrome or not, so, it will be better if we store it somewhere for all substrings and that too in optimized way
// let row number will represent starting index of that particular substring
// & column number will represent ending index of that particular substring
int *isPallindrome[s.length()];
for(int i=0;i<s.length();i++)isPallindrome[i]=new int[s.length()];
// now, substring with same starting and ending index i.e. only one character in it, will be a pallindrome for sure
for(int i=0;i<s.length();i++)isPallindrome[i][i]=true;
// and substrings with two elements will be pallindrome if both starting and ending element of that substring are same
for(int i=0;i<s.length()1;i++)isPallindrome[i][i+1]=(s[i]==s[i+1]);
// now, one thing comes to mind, why we are filling diagonally?
// it is because we can minimise our number of operations to check whether a substring is pallindrome or not if we have answer for it subparts already
for(int gap=2;gap<s.length();gap++){
for(int i=0;i<(s.length()gap);i++){
int j=gap+i;
// in this way, we only need to check if starting and ending index elements are equal or not
//& if they are equal, we can check if the remaining substring (other than starting and ending index chars) is pallindrome or not in O(1) because we have already computed for that
// that's why we are traversing diagonally
if(s[i]==s[j] && isPallindrome[i+1][j1])isPallindrome[i][j]=true;
else isPallindrome[i][j]=false;
}
}
// now, we will come to the part of calculating minimum number of cuts required
// here dp[i] will store minimum number of cuts required if only chars from 0 to i are present
int *dp=new int[s.length()];
// if only one char is there, then minimum number of cuts required will be 0
dp[0]=0;
// now we are going to calculate for i and we have answers for 0 to i1 already
//so, we will be using that information
for(int i=1;i<s.length();i++){
// if chars from 0 to i makes a pallindrome, then no cut is required for that i
if(isPallindrome[0][i])dp[i]=0;
else{
//otherwise, let minimum cuts required is mcr=INT_MAX
int mcr=INT_MAX;
//now we will try making cut before all elements in our current substring
//and since we already have answer for left portion of cut(that we can get from dp[]
//so, we just need to consider the case when right portion is pallindrome(that we can check from isPallindrome[][])
for(int cutBefore=i;cutBefore>0;cutBefore){
//cutBefore is starting index of right portion and i is ending index of right portion
if(isPallindrome[cutBefore][i])mcr=min(mcr,dp[cutBefore1]);
}
// till now, mcr will e storing minimum cuts required for left portion
// and right portion is considered pallindrome as discussed
//therefore, our answer will be mcr+1 because that on cut is required to make that left and right portion
dp[i]=mcr+1;
}
}
return dp[s.length()1];
}
};
Useful Interview Resources
MAQ Interview Preparation
1. Interview Preparation Tips
 Communication: Communication includes not just clarifying questions but also the communication of strategy and tradeoffs in a straightforward manner so that the interviewer can follow along without any difficulty.
 Problemsolving: Understanding the problem and approaching it in a methodical, logical, and precise manner while exploring a variety of potential solutions and compromises is an essential step in the problemsolving process. capability to accurately identify both the time and space complexity of a situation and optimise both.
 Technical competency  The ability to translate proposed solutions into working code without significant struggle is an essential component of technical expertise. This requires an implementation that is spotless and exact, along with a solid understanding of linguistic constructions.
 Testing: The capacity to test code against both typical and edge circumstances, as well as the capacity for programs to selfcorrect errors.
 Coding interview techniques  Techniques for giving coding interviews, including how to locate a solution and improve your approach.
 Coding interview best practices  Best practices for the coding interview include how to conduct yourself throughout the interview to exhibit hire signals
 Algorithms study cheatsheets  The greatest learning resources, must remember (tips, corner cases), and must do practice questions for every data structure and algorithm covered in data structures and algorithms.
Frequently Asked Questions
1. How can I get placed in MAQ?
 It is important to understand the concepts clearly and to complete the projects in a timely manner, and your attitude is crucial.
 It is important to study elitmus and apply for MAQ, too. To be eligible for MAQ Software hiring through the AMCAT platform, you must also take the AMCAT test.
 It is important to master the core computer science subjects, LINUX, shell scripting, and projects such as those made with LISP.
 Write more to master the theoretical concepts and do not forget the core computer science subjects.
 You can also ask for a referral from LinkedIn or other mediums.
2. What is the fresher salary in MAQ?
According to Ambitionbox, the average MAQ Software salary ranges from approximately ₹4.6 Lakhs per year.
3. Is the MAQ interview hard?
The technical interview is challenging and complicated, and it will be based solely on the information you provide in your resume. They will ask you questions based on the areas of study and the projects you've completed while in college.
4. Why do you want to work for MAQ?
Freshers can find comfort in working at MAQ Software. The team members go beyond to satisfy the demands of the company. Working in such an environment makes you realise just how important it is to work together. You will gain a lot of experience in the industry and highquality delivery in a hectic situation. With a focus on innovative Software applications, MAQ Software enables companies to boost their productivity. Using the latest agile engineering methods, the company accelerates software innovations that enable customers to transform their sectors.
Sample Answer:
“There are four reasons why I would like to work for MAQ Software. The first justification is from the fact that, after using some of its goods and services myself, it is obvious that they always put the needs of the client first and are driven to improve people's lives. That is a quality that I actually like in a firm.
The second factor is that this ongoing drive will help us to develop, learn, and get better. Working for this company will provide me with the opportunity to continue learning and growing since I share my desire to do so. The desire to work on diverse, tough tasks is the third justification. After researching this position and your business, I am aware that I will work with many teams and departments that are pursuing the same goals.
Last but not least, it is obvious from your website and social media platforms that you take your obligations seriously, which is another reason I wish to work for your IT firm. You support an inclusive workplace atmosphere, you care about the planet we live on, and you are socially responsible.”
5. Does MAQ pay well?
According to Glassdoor, the typical compensation range for an entrylevel (or E1) software engineer is $110,928.
6. How long is the MAQ Interview Process?
MAQ Software takes an average of five days to interview for all job titles when considering all usersubmitted interviews. The hiring process for software engineers, on the other hand, takes an average of 2 days, while that for software developer roles is on average 7 days.
7. What is the Eligibility Criteria at MAQ
 6 CGPA/60% and no active backlogs are required throughout the academic years
 B.Tech (CS), BCA + MCA, M.Tech, B.Tech+M.Tech(CSE).