80+ MAQ Software Interview Questions and Answers

Calculate the Nth Fibonacci number efficiently using dynamic programming.

• Use dynamic programming to store previously calculated Fibonacci numbers to avoid redundant calculations.

• Start with base cases F(1) and F(2) as 1, then iterate to calculate F(N) efficiently.

• Time complexity can be optimized to O(N) using dynamic programming.

• Example: For N = 5, the 5th Fibonacci number is 5.

Generate a series of numbers by subtracting K from N until 0 or negative, then adding K back to reach N without using loops.

• Create a recursive function to generate the series.

• Subtract K from N until N is 0 or negative, then add K back until N is reached.

• Return the series as an array of integers.

Find the unique element in a sorted array where all other elements appear twice.

• Iterate through the array and XOR all elements to find the unique element.

• Use a hash set to keep track of elements and find the unique one.

• Sort the array and check adjacent elements to find the unique one.

Given a string with parentheses and letters, remove minimum invalid parentheses to make it valid and return all possible valid strings.

• Use BFS to explore all possible valid strings by removing parentheses one by one

• Keep track of visited strings to avoid duplicates

• Return all unique valid strings obtained after removing minimum number of parentheses

Return all permutations of a given string in lexicographically increasing order.

• Use backtracking to generate all permutations of the string.

• Sort the permutations in lexicographical order before printing.

• Ensure the string contains unique characters for correct output.

• Handle multiple test cases by iterating over each case.

Rotate a given array to the left by K steps.

• Create a new array to store the rotated elements.

• Use modular arithmetic to handle cases where K is greater than the array size.

• Shift elements to the left by K steps and update the new array.

• Return the rotated array as output.

Remove all occurrences of a specified string from a singly linked list by checking from the end of the list.

• Traverse the linked list from the end to efficiently remove the specified string occurrences.

• Update the pointers accordingly after removing the string to maintain the integrity of the linked list.

• Consider edge cases such as when the entire linked list contains the specified string.

• Use a temporary buffer to keep track of the nodes that need to be removed.

Sort a string with alternate lowercase and uppercase letters in sorted order.

• Create two separate arrays for lowercase and uppercase letters.

• Sort both arrays individually.

• Merge the two arrays alternately to form the final sorted string.

Sort a Singly Linked List using Merge Sort algorithm.

• Implement the Merge Sort algorithm for linked lists.

• Divide the list into two halves, sort each half recursively, and then merge them.

• Make sure to handle the base case of an empty or single-node list.

• Example: Input: 4 3 2 1 -1, Output: 1 2 3 4

Hash table. No, it is not possible to create a data structure with all operations in O(1) time.

• Hash table uses a hash function to map keys to indices in an array.

• Insertion and deletion can be done in O(1) time on average.

• Search retrieval can also be done in O(1) time on average.

• However, worst-case scenarios can result in O(n) time complexity.

• It is not possible to create a data structure with all operations in O(1) time.

To find the Kth row of Pascal's Triangle given a non-negative integer K.

• Create an array to store the values of the Kth row of Pascal's Triangle

• Use the formula C(n, k) = C(n-1, k-1) + C(n-1, k) to calculate the values

• Return the array as the output

Calculate factorial of a given number N.

• Iterate from 1 to N and multiply each number to get the factorial value.

• Handle edge cases like N=0 or N=1 separately.

• Use recursion or iteration to calculate factorial efficiently.

Find the second largest element in an array of integers.

• Iterate through the array to find the largest and second largest elements.

• Handle cases where all elements are identical.

• Return -1 if a second largest element does not exist.

Given an array of 0s and 1s, find the maximum count of 1s by flipping a sub-array at most once.

• Iterate through the array and keep track of the maximum count of 1s obtained by flipping a sub-array.

• Consider flipping a sub-array from index i to j and calculate the count of 1s in the resulting array.

• Return the maximum count of 1s obtained by flipping a sub-array at most once.

Count the number of islands in a 2D matrix of 1s and 0s.

• Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.

• Mark visited cells to avoid redundant traversal.

• Increment island count whenever a new island is encountered.

Calculate the Nth element of a modified Fibonacci series given the first two numbers and N, with the result modulo 10^9 + 7.

• Implement a function to calculate the Nth element of the series using the Fibonacci rule f(x) = f(x - 1) + f(x - 2)

• Return the answer modulo 10^9 + 7 due to the possibility of a very large result

• The series is 1-based indexed, so the first two numbers are at positions 1 and 2 respectively

Optimized approach to find third largest element from array using half traversal.

• Sort the array in descending order and return the element at index 2.

• Use a max heap to keep track of the top 3 elements while traversing the array.

• Use two variables to keep track of the second and third largest elements while traversing the array.

• Divide the array into two halves and find the maximum and second maximum in each half, then compare them to find the third largest element.

Indexes are used to improve query performance. Multiple clustered and non-clustered indexes can be created on a table.

• Indexes are used to quickly locate data without scanning the entire table.

• Clustered index determines the physical order of data in a table.

• Non-clustered index is a separate structure that contains a copy of the indexed columns and a pointer to the actual data.

• A table can have only one clustered index, but multiple non-clustered indexes.

• Indexes should be create...read more

ACID properties ensure database transactions are reliable. Two transactions can occur simultaneously using locking and isolation.

• ACID stands for Atomicity, Consistency, Isolation, and Durability.

• Atomicity ensures that a transaction is treated as a single unit of work, either all or none of it is executed.

• Consistency ensures that a transaction brings the database from one valid state to another.

• Isolation ensures that concurrent transactions do not interfere with each other.

• Dur...read more

Find the duplicate number in an array of integers from 0 to N-2.

• Iterate through the array and keep track of the frequency of each number using a hashmap.

• Return the number with a frequency greater than 1 as the duplicate number.

The task is to find the frequency of each character from 'a' to 'z' in a given string.

• Create an array of size 26 to store the frequency of each character from 'a' to 'z'.

• Iterate through the string and increment the count of the corresponding character in the array.

• Print the array of frequencies as the output for each test case.

Answering how to print first character of words in a string using one stack and an array.

• For using one stack, push each character onto the stack and pop when a space is encountered. Print the popped character.

• For using an array, split the string into words and print the first character of each word.

• In both cases, handle edge cases like empty string and string with only one word.

The N Queens Problem involves finding all possible placements of N queens on an N x N chessboard without threatening each other.

• Use backtracking algorithm to explore all possible configurations.

• Keep track of rows, columns, and diagonals to ensure queens do not threaten each other.

• Generate all valid configurations and print them out.

Reverse words in a string while handling leading, trailing, and multiple spaces.

• Split the input string by spaces to get individual words

• Reverse the order of the words

• Join the reversed words with a single space in between

Reverse the order of elements in an array and display the reversed array.

• Iterate through the array from both ends and swap the elements until the middle is reached.

• Use a temporary variable to store the element being swapped.

• Print the reversed array after all elements have been swapped.

The task is to determine the maximum profit that can be achieved by performing up to two buy-and-sell transactions on a given set of stock prices.

• Iterate through the array of stock prices and calculate the maximum profit that can be achieved by buying and selling at different points.

• Keep track of the maximum profit after the first transaction and the maximum profit overall by considering different combinations of buy and sell points.

• Return the maximum profit obtained after co...read more

Detect if a given linked list is circular by checking if it forms a closed loop.

• Traverse the linked list using two pointers, one moving at double the speed of the other.

• If the two pointers meet at any point, the linked list is circular.

• If the faster pointer reaches the end of the list (NULL), the linked list is not circular.

Given an integer, find the final single-digit value after summing its digits iteratively.

• Iteratively sum the digits of the given integer until the result is a single-digit number

• Output the final single-digit integer for each test case

• Handle multiple test cases efficiently

Given an array and a number, find if the number can be generated using sum of array members and output those numbers.

