PolicyBazaar Software Developer Intern Interview Questions and Answers

Round duration - 120 minutes
Round difficulty - Medium

10 min for debugging
40 min for problems(coding)
40 min for pyschometric
30 min for aptitude

Q1. 
Total Unique Paths Problem Statement
You are located at point ‘A’, the top-left corner of an M x N matrix, and your target is point ‘B’, the bottom-right corner of the same matrix. Your task is to calcula...read more
Ans. 
The task is to calculate the total number of unique paths from the top-left to bottom-right corner of an M x N matrix by moving only right or down.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell in the matrix.

• Initialize the first row and first column with 1 as there is only one way to reach each cell in the first row and column.

• For each cell ...read more
Answered by AI
Add your answer
Q2. 
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 ...read more
Ans. 
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
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Easy

timing was 4 pm . we connected on amazon chime. Initially he asked me a few things from resume then moved on to problem solving.

Q1. 
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 t...read more
Ans. 
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 all eight possible directions for connectivity while traversing the matrix.

• Handle edge ca...read more
Answered by AI
Add your answer
Q2. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle formed by each bar as the smallest height in the stack times the width.

• Update the maximum area found so far and return it as the result.
Answered by AI
Add your answer

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
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

It was in the morning session around 10:00AM-10:40AM. Platform used for this round was hackerrank. Level of questions were of moderate level.

Q1. 
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...read more
Ans. 
Find the sum of the subarray with the maximum sum among all subarrays in a given array.
• Iterate through the array and keep track of the maximum sum subarray ending at each index.

• Update the maximum sum subarray by comparing it with the sum of the current element or the sum of the current element plus the maximum sum subarray ending at the previous index.

• Return the maximum sum subarray found.

