300+ R-pac Interview Questions and Answers

Q1. Minimum Time in Wormhole Network

Determine the minimum time required to travel from a starting point to a destination point in a two-dimensional coordinate system, considering both direct movement and the use o...read more

Q2. Remove Consecutive Duplicates Problem Statement

For a given string str, remove all the consecutive duplicate characters.

Example:

Input:

Input String: "aaaa"

Output:

Expected Output: "a"

Input:

Input String: "a...read more

Q3. Find The Repeating And Missing Number Problem Statement

You are provided with an array nums which contains the first N positive integers. In this array, one integer appears twice, and one integer is missing. Yo...read more

Q4. Bursting Balloons Problem

Given an array ARR of size N, where each element represents the height of a balloon. The task is to destroy all balloons by shooting arrows from left to right. When an arrow hits a bal...read more

Q5. LCA of Binary Tree Problem Statement

You are given a binary tree consisting of distinct integers and two nodes, X and Y. Your task is to find and return the Lowest Common Ancestor (LCA) of these two nodes.

The ...read more

Q6. Reverse Alternate K Nodes Problem Statement

You are given a singly linked list of integers along with a positive integer 'K'. The task is to modify the linked list by reversing every alternate 'K' nodes of the ...read more

Q7. 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 subse...read more

Q8. Trapping Rain Water Problem Statement

You are given a long type array/list ARR of size N, representing an elevation map. The value ARR[i] denotes the elevation of the ith bar. Your task is to determine the tota...read more

Q9. 0-1 Knapsack Problem Statement

You are tasked with determining the maximum profit a thief can earn. The thief is looting a store and can carry a maximum weight 'W' in his knapsack. There are 'N' items, each wit...read more

Q10. Move All Negative Numbers To Beginning

Rearrange a given array 'ARR' with 'N' integers so that all negative numbers appear before all positive numbers.

Follow Up:

Can you solve this in O(1) auxiliary space? 

No...read more

Q11. Count Leaf Nodes in a Binary Tree

Count the number of leaf nodes present in a given binary tree. A binary tree is a data structure where each node has at most two children, known as the left child and the right...read more

Q12. Maximum Gold Collection from Gold Mine

Imagine a gold mine represented by a 2D matrix with dimensions 'N' by 'M', where 'N' is the number of rows and 'M' is the number of columns. Each cell in this matrix conta...read more

Q13. Shortest Path in a Binary Matrix Problem Statement

Given a binary matrix of size N * M where each element is either 0 or 1, find the shortest path from a source cell to a destination cell, consisting only of 1s...read more

Q14. Reverse Linked List Problem Statement

Given a singly linked list of integers, return the head of the reversed linked list.

Example:

Initial linked list: 1 -> 2 -> 3 -> 4 -> NULL
Reversed linked list: 4 -> 3 -> 2...read more

Q15. Power of Two Problem Statement

Determine whether a given integer N is a power of two. Return true if it is, otherwise return false.

Explanation

An integer 'N' is considered a power of two if it can be expressed...read more

Q16. Merge K Sorted Arrays Problem Statement

Given 'K' different arrays that are individually sorted in ascending order, merge all these arrays into a single array that is also sorted in ascending order.

Input

The f...read more

Q17. Gold Mine Problem Statement

You are provided with a gold mine, represented as a 2-dimensional matrix of size N x M with N rows and M columns. Each cell in this matrix contains a positive integer representing th...read more

Q18. Maximum Sum Path from Leaf to Root

Given a binary tree with 'N' nodes, identify the path from a leaf node to the root node that has the maximum sum among all root-to-leaf paths.

Example:

All the possible root t...read more

Q19. Rod Cutting Problem Statement

Given a rod of a certain length, the rod can be divided into different sizes, each with an associated cost. Your task is to determine the maximum cost that can be obtained by cutti...read more

Q20. Quick Sort Problem Statement

You are provided with an array of integers. The task is to sort the array in ascending order using the quick sort algorithm.

Quick sort is a divide-and-conquer algorithm. It involve...read more

Q21. Count Pairs with Given Sum

Given an integer array/list arr and an integer 'Sum', determine the total number of unique pairs in the array whose elements sum up to the given 'Sum'.

