OATIndia Software Developer Interview Questions and Answers

Numerical and logical aptitude test

There are 5 rounds on datastructure and algorithm

Round duration - 1 hour
Round difficulty - Medium

Q1. 
First Missing Positive Problem Statement
You are provided with an integer array ARR of length 'N'. Your objective is to determine the first missing positive integer using linear time and constant space. T...read more
Ans. 
Find the smallest positive integer missing from an array of integers.
• Iterate through the array and mark positive integers as visited by changing the sign of the corresponding index.

• After marking all positive integers, iterate again to find the first positive integer with a positive value.

• Return the index of the first positive integer found plus one as the answer.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Easy

Had some small chit-chat regarding how Work from Home is going on for him and me. Later he introduced himself and asked the same.
Coming to technical questions, he asked me the algorithm and also asked me to code the questions mentioned below. Discussed the time complexities and edge cases.

Q1. 
Spiral Matrix Problem Statement
You are given a N x M matrix of integers. Your task is to return the spiral path of the matrix elements.
Input
The first line contains an integer 'T' which denotes the nu...read more
Ans. 
The task is to return the spiral path of elements in a given matrix.
• Iterate over the matrix in a spiral path by keeping track of the boundaries.

• Print the elements in the spiral path as you traverse the matrix.

• Handle cases where the matrix is not a square matrix separately.
Answered by AI
Add your answer
Q2. 
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 character frequency.
• Create a hashmap to store sorted strings as keys and corresponding anagrams as values.

• Iterate through the input strings, sort each string, and add it to the hashmap.

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

Round duration - 45 Minutes
Round difficulty - Medium

This round started without any introduction, and he directly jumped into the question. Asked me about the algorithm, and later coded it and ran it. And then he asked me to optimize it. Finally, he asked me if I had any questions.

Q1. 
Tic-Tac-Toe Design Problem
Design a 2-player Tic-Tac-Toe game played on an N * N grid where Player 1 uses ‘X’ and Player 2 uses ‘O’. A move is always valid and occupies an empty spot.
If a player places ...read more
Ans. 
Design a 2-player Tic-Tac-Toe game on an N x N grid where players take turns placing their marks, and the first player to get N marks in a row wins.
• Implement a function move(row, col, player) to handle each player's move and check for a win condition.

• Keep track of the board state and update it after each move.

• Check for winning conditions horizontally, vertically, and diagonally after each move.