• Example: For input arr = [-2,
Answered by AI
Add your answer

Round duration - 20 minutes
Round difficulty - Medium

It was in the evening around 5:00PM-5:30PM and the platform used for this round was skype. There are total 5 students in each group

Q1. 
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 ...read more
Ans. 
Search for integers in a rotated sorted array efficiently.
• Use binary search to find the pivot point where the array is rotated.

• Based on the pivot point, apply binary search on the appropriate half of the array.

• Return the index of the integer if found, else return -1.
Answered by AI
Add your answer

Round duration - 15 minutes
Round difficulty - Easy

It was in the night around 7:00PM-7:15PM. Platform used for this round was skype. Interviewer was very friendly in nature. This round focusses more on your personality rather than knowledge

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
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
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 - 60 Minutes
Round difficulty - Medium

Q1. 
Infix to Postfix Conversion
You are provided with a string EXP which represents a valid infix expression. Your task is to convert this given infix expression into a postfix expression.
Explanation:
An i...read more
Ans. 
Convert infix expression to postfix expression.
• Use a stack to keep track of operators and operands.

• Follow the rules of precedence for operators.

• Handle parentheses by pushing them onto the stack.

• Process the expression from left to right to convert to postfix form.
Answered by AI
Add your answer
Q2. 
Reverse Linked List in Groups of K
You are provided with a linked list containing 'N' nodes and an integer 'K'. The task is to reverse the linked list in groups of size K, which means reversing the nodes ...read more
Ans. 
Reverse a linked list in groups of size K by reversing nodes in each group.
• Iterate through the linked list in groups of size K

• Reverse each group of nodes

• Handle cases where the last group may not have K elements
Answered by AI
Add your answer
Q3. 
Problem Statement: Find the Number of States
You are given ‘n’ cities, some of which are connected by bidirectional roads. You also have an ‘n x n’ matrix ‘roads’, where if city ‘i’ and city ‘j’ are conne...read more
Ans. 
Find the number of states of cities connected by roads in a matrix.
• Iterate through each city and perform depth-first search to find connected cities.

• Use a visited array to keep track of visited cities.

• Increment state count whenever a new state is found.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

Q1. 
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 th...read more
Ans. 
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.
Answered by AI
Add your answer
Q2. 
Clone Linked List with Random Pointer Problem Statement
Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or ...read more
Ans. 
Yes, the cloning of a linked list with random pointer can be accomplished without utilizing extra space.
• Use a hashmap to store the mapping between original nodes and their corresponding cloned nodes.

• Iterate through the original linked list to create the cloned nodes and update the hashmap.

• Iterate through the original linked list again to set the next and random pointers of the cloned nodes using the hashmap.

• Time comple...read more
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Easy

This is the last round, It is just for formality

Q1. What are the ACID properties in database management systems, and how does memory management work in this context?
Ans. 
ACID properties ensure database transactions are processed reliably. Memory management involves allocating and deallocating memory efficiently.
• ACID properties: Atomicity, Consistency, Isolation, Durability

• Atomicity ensures that either all operations in a transaction are completed successfully or none are

• Consistency ensures that the database remains in a valid state before and after the transaction

• Isolation ensures that...read more
Answered by AI
Add your answer
Q2. 
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...read more
Ans. 
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 length of the longest increasi
Answered by AI
Add your answer

Round duration - 150 Minutes
Round difficulty - Medium

It was on Amcat platform from 8 pm to 11 pm. We were allowed to login anytime between 8 pm and 8:3 to start the test. It was a proctored test. It consisted of 4 sections to be finished in 2.5 hours. 1st section was code debugging round were 6 questions were there to fix the bugs in the code within 10 minutes. I did in 4 minutes.

2nd section had 2 coding questions which had to be done within 70 minutes. One was related to merge two sorted Linked Lists and second question was Clone a linked List having random pointers. It was accepting only the optimized code.

I finishes 2nd section in 25 minutes. Thanks to coding Ninjas for help in practice.

3rd section had almost 50 behavioral questions which is to be finishes in 35 minutes.

4th section was an aptitude section consisting of 25 questions which was supposed to be finished in 35 minutes. Questions were mainly to check your analytical skills.

Q1. 
Merge Two Sorted Linked Lists Problem Statement
You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.
...read more
Ans. 
Merge two sorted linked lists into a single sorted linked list.
• Create a dummy node to start the merged list

• Compare the values of the two linked lists and add the smaller value to the merged list

• Move the pointer of the merged list and the pointer of the smaller value list forward

• Continue this process until one of the lists is fully traversed

• Add the remaining elements of the other list to the merged list
Answered by AI
Add your answer
Q2. 
Clone a Linked List with Random Pointers Problem Statement
Given a linked list where each node contains two pointers: the first points to the next node in sequence, and the second is a random pointer that...read more
Ans. 
Clone a linked list with random pointers by creating deep copy of the original list without duplicating references.
• Create a deep copy of the linked list by instantiating new nodes for each node in the original list.

• Ensure that the random pointers in the cloned list point to the corresponding nodes in the new list.

• Do not duplicate references to original nodes while creating the clone.

• Implement the function to clone the ...read more
Answered by AI
Add your answer

Round duration - 40 Minutes
Round difficulty - Medium

It was also a DSA round on Amazon Chime with an SDE-2 guy from amazon. It was for 40 minutes and he asked me to turn my web camera on and he shared a screen with me for code pair.

Q1. 
Longest Common Subsequence Problem Statement
Given two strings, S and T with respective lengths M and N, your task is to determine the length of their longest common subsequence.
A subsequence is a seque...read more
Ans. 
Find the length of the longest common subsequence between two given strings.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the lengths of common subsequences.

• Iterate through the strings to fill the array and find the longest common subsequence length.
Answered by AI
Add your answer
Q2. 
Longest Substring Without Repeating Characters Problem Statement
Given a string S of length L, determine the length of the longest substring that contains no repeating characters.
Example:
Input:
"abac...read more
Ans. 
Find the length of the longest substring without repeating characters in a given string.
• Use a sliding window approach to keep track of the longest substring without repeating characters.

• Use a hashmap to store the index of each character as it appears in the string.

• Update the start index of the window when a repeating character is found.

• Calculate the maximum length of the window as you iterate through the string.

• Return
Answered by AI
Add your answer

Round duration - 42 Minutes
Round difficulty - Medium

It was based on CS core subjects as well as 1 coding question based on dynamic programming. Interview was with one Amazonian who was an SDE 2 there.

Q1. 
Dice Throws Problem Statement
You are given D dice, each having F faces numbered from 1 to F. The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up num...read more
Ans. 
The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the number of ways to achieve each sum with different number of dice.

• Iterate through the dice and sum values to fill up the array.

• Return the result modulo 10^9 + 7.

• Optimize the solution to use ...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Q1. 
Count Inversions Problem Statement
Given an integer array ARR of size N, your task is to find the total number of inversions that exist in the array.
An inversion is defined for a pair of integers in the...read more
Ans. 
Count the total number of inversions in an integer array.
• Iterate through the array and for each pair of elements, check if the conditions for inversion are met.

• Use a nested loop to compare each element with all elements to its right.

• Keep a count of the inversions found and return the total count at the end.
Answered by AI
Add your answer
Q2. 
Postfix Expression Evaluation Problem Statement
Given a postfix expression, your task is to evaluate the expression. The operator will appear in the expression after the operands. The output for each expr...read more
Ans. 
Evaluate postfix expressions by applying operators after operands. Return result modulo (10^9+7).
• Iterate through each character in the postfix expression

• If character is an operand, push it onto the stack

• If character is an operator, pop two operands from stack, apply operator, and push result back

• Continue until end of expression, return final result modulo (10^9+7)
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

Q1. 
String Rearrangement Problem Statement
You are given a string of lowercase characters. The objective is to rearrange (reorder) the string so that no two adjacent characters are identical.
Return the rear...read more
Ans. 
Given a string of lowercase characters, rearrange it so that no two adjacent characters are identical. Return the rearranged string or 'NO SOLUTION'.
• Iterate through the string and count the frequency of each character.

• Sort the characters based on their frequency in non-increasing order.

• Place the characters with highest frequency first, alternating with other characters.

• If there are more than half of the characters with
Answered by AI
Add your answer
Q2. 
Pair Sum Problem Statement
Given an integer array ARR of size N and an integer S, your task is to return a list of all pairs of elements such that the sum of each pair equals S.
Input:
The first line co...read more
Ans. 
The task is to find pairs of elements in an array that sum up to a given target value.
• Iterate through the array and for each element, check if the complement (target - current element) exists in a hash set.

• If the complement exists, add the pair to the result list.

• Ensure pairs are sorted based on the criteria mentioned in the question.
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

Q1. 
Find Number of Islands
You are provided with a 2-dimensional array/list of size N rows by M columns, containing ones (1) and zeroes (0). Here, 1 represents land, and 0 represents water.
A cell is consider...read more
Ans. 
Find the number of islands in a 2D matrix of 1s and 0s.
• Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.

• Use a visited array to keep track of visited cells to avoid counting the same island multiple times.

• Increment the island count whenever a new island is encountered.
Answered by AI
Add your answer
Q2. 
Triplets in a Sorted Doubly Linked List
Given a sorted doubly linked list of distinct nodes, determine how many triplets in the list have a sum equal to a given value 'X'. Each node in the list contains a...read more
Ans. 
Given a sorted doubly linked list of distinct nodes, find and count triplets with a sum equal to a given value 'X'.
• Iterate through the list and for each node, use two pointers to find the other two nodes that sum up to 'X'.

• Keep track of the count of triplets found and return it at the end.

• Handle edge cases like when the list has less than 3 nodes or no triplets are found.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

In this round i was tested for Data Structure competency. Two questions were asked.

Q1. 
Group Anagrams Problem Statement
Given an array or list of strings called inputStr, your task is to return the strings grouped as anagrams. Each group should contain strings that are anagrams of one anoth...read more
Ans. 
Group anagrams in an array of strings based on their characters.
• Iterate through the array of strings and sort each string to group anagrams together.

• Use a hashmap to store the sorted string as key and the list of anagrams as value.

• Return the values of the hashmap as the grouped anagrams.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Two questions were asked in this round on data structures and algorithms.

Q1. 
BST Iterator Problem Statement
You are tasked with creating a class named BSTIterator that acts as an iterator for the inorder traversal of a binary search tree. Implement the following functions:
1. BST...read more
Ans. 
Implement a BSTIterator class for inorder traversal of a binary search tree.
• Create a BSTIterator class with constructor, next, and hasNext functions.

• Use a stack to simulate inorder traversal of the binary search tree.

• Ensure the hasNext function returns true if there are more elements to traverse.

• Example: Input - 4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1, Output - 1 2 3 4 5 6 7
Answered by AI
Add your answer
Q2. 
K Most Frequent Words Problem Statement
Given an array or list WORDS of 'N' non-empty words and an integer 'K', identify the 'K' most frequent words and return them sorted by their frequency, in descendin...read more
Ans. 
Identify the K most frequent words in a list, sorted by frequency and lexicographical order.
• Use a hashmap to store word frequencies

• Use a min heap to keep track of K most frequent words

• Sort the heap based on frequency and lexicographical order
Answered by AI
Add your answer