2000+ Allah Valley Medical Specialists' Center Interview Questions and Answers

Q1. Maximum Subarray Sum Problem Statement

Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

137

E...read more

Q2. Minimum Number of Platforms Needed Problem Statement

You are given the arrival and departure times of N trains at a railway station for a particular day. Your task is to determine the minimum number of platform...read more

Q6. Permutation in String Problem Statement

Determine if the string str2 contains a permutation of the string str1 as one of its substrings.

Input:

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

Q7. Fenwick Tree Problem Statement

You are provided with an array/list ARR consisting of 'N' integers, along with 'Q' queries. Each query can be of one of the following two types:

• Type 1 (Range Sum): Given two int...read more

Q8. Fish Eater Problem Statement

In a river where water flows from left to right, there is a sequence of 'N' fishes each having different sizes and speeds. The sizes of these fishes are provided in an array called ...read more

Q9. Delete Alternate Nodes from a Singly Linked List

Given a Singly Linked List of integers, remove all the alternate nodes from the list.

Input:

The first and the only line of input will contain the elements of th...read more

Q10. Longest Common Subsequence Problem Statement

Given two strings STR1 and STR2, determine the length of their longest common subsequence.

A subsequence is a sequence that can be derived from another sequence by d...read more

Q11. Find Pair With Smallest Difference Problem Statement

Given two unsorted arrays of non-negative integers, arr1 and arr2 with sizes N and M, determine the pair of elements (one from each array) which have the sma...read more

Q13. Fire in the Cells Problem Statement

Given a matrix MAT of size N * M, where each cell is either on fire or safe, determine if a person can reach an escape cell without being burnt. The person starts from a give...read more

Q14. Maximum Sum of Non-Adjacent Elements

Given an array/list of ‘N’ integers, your task is to return the maximum sum of the subsequence where no two elements are adjacent in the given array/list.

Example:

Input:

T ...read more

Q15. Find All Pairs Adding Up to Target

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 the Target.

Input:

The first line conta...read more

Q17. Maximum Path Sum Between Two Leaves

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

Expla...read more

Q18. Car Pooling Problem Statement

You are tasked with driving a cab that moves in a straight line, only forward, and initially has 'C' empty seats available for passengers.

Given 'N' trips, each defined by three in...read more

Q19. Best Time To Buy and Sell Stock Problem Statement

You are given an array 'PRICES' of 'N' integers, where 'PRICES[i]' represents the price of a certain stock on the i-th day. An integer 'K' is also provided, ind...read more

Q20. Search for Indices with Given Difference and Distance

You are provided with an array containing 'N' non-negative integers, along with two other non-negative integers 'K' and 'M'. Your task is to identify and re...read more

Q21. Sum of Minimum and Maximum Elements of All Subarrays of Size K

You are provided with an array containing N integers along with an integer K. Your task is to compute the total sum of the minimum and maximum elem...read more

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

Q23. Inversion Count Problem

Given an integer array ARR of size N with all distinct values, determine the total number of 'Inversions' that exist.

Explanation:

An inversion is a pair of indices (i, j) such that:

• AR...read more

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

Q25. String Transformation Problem Statement

Given a string str of length N, perform a series of operations to create a new string:

1. Select the smallest character from the first 'K' characters of the string, remove ...read more

Q26. Counting Derangements Problem

A derangement is a permutation of 'N' elements, where no element appears in its original position. For instance, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0} because each element ...read more

Q27. Mike and Mobile Keypad Problem

