2000+ Interview Questions and Answers

Q1. Maximum Subarray Sum

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would ...read more

Q2. Minimum Number of Platform Needed

You are given the arrival and departure times of N trains at a railway station in a day. You need to find the minimum of platforms required for the railway station such that no ...read more

Q6. Permutation in String

You have been given two strings ‘str1’ and ‘str2’ of length N and M respectively. Your task is to check whether string ‘str2’ contains one of the permutations of string ‘str1’ as its substr...read more

Q7. Fenwick Tree

You are given an array/list 'ARR' of ‘N’ integers, and ‘Q’ queries. Each query can be of two types:

Given 2 integers ‘L’,’R’ ( L>=0 and R

Given an index ‘i’ update the value of ARR[i] to a given int...read more

Q8. Fish Eater

There is a river which flows in one direction. One day, the river has 'N' number of fishes. You are given an array 'FISHES' of integers representing the size of 'N' fishes. The fishes are present in t...read more

Q9. Count Special Nodes in Generic Tree

Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a p...read more

Q10. Delete alternate nodes

Given a Singly Linked List of integers, delete all the alternate nodes in the list.

Example:

List: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null Alternate nodes will be: 20, 40, and 60. Hence a...read more

Q11. Longest Common Subsequence

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’...read more

Q12. Find Pair With Smallest Difference

Given two unsorted arrays of non-negative integers, 'arr1' and 'arr2' of size 'N' and 'M', respectively. Your task is to find the pair of elements (one from each array), such t...read more

Q14. Fire in the cells.

You are given a matrix 'MAT' of size ‘N’ * ‘M’, where ‘N’ is the number of rows and ‘M’ is the number of columns. Value ‘0’ in a cell represents that the cell is set on fire initially, (at tim...read more

Q15. Maximum sum of non-adjacent elements

You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the given...read more

Q16. Two Sum

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given inde...read more

Q18. Maximum Path Sum Between Two Leaves

You are given a non-empty binary tree where each node has a non-negative integer value. Return the maximum possible sum of path between any two leaves of the given tree.

The p...read more

Q19. Car Pooling

You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.

Now, you are given ‘N’ number ...read more

Q20. Best Time To Buy and Sell Stock

You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the...read more

Q21. Search for integers with given difference and at given distance

You are given an array consisting of 'N' non-negative integers, and two non-negative integers 'K' and 'M', your task is to find a pair of indices(s...read more

Q22. Sum of minimum and maximum elements of all subarrays of size “K”

You are given an array consisting of N integers, and an integer, K. Your task is to determine the total sum of the minimum element and the maximum...read more

Q23. Longest Increasing Subsequence

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increa...read more

Q24. Count Inversions

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array...read more

Q25. Shortest Path in a Binary Matrix

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix....read more

Q26. String Transformation

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from ST...read more

Q27. Count derangements

A Derangement is a permutation of ‘N’ elements, such that no element appears in its original position. For example, an instance of derangement of {0, 1, 2, 3} is {2, 3, 1, 0}, because 2 prese...read more

Q28. Mike and Mobile

Mike is a little boy who loves solving math problems. One day he was playing with his mom’s mobile. The mobile keypad contains 12 buttons { 10 digits(0-9) and 2 characters(‘*’ and ‘#’) }. Mike w...read more

Q29. Selling Stock

You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and sel...read more

Q30. Sort 0 1 2

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' ...read more

Q32. Rotting Oranges

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

...read more

Q33. Spiral Matrix

You are given a 2-D array 'MATRIX' of dimensions N x M, of integers. You need to return the spiral path of the matrix.

Example Of Spiral Path:

Input Format:

The first line contains an integer 'T' ...read more

Q34. Detect Cycle In A Directed Graph

You are given a directed graph having ‘N’ nodes. A matrix ‘EDGES’ of size M x 2 is given which represents the ‘M’ edges such that there is an edge directed from node EDGES[i][0] ...read more

Q35. Kth Smallest and Largest Element of Array

You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed...read more

Q36. Unique Paths

You are present at point ‘A’ which is the top-left cell of an M X N matrix, your destination is point ‘B’, which is the bottom-right cell of the same matrix. Your task is to find the total number of...read more

Q37. Covid Vaccination

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase v...read more

Q38. Find Pair Sum equal to K.

You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.

Note:

Given ...read more

Q39. Maximum In Sliding Windows Of Size K

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ nu...read more

Q40. Rotten oranges problem

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh ora...read more

Q41. Shortest Path In A Binary Maze

Given a maze in the form of a binary rectangular matrix of size M*N, where each element can either be 0 or 1, the task is to find the length of the shortest path in a maze from a g...read more

Q42. Maximum 0-1 Distance

You are given an N*M binary matrix, considering for every 0-cell(cell with value = 0) the distance from this cell to its nearest 1-cell(cell with value = 1) is 'di', you need to find the max...read more

Q43. Special Binary Tree.

You are given an arbitrary binary tree. A binary tree is called special if every node of this tree has either zero or two children. You have to determine if the given binary tree is special ...read more

Q44. First Missing Positive

You are given an array 'ARR' of integers of length N. Your task is to find the first missing positive integer in linear time and constant space. In other words, find the lowest positive in...read more

Q45. Longest Decreasing Subsequence

You are given an array/list ARR consisting of N integers. Your task is to find the length of the longest decreasing subsequence.

A subsequence is a sequence of numbers obtained by ...read more

Q46. Maximum Consecutive Ones

Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this ...read more

Q47. Connect N Ropes With Minimum Cost

You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to conn...read more

Q48. String Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters.

Palindrome

A palindrome is a word, number, phrase, or other sequences of characters which read the sam...read more

Q49. Longest Substring Without Repeating Characters

Given a string 'S' of length 'L', return the length of the longest substring without repeating characters.

Example:

Suppose given input is "abacb", then the length ...read more

Q50. Longest Palindromic Substring

You are given a string (STR) of length N.

Your task is to find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the...read more

Q51. Trapping Rainwater

You have been given a long type array/list 'ARR' of size 'N'. It represents an elevation map wherein 'ARR[i]' denotes the elevation of the 'ith' bar. Print the total amount of rainwater that c...read more

Q52. First and Last Position of an Element In Sorted Array

You have been given a sorted array/list ARR consisting of ‘N’ elements. You are also given an integer ‘K’.

Now, your task is to find the first and last occur...read more

Q53. Sum of Big integers

You have been given two integers ‘NUM1’ and ‘NUM2’ as a string. Your task is to print the sum of both the numbers.

Input Format:

The first line contains a single integer ‘T’ representing the ...read more

Q54. Longest Common Prefix

You are given an array ‘ARR’ consisting of ‘N’ strings. Your task is to find the longest common prefix among all these strings. If there is no common prefix, you have to return an empty str...read more

Q55. Merge Two Sorted Linked Lists

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse...read more

Q56. Strongly Connected Components (Tarjan’s Algorithm)

You are given an unweighted directed graph of 'V' vertices and 'E' edges. Your task is to print all the strongly connected components (SCCs) present in the grap...read more

Q57. Design a stack that supports getMin() in O(1) time and O(1) extra space

Implement a SpecialStack Data Structure that supports getMin() in O(1) time and O(1) extra space along with push(), pop(), top(), isEmpty()...read more

Q58. Check if the Word is present in Sentence or not

You have been given a sentence ‘S’ in the form of a string and a word ‘W’, you need to find whether the word is present in the given sentence or not. The word must...read more

Q59. LRU Cache Implementation

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, o...read more

Q60. Container With Most Water

Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at point 'i'. ...read more

Q61. Anagram Pairs

Pre-requisites: Anagrams are defined as words or names that can be formed by rearranging letters of another word. Such as "spar" can be formed by rearranging letters of "rasp". Hence, "spar" and "...read more

Q62. Minimum Window Subsequence

You are given two strings ‘S’ and ‘T’. Your task is to find the minimum (Contiguous) substring ‘W’ of ‘S’, such that ‘T’ is a subsequence of ‘W’

A subsequence is a sequence that can be...read more

Q63. Evaluation of postfix expression

An expression is called the postfix expression if the operator appears in the expression after the operands.

Example :

Infix expression: A + B * C - D Postfix expression: A B + C...read more

Q64. Dijkstra's shortest path

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between no...read more

Q65. Number of islands

Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 islands

Example:

Input : mat[][] = {{1, 1, 0, 0, 0},

{0,...read more

Q67. Minimum Path Sum

Ninjaland is a country in the shape of a 2-Dimensional grid 'GRID', with 'N' rows and 'M' columns. Each point in the grid has some cost associated with it.

Find a path from top left i.e. (0, 0) ...read more

Q68. Ways To Make Coin Change

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change fo...read more

Q69. Minimum Jumps

Bob lives with his wife in a city named Berland. Bob is a good husband, so he goes out with his wife every Friday to ‘Arcade’ mall.

‘Arcade’ is a very famous mall in Berland. It has a very unique t...read more

Q70. Count Frequency

You are given a string 'S' of length 'N', you need to find the frequency of each of the characters from ‘a’ to ‘z’ in the given string.

Example :

Given 'S' : abcdg Then output will be : 1 1 1 1 0...read more

Q71. Weighted Job Scheduling

You are given 'N' jobs with their start time 'Start', end time 'End' and profit 'Profit'. You need to tell the maximum profit you can obtain by performing these jobs such that no two jobs...read more

Q72. Number with maximum probability

One day Ninja Misha and Ninja Andrew (students of the Ultimate Ninja Ankush) were playing a very simple game. First, each player chooses an integer in the range from 1 to ‘N’. Let...read more

Q73. Subarray With Given Sum

Given an array ARR of N integers and an integer S. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray eq...read more

Q74. Pair Sum

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair shou...read more

Q75. Frequency In A Sorted Array

You are given a sorted array 'ARR' and a number 'X'. Your task is to count the number of occurrences of 'X' in 'ARR'.

Note :

1. If 'X' is not found in the array, return 0. 2. The give...read more

Q76. Boundary Traversal

You have been given a binary tree of integers. Your task is to print the boundary nodes of this binary tree in Anti-Clockwise direction starting from the root node.

NOTE:

The boundary nodes of...read more

Q77. Binary strings with no consecutive 1s

You have been given an integer K.

Your task is to generate all binary strings of length K such that there are no consecutive 1s in the string. This means that the binary str...read more

Q78. Clone a linked List having random pointers

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node ...read more

Q79. Element that appears once

You are given an arbitrary array ‘arr’ consisting of N non-negative integers, where every element appears thrice except one. You need to find the element that appears only once.

Input F...read more

Q80. Maximum Of All Subarrays Of Size k

You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.

For Example:

If A = [3, 2, 3], and K ...read more

Q82. Right View

You have been given a Binary Tree of integers.

Your task is to print the Right view of it.

The right view of a Binary Tree is a set of nodes visible when the tree is viewed from the Right side and the...read more

Q83. Smallest Window

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “b...read more

Q84. Maximum Subarray Sum

You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

A subarray is a ...read more

Q86. Matrix Median

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers where every row is sorted in non-decreasing order. Your task is to find the overall median of the matrix i.e if all ...read more

Q87. Count triplets in a sorted doubly linked list whose sum is equal to a given value x

You have been given an integer ‘X’ and a non-decreasing sorted doubly linked list with distinct nodes.

Your task is to return t...read more

Q88. The Celebrity Problem

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at...read more

Q89. Flip Bits

You are given an array of integers ARR[] of size N consisting of zeros and ones. You have to select a subset and flip bits of that subset. You have to return the count of maximum one’s that you can obt...read more

Q90. Next Greater Element

You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the Next Greater Element(NGE) for every element.

The Next Greater Element for an element ‘...read more

Q91. Find k’th character of decrypted string

Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2” and k=4...read more

Q92. Find Row K

Given a square binary matrix ‘mat[n][n]’, find ‘K’ such that all elements in the Kth row are ‘0’ and all elements in the Kth column are ‘1’. The value of mat[k][k] can be anything (either ‘0’ or ‘1’)....read more

Q93. Closest Sum

Given an array 'ARR'' of 'N' integers and an integer 'target', your task is to find three integers in 'ARR' such that the sum is closest to the target.

Note

In the case of two closest sums, print the...read more

Q94. Rearrange String

You are given a string of lowercase characters. Your task is to rearrange (reorder) the string in such a way that no two adjacent characters are the same.

You have to return the rearranged strin...read more

Q95. Most Frequent Word

You are given two strings 'A' and 'B' of words. Your task is to find out the most frequent and lexicographically smallest word in string 'A', which is not present in string 'B'. If no such wor...read more

Q96. Minimum Travel Cost

Ninjaland is a country having 'N' states numbered from 1 to 'N'. These 'N' states are connected by 'M' bidirectional roads. Each road connects to different states and has some cost to travel ...read more

Q97. K Most Frequent Words

You have been given an array/list 'WORDS' of 'N' non-empty words, and an integer 'K'. Your task is to return the 'K' most frequent words sorted by their frequency from highest to lowest.

N...read more

Q98. Path In A Tree

You are given a binary tree with ‘N’ number of nodes and a node ‘X’. Your task is to print the path from the root node to the given node ‘X’.

A binary tree is a hierarchical data structure in whic...read more

Q99. Square root (decimal)

You have been given two integers 'N' and 'D', Your task is to find the square root of the number 'N' with precision up to 'D' decimal places i.e. the difference between your answer and the...read more