• Iterate through the array and check if the number can be generated using the sum of array members

• Use a hash table to store the difference between the number and each array element

• If the difference is found in the hash table, output the corresponding array elements

• If no such combination is found, output 'Not possible'

Sort an array using pancake flips and return the sequence of flips made.

• Iterate through the array and find the position of the maximum element in each iteration.

• Perform pancake flips to move the maximum element to the correct position.

• Continue this process until the array is sorted.

• Return the sequence of positions from where flips were made.

Check if a given number is a Fibonacci number or not.

• Iterate through the Fibonacci sequence until you find a number greater than or equal to the given number.

• Check if the given number matches the Fibonacci number found in the sequence.

• If the number matches, output 'YES'; otherwise, output 'NO'.

Reverse the letters of a string while keeping non-alphabet characters in their original position.

• Iterate through the string and store the non-alphabet characters in their original positions

• Reverse the letters using two pointers technique

• Combine the reversed letters with the non-alphabet characters to get the final reversed string

Find duplicates in an array of integers within a specified range.

• Iterate through the array and keep track of the count of each element using a hashmap.

• Return elements with count greater than 1 as duplicates.

• Time complexity can be optimized to O(N) using a set to store duplicates.

• Example: For input [0, 3, 1, 2, 3], output should be [3].

Sort an array of 0s, 1s, and 2s in linear time complexity.

• Use three pointers to keep track of 0s, 1s, and 2s while traversing the array.

• Swap elements based on the values encountered to sort the array in-place.

• Time complexity of the algorithm should be O(N) where N is the size of the array.

Query to find the Nth highest salary with employee name

• Use a subquery to rank the salaries in descending order

• Select the distinct salary from the subquery with LIMIT N-1, 1 to get the Nth highest salary

• Join the main table with the subquery on the salary column to get the employee name

Count distinct pairs in an array whose sum equals a given target.

• Use two pointers approach to iterate through the array and find pairs with sum equal to target.

• Keep track of visited pairs to avoid counting duplicates.

• Return -1 if no such pair exists with the given target.

Rearrange array to move zeros to the left while maintaining relative order of non-zero elements.

• Iterate through the array and maintain two pointers, one for zero elements and one for non-zero elements.

• Swap elements at the two pointers until all zeros are moved to the left.

• Ensure to maintain the relative order of non-zero elements while rearranging the array.

Time complexity of data structure operations

• Arrays: O(1) for access, O(n) for search/insert/delete

• Linked Lists: O(n) for access/search, O(1) for insert/delete

• Stacks/Queues: O(1) for access/insert/delete

• Hash Tables: O(1) for access/insert/delete (average case)

• Trees: O(log n) for access/search/insert/delete (balanced)

• Heaps: O(log n) for access/insert/delete

• Graphs: Varies depending on algorithm used

Find the sum of the subarray with the maximum sum among all subarrays in an array of integers.

• Iterate through the array and keep track of the current sum and maximum sum.

• Update the maximum sum whenever a new maximum subarray sum is found.

• Handle cases where all elements are negative or the array is empty.

• Example: For input arr = [-2, 1, -3, 4, -1], the maximum subarray sum is 4.

Detect and remove loop in a singly linked list in place with O(n) time complexity and O(1) space complexity.

• Use Floyd's Cycle Detection Algorithm to identify the loop in the linked list.

• Once the loop is detected, use two pointers to find the start of the loop.

• Adjust the pointers to remove the loop and return the modified linked list.

Count distinct substrings of a given string using trie data structure.

• Implement a trie data structure to store all substrings of the given string.

• Count the number of nodes in the trie to get the distinct substrings count.

• Handle empty string case separately.

• Example: For 'ab', distinct substrings are: '', 'a', 'b', 'ab'.

Find the equilibrium index of an array where sum of elements on left equals sum on right.

• Iterate through array to calculate prefix and suffix sums

• Compare prefix and suffix sums to find equilibrium index

• Return -1 if no equilibrium index is found

