NexTurn Software Developer Interview Questions and Answers

Round duration - 25 Minutes
Round difficulty - Medium

Very friendly interviewer. Although waiting time was very high

Q1. 
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:
...read more
Ans. 
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
• Iterate through the array and for each element, check if the complement (S - current element) exists in a hash set.

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

• Sort the result list based on the criteria mentioned in the question.

• Return the sorted list of pairs.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This is a written round on paper for everyone. Three coding questions were given. Two out of three must be correct covering every single edge case to qualify for the next round. Only the most optimal solution was to be considered. 

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 an array of integers.
• Iterate through the array and keep track of the maximum sum subarray encountered so far.

• Use Kadane's algorithm to efficiently find the maximum subarray sum.

• Consider the sum of an empty subarray as 0.

• Example: For input arr = [-2, 1, -3, 4, -1], the maximum subarray sum is 4.
Answered by AI
Add your answer
Q2. 
Connecting Ropes with Minimum Cost
You are given 'N' ropes, each of varying lengths. The task is to connect all ropes into one single rope. The cost of connecting two ropes is the sum of their lengths. Yo...read more
Ans. 
Connect ropes with minimum cost by merging two smallest ropes at a time.
• Sort the array of rope lengths in ascending order.

• Merge the two smallest ropes at a time and update the cost.

• Repeat the process until all ropes are merged.

• Return the total cost as the minimum cost to connect all ropes.
Answered by AI
Add your answer
Q3. 
Left View of a Binary Tree Problem Statement
Given a binary tree, your task is to print the left view of the tree.
Example:
Input:
The input will be in level order form, with node values separated by a...read more
Ans. 
Print the left view of a binary tree given in level order form.
• Traverse the tree level by level and print the first node encountered at each level

• Use a queue to perform level order traversal

• Keep track of the level while traversing the tree
Answered by AI
Add your answer

Round duration - 50 minutes
Round difficulty - Easy

This was face to face interview round.

Q1. 
Finding Triplets in a Binary Tree Problem Statement
You are given a Binary Tree of integers and an integer 'X'. Your task is to find all the triplets in the tree whose sum is strictly greater than 'X'. Th...read more
Ans. 
Find all triplets in a binary tree whose sum is greater than a given integer X, with a grandparent-parent-child relationship.
• Traverse the binary tree to find all possible triplets with the required relationship.

• Keep track of the sum of each triplet and compare it with the given integer X.

• Return the triplets that satisfy the condition in any order.

• Ensure each triplet follows the format (grand-parent, parent, child).
Answered by AI
Add your answer
Q2. 
Loot Houses Problem Statement
A thief is planning to steal from several houses along a street. Each house has a certain amount of money stashed. However, the thief cannot loot two adjacent houses. Determi...read more
Ans. 
Determine the maximum amount of money a thief can steal from houses without looting two consecutive houses.
• Use dynamic programming to keep track of the maximum amount of money that can be stolen up to each house.

• At each house, the thief can either choose to steal from the current house or skip it and steal from the previous house.

• The maximum amount of money that can be stolen at the current house is the maximum of the ...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was face to face interview round.

Round duration - 90 Minutes
Round difficulty - Medium

This is a written round on paper for everyone. Three coding questions were given. Two out of three must be correct covering every single edge case to qualify for the next round. Only the most optimal solution was to be considered.

Q1. 
Maximum Subarray Sum Problem Statement
Given an array ARR consisting of N integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.
Example of Sub...read more
Ans. 
Find the maximum sum of a contiguous subarray in an array of integers.
• Use Kadane's algorithm to find the maximum subarray sum in linear time.

• Initialize two variables: maxSum and currentSum.

• Iterate through the array and update currentSum by adding the current element or starting a new subarray.

• Update maxSum if currentSum becomes greater than maxSum.

• Return maxSum as the maximum subarray sum.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Easy

This was face to face interview round.

Q1. 
Finding Triplets in a Binary Tree Problem Statement
You are given a Binary Tree of integers and an integer 'X'. Your task is to find all the triplets in the tree whose sum is strictly greater than 'X'. Th...read more
Ans. 
Find all triplets in a binary tree whose sum is greater than a given integer X, with a grandparent-parent-child relationship.
• Traverse the binary tree to find all possible triplets.

• Check if the sum of each triplet is greater than X.

• Ensure the relationship of grandparent-parent-child in each triplet.

• Return the valid triplets in any order.

• Handle constraints and edge cases appropriately.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

FACE TO FACE ROUND INTERVIEW

Q1. Can you tell me about yourself?
Add your answer
Q2. What is the difference between Mutex and Semaphores? Please provide a real-life example.
Ans. 
Mutex is used for exclusive access to a resource by only one thread at a time, while Semaphores can allow multiple threads to access a resource simultaneously.
• Mutex is binary and allows only one thread to access a resource at a time, while Semaphores can have a count greater than one.

• Mutex is used for protecting critical sections of code, while Semaphores can be used for controlling access to a pool of resources.

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