Mike, a young math enthusiast, is playing with his mom’s mobile phone, which has a keypad with 12 buttons (10 digits: 0-9, and 2 special characters: ‘*’ and ‘#’). His challenge is...read more

Q28. Stock Trading Maximum Profit Problem

Given the stock prices for 'N' days, your goal is to determine the maximum profit that can be achieved. You can buy and sell the stocks any number of times but can only hold...read more

Q29. Sort 0s, 1s, and 2s Problem Statement

You are provided with an integer array/list ARR of size 'N' which consists solely of 0s, 1s, and 2s. Your task is to write a solution to sort this array/list.

Input:

The fi...read more

Q31. Detect Cycle in a Directed Graph

You are provided with a directed graph composed of 'N' nodes. You have a matrix called 'EDGES' with dimensions M x 2, which specifies the 'M' edges in the graph. Each edge is di...read more

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

Q33. Spiral Matrix Problem Statement

You are provided with a 2-D array called MATRIX with dimensions N x M containing integers. Your task is to return the matrix's elements in a spiral order.

Example:

Input:

The fi...read more

Q34. Kth Smallest and Largest Element Problem Statement

You are provided with an array 'Arr' containing 'N' distinct integers and a positive integer 'K'. Your task is to find the Kth smallest and Kth largest element...read more

Q35. Rotten Oranges Problem Statement

Given a grid containing oranges in three possible states:

• Value 0 - Empty cell
• Value 1 - Fresh orange
• Value 2 - Rotten orange

Every second, any fresh orange adjacent (4-direct...read more

Q36. Find Pair Sum Equal to K

Given an integer array arr and an integer 'Sum', find and return the total number of pairs in the array which, when added together, result in the 'Sum'.

Note:

The array can contain dupl...read more

Q37. Sliding Window Maximum Problem Statement

You are given an array/list of integers with length 'N'. A sliding window of size 'K' moves from the start to the end of the array. For each of the 'N'-'K'+1 possible wi...read more

Q38. Unique Paths Problem Statement

Given the dimensions of an M x N matrix, determine the total number of unique paths from the top-left corner to the bottom-right corner of the matrix.

Allowed moves are only to th...read more

Q39. Covid Vaccination Distribution Problem

As the Government ramps up vaccination drives to combat the second wave of Covid-19, you are tasked with helping plan an effective vaccination schedule. Your goal is to ma...read more

Q40. Shortest Path in a Binary Maze

Find the length of the shortest path in a binary maze given in the form of a rectangular matrix of size M*N, where each element is 0 or 1. Calculate the shortest path from a desig...read more

Q41. Maximum 0-1 Distance Problem Statement

Given a binary matrix of size N*M, find the maximum distance 'di' for every 0-cell to its nearest 1-cell, where the distance is measured using Manhattan distance. The task...read more

Q42. Special Binary Tree Problem Statement

Determine whether an arbitrary binary tree is special. A binary tree is called special if every node in this tree has either zero or two children.

Example:

Input:

3
5 1
6 2 0...read more

Q43. Sort 0 1 2 Problem Statement

Given an integer array arr of size 'N' containing only 0s, 1s, and 2s, write an algorithm to sort the array.

Input:

The first line contains an integer 'T' representing the number of...read more

Q44. First Missing Positive Problem Statement

You are provided with an integer array ARR of length 'N'. Your objective is to determine the first missing positive integer using linear time and constant space. This me...read more

Q45. Longest Decreasing Subsequence Problem Statement

Given an array/list of integers ARR consisting of N integers, your task is to determine the length of the longest decreasing subsequence.

Explanation:

A subseque...read more

Q46. Maximum Consecutive Ones Problem Statement

Given a binary array 'ARR' of size 'N', your task is to determine the maximum length of a sequence consisting solely of 1’s that can be obtained by converting at most ...read more

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

Q48. String Palindrome Verification

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

Input:

The input is a single string without any leading or trailing space...read more

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

Q50. Triplets in a Sorted Doubly Linked List

Given a sorted doubly linked list of distinct nodes, determine how many triplets in the list have a sum equal to a given value 'X'. Each node in the list contains a uniqu...read more

Q51. Trapping Rainwater Problem Statement

You are given an array ARR of long type, which represents an elevation map where ARR[i] denotes the elevation of the ith bar. Calculate the total amount of rainwater that ca...read more

Q52. First and Last Position of an Element in a Sorted Array

Given a sorted array/list ARR consisting of ‘N’ elements, and an integer ‘K’, your task is to find the first and last occurrence of ‘K’ in ARR.

Explanatio...read more

Q53. Longest Palindromic Substring Problem Statement

You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palindromic ...read more

Q54. Sum of Big Integers Problem Statement

Given two integers represented as strings, 'NUM1' and 'NUM2', compute and return their sum.

Input:

T
NUM1 NUM2
...

Output:

Sum of NUM1 and NUM2 for each test case

Example:

In...read more

Q55. Longest Common Prefix Problem Statement

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

Q56. Reverse a Singly Linked List

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

Explanation:

Reverse a given singly linked list so that the last element becomes...read more

Q57. Strongly Connected Components (Tarjan’s Algorithm) Problem Statement

Given an unweighted directed graph with V vertices and E edges, your task is to identify and print all the strongly connected components (SCC...read more

Q58. Word Presence in Sentence

Determine if a given word 'W' is present in the sentence 'S' as a complete word. The word should not merely be a substring of another word.

Input:

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

Q59. 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; otherwise, re...read more

Q60. Stack with getMin Operation

Create a stack data structure that supports not only the usual push and pop operations but also getMin(), which retrieves the minimum element, all in O(1) time complexity without usi...read more

Q61. Container with Most Water Problem Statement

Given a sequence of 'N' space-separated non-negative integers A[1], A[2], ..., A[i], ..., A[n], where each number in the sequence represents the height of a line draw...read more

Q62. Anagram Pairs Verification

In this task, you need to verify if two provided strings are anagrams of each other. Two strings are considered anagrams if you can rearrange the letters of one string to form the oth...read more

Q63. Minimum Window Subsequence Problem Statement

You are given two strings S and T. Your task is to determine the smallest contiguous substring W of S, such that T is a subsequence of W.

A subsequence is a sequence...read more

Q65. Postfix Expression Evaluation Problem Statement

Given a postfix expression, your task is to evaluate the expression. The operator will appear in the expression after the operands. The output for each expression...read more

Q66. Dijkstra's Shortest Path Problem Statement

Given an undirected graph with V vertices (labeled 0, 1, ..., V-1) and E edges, each edge connects two nodes X and Y with a specified weight representing the distance ...read more

Q67. Minimum Path Sum Problem Statement

Consider a 2-dimensional grid 'GRID' with 'N' rows and 'M' columns in Ninjaland. Each cell in the grid has an associated cost. The goal is to determine the minimum path sum fr...read more

Q68. Ways To Make Coin Change

Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make the c...read more

Q69. Character Frequency Problem Statement

You are given a string 'S' of length 'N'. Your task is to find the frequency of each character from 'a' to 'z' in the string.

Example:

Input:

S : abcdg

Output:

1 1 1 1 0 0 ...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

Q71. Subarray With Given Sum Problem Statement

Given an array ARR of N integers and an integer S, determine if there exists a contiguous subarray within the array with a sum equal to S. If such a subarray exists, re...read more

Q72. Weighted Job Scheduling Problem Statement

You have 'N' jobs, each with a start time, end time, and profit. Your task is to identify the maximum profit that can be earned by scheduling these jobs such that no tw...read more

Q73. Number with Maximum Probability Problem Statement

In this game, players Ninja Misha and Ninja Andrew each choose an integer within the range of 1 to 'N'. After their choices, a random integer 'C' is drawn from ...read more

Q74. 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:

Each pa...read more

Q75. Frequency in a Sorted Array Problem Statement

Given a sorted array ARR and a number X, your task is to determine the count of occurrences of X within ARR.

Note:

• If X is not found in the array, return 0.
• The ar...read more

Q76. Clone a Linked List with Random Pointers Problem Statement

Given a linked list where each node contains two pointers: the first points to the next node in sequence, and the second is a random pointer that can p...read more

Q77. Unique Element in Array

Given an arbitrary array arr consisting of N non-negative integers where every element appears thrice except for one. Your task is to find the element in the array that appears only once...read more

Q78. Boundary Traversal Problem Statement

Given a binary tree of integers, your task is to return the boundary nodes of this binary tree in an anti-clockwise direction starting from the root node.

Example:

Input:

T ...read more

Q79. Binary Strings Without Consecutive 1s Problem Statement

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 the binary str...read more

Q80. Maximum of All Subarrays of Size K

You are provided with an array A containing N integers. Your task is to determine the maximum element in every contiguous subarray of size K as you move from left to right thr...read more

Q82. Right View of Binary Tree Problem Statement

Given a Binary Tree of integers, your task is to compute and print the right view of it.

The right view of a Binary Tree is a set of nodes visible when the tree is vi...read more

Q83. Smallest Window Problem Statement

Given two strings S and X containing random characters, the task is to find the smallest substring in S which contains all the characters present in X.

Input:

The first line co...read more

Q85. Matrix Median Problem Statement

You are provided with a matrix containing 'N' rows and 'M' columns filled with integers. Each row is sorted in non-decreasing order. Your task is to find the overall median of th...read more

Q86. Count Triplets in a Sorted Doubly Linked List

You are provided with an integer X and a non-decreasing sorted doubly linked list consisting of distinct nodes.

Your task is to find and return the count of triplet...read more

Q87. The Celebrity Problem

Imagine there are 'N' people at a party, each assigned a unique ID from 0 to N-1. A celebrity at the party is a person who is known by everyone but knows no one else.

Problem Statement:

Yo...read more

Q88. Flip Bits Problem Explanation

Given an array of integers ARR of size N, consisting of 0s and 1s, you need to select a sub-array and flip its bits. Your task is to return the maximum count of 1s that can be obta...read more

Q89. Find Row K Problem Explanation

You are given a square binary matrix mat[n][n]. The task is to determine an integer 'K' such that:

• All elements in the Kth row are 0.
• All elements in the Kth column are 1.

The v...read more

Q90. Next Greater Element Problem Statement

You are provided with an array or list ARR containing N positive integers. Your task is to determine the Next Greater Element (NGE) for each element in the array.

The Next...read more

Q91. Closest Sum Problem Statement

Given an array of integers ARR of size N and an integer target, find three integers in ARR such that their sum is closest to the target. If there are two closest sums, return the s...read more

Q92. Most Frequent Word Problem Statement

You are given two strings 'A' and 'B' composed of words separated by spaces. Your task is to determine the most frequent and lexicographically smallest word in string 'A' th...read more

Q93. String Rearrangement Problem Statement

You are given a string of lowercase characters. The objective is to rearrange (reorder) the string so that no two adjacent characters are identical.

Return the rearranged ...read more

Q94. Minimum Travel Cost Problem

You are given a country called 'Ninjaland' with 'N' states, numbered from 1 to 'N'. These states are connected by 'M' bidirectional roads, each with a specified travel cost. The aim ...read more

Q95. Minimum Number of Platforms Problem

Your task is to determine the minimum number of platforms required at a railway station so that no train has to wait.

Explanation:

Given two arrays:

• AT - representing the ar...read more

Q96. Square Root with Decimal Precision Problem

Your task is to compute the square root of a given integer N, such that the result is as accurate as D decimal places. The aim is to ensure that the absolute differenc...read more

Q97. Find Number of Islands

You are provided with a 2-dimensional array/list of size N rows by M columns, containing ones (1) and zeroes (0). Here, 1 represents land, and 0 represents water.

A cell is considered con...read more

Q98. K Most Frequent Words Problem Statement

Given an array or list WORDS of 'N' non-empty words and an integer 'K', identify the 'K' most frequent words and return them sorted by their frequency, in descending orde...read more

Q99. Path In A Tree Problem Statement

Given a binary tree with 'N' nodes and a specific node 'X', your goal is to print the path from the root node to the specified node 'X'.

Explanation:

A binary tree is a hierarch...read more