Input:

The first line contains ...read more

Q22. Minimum Insertions to Make a Palindrome

Given a string STR of length N composed of lowercase English letters, your task is to determine the minimum number of characters that need to be added to make the string ...read more

Q23. Implement a Stack using Queues

Create a Stack data structure designed specifically to store integer data using two queues.

Explanation:

You need to implement a stack using two internal queues. You can utilize a...read more

Q24. Sum of Squares of First N Natural Numbers Problem Statement

You are tasked with finding the sum of squares of the first N natural numbers for given test cases.

Input:

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

Q25. Triplets with Given Sum Problem

Given an array or list ARR consisting of N integers, your task is to identify all distinct triplets within the array that sum up to a specified number K.

Explanation:

A triplet i...read more

Q26. Spiral Order Traversal of a Binary Tree

Given a binary tree with N nodes, your task is to output the Spiral Order traversal of the binary tree.

Input:

The input consists of a single line containing elements of ...read more

Q27. Longest Substring Without Repeating Characters Problem Statement

Given a string S of length L, determine the length of the longest substring that contains no repeating characters.

Example:

Input:

"abacb"

Output...read more

Q28. Merge Two Sorted Linked Lists Problem Statement

You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.

Input:...read more

Q29. Longest Palindromic Substring Problem Statement

You are provided with a string STR of length N. The task is to find the longest palindromic substring within STR. If there are several palindromic substrings of t...read more

Q30. Binary Tree Diameter Problem Statement

You are given a Binary Tree, and you need to determine the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any ...read more

Q31. Delete a Node from a Linked List

You are provided with a linked list of integers. Your task is to implement a function that deletes a node located at a specified position 'POS'.

Input:

The first line contains a...read more

Q32. Rotate Matrix by 90 Degrees Problem Statement

Given a square matrix 'MATRIX' of non-negative integers, rotate the matrix by 90 degrees in an anti-clockwise direction using only constant extra space.

Input:

The ...read more

Q33. Cousins of a Given Node in a Binary Tree

Given a binary tree with 'N' nodes and a specific node in this tree, you need to determine and return a sorted list of the values of the node's cousins. The cousins shou...read more

Q34. Convert Binary Tree to Mirror Tree

Convert a given binary tree into its mirror tree, where the left and right children of all non-leaf nodes are interchanged.

Input:

An integer ‘T’ denoting the number of test c...read more

Q35. Detect and Remove Loop in Linked List

For a given singly linked list, identify if a loop exists and remove it, adjusting the linked list in place. Return the modified linked list.

Expected Complexity:

Aim for a...read more

Q36. Cycle Detection in Undirected Graph Problem Statement

You are provided with an undirected graph containing 'N' vertices and 'M' edges. The vertices are numbered from 1 to 'N'. Your objective is to determine whe...read more

Q37. Rain Water Trapping Problem Statement

Given an array/list ARR of size N, representing an elevation map where each element ARR[i] denotes the elevation of the i-th bar. Your task is to calculate and print the to...read more

Q39. Game of Stones Problem Statement

Two players, 'Ale' and 'Bob', are playing a game with a pile of stones. Your task is to determine the winner if both play optimally.

Rules of the Game:

1. On each turn, a player...read more

Q41. Cycle Detection in a Singly Linked List

Determine if a given singly linked list of integers forms a cycle or not.

A cycle in a linked list occurs when a node's next points back to a previous node in the list. T...read more

Q42. Shortest Path in a Binary Maze Problem Statement

Given a maze represented as a binary rectangular matrix of size M*N, where each element can either be 0 or 1, determine the length of the shortest path from a gi...read more

Q43. Minimum Insertions to Make a String Palindrome

Determine the minimal number of characters needed to insert into a given string STR to transform it into a palindrome.

Example:

Input:

STR = "abcaa"

Output:

2

Expl...read more

Q44. Minimum Operation Needed to Convert to the Given String

You are given two strings str1 and str2. Determine the minimum number of operations required to transform str1 into str2.

Explanation:

An operation is def...read more

Q45. Count Subarrays with Given XOR Problem Statement

