Categories of Questions

## Array Questions Cisco

**Maximum Subarray Leetcode Solution** Problem Statement Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example nums = [-2,1,-3,4,-1,2,1,-5,4] 6 Explanation: [4,-1,2,1] has the largest sum = 6. nums = [-1] -1 Approach 1 (Divide and Conquer) In this approach ...

**Merge Sorted Arrays Leetcode Solution** In the problem “Merge Sorted Arrays”, we are given two arrays sorted in non-descending order. The first array is not fully filled and has enough space to accommodate all elements of the second array as well. We have to merge the two arrays, such that the first array contains elements ...

**Search in Rotated Sorted Array Leetcode Solution** Consider a sorted array but one index was picked and the array was rotated at that point. Now, once the array has been rotated you are required to find a particular target element and return its index. In case, the element is not present, return -1. The problem is generally ...

**Sum of f(a[i], a[j]) over all pairs in an array of n integers** The problem statement asks to find out the Sum of f(a[i], a[j]) over all pairs in an array of n integers in such a way that 1 < = i < j < = n considering that we are provided an array of integers. Example arr[] = {1, 2, 3, ...

**Given an Array of Pairs Find all Symmetric Pairs in it** Find all symmetric pairs – You are given some pairs of an array. You have to find out the symmetric pairs in it. The symmetric pair is said to be symmetric when in pairs say (a, b) and (c, d) in which ‘b’ is equal to ‘c’ and ‘a’ is ...

**Length of the largest subarray with contiguous elements** The problem “Length of the largest subarray with contiguous elements” states that you are given an integer array. The problem statement asks to find out the length of the longest contiguous sub-array of which elements can be arranged in a sequence (continuous, either ascending or descending). The numbers in the ...

**Count number of triplets with product equal to given number** The problem “Count number of triplets with product equal to given number” states that we are given an integer array and a number m. The problem statement asks to find out the total number of triplets of with product equals to m. Example arr[] = {1,5,2,6,10,3} m=30 3 Explanation Triplets ...

**Path with maximum average value** Problem Statement The problem “Path with maximum average value” states that you are given a 2D array or a matrix of integers. Now consider you are standing at the top-left cell and need to reach the bottom right. For reaching the destination, you need to move along either in the ...

**Print modified array after executing the commands of addition and subtraction** You are given an array of size n, initially all the values in the array will be 0, and the queries. Each query contains the four values, type of the query T, left point of the range, the right point of a range and a number k, you have to ...

**Check in binary array the number represented by a subarray is odd or even** The problem “Check in binary array the number represented by a subarray is odd or even” states that you are given a binary array and a range. The array consists of the number in the form of 0s and 1s. The problem statement asks to find out the number represented ...

**Find whether a subarray is in form of a mountain or not** Problem Statement The problem “Find whether a subarray is in form of a mountain or not” states that you are given an integer array and a range. The problem statement asks to find out whether the sub-array formed between the given range is in form of a mountain form or ...

**Subset with sum divisible by m** Problem Statement The problem “Subset with sum divisible by m” states that you are given an array of non-negative integers and an integer m. Now you need to find if there is a subset having sum divisible by m. That is the sum of the subset should give 0 as ...

**Best Time to Buy and Sell Stock** Problem Statement The problem “Best Time to Buy and Sell Stock” states that you are given an array of prices of length n, where the ith element stores the price of stock on ith day. If we can make only one transaction, that is, to buy on one day and ...

**Maximum length subsequence with difference between adjacent elements as either 0 or 1** Problem Statement You are given an integer array. The problem “Maximum length subsequence with difference between adjacent elements as either 0 or 1” asks to find out the maximum subsequence length with the difference between the adjacent elements should be none other than 0 or 1. Example arr[] = {1, ...

**Maximum Product Subarray** Problem Statement The problem “Maximum Product Subarray” states that you are given an array of integer containing both positive and negative numbers. The problem statement asks to find out the maximum product of the sub-array. Example arr[] = { 2, -2, 3, 5} 15 Explanation The elements in the sub-array ...

**Count subarrays with equal number of 1’s and 0’s** Problem Statement The problem “Count subarrays with equal number of 1’s and 0’s” states that you are given an array consisting of 0’s and 1’s only. The problem statement asks to find out the count of sub-arrays consisting equal no of 0’s ad 1’s. Example arr[] = {0, 0, 1, ...

**Subarrays with distinct elements** Problem Statement “Subarrays with distinct elements” states that you are given an array of integer elements. The problem statement asks to find the sum of lengths of contiguous sub-arrays that are having all elements different from each other. Example arr[] = {3, 1, 2, 1} 4 Explanation: The sub-arrays are ...

**Common elements in all rows of a given matrix** Problem Statement “Common elements in all rows of a given matrix” problem state that, you are given a matrix of M*N. The problem statement asks to find out all the common elements in a given matrix in each row of the matrix in O(M*N) time. Example arr[]={{12, 1, 4, 5, ...

**Count pairs from two sorted arrays whose sum is equal to a given value x** Problem Statement “Count pairs from two sorted arrays whose sum is equal to a given value x” problem states that you are given two sorted arrays of integers and an integer value called sum. The problem statement asks to find out the total number of pair which sums up to ...

**Maximum sum bitonic subarray** Problem Statement An array having n integers is given to us. We need to find the maximum sum bitonic subarray. A bitonic subarray is nothing but just a subarray where the elements are arranged in a specific order. Such that the first elements are in increasing order and then in ...

**Minimize the maximum difference between the heights** Problem Statement You are given some heights of n towers and a number k. We can either increase the height of the tower by k or decrease the height by k, but just for once. The problem statement asks to minimize the maximum difference between the heights. That is to ...

**Longest Span with same Sum in two Binary arrays** Problem Statement You are given two arrays of which each contains binary number. The problem statement asks to find longest span with same sum in two binary arrays, that is to find out the maximum length common sub-array from (i, j) in such a way that j is greater than ...

**Count Subsets Having Distinct Even Numbers** We have all struggled with the subset problem at some point or the other in an interview. The interviewers love these problems too. These problems help them examine the understanding as well as the thought process of any student. So, without any further ado let us jump straight into the ...

**Word Search** Word search is something like the word-finding puzzles at some time in our life. Today I bring to the table a modified crossword. My readers must be a bit perplexed as to what I am talking about. Without wasting any more time let us get to the problem statement Can ...

**Merge Overlapping Intervals** In merge overlapping intervals problem we have given a collection of intervals, merge and return all overlapping intervals. Example Input : [[2, 3], [3, 4], [5, 7]] Output: [[2, 4], [5, 7]] Explanation: We can merge [2, 3] and [3, 4] together to form [2, 4] Approach for finding Merge ...

**Maximum Subarray** In the Maximum Subarray problem we have given an integer array nums, find the contiguous sub array which has the largest sum and print the maximum sum subarray value. Example Input nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4} Output 6 Algorithm The goal is to find ...

**Merging Intervals** In merging intervals problem we have given a set of intervals of the form [l, r], merge the overlapping intervals. Examples Input {[1, 3], [2, 6], [8, 10], [15, 18]} Output {[1, 6], [8, 10], [15, 18]} Input {[1, 4], [1, 5]} Output {[1, 5]} Naive Approach for merging intervals ...

**Missing Number** In Missing Number problem we have given an array of size N containing a number from 0 to N. All the values in the array are unique. We need to find the missing number which is not present in the array and that number lies between 0 to N. Here ...

**Insertion Sort** Sort a given unsorted array using the insertion sort algorithm. Input: {9,5,1,6,11,8,4} Output: {1,4,5,6,8,9,11} Theory Insertion Sort sorts numbers in the same way as we humans sort a set of numbered objects (ex cards) A number is taken from an unsorted array (right subarray) to a position in the sorted ...

**Longest Span with same Sum in two Binary Arrays II** Problem Statement In the “Longest Span with same Sum in two Binary Arrays II” problem, we have given two binary arrays “a” and “b” with the same size. Write a program to print the longest span with the same sum in two arrays. This can be clearly explained in the ...

**Merge Overlapping Intervals II** Problem Statement In the “Merge Overlapping Intervals II” problem we have given a set of intervals. Write a program that will merge the overlapping intervals into one and print all the non-overlapping intervals. Input Format The first line containing an integer n. Second-line containing n pairs where each pair is ...

**Maximum Subarray Sum using Divide and Conquer** Problem Statement In the “Maximum Subarray Sum using Divide and Conquer” problem we have given an array of both positive and negative integers. Write a program that will find the largest sum of the contiguous subarray. Input Format The first line containing an integer N. Second-line containing an array of ...

**Increasing Subsequence of Length three with Maximum Product** Problem Statement In the “Increasing Subsequence of Length three with Maximum Product” problem, we have given an array of positive integers. Find the subsequence of length 3 with the maximum product. Subsequence should be increasing. Input Format The first and only one line containing an integer N denoting the size ...

**Rearrange Positive and Negative Numbers Alternatively in Array** Problem Statement In the “Rearrange Positive and Negative Numbers Alternatively in Array” problem we have given an array a[]. This array contains positive and negative integers. Rearrange the array in such a way that positive and negative are placed alternatively. Here, the number of positive and negative elements need not ...

**Find the Lost Element From a Duplicated Array** Problem Statement Given two arrays A and B, one array is a duplicate of the other except one element. The one element is missing from either A or B. we need to find the lost element from a duplicated array. Example 5 1 6 4 8 9 6 4 8 ...

**Rearrange given Array in Maximum Minimum Form** Problem Statement In the “Rearrange given Array in Maximum Minimum Form” problem, we have given a sorted array containing N elements. Rearrange the given sorted array of positive integers, such that alternative elements are ith max and ith min. See below for a better understanding of rearrangement of elements- Array[0] ...

**Merge Two Sorted Arrays** Problem Statement In merge two sorted arrays problem, we have given two input sorted arrays, we need to merge these two arrays such that the initial numbers after complete sorting should be in the first array and remaining in the second array. Example Input A[] = {1, 3, 5, 7, ...

**Count of Triplets With Sum Less than Given Value** Problem Statement We have given an array containing N number of elements. In the given array, Count the number of triplets with a sum less than the given value. Example Input a[] = {1, 2, 3, 4, 5, 6, 7, 8} Sum = 10 Output 7 Possible triplets are : ...

**Merging Two Sorted Arrays** Problem Statement In merging two sorted arrays problem we have given two sorted arrays, one array with size m+n and the other array with size n. We will merge the n sized array into m+n sized array and print the m+n sized merged array. Example Input 6 3 M[] = ...

**Find Triplet in Array With a Given Sum** Problem Statement Given an array of integers, find the combination of three elements in the array whose sum is equal to a given value X. Here we will print the first combination that we get. If there is no such combination then print -1. Example Input N=5, X=15 arr[] = ...

**Move All the Zeros to the End of the Given Array** Problem Statement In the given array move all the zeros which are present in the array to the end of the array. Here there is always a way exist to insert all the number of zeroes to the end of the array. Example Input 9 9 17 0 14 0 ...

**Find Smallest Missing Number in a Sorted Array** Problem Statement In the “Find Smallest Missing Number in a Sorted Array” problem we have given an integer array. Find the smallest missing number in N sized sorted array having unique elements in the range of 0 to M-1, where M>N. Example Input [0, 1, 2, 3, 4, 6, 7, ...

**Find the Missing Number** Problem Statement In finding the missing number from an array of 1 to N numbers we have given an array that contains N-1 numbers. One number is missing from an array of numbers from 1 to N. We have to find the missing number. Input Format First-line containing an integer ...

## String Questions Cisco

**Longest Substring Without Repeating Characters** Given a string, we have to find the length of the longest substring without repeating characters. Let’s look into a few examples: Example pwwkew 3 Explanation: Answer is “wke” with length 3 aav 2 Explanation: Answer is “av” with length 2 Approach-1 for Longest Substring Without Repeating Characters Brute Force ...

**Rearrange a binary string as alternate x and y occurrences** Problem Statement Suppose you are given a binary string, and two numbers x and y. The string consists of 0s and 1s only. The problem “Rearrange a binary string as alternate x and y occurrences” asks to rearrange the string such that the 0 comes x times ⇒ 1 comes ...

**Reverse words in a string** Problem Statement “Reverse words in a string” states that you are given a string s of size n. Print the string in reverse order such that the last word becomes the first, second last becomes the second, and so on. Hereby string we refer to a sentence containing words instead ...

**Decode Ways** In Decode Ways problem we have given a non-empty string containing only digits, determine the total number of ways to decode it using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Example S = “123” Number of ways to decode this string is 3 If we ...

**Decode String** Suppose, you are given an encoded string. A string is encoded in some kind of pattern, your task is to decode the string. Let us say, < no of times string occurs > [string ] Example Input 3[b]2[bc] Output bbbcaca Explanation Here “b” occurs 3times and “ca” occur 2 times. ...

**Check if a Linked list of Strings form a Palindrome** Problem Statement In the “Check if a Linked list of Strings form a Palindrome” problem we have given a linked list handling string data. Write a program to check whether the data forms a palindrom or not. Example ba->c->d->ca->b 1 Explanation: In the above example we can see that the ...

## Tree Questions Cisco

**Clone a Binary Tree with Random Pointers** Problem Statement You are given a complete binary tree with some random pointers. Random pointers are referred to nodes which every node points to other than its left and right child. So, this also changes the standard structure of a node in a simple binary tree. Now the node of ...

**Convert BST into a Min-Heap without using array** Problem Statement “Convert BST into a Min-Heap without using array” problem states that you are given a BST (binary search tree) and you need to convert it into a min-heap. The min-heap should contain all the elements in the binary search tree. The algorithm should run in linear time complexity. ...

**K’th Largest Element in BST when modification to BST is not allowed** Problem Statement “K’th Largest Element in BST when modification to BST is not allowed” states that you are given a binary search tree and you need to find the kth largest element. This means that when all the elements of the binary search tree are arranged in descending order. Then ...

**Level Order Traversal of Binary Tree** Level Order Traversal of a given binary tree is the same as the BFS of the binary tree. Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous articles for better understanding. BFS is a ...

## Graph Questions Cisco

**Prim’s Algorithm** Prim’s algorithm is used to find the Minimum Spanning Tree(MST) of a connected or undirected graph. Spanning Tree of a graph is a subgraph that is also a tree and includes all the vertices. Minimum Spanning Tree is the spanning tree with a minimum edge weight sum. Example Graph Minimum ...

**Dijkstra Algorithm** Dijkstra is the shortest path algorithm. Dijkstra algorithm is used to find the shortest distance of all nodes from the given start node. It logically creates the shortest path tree from a single source node, by keep adding the nodes greedily such that at every point each node in the ...

## Stack Questions Cisco

**Decode String** Suppose, you are given an encoded string. A string is encoded in some kind of pattern, your task is to decode the string. Let us say, < no of times string occurs > [string ] Example Input 3[b]2[bc] Output bbbcaca Explanation Here “b” occurs 3times and “ca” occur 2 times. ...

## Queue Questions Cisco

**Level Order Traversal of Binary Tree** Level Order Traversal of a given binary tree is the same as the BFS of the binary tree. Do we already know about what actually BFS is? if not then don’t need to feel bad just read the whole article and visit our previous articles for better understanding. BFS is a ...

## Matrix Questions Cisco

**Word Search Leetcode Solution** Problem Statement Given an m x n board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once. Example ...

**Path with maximum average value** Problem Statement The problem “Path with maximum average value” states that you are given a 2D array or a matrix of integers. Now consider you are standing at the top-left cell and need to reach the bottom right. For reaching the destination, you need to move along either in the ...

**Common elements in all rows of a given matrix** Problem Statement “Common elements in all rows of a given matrix” problem state that, you are given a matrix of M*N. The problem statement asks to find out all the common elements in a given matrix in each row of the matrix in O(M*N) time. Example arr[]={{12, 1, 4, 5, ...

## Other Questions Cisco

**Subtract the Product and Sum of Digits of an Integer Leetcode Solution** Problem Statement In this problem, we need to find the difference between the product of digits and the sum of digits of a given positive integer. Example 1234 14 Explanation: Product = 4 * 3 * 2 * 1 = 24 and Sum = 4 + 3 + 2 + ...

**Palindrome Linked List Leetcode Solution** In the problem “Palindrome Linked List”, we have to check whether a given singly integer linked list is a palindrome or not. Example List = {1 -> 2 -> 3 -> 2 -> 1} true Explanation #1: The list is palindrome as all elements from the start and back are ...

**Convert Sorted Array to Binary Search Tree Leetcode Solution** Consider we are given a sorted array of integers. The goal is to build a Binary Search Tree from this array such that the tree is height-balanced. Note that a tree is said to be height-balanced if the height difference of left and right subtrees of any node in the ...

**House Robber Leetcode Solution** Problem Statement In this problem there are houses in a street and House robber has to rob these houses. But the problem is that he can’t rob more than one house successively i.e which are adjacent to each other. Given a list of non-negative integers representing the amount of money ...

**Check if any two intervals overlap among a given set of intervals** Problem Statement The problem “Check if any two intervals overlap among a given set of intervals” states that you are given some set of intervals. Each interval consists of two values, one is starting time and the other is ending time. The problem statement asks to check if any of ...

**House Robber** The House Robber Problem states that, in a neighborhood in a city, there is a single row of n houses. A thief is planning to carry a heist in this neighborhood. He knows how much gold is concealed in each of the houses. However, in order to avoid triggering an ...

**First Bad Version** We all have heard the saying “Bad Apple Ruins The Bunch”.First Bad Version is a problem that beautifully illustrates the same. Today we have a problem which is First Bad Version. One of the interns has made an nth bad commit due to which commits from n+1 have all been ...

**Number Of 1 bits** We have all heard of the Hamming Weight of a binary number. Hamming weight is the number of set bits/1s in a binary number. In this problem Number Of 1 bits we have to find the hamming weight of the given number. Examples Number = 3 Binary representation = 011 ...

**LRU Cache Implementation** Least Recently Used (LRU) Cache is a type of method which is used to maintain the data such that the time required to use the data is the minimum possible. LRU algorithm used when the cache is full. We remove the least recently used data from the cache memory of ...