Expedia Group
30+ Infosys BPM Interview Questions and Answers
Q1. Count and Say Sequence Problem
The 'Count and Say' sequence is a series of strings in which each consecutive term is generated by describing the previous term. The sequence begins with '1'.
Your task is to dete...read more
Implement a function to determine the 'Count and Say' sequence after N iterations.
Iterate through each term in the sequence, describing the previous term to generate the next term.
Use a count to keep track of consecutive digits and append the count and digit to the result string.
Repeat this process for N iterations to get the sequence after N iterations.
Q2. Ninja's Jump Task
The Ninja has been given a challenge by his master to reach the last stone. These stones are represented as an array of numbers. The Ninja can jump using either odd-numbered or even-numbered j...read more
Find the number of starting indices from which a Ninja can reach the last stone by following specific jump rules.
Iterate through the array and keep track of the possible jumps for each index based on the rules provided.
Use dynamic programming or a stack to efficiently calculate the number of starting indices.
Consider edge cases where some indices may have no possible jumps.
Example: For the input [10, 13, 12, 14, 15], the Ninja can start from indices 0 and 1 to reach the last ...read more
Q3. Buy and Sell Stock Problem Statement
Imagine you are Harshad Mehta's friend, and you have been given the stock prices of a particular company for the next 'N' days. You can perform up to two buy-and-sell transa...read more
Q4. 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
Q5. Binary Tree to Doubly Linked List
Transform a given Binary Tree into a Doubly Linked List.
Ensure that the nodes in the Doubly Linked List follow the Inorder Traversal of the Binary Tree.
Input:
The first line ...read more
Q6. Encode the Message Problem Statement
Given a text message, your task is to return the Run-length Encoding of the given message.
Run-length encoding is a fast and simple method of encoding strings, representing ...read more
Q7. Date Reformatting
You have a string 'S' representing a date in the "Day Month Year" format, where:
- Day is one of {"1st", "2nd", "3rd", ..., "29th", "30th", "31st"}.
- Month is one of {"Jan", "Feb", "Mar", "Apr",...read more
Reformat dates from 'Day Month Year' format to 'YYYY-MM-DD' format.
Parse the input string to extract day, month, and year.
Convert month to its numerical equivalent (e.g., 'Jan' to '01').
Format the date in 'YYYY-MM-DD' format and output.
Q8. Distinct Islands Problem Statement
Given a two-dimensional array/list consisting of integers 0s and 1s, where 1 represents land and 0 represents water, determine the number of distinct islands. A group of conne...read more
Count the number of distinct islands in a 2D array of 0s and 1s.
Identify connected groups of 1s to form islands
Check if islands can be translated to overlap without rotation or reflection
Count the number of distinct islands based on the above criteria
Q9. 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
Q10. Count Ways to Reach the N-th Stair Problem Statement
You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two step...read more
The problem involves counting the number of distinct ways to climb N stairs by taking 1 or 2 steps at a time.
Use dynamic programming to solve the problem efficiently.
Define a recursive function to calculate the number of ways to reach each stair.
Consider base cases for 0 and 1 stairs.
Use memoization to store intermediate results and avoid redundant calculations.
Return the result modulo 10^9+7 to handle large values.
Q11. 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
Ninja's Lootcase Problem Statement
Ninja stumbled upon a locked suitcase while digging in his lawn. The only way to unlock it is by following specific instructions stated on an accompanying paper.
Explanation:
The problem involves transforming an array into specific elements using given operations. Find the minimum number of steps required.
Iterate through the array and calculate the number of steps needed to transform each element into the desired value
For each element, calculate the difference between the current value and the desired value, then determine the minimum number of steps required to reach that value
Keep track of the total number of steps needed for each test case and ...read more
Q13. Problem: Search In Rotated Sorted Array
Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q
queries. Each query is represented by an integer Q[i]
, and you must determ...read more
Search for integers in a rotated sorted array efficiently.
Implement binary search to find the target integer in the rotated array.
Handle the rotation while performing binary search.
Return the index of the target integer if found, else return -1.
Q14. 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 non-decreasing order.
Use a hashmap to store the difference between the target sum and each element in the array.
Iterate through the array and check if the current element's complement exists in the hashmap.
Sort the pairs based on the first element and then the second element.
Return the list of pairs that satisfy the sum condition.
Q15. Version Comparison
Given two strings, Version1
and Version2
, each representing version numbers, determine which one is the latest version.
Explanation:
The input strings consist of digits and dots only. Both st...read more
Compare two version numbers to determine the latest version.
Split the version numbers by '.' and compare each part from left to right.
If a part in Version2 is greater than the corresponding part in Version1, Version2 is the latest.
Handle cases where one version number has more parts than the other.
Return 1 if Version1 is the latest, -1 if Version2 is the latest, and 0 if they are the same.
Q16. Incremental Partitioning Problem Statement
Given two integers N and K, determine how many ways you can partition the number N into K non-empty groups such that the size of each group[i] >= group[i-1] for each v...read more
The problem involves determining the number of ways to partition a number into non-empty groups with specific constraints.
Use dynamic programming to solve the problem efficiently.
Consider the base cases when N = 0 or K = 0.
Keep track of the number of ways to partition N into K groups satisfying the given conditions.
Apply modulo 1e9 + 7 to the final result.
Example: For input 5 3, the output is 2 as there are 2 ways to partition 5 into 3 groups.
Q17. Find the Winner Problem Statement
Given an array/list VOTES
containing names of candidates, where each entry represents the vote received by the candidate.
You need to determine the candidate with the maximum v...read more
Given an array of candidate names and their votes, find the candidate with the maximum votes, with tiebreaker based on lexicographical order.
Iterate through the array of candidate names and keep track of the count of each candidate's votes.
Find the candidate with the maximum votes. If there is a tie, return the lexicographically smaller name.
Handle multiple test cases by repeating the process for each test case.
Output the name of the winning candidate for each test case.
Q18. Find the Third Greatest Element
Given an array 'ARR' of 'N' distinct integers, determine the third largest element in the array.
Input:
The first line contains a single integer 'T' representing the number of te...read more
Find the third largest element in an array of distinct integers.
Sort the array in descending order and return the element at index 2.
Alternatively, keep track of the three largest elements while iterating through the array.
Handle cases where there are less than 3 elements in the array.
Q19. Problem: Deletion in Circular Linked List
You are provided with a Circular Linked List of integers and a specific integer, referred to as 'key'
.
Your task is to implement a function that locates the specified k...read more
Implement a function to delete a specific key from a Circular Linked List of integers.
Traverse the Circular Linked List to find the key to be deleted.
Adjust the pointers to remove the node containing the key.
Handle the case where the Circular Linked List becomes empty after deletion.
Return -1 if the Circular Linked List is empty after deletion.
Q20. Page Faults Identification Problem Statement
In computing, a page fault occurs when a process accesses a memory page that is not currently mapped by the memory management unit. To handle new pages being brought...read more
The problem involves determining the number of page faults using the Least Recently Used (LRU) replacement algorithm.
Page faults occur when a process accesses a memory page not currently mapped by the memory management unit.
Page replacement algorithm like LRU is used to decide which existing page should be replaced.
The goal is to calculate the number of page faults based on the given input sequences and memory capacity.
Constraints include the number of test cases, number of p...read more
Q21. Closest Sum Problem Statement
Given an array of integers ARR
of size N
and an integer target
, find three integers in ARR
such that their sum is closest to the target
. If there are two closest sums, return the s...read more
Find three integers in an array whose sum is closest to a given target, return the smallest sum if there are two closest sums.
Iterate through all possible triplets in the array to find the sum closest to the target.
Keep track of the closest sum found so far and update it if a closer sum is found.
Return the closest sum at the end of the iteration.
Q22. Position of Right Most Set Bit
Determine the position of the rightmost set bit in the binary representation of a given number N.
Input:
T: Number of test cases
N: An integer for which the position of the rightmo...read more
Find the position of the rightmost set bit in a given number's binary representation.
Convert the number to binary representation.
Find the position of the rightmost set bit by counting from right to left.
Return the position of the rightmost set bit.
Q23. Count Substrings with Only Vowels
In this task, you need to find the number of substrings within a given string ’S’ that consist only of vowels.
Explanation:
A substring is defined as a contiguous sequence of c...read more
Count the number of substrings consisting of only vowels in a given string.
Iterate through all substrings of the input string.
Check if each substring consists only of vowels.
Increment a counter for each valid substring found.
Return the final count as the output.
Q24. Cycle Detection in a Singly Linked List
Determine if a given singly linked list of integers forms a cycle or not.
A cycle in a linked list occurs when a node's next
points back to a previous node in the list. T...read more
Detect if a singly linked list forms a cycle by checking if a node's next points back to a previous node.
Traverse the linked list using two pointers, one moving one step at a time and the other moving two steps at a time.
If the two pointers meet at any point, it indicates the presence of a cycle in the linked list.
Use Floyd's Cycle Detection Algorithm for efficient detection of cycles in a linked list.
Q25. Distribute Items Problem Statement
Calculate the number of ways to distribute a given number of items 'N' among three people such that each person gets at least one item, and only one person receives the maximu...read more
Calculate the number of ways to distribute items among three people with constraints.
Start by distributing one item to each person, then distribute the remaining items to one person.
Use combinatorics to calculate the number of ways to distribute the remaining items to one person.
Consider edge cases like when N is less than 3 or when N is equal to 3.
Example: For N=7, distribute 1 item to each person and then distribute the remaining 4 items to one person in 4 ways.
Q26. 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) or Breadth First Search (BFS) 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 edge cases like boundary conditions and handling of diagonals while traversing.
Handle the input matrix efficiently to optimize the solution.
Example...read more
Q27. Minimum Distinct Labels Problem Statement
You are given N boxes on a table, each with an integer label. The labels of these boxes are provided in an array ARR
. Your task is to remove exactly M boxes such that t...read more
Given N boxes with integer labels, remove M boxes to minimize distinct labels left.
Iterate through the array and count the frequency of each label
Sort the frequencies in descending order
Remove M boxes with the highest frequencies to minimize distinct labels
To find and correct a bug in code, analyze problem statement, review code, use debugging tools, and test different scenarios.
Understand the problem statement thoroughly to identify the expected behavior of the code.
Review the code line by line to identify any syntax errors, logical errors, or potential bugs.
Use debugging tools like breakpoints, print statements, or IDE debuggers to trace the flow of code execution.
Test the code with different input scenarios to reproduce the ...read more
Q29. Given array of integer create subarray with sum = 0
Create subarrays with sum = 0 from given array of integers.
Iterate through the array and keep track of the running sum.
Store the running sum in a hashmap and check if the current sum - any previous sum equals 0.
If yes, then the subarray between those two indices has a sum of 0.
Q30. Combinatorics, find pivot in rotated sorted array, count sort
The question involves finding the pivot in a rotated sorted array using combinatorics and count sort.
To find the pivot in a rotated sorted array, we can use a modified binary search algorithm.
First, we compare the middle element with the first element to determine if the pivot is in the left or right half.
Then, we continue dividing the array in half and adjusting the search range based on the pivot's location.
Count sort is a sorting algorithm that works well when the range of...read more
Q31. Sum of right leaf nodes, swap nodes in k groups
The question involves finding the sum of right leaf nodes and swapping nodes in groups of k.
The sum of right leaf nodes can be found by traversing the tree and checking if a node is a right leaf node.
Swapping nodes in groups of k can be done by iterating through the linked list and swapping the nodes in each group.
Examples: For the sum of right leaf nodes, consider a binary tree with nodes 1, 2, 3, 4, 5. The sum would be 5. For swapping nodes in groups of k, consider a linked...read more
Q32. Reverse nodes in k groups, sum of right leaf nodes
The question involves reversing nodes in groups of k and finding the sum of right leaf nodes.
Implement a function to reverse nodes in groups of k
Traverse the reversed linked list and find the sum of right leaf nodes
Handle edge cases like when the number of nodes is not a multiple of k
Q33. Left view of binary tree
The left view of a binary tree is the set of nodes visible when the tree is viewed from the left side.
Traverse the tree in a level order manner and keep track of the first node at each level.
Use a queue to store nodes at each level and update the left view nodes accordingly.
Example: For a binary tree with root node 1, left child 2, and right child 3, the left view would be [1, 2].
Top HR Questions asked in Infosys BPM
Interview Process at Infosys BPM
Top Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month