KodNest Software Developer Intern Interview Questions and Answers

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
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 keep track of the longest increasing subsequence ending at each element.

• 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 ar...read more
Answered by AI
Add your answer
Q2. 
Digits Decoding Problem
Ninja has a string of characters from 'A' to 'Z', encoded using their numeric values (A=1, B=2, ..., Z=26). The encoded string is given as a sequence of digits (SEQ). The task is t...read more
Ans. 
The task is to determine the number of possible ways to decode a sequence of digits back into a string of characters from 'A' to 'Z'.
• Use dynamic programming to keep track of the number of ways to decode the sequence at each position.

• Consider different cases when decoding the sequence, such as single digit decoding and double digit decoding.

• Handle edge cases like '0' and '00' appropriately.

• Return the final count modulo
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Leaves at Same Level Problem Statement
Given a binary tree with 'N' nodes, determine if all the leaf nodes are situated at the same level. Return true if all the leaf nodes are at the same level, otherwis...read more
Ans. 
Check if all leaf nodes in a binary tree are at the same level.
• Traverse the binary tree and keep track of the level of each leaf node.

• Compare the levels of all leaf nodes at the end to determine if they are at the same level.

• Use a queue for level order traversal of the binary tree.
Answered by AI
Add your answer
Q2. 
Maximum Non-Adjacent Subsequence Sum
Given an array of integers, determine the maximum sum of a subsequence without choosing adjacent elements in the original array.
Input:
The first line consists of an...read more
Ans. 
Find the maximum sum of a subsequence without choosing adjacent elements in an array.
• Use dynamic programming to keep track of the maximum sum of non-adjacent elements at each index.

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

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
• Use a combination of hashmap and doubly linked list to implement the LRU cache.

• Keep track of the least recently used item and update it accordingly when inserting new items.

• Ensure to handle the capacity constraint by evicting the least recently used item when the cache is full.

• Implement get(key) and put...read more
Answered by AI
Add your answer
Q2. What is the difference between Mutex and Semaphores?
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 can be locked by only one thread 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.

• Mutex is simpler ...read more
Answered by AI
Add your answer
Q3. Given the employee and department tables, how would you find the number of employees in each department? (This question focuses on SQL Joins.)
Ans. 
Use SQL Joins to find the number of employees in each department.
• Use a JOIN statement to combine the employee and department tables based on the department ID.

• Group the results by department ID and use COUNT() function to find the number of employees in each department.

• Example: SELECT department.department_id, COUNT(employee.employee_id) AS num_employees FROM department JOIN employee ON department.department_id = emplo...read more
Answered by AI
Add your answer

Round duration - 75 Minutes
Round difficulty - Medium

Timing was 10AM. Environment was quite good.

