# CodeNation Interview Questions  Directi Interview Questions

## Array Questions CodeNation

Question 1. Count all subsequences having product less than K The problem “Count all subsequences having product less than K” states that you are given an array of integers. Now find the number of subsequences that have a product less than a given input K. Example   a[] = {1, 2, 3, 4, 5} k = 8 Number of subsequences less ...

Question 2. Range Queries for Longest Correct Bracket Subsequence You are given a sequence of some brackets subsequence, in other words, you are given brackets like ‘(’ and ‘)’ and you are given a query range as a starting point and ending point. The problem “Range Queries for Longest Correct Bracket Subsequence” asks to find out the maximum length ...

Question 3. Longest Bitonic Subsequence Suppose you have an array of integers, the problem statement asks to find out the longest bitonic subsequence. The bitonic sequence of an array is considered as the sequence which first increases and then decreases. Example   arr[] = {1,4,2,76,43,78,54,32,1,56,23} 7 Explanation 1 ⇒ 4 ⇒ 76 ⇒ 78 ⇒ 54 ...

Question 4. Difference Array | Range update query in O(1) You are given an integer array and two types of queries, one is to add a given number in a range and the other to print the whole array. The problem “Difference Array | Range update query in O(1)” requires us to perform the range updates in O(1). Example   arr[] ...

Question 5. Painting Fence Algorithm Problem Statement   The “Painting Fence Algorithm” states that you are given a fence having some posts (some wooden pieces or some other pieces) and some colors. Find out the number of ways to paint the fence such that at most only 2 adjacent fences have the same color. Since this ...