You are given an array of integers ARR and an integer X. Your task is to determine the number of subarrays of ARR whose bitwise XOR is equal to X.

Example:

Input...read more

Q47. 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 conne...read more

Q48. Stack using Two Queues Problem Statement

Develop a Stack Data Structure to store integer values using two Queues internally.

Your stack implementation should provide these public functions:

Explanation:

1. Cons...read more

Q49. Word Search Problem Statement

Given a two-dimensional grid with 'N' rows and 'M' columns consisting of uppercase characters, and a string 'WORD', your task is to determine the number of times the word appears i...read more

Q50. Rotting Oranges Problem Statement

You are given a grid containing oranges where each cell of the grid can contain one of the three integer values:

• 0 - representing an empty cell
• 1 - representing a fresh orange...read more

Q51. Substrings Differ by One Problem Statement

Ninja needs help in a battle against the string man. Given two strings, 'S' and 'T', the task is to find the number of substrings in 'S' that differ from some substrin...read more

Q52. Implement a Stack Using Two Queues

You are tasked with implementing a Stack data structure specifically designed to store integer data using two Queues. Utilize the inbuilt Queue for this purpose.

Function Requ...read more

Q53. Convert a Binary Tree to its Sum Tree

Given a binary tree of integers, convert it to a sum tree where each node is replaced by the sum of the values of its left and right subtrees. Set leaf nodes to zero.

Input...read more

Q54. Largest Number in Binary Tree

You are provided with a Binary Tree consisting of 'N' nodes, where each node holds an integer value. Your task is to determine the largest possible number that can be formed by con...read more

Q55. Maximum Product Subarray Problem Statement

Given an array of integers, determine the contiguous subarray that produces the maximum product of its elements.

Explanation:

A subarray can be derived from the origin...read more

Q56. Delete a Given Node from Doubly Linked List

Ninja is learning about doubly linked lists and wants to remove a specified element from the list. Can you assist Ninja in doing this and returning the modified linke...read more

Q57. Topological Sort Problem Statement

Given a Directed Acyclic Graph (DAG) consisting of V vertices and E edges, your task is to find any topological sorting of this DAG. You need to return an array of size V repr...read more

Q58. Reach the Destination Problem Statement

You are given a source point (sx, sy) and a destination point (dx, dy). Determine if it is possible to reach the destination point using only the following valid moves:

...read more

Q59. Triplets with Given Sum

Given an array ARR consisting of N integers, find all distinct triplets in the array that add up to a given number K.

Example:

Input:

T = 2
N = 5
ARR = [1, 2, 3, 4, 5]
K = 9

