MAQ Interview Questions

1. 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.
2. 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.
3. 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 Software conducts a selection process every year to pick new candidates. These selection rounds are as follows:

1. Written Test
2. Technical Interview
3. 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.

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[c-k,..,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,...,i-1].

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 sub-strings 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][j-1])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 i-1 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[cutBefore-1]);
                }
				// 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

• HR Interview Questions
• Free Mock Coding Interview
• Coding Interview Questions for Practice
• Technical Interview Questions for Practice
• Interview Preparation

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[n-1]!=9)digits[n-1]+=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;
    }
};

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+(end-start)/2;
        if(nums[mid]==target)
            return mid;
        else if(nums[mid]<target)
            return binarySearchInsert(nums, mid+1, end, target);
        else
            return binarySearchInsert(nums, start, mid-1, target);
    }
    
    public int searchInsert(int[] nums, int target) {
        int idx = binarySearchInsert(nums, 0, nums.length-1, target);
        return idx>=0 ? idx : -idx-1;
    }
}

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 + (r-l)/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[fir-1];
           }
           if(sec>0)
           {
               l2 = nums2[sec-1];
           }
           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 = fir-1;
           }
           else
           {
               l = fir+1;
           }
       }
       
       return 0;
       
   }
};

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;
    }

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+k-1], [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 k-1 times
            int rot = k-1;         
            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;
    }
};

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 in-place 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; 
    }
};

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
    }
};

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, i-p+1);
                if(mn > i-p+1)
                {
                    mn = i-p+1;
                    mxstr = s.substr(p,i-p+1);
                }
                
                
            }
        }
        return mxstr;
        
    }
};

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 = 3-0 = 3.
  Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 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 = 5-1 = 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 moving-back 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[i-1] + 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;
    }

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 multi-programming to benefit from its advantages, you can show your understanding of a system that might be important to the interviewer.

The index of the node to which the tail of the next pointer is connected is used to determine whether there is a cycle. If there is not a cycle, then return true. Otherwise, return false.

Example 1:

• Input: head = [3,2,0,-4], pos = 1
• Output: true
• Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

• Input: head = [1,2], pos = 0
• Output: true
• Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

• Input: head = [1], pos = -1
• Output: false
• Explanation: There is no cycle in the linked list.

Solution: 

Using only two pointers, Floyd's cycle-moving algorithm traverses a sequence at different speeds. It determines whether a linked list has a cycle or not. First, we keep two pointers to the leading node, one that moves slowly and one that moves quickly. We scan the linked list in two steps and one step each, starting with the slow pointer and ending with the fast pointer. This procedure produces two-pointers and one pointer, which we call the tortoise and the hare. If the fast pointer reaches the tail of the list (or null), there is no cycle (i.e. if the fast pointer meets the slow pointer, there is a cycle). If the fast pointer meets the slow pointer, then there is a cycle (i.e. if the fast pointer and slow pointer meet).

We can see that Car M is a slow pointer and Car B is a fast pointer in the below example.

public boolean hasCycle(ListNode head) {
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        
        do {
            if (slowPointer == null || fastPointer == null || fastPointer.next == null) {
                return false;
            } 
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        } while (slowPointer != fastPointer);
        
        return true;
    }

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);
        }
    }

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 three-pointers 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.length-1;
        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--;
            }
        }   
    }
}

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 built-in garbage collection mechanism. A structure can be created in C++ whereas Java cannot.

A self-balancing BST (like the AVL and Red-Black-Trees) keeps its height constant by balancing itself. These self-balancing 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 self-balancing binary search tree, we can implement a priority queue with extractMin() or extractMax(). If we also support both extractMin() and extractMax(), we use a Self-Balancing 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 self-balancing BST is suitable.

In object-oriented 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 multi-paradigm 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 Object-Oriented Programming paradigms, which are crucial to Java and Python or any other object-oriented programming languages.

An object that can take on a set of characteristics from other classes of objects is called inheritance in object-oriented 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 re-utilize 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.

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 short-lived 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 application-system problems. Because GC eliminates certain types of application-program faults, for example, it significantly reduces or eliminates certain types of problems.

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;
    }
}

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;
    }
}

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(K-1, cut-1) - help(K, N-cut);
        while(diff != 0 && end - begin > 1) {
            if(diff > 0){
                end = cut;
                cut = (begin + end) / 2;
                diff = help(K-1, cut-1) - help(K, N-cut);
            }
            else{
                begin = cut;
                cut = (begin + end) / 2;
                diff = help(K-1, cut-1) - help(K, N-cut);
            }
        }
        int move1 = 1 + max(help(K-1, begin-1), help(K, N-begin));
        int move2 = 1 + max(help(K-1, end-1), help(K, N-end));
        int move3 = 1 + max(help(K-1, cut-1), help(K, N-cut));
        
        moveNum[K][N] = min(move1, min(move2, move3));
        return moveNum[K][N];
    }
};

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;
    }
};	

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, end-users 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).
 

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 platform-independent. 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 machine-language instructions. Without the JVM, you cannot run a Java program.

Wrapper classes wrap data types in object-like 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.

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 large-sized 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.

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.

1. 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.
2. Problem-solving: 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 problem-solving process. capability to accurately identify both the time and space complexity of a situation and optimise both.
3. 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.
4. Testing: The capacity to test code against both typical and edge circumstances, as well as the capacity for programs to self-correct errors.
5. Coding interview techniques - Techniques for giving coding interviews, including how to locate a solution and improve your approach.
6. Coding interview best practices - Best practices for the coding interview include how to conduct yourself throughout the interview to exhibit hire signals
7. 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.

1. It is important to understand the concepts clearly and to complete the projects in a timely manner, and your attitude is crucial.
2. 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.
3. It is important to master the core computer science subjects, LINUX, shell scripting, and projects such as those made with LISP.
4. Write more to master the theoretical concepts and do not forget the core computer science subjects.
5. You can also ask for a referral from LinkedIn or other mediums.

According to Ambitionbox, the average MAQ Software salary ranges from approximately ₹4.6 Lakhs per year.

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.

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 high-quality 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.”

According to Glassdoor, the typical compensation range for an entry-level (or E1) software engineer is $110,928.

MAQ Software takes an average of five days to interview for all job titles when considering all user-submitted 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.

• 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).