Question 6. Constant time range add operation on an array You have given an integer array and initially, it was initialized as 0 and also given a range. The task is to add the given number in the range of the array and print the resultant array. Example   arr[] = {0, 0, 0, 0, 0} Query: {(0, 2, 50), (3, ...

Question 7. Number of elements less than or equal to a given number in a given subarray Problem Statement   The problem “Number of elements less than or equal to a given number in a given subarray” states that you are given an integer array and q number of queries. There will be two types of queries à queryUpdate(i, v): There will be two integers i and v, ...

Question 8. K maximum sums of overlapping contiguous sub-arrays Problem Statement   The problem “K maximum sums of overlapping contiguous sub-arrays” states that you are given an array of integers. Find the maximum sum of k-subarrays such that their sum is maximum. These k-subarrays might be overlapping. So, we need to find k-subarrays such that their sum is maximum among ...

Question 9. Maximum Subarray Sum Excluding Certain Elements Problem Statement   We are given an array, and we need to find maximum subarray sum excluding certain elements. That is, we need to find the max sum of subarray such that the subarray we are considering does not contain the elements which are told to be excluded. Example of maximum ...

Question 10. Largest rectangular sub-matrix whose sum is 0 Problem Statement   Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with ...

Question 11. Matrix Chain Multiplication In the matrix chain multiplication II problem, we have given the dimensions of matrices, find the order of their multiplication such that the number of operations involved in multiplication of all the matrices is minimized. Consider you have 3 matrices A, B, C of sizes a x b, b x ...

Question 12. Maximum Sum Increasing Subsequence Problem Statement   In the “Maximum Sum Increasing Subsequence” problem we have given an array. Find the sum of the maximum subsequence of the given array, that is the integers in the subsequence are in sorted order. A subsequence is a part of an array which is a sequence that is ...

## String Questions CodeNation

Question 13. Minimum insertions to form a palindrome with permutations allowed The problem “Minimum insertions to form a palindrome with permutations allowed” states that you are given a String with all letters in lowercase. The problem statement asks to find out the minimum insertion of a character to a string that it can become Palindrome. The position of characters can be ...

Question 14. LCS (Longest Common Subsequence) of three strings The problem “LCS (Longest Common Subsequence) of three strings” states that you are given 3 strings. Find out the longest common subsequence of these 3 strings. LCS is the string that is common among the 3 strings and is made of characters having the same order in all of the ...

Question 15. Maximum weight transformation of a given string Problem Statement   The maximum weight transformation of a given string problem states that given a string consisting only of two characters ‘A’ and ‘B’. We have an operation where we can transform string to another string by toggling any character. Thus many transformations are possible. Out of all the possible ...

Question 16. Backspace String Compare In the backspace string compare problem we have given two Strings S and T, check if they are equal or not. Note that the strings contain ‘#’ which means backspace character. Examples   Input S = “ab#c” T = “ad#c” Output true (as both S and T converts to “ac”) Input ...

Question 17. Check length of a String is Equal to the Number Appended at its Last Problem Statement   In the “Check length of a string is Equal to the Number Appended at its Last” problem we have given a string that is appended with a number at last. Write a program that checks whether the length of the string excluding the number is the same as ...

## Tree Questions CodeNation

Question 18. Number of elements less than or equal to a given number in a given subarray Problem Statement   The problem “Number of elements less than or equal to a given number in a given subarray” states that you are given an integer array and q number of queries. There will be two types of queries à queryUpdate(i, v): There will be two integers i and v, ...

Question 19. Red-Black Tree Introduction Red Black Tree is a self-balancing binary tree. In this tree, every node is either a red node or a black node. In this Red-black Tree Introduction, we will try to cover all of its basic properties. Properties of Red-Black Tree   Every node is represented as either red or black. ...

Question 20. Number of siblings of a given Node in n-ary Tree Problem Statement   The problem “Number of siblings of a given Node in n-ary Tree” states that you are given an n-ary Tree and a target node. Find the number of siblings of the target node. Assume that node is always present in the tree and the first node is the ...

Question 21. Segment Tree If we have performing addition on a given range of array whose element values updated any time. Then in that type of problem, we handle using a segment tree structure. Given an array a[] with n elements and you have to answer multiple queries, each of the queries is one ...

## Stack Questions CodeNation

Question 22. Range Queries for Longest Correct Bracket Subsequence You are given a sequence of some brackets subsequence, in other words, you are given brackets like ‘(’ and ‘)’ and you are given a query range as a starting point and ending point. The problem “Range Queries for Longest Correct Bracket Subsequence” asks to find out the maximum length ...

Question 23. Backspace String Compare In the backspace string compare problem we have given two Strings S and T, check if they are equal or not. Note that the strings contain ‘#’ which means backspace character. Examples   Input S = “ab#c” T = “ad#c” Output true (as both S and T converts to “ac”) Input ...

## Queue Questions CodeNation

Question 24. Number of siblings of a given Node in n-ary Tree Problem Statement   The problem “Number of siblings of a given Node in n-ary Tree” states that you are given an n-ary Tree and a target node. Find the number of siblings of the target node. Assume that node is always present in the tree and the first node is the ...

Question 25. Priority Queue A priority queue is a type of data structure which is similar to a regular queue but has a priority associated with each of its element. Higher the priority earlier the element will be served. In some cases, there are two elements with the same priority then, the element enqueued ...

## Matrix Questions CodeNation

Question 26. Find maximum length Snake sequence The problem “Find maximum length Snake sequence” states that we are provided with a grid containing integers. The task is to find a snake sequence with the maximum length. A sequence having adjacent numbers in the grid with an absolute difference of 1, is known as a Snake sequence. Adjacent ...

Question 27. Number of palindromic paths in a matrix Problem Statement   We are given a two-dimensional matrix containing lowercase English alphabets, we need to count the number of palindromic paths in it. A palindromic path is nothing but a path following palindromic property. A word which when reversed remains the same as the initial word is said to be ...

Question 28. Largest rectangular sub-matrix whose sum is 0 Problem Statement   Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with ...

Question 29. Matrix Chain Multiplication In the matrix chain multiplication II problem, we have given the dimensions of matrices, find the order of their multiplication such that the number of operations involved in multiplication of all the matrices is minimized. Consider you have 3 matrices A, B, C of sizes a x b, b x ...

## Other Questions CodeNation

Question 30. Sequences of given length where every element is more than or equal to twice of previous The problem “Sequences of given length where every element is more than or equal to twice of previous” provides us with two integers m and n. Here m is the largest number that can exist in the sequence and n is the number of elements that must be present in the ...

Question 31. Count ways to reach the nth stair using step 1, 2 or 3 The problem “Count ways to reach the nth stair using step 1, 2, or 3” states that you are standing on the ground. Now you need to reach the end of the staircase. So how many ways are there to reach the end if you can jump only 1, 2, ...

Question 32. Maximum path sum in a triangle Problem Statement   The problem “Maximum path sum in a triangle” states that you are given some integers. These integers are arranged in the form of a triangle. You are starting from the top of the triangle and need to reach the bottom row. For doing this, you move to the ...

Question 33. The Painter’s Partition Problem Problem Statement   The Painter’s Partition problem states that we have some fences and we have some painters. We want to minimize the time of painting all the fences by painters. There is a bound on the order of painting the fences by painters. Consider we have n painters, then painter ...

Question 34. A Space Optimized DP solution for 0-1 Knapsack Problem Problem Statement   We are given a knapsack which can hold some weight, we need to pick some of the items out of given items with some value. The items should be picked such that the value of the knapsack ( total value of picked up items ) should be maximized. ...

Question 35. Longest Increasing Subsequence We are provided with an array of integers that is unsorted and we have to find the longest increasing subsequence. The subsequence need not be consecutive The subsequence shall be increasing Let’s understand that better by a few examples. Example   Input [9, 2, 5, 3, 7, 10, 8] Output Please ...