INCREFF Software Developer Intern Interview Questions and Answers

Round duration - 70 Minutes
Round difficulty - Medium

Timing was 9:15AM. Platform was not very good. Questions were not well explained.

Q1. Merge overlapping intervals
Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and ...read more
Ans. Brute Force
1. We are given the function MERGEINTERVALS(), which takes a 2D vector representing the vector of intervals and returns another 2D vector which is the vector of merged intervals.
2. We create another function ISOVERLAP() to check if the current interval overlaps with the other interval.
3. Now we create an empty 2D vector “RES” to store finally merged intervals and another boolean vector “VIS” to mark if the current in...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Rat in a Maze
You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a...read more
Ans. Bactracking
Approach: We can start the traversal of the paths from the rat’s starting position, i.e. (0,0) keeping track of the visited cells during the traversal. We will recursively go through all the paths possible until the last index of the grid (destination) is reached, and add the path information using which the rat successfully reached the end.
 
Algorithm is as follows:
 
1. Take the starting position of th...read more
Answered by CodingNinjas
Add your answer
Q3. Permutations of a String
You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.
S...read more
Ans. Backtracking
The idea is to fix a character at a position and then find the permutations for rest of the characters.
Make a list ‘ans’ which will contain the permutations of the given string.
 
Algorithm:
Let’s define a function generatePermutaionsHelper(Str, l, r). This function generates the permutations of the substring which starts from index  ‘l’ and ends at index  ‘r’.
• Call the function: generatePermutai...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 90 minutes
Round difficulty - Medium

Timing was 10AM. The platform was quite good.

Q1.  Maximum size rectangle sub-matrix with all 1's
You are given an 'N' * 'M' sized binary-valued matrix 'MAT, where 'N' is the number of rows and 'M' is the number of colu...read more
Ans. 
If the height of bars of the histogram is given then the largest area of the histogram can be found. This way in each row, the largest area of bars of the histogram can be found. To get the largest rectangle full of 1’s, update the next row with the previous row and find the largest area under the histogram, i.e. consider each 1’s as filled squares and 0’s with an empty square and consider each row as the base.
Answered by CodingNinjas
View 2 more amswers
Q2. Maximum Sum path of a binary tree.
You are given a binary tree having 'N' nodes. Each node of the tree has an integer value. Your task is to find the maximum possible sum of a simple path between a...read more
Ans. 
For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child
Answered by CodingNinjas
View 1 more amswer
Q3. Minimum number of swaps required to sort an array
You have been given an array 'ARR' of 'N' distinct elements.
Your task is to find the minimum no. of swaps required to sort the array.
F...read more
Ans. 
This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.
Answered by CodingNinjas
View 2 more amswers
Q4. Prefix to Infix
Given a string denoting a valid Prefix expression containing ‘+’, ’-’, ’*’, ‘/’ and uppercase letters. You are supposed to convert the given Prefix expression into an Infix expression.
Not...read more
Ans. 
Algorithm for Prefix to Infix:

Read the Prefix expression in reverse order (from right to left)
If the symbol is an operand, then push it onto the Stack
If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator between them.
string = (operand1 + operator + operand2)
And push the resultant string back to Stack
Repeat the above steps until end of Prefix
Answered by CodingNinjas
View 1 more amswer

Round duration - 70 minutes
Round difficulty - Medium

Timing was 9:15AM. Platform was not very good. Questions were not well explained.

Q1. Merge overlapping intervals
Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and ...read more
Ans. Brute Force
1. We are given the function MERGEINTERVALS(), which takes a 2D vector representing the vector of intervals and returns another 2D vector which is the vector of merged intervals.
2. We create another function ISOVERLAP() to check if the current interval overlaps with the other interval.
3. Now we create an empty 2D vector “RES” to store finally merged intervals and another boolean vector “VIS” to mark if the current in...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Rat in a Maze
You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a...read more
Ans. Bactracking
Approach: We can start the traversal of the paths from the rat’s starting position, i.e. (0,0) keeping track of the visited cells during the traversal. We will recursively go through all the paths possible until the last index of the grid (destination) is reached, and add the path information using which the rat successfully reached the end.
 
Algorithm is as follows:
 
1. Take the starting position of th...read more
Answered by CodingNinjas
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Timing was 10AM. The platform was user-friendly.

Q1. Maximum size rectangle sub-matrix with all 1's
You are given an 'N' * 'M' sized binary-valued matrix 'MAT, where 'N' is the number of rows and 'M' is the number of colum...read more
Ans. Dynamic Programming.
1. We start from the first row and move downwards.
2. We create three 1-dimensional arrays HEIGHT[], LEFT[], RIGHT[].
3. ‘HEIGHT’[i]: stores the number of current continuous 1’s in column i.
4. LEFT[i] : stores the leftmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [j, i], ‘HEIGHT’[k] >= ‘HEIGHT’[i].
5. RIGHT [i]: stores the rightmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [i, j], ‘HE...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Binary Tree Maximum Path Sum
You are given a binary tree with ‘N’ nodes.
Your task is to find the “Maximum Path Sum” for any path.
Note :
1. A ‘path’ is a sequence of adjacent pair nodes with an edge ...read more
Ans. Recursive Approach
The idea here is to use the recursion. For each node, We can calculate the maximum path sum by keeping track of the following paths:
• Max path sum starting from Left child + Max Path sum starting from Right child + Node’s value.
• Max path sum starting from Left child + Node’s value
• Max path sum starting from Right child + Node’s value
• Node’s value
 
We then pick the maximum one among them. The root of ev...read more
Answered by CodingNinjas
Add your answer
Q3. Minimum number of swaps required to sort an array
You have been given an array 'ARR' of 'N' distinct elements.
Your task is to find the minimum no. of swaps required to sort the array.
F...read more
Ans. Naive Approach
While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element which should have come in this place.
 
Below is the algorithm:
1. Create a copy of the given input array and store it in temp.
2. Sort the temp array.
3. Iterate over the input array, and check whether the current element is at the right place or not by comparing it with t...read more
Answered by CodingNinjas
View 1 more amswer
Q4. Prefix to Infix
Given a string denoting a valid Prefix expression containing ‘+’, ’-’, ’*’, ‘/’ and uppercase letters. You are supposed to convert the given Prefix expression into an Infix expression.
Not...read more
Ans. Stack Based
The idea is to iterate over the expression from right to left and store the operands in a stack. Here, we are using a stack of strings for storing the operands. Whenever we encounter an operator, pop the top two operands from the stack and convert the expression to its infix form and then push back to the stack.
 
• Iterate from ‘i’ = |S| - 1 to 0. The idea behind this step is to store the operands.
  1. If the c...read more
Answered by CodingNinjas
Add your answer