N = 4
ARR = [0, ...read more

Q60. Maximum Number from Linked List Problem Statement

Given a linked list where each node contains a single digit, your task is to construct the largest possible number using these digits.

Objective:

Print the maxi...read more

Q61. Sum of Digits Problem Statement

Given an integer 'N', continue summing its digits until the result is a single-digit number. Your task is to determine the final value of 'N' after applying this operation iterat...read more

Q62. Maximum Subsequence Sum Without Three Consecutive Elements

Given an array A of length N consisting of positive integers, your task is to determine the maximum subsequence sum where no three consecutive elements...read more

Q63. 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 algorit...read more

Q64. Find Shortest Path in a Tree

Given a tree with 'N' nodes and 'N - 1' distinct edges, along with two nodes 'N1' and 'N2', find and print the shortest path between 'N1' and 'N2'.

Explanation:

A tree is a nonlinea...read more

Q65. Reverse the String Problem Statement

You are given a string STR which contains alphabets, numbers, and special characters. Your task is to reverse the string.

Example:

Input:

STR = "abcde"

Output:

"edcba"

Input...read more

Q66. Binary Tree to Doubly Linked List

Transform a given Binary Tree into a Doubly Linked List.

Ensure that the nodes in the Doubly Linked List follow the Inorder Traversal of the Binary Tree.

Input:

The first line ...read more

Q67. Palindrome Linked List Problem Statement

You are provided with a singly linked list of integers. Your task is to determine whether the given singly linked list is a palindrome. Return true if it is a palindrome...read more

Q69. Trie Data Structure Implementation

Design and implement a Trie (prefix tree) to perform the following operations:

• insert(word): Add a string "word" to the Trie.
• search(word): Verify if the string "word" exists...read more

Q70. Minimum Jumps Problem Statement

Bob and his wife are in the famous 'Arcade' mall in the city of Berland. This mall has a unique way of moving between shops using trampolines. Each shop is laid out in a straight...read more

Q72. Doctor Ninja's House Problem Statement

In a network of 'N' cities with 'M' paths connecting them, Doctor Ninja aims to purchase a house in a city 'X' such that it is possible to reach every other city from city...read more

Q73. The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Q74. Circle of Words Problem Statement

Given an array or list of words, determine whether the words can be rearranged to form a circle where the last character of one word matches the first character of the next.

In...read more

Q75. Next Greater Number Problem Statement

Given a string S which represents a number, determine the smallest number strictly greater than the original number composed of the same digits. Each digit's frequency from...read more

Q76. Most Stones Removed with Same Row or Column

On a 2-D plane, there are ‘N’ stones placed at some integer coordinate points. Each coordinate point can have at most one stone. A stone can be removed if it shares t...read more

Q77. M - Coloring Problem Statement

Given an undirected graph with 'N' nodes in the form of an adjacency matrix and an integer 'M', determine if it is possible to color the vertices of the graph using at most 'M' co...read more

Q78. Maximum Sum Rectangle Problem

Given an M x N matrix of integers ARR, your task is to identify the rectangle within the matrix that has the greatest sum of its elements.

Input:

The first line of input contains a...read more

Q79. 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 matrix w...read more

Q80. Merge Sort Linked List Problem Statement

You are given a singly linked list of integers. Your task is to sort the linked list using the merge sort algorithm.

Explanation:

Merge Sort is a divide and conquer algo...read more

Q81. Check if Two Trees are Mirror

Given two arbitrary binary trees consisting of 'N' and 'M' number of nodes respectively, your task is to check whether the two trees are mirror images of each other or not.

Definit...read more

Q82. Build Max Heap Problem Statement

Given an integer array with N elements, the task is to transform this array into a max binary heap structure.

Explanation:

A max-heap is a complete binary tree where each intern...read more

Q83. Water Supply Optimization Problem

Given N houses in a village, determine the minimum cost to supply water to all houses either by building wells in the houses or by connecting them with pipes.

Explanation:

For ...read more

Q84. Implementing a Priority Queue Using Heap

Ninja has been tasked with implementing a priority queue using a heap data structure. However, he is currently busy preparing for a tournament and has requested your ass...read more

Q86. All Possible Balanced Parentheses Problem Statement

Given a positive integer N, generate all possible sequences of balanced parentheses using N pairs of parentheses.

A sequence of brackets is called balanced if...read more

Q88. Bipartite Graph Check

Determine if a given graph is bipartite. A graph is considered bipartite if its vertices can be divided into two disjoint sets, 'U' and 'V', such that every edge connects a vertex in 'U' t...read more

Q89. Maximum Sum Path in a Binary Tree

Your task is to determine the maximum possible sum of a simple path between any two nodes (possibly the same) in a given binary tree of 'N' nodes with integer values.

Explanati...read more

Q92. Count Diagonal Paths

You are given a binary tree. Your task is to return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Inp...read more

Q93. BST to Greater Tree Conversion

Convert a given binary search tree (BST) with 'N' nodes into a Greater Tree. In this transformation, each node's data is modified to the sum of the original node's data plus the s...read more

Q94. Ceil Value from BST Problem Statement

Given a Binary Search Tree (BST) and an integer, write a function to return the ceil value of a particular key in the BST.

The ceil of an integer is defined as the smallest...read more

Q95. Remove BST Keys Outside Given Range

Given a Binary Search Tree (BST) and a specified range [min, max], your task is to remove all keys from the BST that fall outside this range. The BST should remain valid afte...read more

Q97. AVL Tree Insertion Task

Create an AVL tree from scratch. You will be provided with ‘N’ values representing node values you need to insert into the AVL tree. After inserting all values, return the root of the AV...read more