Q1. 
GCD Sum Problem Statement
Given an integer 'N', the task is to find the sum of the greatest common divisor (GCD) of all pairs (i, j) such that 1 <= i < j <= N.
Input:
T (the number of test case...read more
Add your answer
Q2. 
Consecutive Elements
Given an array arr of N non-negative integers, determine whether the array consists of consecutive numbers. Return true if they do, and false otherwise.
Input:
The first line of inp...read more
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

Timing was 10AM. Environment was quite good.

Q1. 
GCD Sum Problem Statement
Given an integer 'N', the task is to find the sum of the greatest common divisor (GCD) of all pairs (i, j) such that 1 <= i < j <= N.
Input:
T (the number of test case...read more
Ans. 
Calculate the sum of GCD of all pairs of numbers from 1 to N.
• Iterate through all pairs of numbers from 1 to N and calculate GCD

• Add all the calculated GCDs to get the final sum

• Optimize the GCD calculation using Euclidean algorithm
Answered by AI
Add your answer
Q2. 
Consecutive Elements
Given an array arr of N non-negative integers, determine whether the array consists of consecutive numbers. Return true if they do, and false otherwise.
Input:
The first line of inp...read more
Ans. 
Check if an array of integers consists of consecutive numbers.
• Iterate through the array and check if the absolute difference between consecutive elements is 1.

• Sort the array and check if the elements are consecutive.

• Use a set to store unique elements and check if the size of the set matches the length of the array.
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Easy

Timing was 10AM. Environment was quite good.

Q1. 
GCD Sum Problem Statement
Given an integer 'N', the task is to find the sum of the greatest common divisor (GCD) of all pairs (i, j) such that 1 <= i < j <= N.
Input:
T (the number of test case...read more
Ans. 
Calculate the sum of GCD of all pairs of numbers from 1 to N.
• Iterate through all pairs of numbers from 1 to N and calculate GCD

• Sum up all the calculated GCDs to get the final result

• Optimize the GCD calculation using Euclidean algorithm
Answered by AI
Add your answer
Q2. 
Consecutive Elements
Given an array arr of N non-negative integers, determine whether the array consists of consecutive numbers. Return true if they do, and false otherwise.
Input:
The first line of inp...read more
Ans. 
Check if an array of integers consists of consecutive numbers.
• Iterate through the array and check if the absolute difference between consecutive elements is 1.

• Sort the array and check if the elements are consecutive.

• Use a set to store the elements and check if the size of the set is equal to the length of the array.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

Q1. 
Cycle Detection in a Directed Graph
Given a directed graph, you need to determine whether or not the graph contains a cycle.
Your function should return true if there is at least one cycle in the graph; ...read more
Ans. 
Detect cycles in a directed graph and return true if a cycle exists, false otherwise.
• Use Depth First Search (DFS) to detect cycles in the graph.

• Maintain a visited array to keep track of visited vertices and a recursion stack to keep track of vertices in the current DFS traversal.

• If a vertex is visited and is present in the recursion stack, then a cycle exists.

• Example: For the input graph with vertices 0, 1, 2 and edges...read more
Answered by AI
Add your answer
Q2. 
Next Permutation Problem Statement
Given a permutation of ‘N’ integers, rearrange them to generate the lexicographically next greater permutation. A sequence is a permutation if it contains all integers f...read more
Ans. 
The problem involves rearranging a permutation of integers to generate the lexicographically next greater permutation.
• Understand the concept of lexicographically next greater permutation.

• Implement a function to find the next greater permutation.

• Handle cases where no greater permutation exists by returning the smallest permutation.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

Q1. 
Validate BST Problem Statement
Given a binary tree with N nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true; otherwise, return false.
A binary search tree (BST)...read more
Ans. 
Validate if a binary tree is a Binary Search Tree (BST) or not.
• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Recursively check if both the left and right subtrees are also binary search trees.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Hard

Timing was 11 am. Platform was quite well.

Q1. 
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.

• Recursively try moving in all directions (up, down, left, right) until reaching the destination.

• Add the path to the result list when the destination is reached.

• Sort the result list alphabetically before returning.
Answered by AI
Add your answer
Q2. 
Minimum Cost to Destination
You are given an NxM matrix consisting of '0's and '1's. A '1' signifies that the cell is accessible, whereas a '0' indicates that the cell is blocked. Your task is to compute ...read more
Ans. 
Find the minimum cost to reach a destination in a matrix with specified rules.
• Use BFS traversal to explore all possible paths from the starting point to the destination.

• Keep track of the cost incurred at each cell and update it accordingly.

• Return the minimum cost to reach the destination or -1 if unreachable.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

The test was scheduled at 2:30 PM, IST. The test was conducted online, due to the ongoing pandemic situation. Webcam was required to be switched on during the complete duration of the test. I had solved 2/2 coding questions with all test cases successfully passing. Out of the 10 MCQ questions, I had done 6. Around 90 students sat for the online coding round, 19 were shortlisted for the interview. Those who had solved both coding questions were called for interview.

Q1. 
Candies Distribution Problem Statement
Prateek is a kindergarten teacher with a mission to distribute candies to students based on their performance. Each student must get at least one candy, and if two s...read more
Ans. 
The task is to distribute candies to students based on their performance while minimizing the total candies distributed.
• Iterate through the array of student ratings to determine the minimum number of candies required.

• Assign each student at least one candy.

• Adjust the number of candies based on the ratings of adjacent students to minimize the total candies distributed.

• Example: For ratings [5, 8, 1, 5, 9, 4], the optimal ...read more
Answered by AI
Add your answer
Q2. 
Problem Statement: Minimum Cost to Buy Ninja Blades
Ninja Yuki wants to purchase ninja blades at the Spring Fair in his village. Initially, he has 0 blades, and his goal is to buy 'N' blades. The merchant...read more
Ans. 
Calculate the minimum cost to acquire a specific number of ninja blades using a given pricing mechanism.
• Iterate through each test case to determine the minimum cost needed to acquire the desired number of blades.

• Consider the cost of adding 1 blade versus doubling the current number of blades to reach the target quantity.

• Keep track of the total cost as blades are acquired based on the pricing mechanism.

• Return the minimu
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This was a pure DSA based round. Two questions were asked in this round. The interviewer was quite good, and helped in between.

Q1. 
First Unique Character in a Stream Problem Statement
Given a string A consisting of lowercase English letters, determine the first non-repeating character at each point in the stream of characters.
Examp...read more
Ans. 
Given a string of lowercase English letters, find the first non-repeating character at each point in the stream.
• Iterate through the characters in the string and maintain a count of each character.

• Use a queue to keep track of the order of characters encountered.

• For each character, check if it is the first non-repeating character by looking at its count in the map.

• If a character's count is 1, it is the first non-repeatin...read more
Answered by AI
Add your answer
Q2. 
Boolean Matrix Transformation Challenge
Given a 2-dimensional boolean matrix mat of size N x M, your task is to modify the matrix such that if any element is 1, set its entire row and column to 1. Specifi...read more
Ans. 
Modify a boolean matrix such that if any element is 1, set its entire row and column to 1 in-place.
• Iterate through the matrix to find elements with value 1.

• Use additional arrays to keep track of rows and columns to be modified.

• Update the matrix in-place based on the identified rows and columns.
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

This round was also again focused on DSA. Two interviewers were present. This round was very extensive and everything was asked in depth as well as they asked to write the codes as well for all the questions. I was also asked to explain my projects, they were based on ML. Many aspects of OOPs, POP, memory allocation was asked as well.

Q1. 
Maximum Sum of Index-Multiplied Rotations
Given an array ARR of size N, determine the maximum sum of i * ARR[i] possible through any number of rotations. Both left and right rotations are allowed, and can...read more
Ans. 
Find maximum sum of i * ARR[i] possible through any number of rotations in an array.
• Calculate the sum of i * ARR[i] for each rotation and find the maximum sum.

• Consider both left and right rotations.

• Optimize the solution to avoid redundant calculations.

• Handle edge cases like empty array or single element array.
Answered by AI
Add your answer
Q2. 
Averages of Levels in Binary Tree Problem Statement
Given an arbitrary binary tree consisting of 'N' nodes numbered from 1 to 'N'. Each node is associated with a positive integer value. Your task is to ca...read more
Ans. 
Calculate the average of node values at each level in a binary tree.
• Traverse the binary tree level by level using BFS

• Calculate the sum of node values at each level and divide by the number of nodes at that level

• Print the floor value of the average for each level
Answered by AI
Add your answer