Info Edge Software Developer Intern Interview Questions and Answers

Round duration - 90 minutes
Round difficulty - Easy

This round was held during university hours and consisted of 2 coding questions.

Round duration - 120 minutes
Round difficulty - Easy

Make sure you do no cutting and are clear about the approach you'd be following. 
 

Q1. What is the running median of an input stream?
Ans. 
Running median of an input stream is the median value of the numbers seen so far in a continuous stream of data.
• Maintain two heaps - a max heap for the lower half of the numbers and a min heap for the upper half.

• Keep the number of elements in the two heaps balanced or differ by at most 1.

• If the total number of elements is odd, the median is the root of the max heap. If even, it is the average of the roots of the two he...read more
Answered by AI
Add your answer

Round duration - 90 Miinutes
Round difficulty - Medium

First round had MCQ + 2 coding questions. It was held in morning around 11 am. It was held on campus.

Q1. 
Robot Delivery Path Problem
You are tasked with directing a robot from the top-left corner of an N*N matrix to a specified point (x, y), delivering a parcel. The robot is restricted to move only on flat a...read more
Ans. 
Determine if a robot can reach a specified destination in a matrix by moving only downwards or rightwards.
• Start at (0,0) and move towards the destination (x, y) only downwards or rightwards.

• Check if the path is clear (1) and avoid obstacles (0) while staying within matrix boundaries.

• Return true if the robot can reach the destination, false otherwise.

• Example: For input matrix [[1, 0, 1], [1, 1, 1], [1, 1, 5]] with desti...read more
Answered by AI
Add your answer
Q2. 
Unique Element in Array
Given an arbitrary array arr consisting of N non-negative integers where every element appears thrice except for one. Your task is to find the element in the array that appears onl...read more
Ans. 
Find the unique element in an array where every element appears thrice except for one.
• Use XOR operation to find the unique element.

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

• The XOR operation cancels out elements that appear thrice, leaving only the unique element.

• Example: arr = [2, 2, 3, 2], XOR of all elements = 3.

• Example: arr = [0, 1, 0, 1, 0, 1, 99], XOR of all elements = 99.
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

Second Round was held in morning around 10-11 am. There was one interviewer working on his laptop. Interviewer was really helpful and first offered me water and then for a bit talked about himself.

Q1. 
BST Iterator Problem Statement
You are tasked with implementing a class BSTIterator, which is designed to traverse a Binary Search Tree (BST) in the inorder manner. The class must support the following op...read more
Ans. 
Implement a BSTIterator class to traverse a Binary Search Tree in inorder manner.
• Implement a constructor to initialize the iterator with the root of the BST.

• Implement next() and hasNext() methods to traverse the BST in inorder.

• Implement prev() and hasPrev() methods to access the previous element in the inorder traversal.

• Use level-order traversal format to represent the tree input.

• Output the inorder traversal of the bin...read more
Answered by AI
Add your answer
Q2. 
Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum num...read more
Ans. 
Calculate the distance between two nodes in a binary tree.
• Traverse the tree to find the paths from the root to each node

• Find the lowest common ancestor of the two nodes

• Calculate the distance by adding the distances from the LCA to each node
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

2 coding questions and 20 mcq
 

Q1. 
Rotting Oranges Problem Statement
You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:
• 0 - representing an empty cell
• 1 - representing a fre...read more
Ans. 
Find the minimum time required to rot all fresh oranges in a grid.
• Use Breadth First Search (BFS) to simulate the rotting process.

• Track the time taken to rot all oranges and return -1 if any fresh oranges remain.

• Handle edge cases like no fresh oranges or all oranges already rotten.

• Consider using a queue to efficiently process adjacent oranges.

• Ensure to update the grid with the new state of oranges after each second.
Answered by AI
Add your answer
Q2. 
Calculate Sum of Proper Divisors
Given a natural number N, return the sum of all its proper divisors.
A proper divisor of Y is defined as a number X such that X < Y and Y % X = 0.
Example:
Input:
T...read more
Ans. 
Calculate the sum of proper divisors of a given natural number.
• Iterate from 1 to sqrt(N) and check for divisors

• If a divisor is found, add it to the sum and also add N/divisor if it is not the same as divisor

• Return the sum as the result
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

Technical interview