Round duration - 60 minutes
Round difficulty - Easy

Round duration - 50 minutes
Round difficulty - Easy

Round duration - 60 minutes
Round difficulty - Easy

At the beginning of this round, the interviewer asked me about the data structures I knew. Linked lists, trees, graphs, arrays etc. was my answer. He asked me how well I knew Dynamic Programming. I said I wasn’t strong in that and he said that he would ask me a question on dynamic programming for sure.

Round duration - 40 minutes
Round difficulty - Easy

The interviewer asked me if I was comfortable with the interview process so far and how the previous interviews were. I said it was good and he gave me the first problem to solve.

Round duration - 60 minutes
Round difficulty - Easy

The interviewer asked me some Com­puter Sci­ence‍ fundamentals in this round as well as some behavioural questions.

Q1. Implement a Trie data structure and write functions to insert and search for a few words in it.
Ans. 
Implement a Trie data structure with insert and search functions.
• Create a TrieNode class with children and isEndOfWord attributes.

• Implement insert function to add words by iterating through characters.

• Implement search function to check if a word exists by traversing the Trie.

• Example: Insert 'apple', 'banana', 'orange' and search for 'apple' and 'grape'.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This round consist of two questions and we have to solve both the questions to qualify for the next round.

Round duration - 40 minutes
Round difficulty - Easy

A single coding question was asked that had a lot of corner cases.

Round duration - 45 minutes
Round difficulty - Easy

It had 3 coding questions followed by basic concepts of DP.

Q1. How do you find the maximum difference between a node and its descendant in the same path in a binary tree?
Ans. 
To find the maximum difference between a node and its descendant in the same path in a binary tree, we can perform a depth-first search while keeping track of the minimum value encountered so far.
• Perform a depth-first search on the binary tree, keeping track of the minimum value encountered so far in the path.

• At each node, calculate the difference between the current node value and the minimum value encountered so far ...read more
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

It had 2 coding questions which were of good level.

Q1. How can you find a Minimum Spanning Tree (MST) from a given graph using Kruskal’s algorithm?
Ans. 
Kruskal's algorithm finds MST by sorting edges, adding smallest edge that doesn't create a cycle, repeat until all vertices are connected.
• Sort all edges in non-decreasing order of their weights.

• Initialize an empty graph to store the MST.

• Iterate through sorted edges and add the smallest edge that doesn't create a cycle in the MST.

• Repeat until all vertices are connected in the MST.
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This was the last round.

Round duration - 150 minutes
Round difficulty - Medium

We could attempt at any time out of the 3 given days.
The round was very time constrained and we could NOT go back to the question that we already attempted.

Q1. 
Merge Two Sorted Linked Lists
Given two sorted linked lists, your task is to merge them into a single sorted linked list. Return the head of the newly combined list.
Note:
The given linked lists may or ...read more
Ans. 
Merge two sorted linked lists into a single sorted linked list.
• Create a dummy node to start the merged list

• Compare nodes from both lists and add the smaller one to the merged list

• Move the pointer of the merged list and the list with the smaller node

• Handle cases where one list is exhausted before the other

• Return the head of the merged list
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Hard

Evening at 5:00 pm. It was held on Amazon Chime app
Face cam was to be kept on COMPULSARILY. You could however not see the interviewer.
Codepen type environment was also used for typing my code which could be edited by the interviewer also.
(Shared document kind of)
Interviewer was very professional and was trying to push me towards getting the most optimal solution. Each and every answer was asked a counter question as to why I made that choice

Q1. 
Missing Numbers Problem Statement
You are provided with an array called ARR, consisting of distinct positive integers. Your task is to identify all the numbers that fall within the range of the smallest a...read more
Ans. 
Identify missing numbers within the range of smallest and largest elements in an array.
• Find the smallest and largest elements in the array.

• Generate a list of numbers within the range of smallest and largest elements.

• Remove the numbers that are present in the array to get the missing numbers.

• Sort and return the missing numbers.
Answered by AI
Add your answer
Q2. 
Find Maximum Element Between Two Nodes in a BST
Given a Binary Search Tree (BST) and two integers, NODE1 and NODE2, determine the maximum element found in the path between NODE1 and NODE2.
Explanation:
...read more
Ans. 
Find the maximum element between two nodes in a Binary Search Tree (BST) path.
• Traverse the BST to find the path between NODE1 and NODE2.

• Keep track of the maximum element encountered in the path.

• Return the maximum element found, or -1 if NODE1 or NODE2 are not in the BST or no elements exist between them.
Answered by AI
Add your answer
Q3. 
String Compression Problem Statement
Implement a program that performs basic string compression. When a character is consecutively repeated more than once, replace the consecutive duplicates with the coun...read more
Ans. 
Implement a program to compress a string by replacing consecutive duplicates with the count of repetitions.
• Iterate through the string and keep track of consecutive characters and their counts.

• Replace consecutive duplicates with the count of repetitions.

• Ensure the count of repetitions is ≤ 9.

• Return the compressed string.
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
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