The task is to return the spiral path of elements in a given matrix.

• Iterate through the matrix in a spiral path by adjusting the boundaries of rows and columns.

• Keep track of the direction of traversal (right, down, left, up) to form the spiral path.

• Handle edge cases like when the matrix is a single row or column.

• Implement a function that takes the matrix dimensions and elements as input and returns the spiral path.

Span is an inline element used for styling small portions of text, while div is a block-level element used for grouping and styling larger sections of content.

• Span is an inline element, div is a block-level element

• Span is used for styling small portions of text, div is used for grouping larger sections of content

• Span does not create a new line, div creates a new block-level element

The task is to determine the minimum time required to visit all cities and roads in Ninja Land.

• Create a graph representation of the cities and roads.

• Use a traversal algorithm to find the minimum time to visit all cities and roads.

• Return -1 if it is impossible to visit all roads.

• Consider the constraints provided in the problem statement.

• Implement the function to calculate the minimum travel time.

Normalization is the process of organizing data in a database to reduce redundancy and improve data integrity.

• Normalization is a technique used to organize data in a database efficiently.

• Third Normal Form (3NF) is a level of normalization that ensures that data is stored in a way that prevents certain types of data anomalies.

• In 3NF, every non-prime attribute is fully functionally dependent on the primary key.

• For example, if we have a table 'Employees' with columns 'EmployeeID...read more

Generate all permutations of a given string using recursion and backtracking.

• Use recursion to generate all possible permutations of the string.

• Use backtracking to backtrack and explore all possible combinations.

• Store each permutation in an array of strings.

SQL query to find the second highest salary from a table

• Use the MAX() function to find the highest salary

• Use the NOT IN operator to exclude the highest salary from the results

• Order the results in descending order and limit the query to return only the second row

Reducing page loading time can be achieved through various techniques.

• Optimizing images and videos

• Minimizing HTTP requests

• Using a content delivery network (CDN)

• Enabling browser caching

• Minimizing JavaScript and CSS files

• Using lazy loading for images and videos

• Reducing server response time

• Using gzip compression

• Minimizing redirects

• Using a faster web hosting service

One method to rotate an array by k positions is to reverse the array, then reverse the first k elements, and finally reverse the remaining elements.

• Reverse the entire array

• Reverse the first k elements

• Reverse the remaining elements

• Example: Array = ['a', 'b', 'c', 'd', 'e'], k = 2. After rotation: ['d', 'e', 'a', 'b', 'c']

To find the area of a circle inscribed in a square, calculate the radius using the given point and then use the formula for the area of a circle.

• Calculate the distance from the given point to the center of the square to find the radius of the circle

• Use the formula for the area of a circle (A = πr^2) to calculate the area

• Remember that the radius of the circle is half the side length of the square

Reversing k nodes in a linked list

• Iterate through the linked list in groups of k nodes

• Reverse each group of k nodes

• Update the pointers accordingly to maintain the reversed order

Joins in SQL are used to combine rows from two or more tables based on a related column between them.

• Joins are used to retrieve data from multiple tables based on a related column

• Common types of joins include INNER JOIN, LEFT JOIN, RIGHT JOIN, and FULL JOIN

• Example: SELECT * FROM table1 INNER JOIN table2 ON table1.column = table2.column

Normalization is the process of organizing data in a database to reduce redundancy and improve data integrity.

• Normalization is used to eliminate data redundancy by breaking up tables into smaller, related tables.

• There are different normal forms such as 1NF, 2NF, 3NF, BCNF, and 4NF, each with specific rules to follow.

• Normalization helps in reducing data anomalies and ensures data integrity.

• Example: Breaking up a customer table into separate tables for customer details and orde...read more

Program to find nth prime number and optimize the code

• Use Sieve of Eratosthenes algorithm to generate prime numbers

• Implement binary search to find nth prime number

• Use memoization to optimize the code

• Avoid unnecessary calculations by checking if a number is prime before checking its factors