Q1. 
Rearrange Array to Form Largest Number
Given an array ARR consisting of non-negative integers, rearrange the numbers to form the largest possible number. The digits within each number cannot be changed.
...read more
Ans. 
Rearrange the array elements to form the largest possible number by concatenating them.
• Sort the array elements in a custom comparator function to get the largest number.

• Convert the sorted array elements to strings and concatenate them to form the final number.

• Handle cases where the numbers have the same prefix by comparing the concatenated forms.
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

Evening test around 5
Platform :- SHL
Environment was amazing

Q1. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
• Check if the second tree is a subtree of the first tree by comparing their structures and node values.

• Use a recursive approach to traverse both trees and check for equality.

• Handle cases where one tree is null or the values do not match.

• Return true if S is a subtree of T, false otherwise.
Answered by AI
Add your answer
Q2. 
Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the positi...read more
Ans. 
Given a sorted N*N matrix, find the position of a target integer X.
• Iterate over each row and column to find the target integer X

• Utilize the sorted nature of the matrix to optimize the search process

• Return the position of X if found, else return -1 -1
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

1 Hour 
Afternoon

Q1. 
Intersection of Linked List Problem
You are provided with two singly linked lists containing integers, where both lists converge at some node belonging to a third linked list.
Your task is to determine t...read more
Ans. 
Find the node where two linked lists merge, return -1 if no merging occurs.
• Traverse both lists to find their lengths and the difference in lengths

• Move the pointer of the longer list by the difference in lengths

• Traverse both lists simultaneously until they meet at the merging point
Answered by AI
Add your answer
Q2. 
Problem: Pair Sum in a Binary Search Tree
Given a Binary Search Tree (BST) and an integer 'S', your task is to find all pairs of nodes within the BST that total to 'S' and return these pairs. If no such p...read more
Ans. 
Find pairs of nodes in a BST that sum up to a given value 'S'.
• Traverse the BST in-order to get a sorted list of nodes.

• Use two pointers approach to find pairs with sum 'S'.

• Keep track of visited nodes to avoid using the same node twice in a pair.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Online Round held on Chime

Q1. 
Is Binary Heap Tree Problem Statement
You are given a binary tree of integers. Your task is to determine if it is a binary heap tree or not.
Input:
The first line of input contains an integer ‘T’ denoti...read more
Ans. 
Determine if a given binary tree is a binary heap tree or not based on certain properties.
• Check if the binary tree is a complete binary tree where every level, except the last level, is completely filled and the last level is as far left as possible.

• Ensure that every parent node is greater than all its children nodes, forming a max-heap.

• If any node does not have a left or right child, it should be represented as -1 in ...read more
Answered by AI
Add your answer
Q2. 
Edit Distance Problem Statement
Given two strings S and T with lengths N and M respectively, your task is to find the "Edit Distance" between these strings.
The Edit Distance is defined as the minimum nu...read more
Ans. 
The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the edit distances between substrings of the two input strings.

• Fill up the array based on the minimum of three possible operations: insert, delete, or replace.

• The final answer will be the value at...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Q1. 
String Transformation Problem Statement
Given a string str of length N, perform a series of operations to create a new string:
1. Select the smallest character from the first 'K' characters of the string,...read more
Ans. 
The problem involves selecting the smallest character from the first 'K' characters of a string and appending it to a new string until the original string is empty.
• Iterate through the string, selecting the smallest character from the first 'K' characters each time.

• Remove the selected character from the original string and append it to the new string.

• If fewer than 'K' characters remain, sort and append them in order.

• Rep...read more
Answered by AI
Add your answer
Q2. 
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 el...read more
Ans. 
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) as the result could be very large.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

1 hour online interview. 
Slot was given prior via email.
The HR contacted me via email and simultaneously provided me a link where I had to write the codes during my interview

