50+ MAQ Software Interview Questions and Answers for Freshers

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.

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

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.

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'

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

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

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

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.

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

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

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.

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.

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.

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

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.

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

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

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.

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

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

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

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

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