Circular linked list is a data structure where the last node points back to the first node.

• In a circular linked list, each node has a pointer to the next node and the last node points back to the first node.

• Traversal in a circular linked list can start from any node and continue until the starting node is reached again.

• Insertion and deletion operations in a circular linked list are similar to those in a regular linked list, but special care must be taken to update the pointer...read more

Use ALTER TABLE to add a new column and then use MAX function to find the highest salary.

• Use ALTER TABLE statement to add a new column to the table.

• Use MAX function in SQL to find the maximum salary of employees.

Count the occurrence of each element in an array of strings

• Iterate through the array and use a hashmap to store the count of each element

• If element already exists in the hashmap, increment its count by 1

• Return the hashmap with element counts

Cubes are multidimensional data structures used for analysis and reporting. They differ from databases in their structure and purpose.

• Cubes store data in a multidimensional format, allowing for efficient analysis and reporting.

• They are designed to handle large volumes of data and provide fast query performance.

• Cubes use dimensions, measures, and hierarchies to organize and analyze data.

• Unlike databases, cubes are optimized for analytical processing rather than transactional p...read more

Indexes in SQL are used to improve the performance of queries by allowing the database to quickly retrieve data.

• Indexes are created on columns in a table to speed up data retrieval.

• They work similar to an index in a book, allowing the database to quickly find the relevant data.

• Primary keys automatically have an index created on them.

• Indexes can be unique, meaning that each value in the indexed column must be unique.

• Examples: CREATE INDEX idx_name ON table_name(column_name);

Windows and Android OS have evolved with new features and improvements compared to past versions.

• Windows 10 introduced a new Start menu and Cortana virtual assistant.

• Android 11 focused on improved privacy controls and messaging features.

• Both OS have enhanced security measures compared to their past versions.

A SQL query to move a table from one schema to another.

• Use the ALTER TABLE statement to rename the table and move it to the new schema.

• Specify the new schema name in the ALTER TABLE statement.

• Ensure that the user executing the query has the necessary privileges to perform the operation.

Program to find length of string using custom function

• Create a custom function that takes an array of strings as input

• Iterate through each string in the array and calculate its length

• Return the lengths of all strings in an array

Reverse the array of strings

• Create a new array and iterate through the original array in reverse order, adding each element to the new array

• Use built-in array methods like reverse() or spread operator for a more concise solution

• Ensure to handle edge cases like empty array or array with only one element

Sort a vector based on another vector

• Use std::sort with a custom comparator function

• The comparator function should compare the indices of the elements in the second vector

• The first vector should be sorted based on the order of the indices in the second vector

State management in React involves managing and updating the state of components efficiently.

• Use React's built-in state management with setState() method

• Utilize React Context API for managing global state

• Implement Redux for complex state management in larger applications

A stored procedure is a precompiled set of SQL statements that can be executed on a database server.

• Stored procedures are used to encapsulate and execute complex database operations.

• They can be used to improve performance by reducing network traffic.

• Stored procedures can be parameterized and reused across multiple applications.

• They provide a level of security by allowing access to the database only through the procedure.

• Examples: Creating a stored procedure to insert data int...read more

Data preprocessing involves cleaning, transforming, and organizing raw data before analysis.

• 1. Data cleaning: Removing or correcting errors in the data, handling missing values.

• 2. Data transformation: Normalizing, scaling, encoding categorical variables.

• 3. Data reduction: Dimensionality reduction techniques like PCA.

• 4. Data integration: Combining data from multiple sources.

• 5. Feature engineering: Creating new features from existing data.

• 6. Splitting data: Dividing data into t...read more

Level Order Traversal for Binary Tree is a method to visit all nodes level by level starting from the root.

• Use a queue data structure to keep track of nodes at each level

• Start by pushing the root node into the queue

• While the queue is not empty, dequeue a node, visit it, and enqueue its children

The minimum number of swaps needed to group all ones together in an array of 0s and 1s.

• Iterate through the array to count the total number of ones.