Q1. 
Mike and Mobile Keypad Problem
Mike, a young math enthusiast, is playing with his mom’s mobile phone, which has a keypad with 12 buttons (10 digits: 0-9, and 2 special characters: ‘*’ and ‘#’). His challe...read more
Ans. 
Calculate the number of distinct numbers that can be formed by pressing 'N' buttons on a mobile keypad following specific rules.
• Use dynamic programming to keep track of the number of distinct numbers that can be formed at each step.

• Consider the possible transitions from each button to calculate the total number of distinct numbers.

• Implement a solution that efficiently handles large values by using modulo arithmetic.

• Ens...read more
Answered by AI
Add your answer
Q2. 
Maximum Subarray Sum Problem Statement
Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.
Example:
Input:
array = [34, -50, 42, 14, -5, 86]
Out...read more
Ans. 
Find the maximum sum of any contiguous subarray within an array of integers.
• Iterate through the array and keep track of the maximum sum of subarrays encountered so far.

• At each index, decide whether to include the current element in the subarray or start a new subarray.

• Use Kadane's algorithm to efficiently find the maximum subarray sum in O(N) time complexity.
Answered by AI
View 42 more answers
Q3. 
Maximum Sum of Non-Adjacent Elements
Given an array/list of ‘N’ integers, your task is to return the maximum sum of the subsequence where no two elements are adjacent in the given array/list.
Example:
I...read more
Ans. 
Find the maximum sum of non-adjacent elements in an array.
• Use dynamic programming to keep track of the maximum sum at each index, considering whether to include the current element or skip it.

• At each index, the maximum sum is either the sum of the current element and the element two positions back, or the sum at the previous index.

• Iterate through the array and update the maximum sum at each index accordingly.

• Return the...read more
Answered by AI
Add your answer
Q4. 
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 t...read more
Ans. 
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.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Strongly Connected Components (Tarjan’s Algorithm) Problem Statement
Given an unweighted directed graph with V vertices and E edges, your task is to identify and print all the strongly connected component...read more
Ans. 
Tarjan's Algorithm is used to find strongly connected components in an unweighted directed graph.
• Tarjan's Algorithm is a depth-first search based algorithm.

• It uses a stack to keep track of vertices in the current SCC.

• The algorithm assigns a unique id to each vertex and keeps track of the lowest id reachable from the current vertex.

• Once a SCC is identified, the vertices in the stack form that SCC.

• The algorithm runs in O...read more
Answered by AI
Add your answer
Q2. 
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 onl...read more
Ans. 
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 achie...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was a one hour round in which I was first told to introduce myself and then moved to questions.

Q1. 
Permutation in String Problem Statement
Determine if the string str2 contains a permutation of the string str1 as one of its substrings.
Input:
The first line contains an integer 'T', representing the n...read more
Ans. 
Check if a permutation of one string is a substring of another string.
• Create a frequency map of characters in str1.

• Iterate through str2 with a window of size N and check if the frequency map matches.

• Return 'Yes' if a permutation is found, 'No' otherwise.
Answered by AI
Add your answer
Q2. 
Sort 0s, 1s, and 2s Problem Statement
You are provided with an integer array/list ARR of size 'N' which consists solely of 0s, 1s, and 2s. Your task is to write a solution to sort this array/list.
Input:
...read more
Ans. 
Sort an array of 0s, 1s, and 2s in linear time with a single scan approach.
• Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.

• Iterate through the array once and swap elements based on their values and the pointers.

• After the single scan, the array will be sorted in the required order.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This was based more on my communication skills rather than my technical skills. The interviewer didn't only focus on whether I knew the answer or not but if I was able to communicate my knowledge to the interviewer.

It was more of theory based interview
Questions are as follows:-
1. What are SQL and acid properties?

2. How does a website start?

3. What are deadlocks with real life examples? Give necessary conditions for deadlock. 
-> Real life examples were must. 

4. What is virtual function?

5. Tell me the most challenging this while you made your project. ( I had to pick my project on my own) 

6. Tell me the most interesting feature you found working on a language. 

7. Technical question on structures in C as I used it in my project. The interviewer asked if the structure for a linked list is changed as:-
struct node

{
int data;
struct next; 
};
I explained how this won't work as struct will be created again and again which will lead to memory limit exceeded.

Q1. 
Delete Alternate Nodes from a Singly Linked List
Given a Singly Linked List of integers, remove all the alternate nodes from the list.
Input:
The first and the only line of input will contain the elemen...read more
Ans. 
Remove alternate nodes from a singly linked list of integers.
• Traverse the linked list and skip every alternate node while updating the next pointers.

• Make sure to handle cases where there are less than 3 nodes in the list.

• Update the next pointers accordingly to remove alternate nodes.

• Example: Input: 10 20 30 40 50 60 -1, Output: 10 30 50
Answered by AI
Add your answer