• Return the result (0 for ...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

This round was conducted in Hackerrank portal for a total duration of 95 minutes and was divided into 4 sections.

1st Section : Aptitude Section : 14 questions , 28 minutes
2nd Section : Technical Section : 12 questions , 17 minutes
3rd Section :1 coding Questions : 20 minutes+30 minutes

Q1. 
Water Equalization Problem Statement
You are provided with an array ARR of positive integers. Each integer represents the number of liters of water in a bucket. The goal is to make the liters of water in ...read more
Ans. 
Given an array of water buckets, find the minimum liters of water to remove to make all buckets contain the same amount of water.
• Iterate through the array to find the most common amount of water in the buckets.

• Calculate the total liters of water that need to be removed to equalize all buckets to the most common amount.

• Return the total liters of water to be removed.
Answered by AI
Add your answer
Q2. 
Rat in a Maze Problem Statement
You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N ma...read more
Ans. 
Find all possible paths for a rat in a maze from source to destination.
• Use backtracking to explore all possible paths in the maze.

• Keep track of visited cells to avoid revisiting them.

• Explore all possible directions (up, down, left, right) from each cell.

• Add the current direction to the path and recursively explore further.

• If the destination is reached, add the path to the list of valid paths.
Answered by AI
Add your answer

Round duration - 120 Minutes
Round difficulty - Medium

This was an Online F2F Technical Round conducted on CodePair : Hackerrank. So, Basically You have to Run and Submit ( Pass All Test cases) in the Interview Round also (Like normal Coding Test) in Codepair : Hackerrank & along with that You should have to explain your Code and Approach to the Interviewers.
The Interviewers were helpful and didn't hesitate in giving hints.
Timing - 10:00 A.M to 12:00 P.M

Q1. 
Minimum Fountains Activation Problem
In this problem, you have a one-dimensional garden of length 'N'. Each position from 0 to 'N' has a fountain that can provide water to the garden up to a certain range...read more
Ans. 
Find the minimum number of fountains to activate to water the entire garden.
• Iterate through the array to find the coverage of each fountain.

• Keep track of the farthest coverage reached by activating fountains.

• Activate the fountain that covers the farthest point not yet covered.

• Repeat until the entire garden is watered.
Answered by AI
Add your answer
Q2. 
Minimize Cash Flow Problem
You are provided with a list of 'transactions' involving 'n' friends who owe each other money. Each entry in the list contains information about a receiver, sender, and the tran...read more
Ans. 
Minimize cash flow problem among friends by optimizing transactions.
• Create a graph where nodes represent friends and edges represent transactions.

• Calculate net amount each friend owes or is owed by summing up all transactions.

• Use a recursive algorithm to minimize cash flow by settling debts between friends.

• Update the graph and repeat the process until all debts are settled.
Answered by AI
Add your answer

Round duration - 120 Minutes
Round difficulty - Hard

A lot of Variants based on Constraints were asked in this Round. They will ask you to write the final code for every question before Submitting it(run all test cases) so you won’t get any hints after running test cases in the IDE. ( So don’t Submit your code before dry running it on a lot of Test Cases on pen & paper , they allow to use pen & blank paper at the time of Interviews) .The Interviewers tried to trick in case of time complexities even if you gave the best one. So try to be confident.

Q1. 
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 ...read more
Ans. 
The task is to determine the maximum profit that can be achieved by performing up to two buy-and-sell transactions on a given set of stock prices.
• Iterate through the array of stock prices and keep track of the maximum profit that can be achieved by buying and selling at different points.

• Maintain variables to store the maximum profit after the first transaction, the maximum profit after the second transaction, and the m...read more
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This was HR Round. The HR was friendly and asked basic questions.
The timing was 2:00 PM to 2:30 PM.

Round duration - 90 minutes
Round difficulty - Easy

This round was the online coding test conducted on the platform Mettl. The languages allowed were C, C++, Java and Python. There were three questions. One was of graphs (Depth-first search), other was a big integer problem and the third was a string problem.

Q1. 
Graph Coloring Problem Statement
You are provided with a graph consisting of N vertices, numbered from 1 to N, and M edges. Your task is to color the graph using two colors, Blue and Red, such that no two...read more
Ans. 
Given a graph with vertices and edges, determine if it can be colored using two colors without adjacent vertices sharing the same color.
• Check if the graph is bipartite using graph coloring algorithm like BFS or DFS.

• If the graph is bipartite, return 'Possible' with a valid coloring assignment.

• If the graph is not bipartite, return 'Impossible'.
Answered by AI
Add your answer
Q2. 
String Compression Problem Statement
Write a program to perform basic string compression. For each character that repeats consecutively more than once, replace the consecutive duplicate occurrences with t...read more
Ans. 
Write a program to compress a string by replacing consecutive duplicate characters with the character followed by the number of repetitions.
• Iterate through the string and count consecutive occurrences of each character

• Append the character and its count to a new string

• Return the compressed string if it is shorter than the original, else return the original string

• Handle edge cases like single characters or when compresse...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was a pen and paper subjective interview round. You were expected to write full code on paper. Make sure you use proper names for the variables and write comments explaining very clearly what the code does. Also, try writing code in good handwriting which can be understood by the interviewer.

Q1. Find the total number of palindromic substrings in a given string.
Ans. 
Count total palindromic substrings in a given string.
• Iterate through each character in the string and consider it as the center of a palindrome. Expand outwards to find all palindromic substrings.

• Use dynamic programming to efficiently check if a substring is a palindrome.

• Consider both odd-length and even-length palindromes.

• Example: Input 'ababa', output 7 (a, b, a, b, a, aba, aba)
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

The interview took place in the morning and the interviewer was very friendly.

Q1. 
Count Inversions Problem Statement
Let A[0 ... n-1] be an array of n distinct positive integers. An inversion of A is a pair of indices (i, j) such that i < j and A[i] > A[j]. Given an integer array...read more
Ans. 
Count the number of inversions in an array of distinct positive integers.
• Use merge sort algorithm to count inversions efficiently.

• Divide the array into two halves and recursively count inversions in each half.

• Merge the two sorted halves while counting split inversions.

• Time complexity can be optimized to O(n log n) using merge sort.

• Example: For input A = [2, 4, 1, 3, 5], the output should be 3.
Answered by AI
Add your answer
Q2. 
Sum Tree Conversion Problem Statement
Transform a given binary tree into a sum tree where each node is replaced by the sum of its immediate children's values. Leaf nodes should be replaced with 0. Then, p...read more
Ans. 
Convert a binary tree into a sum tree by replacing each node with the sum of its children's values, and return the preorder traversal.
• Traverse the tree recursively and replace each node with the sum of its children's values

• Leaf nodes should be replaced with 0

• Perform a preorder traversal on the transformed sum tree to get the final result
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

The HR Interview round was held in the morning and it was right after my technical interview.

Round duration - 90 minutes
Round difficulty - Easy

This round consists of 3 coding questions with a total time limit of 90 minutes. The first two questions were of easy level and the third question was of medium level. No two candidates had the same set of questions, the distribution of questions was random. The test was conducted on mettl platform with both audio and video on for monitoring on the candidate.

Q1. 
Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5  
Stre...read more
Ans. 
Calculate and print the median after each new integer is added to the stream.
• Use two heaps - a max heap to store the smaller half of the numbers and a min heap to store the larger half.

• Keep the sizes of the two heaps balanced to efficiently calculate the median.

• If the total number of elements is odd, the median will be the top element of the max heap.

• If the total number of elements is even, the median will be the avera...read more
Answered by AI
Add your answer
Q2. 
Fruits and Baskets Problem Statement
You are given 'n' fruit trees planted along a road, numbered from 0 to n-1. Each tree bears a fruit type represented by an uppercase English alphabet. A Ninja walking ...read more
Ans. 
The Ninja must collect fruits from trees in consecutive order, maximizing the number of fruits in two baskets.
• Iterate through the trees while keeping track of the types of fruits collected in each basket.

• Use a sliding window approach to find the maximum number of fruits collected.

• Keep track of the count of each fruit type encountered to handle the condition of only two types of fruits in each basket.
Answered by AI
Add your answer
Q3. 
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 the given number of dice.

• Iterate through the dice and faces to calculate the number of ways to reach each sum.

• Return the result modulo 10^9 + 7.

• Optim...read more
Answered by AI
Add your answer

Round duration - 50 miutes
Round difficulty - Medium

This was my first interview and I was a bit nervous. The interview was conducted on Microsoft Team. He told me to share my screen and write the pseudo code on notepad. The interviewer was very friendly and also gave me hints for the question. However, he mostly focused on optimization of the code. At the end of the question, few questions related to Operating Systems 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 character frequency.
• Iterate through each string in the input array

• For each string, sort the characters and use the sorted string as a key in a hashmap to group anagrams

• Return the grouped anagrams as arrays of strings
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

The second round consisted questions related to concepts of object oriented programming and databases. At the end of the interview he asked me to explain any one good project. The interview lasted for 45 minutes. The interviewer was friendly and good.

Q1. 
Merge Sort Problem Statement
You are given a sequence of numbers, ARR. Your task is to return a sorted sequence of ARR in non-descending order using the Merge Sort algorithm.
Explanation:
The Merge Sort...read more
Ans. 
Implement Merge Sort algorithm to sort a given sequence of numbers in non-descending order.
• Divide the input array into two halves recursively until each array has only one element.

• Merge the sorted halves to produce a completely sorted array.

• Time complexity of Merge Sort is O(n log n).
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This was my last round and I was a bit tensed. It was an HR round. The interviewer was very professional. He discussed and asked questions about my various achievements, my interests apart from the technical field and also asked about my projects. I made sure to answer all the questions confidently and calmly.

Round duration - 45 minutes
Round difficulty - Medium

The interview was with a Korean employee. 

Q1. 
Bridge in Graph Problem Statement
Given an undirected graph with V vertices and E edges, your task is to find all the bridges in this graph. A bridge is an edge that, when removed, increases the number of...read more
Ans. 
Find all the bridges in an undirected graph.
• Use Tarjan's algorithm to find bridges in the graph.

• A bridge is an edge whose removal increases the number of connected components.

• Check for bridges by removing each edge and checking the number of connected components.

• Return the edges that are bridges in non-decreasing order.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

Interviewer was an Indian employee. 

Q1. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palind...read more
Ans. 
Identify the longest palindromic substring in a given string.
• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found

• Return the longest palindrome with the smallest start index
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee.

Q1. 
Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictiona...read more
Ans. 
Given a sorted alien dictionary in an array of strings, determine the character order of the alien language.
• Iterate through the words in the dictionary to build a graph of character dependencies.

• Perform a topological sort on the graph to determine the character order.

• Return the character order as a list of characters.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee. 

Q1. 
Problem: Ninja's Robot
The Ninja has a robot which navigates an infinite number line starting at position 0 with an initial speed of +1. The robot follows a set of instructions which includes ‘A’ (Acceler...read more
Ans. 
Determine the minimum length of instruction sequence for a robot to reach a given target on an infinite number line.
• Start at position 0 with speed +1, update position and speed based on 'A' and 'R' instructions

• For each test case, find the shortest sequence of instructions to reach the target

• Consider both positive and negative positions for the robot
Answered by AI
Add your answer

Round duration - 120 Minutes
Round difficulty - Easy

The round was conducted in day around 3PM.

Q1. 
Partition Equal Subset Sum Problem
Given an array ARR consisting of 'N' positive integers, determine if it is possible to partition the array into two subsets such that the sum of the elements in both sub...read more
Ans. 
The problem is to determine if it is possible to partition an array into two subsets with equal sum.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the results of subproblems.

• Check if the sum of the array is even before attempting to partition it.

• Iterate through the array and update the 2D array based on the sum of subsets.

• Return true if a subset with half the sum is found, false ot...read more
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

The interview was preponed and was conducted at 9AM.
The interviewer was friendly and I had saw him earlier at pre-placement talk.

Q1. 
Convert Sentence to Pascal Case
Given a string STR, your task is to remove spaces from STR and convert it to Pascal case format. The function should return the modified STR.
In Pascal case, words are con...read more
Ans. 
Convert a given string to Pascal case format by removing spaces and capitalizing the first letter of each word.
• Iterate through each character in the string

• If the character is a space, skip it

• If the character is not a space and the previous character is a space or it is the first character, capitalize it
Answered by AI
Add your answer
Q2. Write an SQL query to retrieve the Nth highest salary from a database.
Ans. 
SQL query to retrieve the Nth highest salary from a database
• Use the ORDER BY clause to sort salaries in descending order

• Use the LIMIT clause to retrieve the Nth highest salary

• Consider handling cases where there might be ties for the Nth highest salary
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

This round was conducted 15mins after 1st round.

Q1. 
Remove the Kth Node from the End of a Linked List
You are given a singly Linked List with 'N' nodes containing integer data and an integer 'K'. Your task is to delete the Kth node from the end of this Lin...read more
Ans. 
Remove the Kth node from the end of a singly linked list.
• Traverse the list to find the length 'N'.

• Calculate the position of the node to be removed from the beginning as 'N - K + 1'.

• Remove the node at the calculated position.

• Handle edge cases like removing the head or tail of the list.

• Update the pointers accordingly after removal.
Answered by AI
Add your answer