• Use a sliding window of size equal to the total number of ones to find the window with the minimum number of zeros.

• Calculate the number of swaps needed to move all ones to that window.

A project manager is responsible for planning, executing, and closing projects within a specific timeframe and budget.

• Developing project plans and timelines

• Assigning tasks to team members

• Monitoring progress and adjusting plans as needed

• Communicating with stakeholders

• Ensuring project goals are met within constraints

DevOps components include culture, automation, measurement, and sharing.

• Culture: Encouraging collaboration and communication between development and operations teams.

• Automation: Implementing tools for continuous integration, continuous delivery, and infrastructure as code.

• Measurement: Monitoring and analyzing performance metrics to improve processes and identify areas for optimization.

• Sharing: Facilitating knowledge sharing and feedback loops to foster continuous improvement.

Calculate the sum of digits of a given number.

• Iterate through each digit of the number and add them together.

• Use modulo operator to extract each digit.

• Repeat until all digits are processed.

• Example: For number 123, sum of digits = 1 + 2 + 3 = 6.

Replace alternative characters in a string with a specified character

• Iterate through the string and replace characters at odd indices with the specified character

• Use a loop to go through each character and check if its index is odd or even before replacing

• Example: Input string 'hello' and replacement character '*', output 'h*l*'

Left join includes all records from the left table and matching records from the right table, while right join includes all records from the right table and matching records from the left table.

• Left join keeps all records from the left table, even if there are no matches in the right table.

• Right join keeps all records from the right table, even if there are no matches in the left table.

• Example: If we have a table of employees and a table of departments, a left join will inclu...read more

Zigzag traversal of binary tree involves alternating the direction of traversal at each level.

• Use a queue to perform level order traversal of the binary tree.

• For each level, alternate between adding nodes to the result list from left to right and right to left.

• Continue this process until all levels have been traversed.

SSMS is a management tool for SQL Server, SSIS is an ETL tool, and SSAS is a BI tool for analyzing data.

• SSMS (SQL Server Management Studio) is a graphical management tool for SQL Server.

• SSIS (SQL Server Integration Services) is an ETL (Extract, Transform, Load) tool used for data integration and workflow applications.

• SSAS (SQL Server Analysis Services) is a BI (Business Intelligence) tool used for analyzing and reporting data.

• SSMS is used for managing databases, creating and ...read more

ATM (Automated Teller Machine) is an electronic banking outlet that allows customers to complete basic transactions without the aid of a branch representative.

• ATMs allow customers to withdraw cash, deposit checks, transfer money between accounts, and check account balances.

• ATMs communicate with the bank's computer system to verify account information and process transactions.

• ATMs use a magnetic stripe or chip on the customer's debit or credit card to identify the account and ...read more

Plane flying between two points puzzle

• The plane is flying between two points on the globe

• The shortest path between two points on a sphere is a great circle route

• Factors like wind speed and direction can affect the plane's route

Normalization is the process of organizing data in a database to reduce redundancy and improve data integrity. Keys are used to uniquely identify records in a table.

• Normalization involves breaking down data into smaller, more manageable parts to reduce redundancy.

• Keys are used to uniquely identify records in a table. Examples include primary keys, foreign keys, and candidate keys.

• Normalization helps in maintaining data integrity and reducing anomalies such as insertion, updat...read more

Sort an array of strings containing '0', '1', and '2'.

• Use counting sort algorithm to count the occurrences of '0', '1', and '2'.

• Create a new array with the sorted counts of '0', '1', and '2'.

• Join the sorted array back into a single array of strings.

Oops concepts refer to Object-Oriented Programming principles like Inheritance, Polymorphism, Encapsulation, and Abstraction.

• Inheritance: Allows a class to inherit properties and behavior from another class.

• Polymorphism: Ability of objects to take on multiple forms.

• Encapsulation: Bundling data and methods that operate on the data into a single unit.

• Abstraction: Hiding the complex implementation details and showing only the necessary features.