Nagarro
400+ MotionCut Interview Questions and Answers
Q1. Crazy Numbers Pattern Challenge
Ninja enjoys arranging numbers in a sequence. He plans to arrange them in 'N' rows such that:
- The first row contains 1 number.
- The second row contains 2 numbers.
- The third row c...read more
Arrange numbers in a sequence in 'N' rows with increasing order and repeating after 9.
Iterate through each test case and for each row, print numbers in increasing order with a loop.
Keep track of the current number to print and reset to 1 after reaching 9.
Handle formatting to align numbers correctly in each row.
Ensure to print the correct number of rows based on the input 'N'.
Q2. String Compression Problem Statement
Ninja needs to perform basic string compression. For any character that repeats consecutively more than once, replace the repeated sequence with the character followed by th...read more
Implement a function to compress a string by replacing consecutive characters with the character followed by the count of repetitions.
Iterate through the input string and keep track of consecutive characters and their counts.
Replace consecutive characters with the character followed by the count of repetitions if count is greater than 1.
Return the compressed string as output.
Q3. Write a program: two input, one is N(any integer, lets say 3), second input will be array of integers(duplicate/multiple occurrences of same integer, lets say [2,3,2,4,2] ). You have to return the number whose...
read moreProgram to find the number whose occurrence is greater than N/2 in an array of integers.
Take two inputs, one integer N and an array of integers.
Loop through the array and count the occurrence of each number.
Return the number whose occurrence is greater than N/2.
If no such number found, return '-1'.
Q4. Ninja and the New Year Guests Problem
Ninja has organized a new year party and wants to verify if the guests are programmers by challenging them with a coding task. As an invited programmer, you're tasked to so...read more
Compute the number of valid permutations of integers from 0 to N-1 such that at least K positions satisfy ARR[I] = I.
Use dynamic programming to solve the problem efficiently.
Consider the cases where K is equal to N or N-1 separately.
Modulo the result by 10^9 + 7 to avoid overflow issues.
Q5. Fibonacci Membership Check
Given an integer N
, determine if it is a member of the Fibonacci series. Return true
if the number is a member of the Fibonacci series, otherwise return false
.
Fibonacci Series Defini...read more
Check if a given integer is a member of the Fibonacci series.
Implement a function to check if the given number is a perfect square.
Check if 5*N^2 + 4 or 5*N^2 - 4 is a perfect square to determine Fibonacci membership.
Return true if the number is a perfect square of 5*N^2 + 4 or 5*N^2 - 4, otherwise false.
Q6. Maximum Meetings Problem Statement
Given the schedule of N meetings with their start time Start[i]
and end time End[i]
, you need to determine which meetings can be organized in a single meeting room such that t...read more
Given N meetings with start and end times, find the maximum number of meetings that can be organized in a single room without overlap.
Sort the meetings based on their end times.
Iterate through the sorted meetings and select the next meeting that does not overlap with the current meeting.
Keep track of the selected meetings and return their indices in the order they are organized.
Q7. Count Pairs with Difference K
Given an array of integers and an integer K
, determine and print the count of all pairs in the array that have an absolute difference of K
.
Input:
The first line of the input conta...read more
Count pairs in an array with a specific absolute difference.
Iterate through the array and for each element, check if the element + K or element - K exists in the array.
Use a hash set to store elements for constant time lookups.
Keep track of the count of valid pairs found.
Q8. Next Permutation Problem Statement
You are given a permutation of 'N' integers. A sequence of 'N' integers is considered a permutation if it includes all integers from 1 to 'N' exactly once. Your task is to rea...read more
Given a permutation of 'N' integers, rearrange the numbers to form the lexicographically next greater permutation.
Iterate from right to left to find the first element that is smaller than the element to its right.
Swap this element with the smallest element to its right that is greater than it.
Reverse the elements to the right of the swapped element to get the lexicographically next greater permutation.
If no such element is found in step 1, then the permutation is already the ...read more
Q9. Maximum Subarray Sum Problem Statement
Given an array arr
of length N
consisting of integers, find the sum of the subarray (including empty subarray) with the maximum sum among all subarrays.
Explanation:
A sub...read more
Find the sum of the subarray with the maximum sum among all subarrays in an array of integers.
Use Kadane's algorithm to find the maximum subarray sum in linear time complexity.
Initialize two variables: maxEndingHere and maxSoFar to keep track of the current subarray sum and the maximum subarray sum found so far.
Iterate through the array and update the variables accordingly.
Return the maxSoFar as the result.
Q10. Swap Kth Elements in an Array
Given an array ARR
of size N
, perform the operation to swap the Kth element from the beginning with the Kth element from the end of the array.
Example:
Input:
N = 5, K = 2
ARR = [1,...read more
Swap Kth elements from the beginning and end of an array.
Create a temporary variable to store the Kth element from the beginning
Swap the Kth element from the beginning with the Kth element from the end
Return the modified array
Q11. Coin Game Winner Problem Statement
Two players 'X' and 'Y' are participating in a coin game. Starting with 'N' coins, players alternate turns, with 'X' starting first. On each turn, a player has three choices: ...read more
Determine the winner of a coin game where players take turns picking coins optimally.
Players take turns picking 'A', 'B', or 1 coin each turn
The player unable to make a move loses
Implement a function to determine the winner based on the given inputs
Q12. Problem: Sort an Array of 0s, 1s, and 2s
Given an array/list ARR
consisting of integers where each element is either 0, 1, or 2, your task is to sort this array in increasing order.
Input:
The input starts with...read more
Sort an array of 0s, 1s, and 2s in increasing order.
Use a three-pointer approach to partition the array into sections of 0s, 1s, and 2s.
Iterate through the array and swap elements based on their values and the pointers.
After sorting, the array will have 0s on the left, 1s in the middle, and 2s on the right.
Q13. Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the c...read more
The task is to find the total number of ways to make change for a specified value using given denominations.
Use dynamic programming to solve this problem efficiently.
Create a 1D array to store the number of ways to make change for each value from 0 to the target value.
Iterate through the denominations and update the array based on the current denomination.
The final answer will be the value at the target index of the array.
Q14. Complete String Problem Statement
Given an array of strings A
of size N
, determine the longest complete string. A string is deemed complete if every prefix of the string also appears in the array. If multiple s...read more
Given an array of strings, find the longest complete string where every prefix of the string also appears in the array.
Iterate through each string in the array and check if all its prefixes exist in the array.
Keep track of the longest complete string found so far, and return the lexicographically smallest one if multiple exist.
If no complete string is found, return 'None'.
Q15. K - Sum Path In A Binary Tree
Given a binary tree where each node contains an integer value, and a value 'K', your task is to find all the paths in the binary tree such that the sum of the node values in each p...read more
Find all paths in a binary tree with nodes summing up to a given value K.
Traverse the binary tree and keep track of the current path and its sum.
At each node, check if the sum equals K and store the path if true.
Recursively explore left and right subtrees while updating the path and sum.
Return the list of paths that sum up to K in the binary tree.
Q16. Convert Sentence Problem Statement
Convert a given string 'S' into its equivalent representation based on a mobile numeric keypad sequence. Using the keypad layout shown in the reference, output the sequence of...read more
Convert a given string into its equivalent representation based on a mobile numeric keypad sequence.
Iterate through each character in the input string and map it to its corresponding numeric keypad sequence.
Use a dictionary to store the mapping of characters to numeric sequences.
Handle lowercase characters only and ignore special characters, capital letters, and spaces.
Q17. Digits Decoding Problem Statement
A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes, he encoded each character of the stri...read more
The problem involves decoding a numeric sequence into a valid string using a given mapping of characters to numbers.
Use dynamic programming to count the number of ways to decode the sequence.
Consider different cases for decoding single digits and pairs of digits.
Keep track of the number of ways to decode at each position in the sequence.
Return the final count modulo 10^9 + 7 as the answer.
Q18. Count Ways To Reach The N-th Stair Problem Statement
You are given a number of stairs, N
. Starting at the 0th stair, you need to reach the Nth stair. Each time you can either climb one step or two steps. You ha...read more
The problem involves finding the number of distinct ways to climb to the Nth stair by taking one or two steps at a time.
Use dynamic programming to solve this problem efficiently.
The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.
Handle large inputs by taking modulo 10^9+7 to avoid overflow.
Example: For N=3, there are 3 ways to climb to the third stair: (0, 1, 2, 3), (0, 2, 3), and (0, 1, 3).
Q19. Find the Longest Palindromic Substring
Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.
If there are multiple longest palindromic ...read more
Find the longest palindromic substring in a given string, returning the rightmost one if multiple exist.
Iterate through the string and expand around each character to find palindromes
Keep track of the longest palindrome found and its starting index
Return the substring starting from the index of the longest palindrome found
Q20. K Subsets with Equal Sum Problem Statement
Determine whether it is possible to partition an array ARR
into K
subsets, each having an equal sum.
Example:
Input:
ARR = [3, 5, 2, 4, 4], K = 2
Output:
true
Explanat...read more
Yes, it is possible to partition an array into K subsets with equal sum.
Check if the total sum of the array is divisible by K.
Use backtracking to try all possible combinations of subsets.
Keep track of visited elements to avoid repetition.
Example: ARR = [3, 5, 2, 4, 4], K = 2. Possible subsets: [4, 5] and [2, 3, 4].
Q21. Subsequences of String Problem Statement
You are provided with a string 'STR'
that consists of lowercase English letters ranging from 'a' to 'z'. Your task is to determine all non-empty possible subsequences of...read more
Generate all possible subsequences of a given string.
Use recursion to generate all possible subsequences by including or excluding each character in the string.
Maintain a current index to keep track of the characters being considered.
Append the current character to each subsequence generated so far.
Recursively call the function with the next index to include the next character in subsequences.
Q22. Find Duplicates in an Array
Given an array ARR
of size 'N', where each integer is in the range from 0 to N - 1, identify all elements that appear more than once.
Return the duplicate elements in any order. If n...read more
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 HashSet to store seen elements.
Q23. 0/1 Knapsack Problem Statement
A thief is planning to rob a store and can carry a maximum weight of 'W' in his knapsack. The store contains 'N' items where the ith item has a weight of 'wi' and a value of 'vi'....read more
Yes, the 0/1 Knapsack problem can be solved using dynamic programming with a space complexity of not more than O(W).
Use a 1D array to store the maximum value that can be stolen for each weight from 0 to W.
Iterate through the items and update the array based on whether including the current item would increase the total value.
The final element of the array will contain the maximum value that can be stolen within the weight limit.
Q24. N-th Term Of Geometric Progression
Find the N-th term of a Geometric Progression (GP) series given the first term A, the common ratio R, and the term position N.
Explanation:
The general form of a GP series is ...read more
Calculate the N-th term of a Geometric Progression series given the first term, common ratio, and term position.
Iterate through each test case and apply the formula A * R^(N-1) to find the N-th term
Use modular arithmetic to handle large calculated terms by returning the result modulo 10^9 + 7
Q25. Equilibrium Index Problem Statement
Given an array Arr
consisting of N integers, your task is to find the equilibrium index of the array.
An index is considered as an equilibrium index if the sum of elements of...read more
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
Q26. Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This subse...read more
Find the length of the longest strictly increasing subsequence in an array of integers.
Use dynamic programming to solve this problem efficiently.
Initialize an array to store the length of the longest increasing subsequence ending at each index.
Iterate through the array and update the length of the longest increasing subsequence for each element.
Return the maximum value in the array as the result.
Q27. Trapping Rain Water Problem Statement
You are given a long type array/list ARR
of size N
, representing an elevation map. The value ARR[i]
denotes the elevation of the ith
bar. Your task is to determine the tota...read more
Calculate the total amount of rainwater that can be trapped between given elevations in an array.
Iterate through the array and calculate the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water at each bar to get the total trapped water for the entire array.
Q28. Find All Pairs Adding Up to Target
Given an array of integers ARR
of length N
and an integer Target
, your task is to return all pairs of elements such that they add up to the Target
.
Input:
The first line conta...read more
Given an array of integers and a target, find all pairs of elements that add up to the target.
Iterate through the array and for each element, check if the target minus the element exists in a hash set.
If it exists, add the pair to the result. If not, add the element to the hash set.
Handle cases where the same element is used twice to form a pair.
Return (-1, -1) if no pair is found.
Q29. Letter Combinations of a Phone Number Problem Statement
You are given a string S
containing digits from 2 to 9 inclusive. Your task is to find all possible letter combinations that the number could represent, b...read more
Given a string of digits, find all possible letter combinations based on phone keypad mapping.
Use a recursive approach to generate all possible combinations of letters for each digit in the input string.
Create a mapping of digits to corresponding letters on a phone keypad.
Iterate through the input string and generate combinations by combining letters for each digit.
Return the list of all possible letter combinations as an array of strings.
Q30. Closest Perfect Square Problem Statement
Given a positive integer 'N', determine the perfect square number closest to 'N' and the number of steps required to reach that perfect square.
Example:
Input:
N = 21
Ou...read more
Given a positive integer 'N', find the closest perfect square number and the steps required to reach it.
Find the square root of N and round it to the nearest integer to get the closest perfect square.
Calculate the difference between the closest perfect square and N to get the number of steps required.
Return the closest perfect square and the number of steps as output.
Q31. This is for Mainframe Dev. how would you sort two unsorted ps files into three different ps files having unique records of both the files in different files and common records in one. explain the steps.
Sort two unsorted PS files into three different PS files with unique and common records.
Use SORT utility to sort the two input files individually.
Use JOINKEYS to join the two sorted files on a common key.
Use OUTFIL to direct the output to three different files based on the record type.
Ensure that the output files have unique records and common records as required.
Q32. Valid Parentheses Problem Statement
Given a string 'STR' consisting solely of the characters “{”, “}”, “(”, “)”, “[” and “]”, determine if the parentheses are balanced.
Input:
The first line contains an integer...read more
The task is to determine if given strings containing only parentheses are balanced or not.
Iterate through each character in the string and use a stack to keep track of opening parentheses.
If a closing parenthesis is encountered, check if the stack is empty or if the top of the stack matches the corresponding opening parenthesis.
If all parentheses are balanced, the stack should be empty at the end.
Return 'Balanced' if the stack is empty, otherwise return 'Not Balanced'.
Q33. Missing Number Statement
Given an array ARR
of integers with size N
, where all elements appear an even number of times except for one element which appears an odd number of times, identify the element that appe...read more
Identify the element that appears an odd number of times in an array of integers where all other elements appear an even number of times.
Iterate through the array and use XOR operation to find the element that appears an odd number of times.
XOR of a number with itself is 0, so XOR of all elements will give the odd occurring element.
Return the result after XORing all elements in the array.
Q34. Trailing Zeros in Factorial Problem
Find the number of trailing zeroes in the factorial of a given number N
.
Input:
The first line contains an integer T
representing the number of test cases.
Each of the followi...read more
Count the number of trailing zeros in the factorial of a given number.
To find the number of trailing zeros in N!, count the number of factors of 5 in the prime factorization of N.
Each factor of 5 contributes to a trailing zero in the factorial.
For example, for N=10, there are 2 factors of 5 in the prime factorization (5 and 10), so there are 2 trailing zeros.
Q35. Rotational Equivalence of Strings Problem Statement
Given two strings 'P' and 'Q' of equal length, determine if string 'P' can be transformed into string 'Q' by cyclically rotating it to the right any number of...read more
Check if one string can be transformed into another by cyclically rotating it to the right.
Iterate through all possible rotations of string P and check if any of them match string Q.
Use string concatenation and substring operations to simulate the rotation.
Optimize the solution to O(N) time complexity by checking if string Q is a substring of P concatenated with itself.
Q36. Common Elements Problem Statement
Identify and output the common strings present in both given arrays of lowercase alphabets for each test case.
Input:
The first line contains an integer 'T' representing the nu...read more
The problem requires identifying and outputting common strings present in two arrays of lowercase alphabets for each test case.
Iterate through the elements of the second array and check if they are present in the first array.
Use a hash set or map to efficiently check for common elements.
Return the common strings in the order they appear in the second array.
Q37. Partition to K Equal Sum Subsets Problem
Given an array of integers and a positive integer 'K', determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of elements in each s...read more
The problem involves dividing an array into K subsets with equal sum.
Use backtracking to try all possible combinations of subsets.
Keep track of the sum of elements in each subset and check if they are equal to the target sum.
Optimize by sorting the array in descending order and assigning elements to subsets greedily.
Handle edge cases like when the sum of elements is not divisible by K.
Q38. Secret Message Decoding Problem
Ninja encountered an encoded secret message where each character from 'A' to 'Z' is mapped to a numeric value (A = 1, B = 2, ..., Z = 26). Given a numeric sequence (SEQ) derived ...read more
The problem involves decoding a numeric sequence back into a valid string based on a given mapping of characters to numeric values.
Use dynamic programming to keep track of the number of ways to decode the sequence at each position.
Consider edge cases such as '0' and '00' which do not have valid decodings.
Handle cases where two digits can be combined to form a valid character (e.g., '12' corresponds to 'L').
Q39. Remove String from Linked List Problem
You are provided with a singly linked list where each node contains a single character, along with a string 'STR'. Your task is to remove all occurrences of the string 'ST...read more
Remove all occurrences of a given string from a singly linked list by starting from the end of the list.
Traverse the linked list from the end to the beginning to efficiently remove the string occurrences.
Check for the string 'STR' in each node and remove it if found.
Continue checking for new occurrences of 'STR' after removal to ensure all instances are removed.
Return the head of the modified linked list after processing each test case.
Q40. Sort a "K" Sorted Doubly Linked List
Given a doubly-linked list with N
nodes, where each node’s position deviates at most K
positions from its position in the sorted list, your task is to sort this given doubly...read more
Sort a doubly linked list where each node's position deviates at most K positions from its position in the sorted list.
Iterate through the doubly linked list and maintain a min-heap of size K+1 to keep track of the next smallest element.
Remove the smallest element from the heap and add it to the sorted list. Update the heap with the next element from the removed node's next position.
Continue this process until all nodes are added to the sorted list.
Q41. Character Counting Challenge
Create a program that counts and prints the total number of specific character types from user input. Specifically, you need to count lowercase English alphabets, numeric digits (0-...read more
Create a program to count lowercase alphabets, digits, and white spaces from user input until '$' is encountered.
Read characters from input stream until '$' is encountered
Count lowercase alphabets, digits, and white spaces separately
Print the counts of each character type as three integers separated by spaces
Q42. Minimum Number of Platforms Needed Problem Statement
You are given the arrival and departure times of N trains at a railway station for a particular day. Your task is to determine the minimum number of platform...read more
The problem involves determining the minimum number of platforms needed at a railway station based on arrival and departure times of trains.
Sort the arrival and departure times in ascending order.
Use two pointers to keep track of overlapping schedules.
Increment platform count when a train arrives and decrement when it departs.
Return the maximum platform count needed.
Q43. Pair Sum Problem Statement
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.
Note:
Each pa...read more
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
Iterate through the array and use a hashmap to store the difference between the target sum and each element.
Check if the current element's complement exists in the hashmap, if so, add the pair to the result list.
Sort the pairs based on the criteria mentioned in the question.
Return the list of pairs as the final output.
Q44. Palindrome String Validation
Determine if a given string 'S' is a palindrome, considering only alphanumeric characters and ignoring spaces and symbols.
Note:
The string 'S' should be evaluated in a case-insensi...read more
Check if a given string is a palindrome after removing special characters, spaces, and converting to lowercase.
Remove special characters and spaces from the input string
Convert the string to lowercase
Check if the modified string is a palindrome by comparing characters from start and end
Q45. Validate BST Problem Statement
Given a binary tree with N
nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true
; otherwise, return false
.
A binary search tree (BST) is a b...read more
Validate if a given binary tree is a Binary Search Tree (BST) or not.
Check if the left subtree of a node contains only nodes with data less than the node's data.
Check if the right subtree of a node contains only nodes with data greater than the node's data.
Recursively check if both the left and right subtrees are also binary search trees.
Use level order traversal to construct the binary tree from input data.
Q46. Nearest Numbers with the Same Number of Set Bits
Given a positive integer n
, your task is to determine the next smallest integer and the previous largest integer that have the same number of '1' bits in their b...read more
Given a positive integer, find the next smallest and previous largest integers with the same number of set bits in their binary representation.
Count the number of set bits in the binary representation of the given integer 'n'.
Find the next smallest integer by iterating from 'n+1' onwards and checking for the same number of set bits.
Find the previous largest integer by iterating from 'n-1' downwards and checking for the same number of set bits.
Q47. Sort a "K" Sorted Doubly Linked List Problem Statement
You are given a doubly linked list with 'N' nodes, where each node can deviate at most 'K' positions from its actual position in the sorted list. Your task...read more
Sort a doubly linked list with nodes that can deviate at most K positions from their actual position in the sorted list.
Iterate through the doubly linked list and maintain a window of size K+1 to sort the elements within the window.
Use insertion sort within the window to sort the elements efficiently.
Repeat the process until the entire list is sorted.
Time complexity can be optimized to O(N*log(K)) using a priority queue.
Q48. Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N
rows and M
columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in this ma...read more
Count the number of islands in a 2D matrix of 1s and 0s.
Use depth-first search (DFS) to traverse the matrix and identify connected groups of 1s.
Maintain a visited array to keep track of visited cells to avoid redundant traversal.
Increment the island count each time a new island is encountered.
Consider all eight possible directions for connectivity while traversing the matrix.
Handle edge cases such as out of bounds indices and already visited cells.
Q49. Code Optimization Problem
Ninja encountered an issue with a practice problem where certain test cases could not be passed due to high time complexity. You are provided with a snippet of pseudocode, and your tas...read more
Optimize pseudocode to compute XOR operations in a given range and return sum modulo 1000000007.
Use bitwise XOR properties to optimize the computation.
Avoid unnecessary nested loops by simplifying the logic.
Consider using modular arithmetic to handle large numbers efficiently.
Q50. Zigzag Binary Tree Traversal Problem
Given a binary tree, compute the zigzag level order traversal of the node values in the tree. The zigzag traversal requires traversing levels from left to right, then right ...read more
Zigzag level order traversal of a binary tree is computed by alternating between left to right and right to left traversal at each level.
Use a queue to perform level order traversal of the binary tree.
Maintain a flag to switch between left to right and right to left traversal at each level.
Store the node values in a list while traversing and alternate the order based on the flag.
Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the output should be 1 3 2 4 5 6 7.
Q51. Reverse Alternate K Nodes Problem Statement
You are given a singly linked list of integers along with a positive integer 'K'. The task is to modify the linked list by reversing every alternate 'K' nodes of the ...read more
Reverse every alternate K nodes in a singly linked list
Traverse the linked list and reverse every alternate K nodes
Handle cases where the number of nodes left is less than K
Ensure to properly link the reversed nodes back to the original list
Q52. Count Derangements Problem Statement
You are tasked with finding the total number of derangements for a given set of elements. Specifically, for an integer N
, determine how many ways there are to permute a set ...read more
Count the total number of derangements for a given set of elements.
A derangement is a permutation where no element appears in its original position.
Use the formula for derangements: !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!).
Calculate the derangements modulo 10^9 + 7 to handle large numbers efficiently.
Q53. Maximum Meetings Selection
You are tasked with scheduling meetings in a single meeting room. Given N
meetings, each with a start time Start[i]
and end time End[i]
, determine the maximum number of meetings that ...read more
Given start and end times of meetings, find the maximum number of meetings that can be scheduled in a single room.
Sort the meetings based on their end times in ascending order.
Iterate through the sorted meetings and select the ones that do not overlap with the previously selected meetings.
Keep track of the selected meetings and return their indices.
Q54. Nth Prime Number Problem Statement
Find the Nth prime number given a number N.
Explanation:
A prime number is greater than 1 and is not the product of two smaller natural numbers. A prime number has exactly two...read more
Find the Nth prime number given a number N.
A prime number is greater than 1 and is not the product of two smaller natural numbers
A prime number has exactly two distinct positive divisors: 1 and itself
Implement a function to find the Nth prime number based on the given input
Q55. Rearrange Array: Move Negative Numbers to the Beginning
Given an array ARR
consisting of N
integers, rearrange the elements such that all negative numbers are located before all positive numbers. The order of e...read more
Yes, this can be achieved by using the two-pointer approach to rearrange the array in-place with O(1) auxiliary space.
Use two pointers, one starting from the beginning and one from the end of the array.
Swap elements at the two pointers if they are not in the correct order (negative before positive).
Continue this process until the two pointers meet in the middle of the array.
Q56. Counting Derangements Problem
A derangement is a permutation of 'N' elements, where no element appears in its original position. For instance, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0} because each element ...read more
Count the total number of derangements possible for a set of 'N' elements.
A derangement is a permutation where no element appears in its original position.
Use the formula for derangements: !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)
Return the answer modulo (10^9 + 7) to handle large results.
Q57. Print All Paths Problem Statement
In this problem, you are provided with a graph consisting of 'N' nodes and 'M' unidirectional edges. Additionally, two integers 'S' and 'D' are given, representing the source a...read more
The task is to find all unique paths from a source node to a destination node in a graph.
Identify all unique paths from source node to destination node in a graph
Ensure all nodes in the path are unique
Output total number of valid paths and list nodes in each path in lexicographical order
Q58. Factorial Calculation Problem Statement
Develop a program to compute the factorial of a given integer 'n'.
The factorial of a non-negative integer 'n', denoted as n!
, is the product of all positive integers les...read more
Program to compute factorial of a given integer 'n', with error handling for negative values.
Create a function to calculate factorial using a loop or recursion
Check if input is negative, return 'Error' if true
Handle edge cases like 0 and 1 separately
Use long data type to handle large factorials
Q59. Stock Trading Maximum Profit Problem
Given the stock prices for 'N' days, your goal is to determine the maximum profit that can be achieved. You can buy and sell the stocks any number of times but can only hold...read more
The goal is to determine the maximum profit that can be achieved by buying and selling stocks on different days.
Iterate through the stock prices and buy on days when the price is lower than the next day, and sell on days when the price is higher than the next day.
Calculate the profit by summing up the differences between buying and selling prices.
Repeat the process for each test case and output the maximum profit possible for each case.
Q60. Minimum Steps for a Knight to Reach Target
Given a square chessboard of size N x N
, you need to determine the minimum number of steps a Knight takes to reach a target position from its starting position.
Input:...read more
Find the minimum number of steps a Knight takes to reach a target position on a chessboard.
Use BFS algorithm to find the shortest path from knight's starting position to target position.
Consider all possible moves of the knight on the chessboard.
Keep track of visited positions to avoid revisiting them.
Return the minimum number of steps required to reach the target position.
Q61. K Sum Subset Problem Statement
Given an array arr
of size 'N' and an integer 'K', determine the maximum subset sum of the array that does not exceed 'K'.
Example:
Input:
arr = [1, 3, 5, 9], K = 16
Output:
15
Ex...read more
Find the maximum subset sum of an array that does not exceed a given integer K.
Use dynamic programming to solve this problem efficiently.
Iterate through all possible subsets of the array and keep track of the maximum sum that does not exceed K.
Consider the choice of including or excluding each element in the subset.
Optimize the solution by using memoization to avoid redundant calculations.
Q62. Guess The Hidden Number Problem Statement
You are given an integer N
and there is a hidden number within the range [0, N] that you must guess. You have access to a function higherLower(k)
which helps in guessin...read more
The task is to guess a hidden number within a given range using a function that provides hints about the number's relation to a given input.
Use the higherLower(k) function to determine if the hidden number is smaller, equal to, or greater than the input k.
Implement a binary search algorithm to efficiently guess the hidden number within the given range.
Iteratively narrow down the range based on the hints provided by the higherLower(k) function.
Return the guessed hidden number ...read more
Q63. Count Derangements
Determine the number of derangements possible for a set of 'N' elements. A derangement is a permutation where no element appears in its original position.
Input:
An integer 'T' representing t...read more
Count the number of derangements possible for a set of 'N' elements.
Use dynamic programming to calculate the number of derangements for each test case
The formula for derangements is D(n) = (n-1)*(D(n-1) + D(n-2)), with base cases D(1) = 0 and D(2) = 1
Calculate derangements modulo (10^9 + 7) to avoid overflow issues
Q64. Convert First Letter to Upper Case
Given a string STR
, transform the first letter of each word in the string to uppercase.
Example:
Input:
STR = "I am a student of the third year"
Output:
"I Am A Student Of The...read more
The function takes a string as input and transforms the first letter of each word to uppercase.
Split the input string into individual words using spaces as delimiters.
For each word, convert the first letter to uppercase and concatenate the rest of the word.
Join the modified words back together with spaces to form the final transformed string.
Q65. Most Frequent Word Problem Statement
You are given two strings 'A' and 'B' composed of words separated by spaces. Your task is to determine the most frequent and lexicographically smallest word in string 'A' th...read more
Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.
Split strings 'A' and 'B' into words
Count frequency of each word in 'A'
Check if word is not in 'B' and is the most frequent and lexicographically smallest
Return the word or -1 if no such word exists
Q66. Merge Sort Linked List Problem Statement
You are given a singly linked list of integers. Your task is to sort the linked list using the merge sort algorithm.
Explanation:
Merge Sort is a divide and conquer algo...read more
Implement merge sort algorithm to sort a singly linked list of integers.
Divide the linked list into two halves using slow and fast pointers.
Recursively sort the two halves.
Merge the sorted halves using a merge function.
Handle base cases like empty list or single node list.
Ensure the termination of the linked list with -1 at the end.
Q67. Binary Palindrome Check
Given an integer N
, determine whether its binary representation is a palindrome.
Input:
The first line contains an integer 'T' representing the number of test cases.
The next 'T' lines e...read more
Check if the binary representation of a given integer is a palindrome.
Convert the integer to binary representation.
Check if the binary representation is a palindrome by comparing it with its reverse.
Return true if it is a palindrome, false otherwise.
Q68. Maximum Path Sum Between Two Leaves
Given a non-empty binary tree where each node has a non-negative integer value, determine the maximum possible sum of the path between any two leaves of the given tree.
Expla...read more
Find the maximum path sum between two leaf nodes in a binary tree.
Traverse the tree to find the maximum path sum between two leaf nodes
Keep track of the maximum sum as you traverse the tree
Consider all possible paths that pass through the root and those that do not
Handle cases where there is only one leaf node in the tree
Q69. First Non-Repeating Character Problem Statement
You are given a string consisting of English alphabet characters. Your task is to identify and return the first character in the string that does not repeat. If e...read more
Identify and return the first non-repeating character in a string, or the first character if all characters repeat.
Iterate through the string to count the frequency of each character
Return the first character with a frequency of 1, or the first character if all characters repeat
Use a hashmap to store character frequencies efficiently
Q70. Count Palindrome Words in a String
Given a string 'S' consisting of words, your task is to determine the number of palindrome words within 'S'. A word is considered a palindrome if it reads the same backward as...read more
Count the number of palindrome words in a given string.
Split the string into words using whitespace as delimiter.
Check each word if it is a palindrome by comparing it with its reverse.
Increment a counter for each palindrome word found.
Output the total count of palindrome words for each test case.
Q71. Check If Binary Representation of a Number is Palindrome
Given an integer N
, determine if its binary representation is a palindrome.
Input:
The first line contains a single integer ‘T’ representing the number o...read more
Check if the binary representation of a number is a palindrome.
Convert the integer to binary representation.
Check if the binary representation is a palindrome by comparing it with its reverse.
Return true if it is a palindrome, false otherwise.
Q72. Merge k Sorted Linked Lists
You are provided with 'K' sorted linked lists, each sorted in increasing order. Your task is to merge all these lists into one single sorted linked list and return the head of the re...read more
Merge k sorted linked lists into one single sorted linked list.
Create a min-heap to store the heads of all linked lists.
Pop the smallest element from the heap and add it to the result list.
If the popped element has a next element, push it back to the heap.
Repeat until all elements are merged into a single sorted list.
Q73. Duplicate Subtrees Problem Statement
Given a binary tree, return the root values of all duplicate subtrees. Two subtrees are considered duplicate if they have the same structure with identical node values. For ...read more
Find root values of duplicate subtrees in a binary tree.
Traverse the tree in a bottom-up manner to identify duplicate subtrees.
Use a hashmap to store the subtree structures and their frequencies.
Return the root values of duplicate subtrees based on hashmap entries.
Q74. Sort 0 and 1 Problem Statement
Given an integer array ARR
of size N
containing only integers 0 and 1, implement a function to sort this array. The solution should scan the array only once without using any addi...read more
Sort an array of 0s and 1s in linear time without using additional arrays.
Use two pointers approach to swap 0s to the left and 1s to the right.
Maintain two pointers, one for 0s and one for 1s, and iterate through the array.
Swap elements at the two pointers based on the values encountered.
Continue until the two pointers meet in the middle of the array.
Q75. Find the Second Largest Element
Given an array or list of integers 'ARR', identify the second largest element in 'ARR'.
If a second largest element does not exist, return -1.
Example:
Input:
ARR = [2, 4, 5, 6, ...read more
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 by returning -1.
Consider edge cases like empty array or array with less than 2 elements.
Q76. String Rotation Problem Statement
You are given a string named str
and an integer D
. Your task is to perform both left (anticlockwise) and right (clockwise) rotations on the given string by D
units, starting fr...read more
Implement left and right string rotations by D units on a given string.
Implement leftRotate() function to return string after left rotation by D units.
Implement rightRotate() function to return string after right rotation by D units.
Consider handling edge cases like empty string or D exceeding string length.
Example: For input 'coding', D=2, leftRotate() should return 'dingco' and rightRotate() should return 'ngcodi'.
Q77. Write a program: single input as a string(lets say "aaabcccfffghh"), you have to return the char and their occurrence as a string. In this case you have to return "a3b1c3f3g1h2"
Program to return character and their occurrence in a string.
Iterate through the string and count the occurrence of each character.
Store the count in a dictionary or hashmap.
Create a new string by concatenating the character and their count.
Return the new string.
Q78. Word Break Problem Statement
You are given a list of N
strings called A
. Your task is to determine whether you can form a given target string by combining one or more strings from A
.
The strings from A
can be u...read more
Given a list of strings, determine if a target string can be formed by combining one or more strings from the list.
Iterate through all possible combinations of strings from the list to check if they can form the target string.
Use recursion to try different combinations of strings.
Keep track of the current position in the target string and the strings used so far.
Return true if the target string can be formed, false otherwise.
Q79. Preorder Traversal Problem Statement
You are provided with the root node of a binary tree comprising N
nodes. Your objective is to output its preorder traversal. Preorder traversal of a binary tree is performed...read more
Implement a function to perform preorder traversal on a binary tree given the root node.
Create a recursive function to traverse the tree in preorder fashion.
Visit the root node, then recursively traverse left subtree, followed by right subtree.
Store the visited nodes in an array and return the array as the result.
Example: For the input tree [1, 2, 3, 4, -1, 5, 6, -1, 7, -1, -1, -1, -1, -1, -1], the preorder traversal output should be [1, 2, 4, 7, 3, 5, 6].
Q80. Character Formation Check
Determine if the second string STR2
can be constructed using characters from the first string STR1
. Both strings may include any characters.
Input:
The first line contains an integer T...read more
Check if second string can be formed using characters from the first string.
Iterate through each character in STR2 and check if it exists in STR1.
Use a hashmap to store the frequency of characters in STR1 for efficient lookup.
Return 'YES' if all characters in STR2 are found in STR1, otherwise return 'NO'.
Q81. Detect and Remove Loop in Linked List
For a given singly linked list, identify if a loop exists and remove it, adjusting the linked list in place. Return the modified linked list.
Expected Complexity:
Aim for a...read more
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.
Q82. Trapping Rainwater Problem Statement
You are given an array ARR
of long type, which represents an elevation map where ARR[i]
denotes the elevation of the ith
bar. Calculate the total amount of rainwater that ca...read more
Calculate the total amount of rainwater that can be trapped within given elevation map.
Iterate through the array to find the maximum height on the left and right of each bar.
Calculate the amount of water that can be trapped above each bar by taking the minimum of the maximum heights on the left and right.
Sum up the trapped water above each bar to get the total trapped water for the elevation map.
Q83. String Transformation Problem
Given a string (STR
) of length N
, you are tasked to create a new string through the following method:
Select the smallest character from the first K
characters of STR
, remove it fr...read more
The task is to transform a given string by selecting the smallest character from the first K characters and appending it to a new string until the original string becomes empty.
Iterate through the string while there are characters remaining
For each iteration, select the smallest character from the first K characters
Remove the selected character from the original string and append it to the new string
Repeat until the original string is empty
Return the final new string
Q84. how would you handle overflow condition of an array? SB37,SD37,SE37,S0C4,S0C7?JCL - how to backup all GDG versions in one step? what are COMP & COMP-3 vars and what it's used for?
Handling overflow condition of an array and backing up GDG versions in one step in JCL
For overflow, check array bounds before accessing elements
For SB37, increase primary/secondary space allocation
For SD37, increase directory blocks
For SE37, increase primary/secondary space allocation for PDS
For S0C4, check for null pointers or uninitialized variables
For S0C7, check for invalid data types or out-of-bounds array access
To backup all GDG versions in one step, use the GDG base na...read more
Q85. Spiral Order Traversal of a Binary Tree
Given a binary tree with N
nodes, your task is to output the Spiral Order traversal of the binary tree.
Input:
The input consists of a single line containing elements of ...read more
The task is to output the Spiral Order traversal of a binary tree given in level order.
Implement a function that returns the spiral order traversal as a list
Traverse the binary tree in a spiral order alternating between left to right and right to left
Use a queue to keep track of nodes at each level
Handle null nodes represented by -1 in the input
Q86. 1. How to make object thread-safe? 2. Create an Immutable class. 3. Which Garbage collection algorithm is used in Java. 4. print the left view of the Binary tree 5. working of Circuiter breaker design pattern....
read moreTechnical interview questions for Associate Staff Engineer position
To make an object thread-safe, use synchronization or use thread-safe data structures
Immutable class is a class whose state cannot be modified after creation
Java uses a mark-and-sweep algorithm for garbage collection
To print the left view of a binary tree, perform a level order traversal and print the first node at each level
Circuit breaker design pattern is used to prevent cascading failures in distributed sy...read more
Q87. Jumping Game Problem Statement
In this problem, you have ‘n’ carrots lined up and denoted by numbers 1 through ‘n’. There are ‘k’ rabbits, and each rabbit can jump to carrots that are multiples of its unique ju...read more
Calculate uneaten carrots after rabbits jump based on their unique factors.
Iterate through each rabbit's jumping factor and mark the carrots they land on as eaten
Calculate the remaining uneaten carrots by counting the ones not marked as eaten
Consider using a data structure like an array to keep track of eaten carrots efficiently
Q88. Distribute N Candies Among K People
Explanation: Sanyam wishes to distribute 'N' candies among 'K' friends. The friends are arranged based on Sanyam's order of likeness. He initially distributes candies such th...read more
Distribute N candies among K people in Sanyam's order of likeness, incrementing distribution by K each round until all candies are distributed.
Distribute candies starting from 1st friend, incrementing by K each round
If remaining candies are fewer than what a friend is supposed to receive, stop distribution
Output the number of candies each friend ends up with at the end of distribution
Q89. Segregate Odd-Even Problem Statement
In a wedding ceremony at NinjaLand, attendees are divided into two groups: bride’s side and groom’s side. Attendees from the bride’s side hold odd numbers, while those from ...read more
Rearrange attendees from bride's side and groom's side while maintaining original order within each group.
Iterate through the linked list and separate odd and even numbers into two separate lists.
Merge the two lists while maintaining the original order within each group.
Output the rearranged linked list with bride's side attendees followed by groom's side attendees.
Q90. Reverse Linked List Problem Statement
Given a Singly Linked List of integers, your task is to reverse the Linked List by altering the links between the nodes.
Input:
The first line of input is an integer T, rep...read more
Reverse a singly linked list by altering the links between nodes.
Iterate through the linked list and reverse the links between nodes
Use three pointers to keep track of the current, previous, and next nodes
Update the links between nodes to reverse the list
Return the head of the reversed linked list
Q91. Difference between microflow flow and nano flow
Microflow is a flow with a rate of 1-1000 µL/min while nano flow is a flow with a rate of 1-1000 nL/min.
Microflow is used in HPLC and capillary electrophoresis while nano flow is used in nano-LC and proteomics.
Microflow requires larger sample volumes while nano flow requires smaller sample volumes.
Microflow has lower sensitivity compared to nano flow.
Q92. Height of Binary Tree
You are provided with the Inorder and Level Order traversals of a Binary Tree composed of integers. Your goal is to determine the height of this Binary Tree without actually constructing i...read more
Calculate the height of a Binary Tree given its Inorder and Level Order traversals without constructing it.
Use the properties of Inorder and Level Order traversals to determine the height of the Binary Tree.
The height of a Binary Tree is the number of edges on the longest path from the root to a leaf node.
Consider edge cases like a single node tree or empty tree when calculating the height.
Q93. Count Pairs with Given Sum
Given an integer array/list arr
and an integer 'Sum', determine the total number of unique pairs in the array whose elements sum up to the given 'Sum'.
Input:
The first line contains ...read more
Count the total number of unique pairs in an array whose elements sum up to a given value.
Use a hashmap to store the frequency of each element in the array.
Iterate through the array and for each element, check if (Sum - current element) exists in the hashmap.
Increment the count of pairs if the complement exists in the hashmap.
Divide the count by 2 to avoid counting duplicates (arr[i], arr[j]) and (arr[j], arr[i]) separately.
Q94. write a program: if input is "my_first_variable" return output as "myFirstVariable" and vice-versa
A program to convert a variable name from snake_case to camelCase and vice-versa.
Split the input string by underscore (_) to get an array of words.
For snake_case to camelCase conversion, capitalize the first letter of each word except the first one.
For camelCase to snake_case conversion, insert an underscore (_) before each capital letter except the first one.
Join the array of words with the appropriate delimiter to get the converted variable name.
Q95. Smallest Window Problem Statement
Given two strings S
and X
containing random characters, the task is to find the smallest substring in S
which contains all the characters present in X
.
Input:
The first line co...read more
The task is to find the smallest substring in string S which contains all the characters present in string X.
Iterate through string S and keep track of characters in X using a hashmap
Use two pointers to maintain a sliding window containing all characters in X
Update the window size and result as you iterate through S
Q96. Reverse Stack with Recursion
Reverse a given stack of integers using recursion. You must accomplish this without utilizing extra space beyond the internal stack space used by recursion. Additionally, you must r...read more
Reverse a given stack of integers using recursion without extra space or loop constructs.
Use recursion to pop all elements from the original stack and store them in function call stack.
Once the stack is empty, push the elements back in reverse order using recursion.
Ensure to handle base cases for empty stack or single element stack.
Example: If the input stack is [1, 2, 3], after reversal it should be [3, 2, 1].
Q97. How to write HTML code considering web accessibility for disabled person
Consider web accessibility guidelines for disabled persons when writing HTML code.
Use semantic HTML elements like <nav>, <header>, <main>, <footer> to improve screen reader accessibility.
Provide alternative text for images using the alt attribute.
Ensure proper color contrast for text and background to aid visually impaired users.
Use ARIA roles and attributes to enhance accessibility for interactive elements.
Test your website using screen readers and keyboard navigation to ide...read more
Q98. Make Unique Array Challenge
Your task is to determine the minimum number of elements that need to be removed from an array 'ARR' of size 'N' such that all the remaining elements are distinct. In simpler terms, ...read more
Find the minimum number of elements to remove from an array to make all elements distinct.
Iterate through the array and keep track of the frequency of each element using a hashmap.
Count the number of elements that have a frequency greater than 1, as those need to be removed.
Return the count of elements to be removed.
Q99. Median of Two Sorted Arrays
Given two sorted arrays A
and B
of sizes N
and M
, find the median of the merged array formed by combining arrays A
and B
. If the total number of elements, N + M
, is even, the median ...read more
Find the median of two sorted arrays by merging them and calculating the middle element(s).
Merge the two sorted arrays into one sorted array.
Calculate the median based on the total number of elements in the merged array.
If the total number of elements is even, take the mean of the two middle elements as the median.
Q100. Prime Numbers Identification
Given a positive integer N
, your task is to identify all prime numbers less than or equal to N
.
Explanation:
A prime number is a natural number greater than 1 that has no positive d...read more
Identify all prime numbers less than or equal to a given positive integer N.
Iterate from 2 to N and check if each number is prime
Use the Sieve of Eratosthenes algorithm for efficient prime number identification
Optimize by only checking up to the square root of N for divisors
More about working at Nagarro
Interview Process at MotionCut
Top Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month