CSE Company Interview Questions

PROBLEM : Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K. Output: For each test case print the space separated values of the new matrix. Constraints: 1<=T<=10 1<=M[][]<=100 Example: Input: 2 3 4 0 1 1 0 1 1 1 1 0 1 2 3 0 1 5 2 2 1 1 1 1 0 1 8 Output: 0 5 5 0 5 5 5 5 0 5 2 3 8 8 8 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostr

Transitive closure of a Graph

PROBLEM : Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a graph. Input: First line consists of T test cases. First line of every test case consists of N , denoting number of vertices. Second line consists of N*N spaced integer(Only 0 and 1), denoting the edge b/w i to j. Output: Single line output, print the trasitive closure formed of graph. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 1 4 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : (using Floyd Warshall ) -------------------------------------------------------------------------------- #include<iostream> using namespace std; #define MAX 1000 void F

Floyd Warshall Algorithm

PROBLEM : The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph. Input: The first line of input contains an integer T denoting the no of test cases . Then T test cases follow . The first line of each test case contains an integer V denoting the size of the adjacency matrix and in the next line are V*V space separated values of the matrix (graph) . Output: For each test case output will be V*V space separated integers where the i-jth integer denote the shortest distance of ith vertex from jth vertex. Constraints: 1<=T<=20 1<=V<=20 -1000<=graph[][]<=1000 Example: Input 2 2 0 25 25 0 3 0 1 43 1 0 6 43 6 0 Output 0 25 25 0 0 1 7 1 0 6 7 6 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #defin

Count the paths

PROBLEM : Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print the count of all paths from given ‘s’ to ‘d’. Input: First line consists of T test cases. First line of every test case consists of V and E, denoting the vertices and edges. Second line of every test case consists of 2*E spaced integers denoting the edge between vertices. Third line of every test case consists of S and D. Output: Single line output, print the count of all paths from 's' to 'd'. Constraints: 1<=T<=100 1<=V,E<=10 Example: Input: 1 4 6 0 1 0 2 0 3 2 0 2 1 1 3 2 3 Output: 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; #include <list> class graph { int v ; list<int> *adj ; public : graph(int v) ;

Shortest path from 1 to n

PROBLEM : Consider a directed graph whose vertices are numbered from 1 to n. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The task is to find the minimum number of edges in a path in G from vertex 1 to vertex n. Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case contains a value of n. Output: Print the number of edges in the shortest path from 1 to n. Constraints: 1<=T<=30 Example: 1<=n <=1000 Example: Input: 2 9 4 Output: 2 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace std; int main() { int t ; cin>>t ; while(t--) { int no ; cin>>no ; int count=0 ;

Rat in a Maze Problem

PROBLEM : Consider a rat placed at (0, 0) in a square matrix m[][] of order n and has to reach the destination at (n-1, n-1). Your task is to complete the function which returns a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). For example 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR when printed in sorted order we get DDRDRR DRDDRR. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line contains an integer n denoting the size of the square matrix. The next line contains n*n space separated values of the matrix m where 0's represents blocked paths and 1 represent valid path

Permutations of a given string

PROBLEM : Given a string, print all permutations of a given string. Input: The first line of input contains an integer T denoting the number of test cases. Each test case contains a single string in capital letter. Output: Print all permutations of a given string with single space and all permutations should be in lexicographically increasing order. Constraints: 1 = T = 10 1 = size of string = 5 Example: Input: 2 ABC ABSG Output: ABC ACB BAC BCA CAB CBA ABGS ABSG AGBS AGSB ASBG ASGB BAGS BASG BGAS BGSA BSAG BSGA GABS GASB GBAS GBSA GSAB GSBA SABG SAGB SBAG SBGA SGAB SGBA -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> #include<vector> #include<algorithm> #include<string.h> using namespace std; vector<string>v; void swap(char *x, char *y) { char temp;

Jumping Numbers

PROBLEM : Given a positive number x, print all Jumping Numbers smaller than or equal to x. A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not. Input: The first line of the input contains T denoting the number of testcases. Each testcase contain a positive number 'x'. Output: All the jumping numbers less than 'x' are generated in increasing order of the most significant digit. See example for better understanding. Constraints: 1 <=T<= 100 1 <=N<= 100000 Example: Input: 2 10 50 Output: 0 1 10 2 3 4 5 6 7 8 9 0 1 10 12 2 21 23 3 32 34 4 43 45 5 6 7 8 9 Here, the most significant digits of each jumping number is following increasing order, i.e., jumping numbers starting from 0, followed by 1, then 2 and so on, them

Stock buy and sell

PROBLEM : The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days. Input: First line contains number of test cases T. Each test case contain the integer value 'N' denoting days followed by an array of stock prices in N days. Output: The maximum profit is displayed as shown below. And if there is no profit then print "No Profit". Constraints: 1 <=T<= 100 2 <=N<= 100 1 <=arr[i]<= 10000 Example Input: 2 7 100 180 260 310 40 535 695 10 23 13 25 29 33 19 34 45 65 67 Output: (0 3) (4 6) (1 4) (5 9) Notice: Output format is as follows - (buy_day sell_day) (buy_day sell_day) For each input, output should be in a single line. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- #include<iostream> using namespace

Finding Number

PROBLEM : An array is bitonic if it is comprises of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Given such a array, you need to find a element X in it and print its index. In case, X does not exist in the array print "OOPS! NOT FOUND" without quotes. Note: It is guaranteed that array consist of distinct elements. And array indexing is from 0. Input: First line will consist a number T, the number of test cases. Each test case will then consist of two numbers N and X. N being the array size and X being the element to be searched for. Next line will consist of N space separated integers. Output: Print the required answer on separate lines. Constraints: 1<=T<=10 1<=N<=200 -100<=A[i]<=100 Example: INPUT 1 5 2 1 2 7 4 3 OUTPUT 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------------------------------------

BFS traversal of graph

PROBLEM : Write a function to print the bredth first traversal for a graph from a given source s. Input: The task is to complete the function BFS which takes 3 arguments an integer denoting the starting node (s) of the bfs travel , a graph (g) and an array of visited nodes (vis) which are initially all set to false . There are multiple test cases. For each test case, this method will be called individually. Output: The function should print the breath first traversal for the graph from the given source. Note : The expected output button always produces BFS starting from node 1. Constraints: 1 <=T<= 100 1 <=Number of edges<= 100 Example: Input: 1 4 1 2 1 3 1 4 3 5 Output: 1 2 3 4 5 //bfs from node 1 There is one test cases. First line of each test case represent an integer N denoting no of edges and then in the next line N pairs of values a and b are fed which denotes there is a unidirectional edge from a to b . ------------------------

Print Common Nodes in BST

PROBLEM : Given two Binary Search Trees, task is to complete the function printCommon, which print's the common nodes in them. In other words, find intersection of two BSTs. Example root1 5 / \ 1 10 / \ / 0 4 7 \ 9 root2: 10 / \ 7 20 / \ 4 9 Output: 4 7 9 10 Input: The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow. For each test case two root nodes "root1" and "root2" pointing to the two tree's, are send to the function printCommon. Output: For each test case output a new line, containing space separated integers denoting the intersection of two BST's in sorted order. Constraints: 1<=T<=50 1<=N<=50 Example: Input: 1 7 5 1 10 0 4 7 9 5 10 7 20 4 9 O

Linked List that is Sorted Alternatingly

PROBLEM : Given a Linked list of size N, the list is in alternating ascending and descending orders, your task is to complete the function sort() that sorts the given linked list in non-decreasing order. Example: Input List: 10->40->53->30->67->12->89->NULL Output List: 10->12->30->43->53->67->89->NULL Input: The function takes a single argument as input the reference pointer to the head of the linked list. There are T test cases and for each test case the function will be called separately. Output: For each test case function should return reference pointer to the head of the new linked list. Constraints: 1<=T<=100 1<=N<=100 0<=A[]<=10^3 Example: Input: 2 6 1 9 2 8 3 7 5 13 99 21 80 50 Output: 1 2 3 7 8 9 13 21 50 80 99 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------------------------------------------------------

Counting elements in two arrays

PROBLEM : Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[]. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains two integers m and n denoting the size of the two arrays. The following two lines will contain both the arrays respectively. Output: Print the count of elements less than or equal to it in arr2 for each element in arr1. Constraints: 1<=T<=10^5 1<=m,n<=10^5 1<=arr1[i],arr2[j]<=10^5 Example: Input: 2 6 6 1 2 3 4 7 9 0 1 2 1 1 4 5 7 4 8 7 5 1 4 48 3 0 1 1 5 Output: 4 5 5 6 6 6 5 6 6 6 3 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- // function to count for each element in 1st array, // elements

Modify Linked List

PROBLEM : Given a singly linked list containing n nodes. Modify the value of first half nodes such that 1st node’s new value is equal to the last node’s value minus first node’s current value, 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes. If n is odd then the value of the middle node remains unchanged. Note: Input in the linked list is like new node will be entered at the head position (1st position). Input: First line consists of T test cases. First line of every test case consists of N, denoting the number of nodes. Second line of every test case consists of Node of linked list. Output: Single line output, return the head of modified linked list. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 2 5 10 4 5 3 6 6 2 9 8 12 7 10 Output: -4 -1 5 4 10 8 -2 4 8 9 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :

Add One Row to Tree @LeetCode

PROBLEM : Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1. The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree. Example 1: Input: A binary tree as following: 4 / \ 2 6 / \ / 3 1 5 v = 1 d = 2 Output: 4 / \ 1 1 / \ 2 6 / \ / 3 1 5 Example 2: Input: A binary tree as followin

Construct String from Binary Tree @LeetCode

PROBLEM : You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree. Example 1: Input: Binary tree: [1,2,3,4] 1 / \ 2 3 / 4 Output: "1(2(4))(3)" Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)". Example 2: Input: Binary tree: [1,2,3,null,4] 1 / \ 2 3 \ 4 Output: "1(2()(4))(3)" Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the ou

Subtree of Another Tree @LeetCode

PROBLEM : Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s: 3 / \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s: 3 / \ 4 5 / \ 1 2 / 0 Given tree t: 4 / \ 1 2 Return false. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(

Binary Tree Tilt @LeetCode

PROBLEM : Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the whole tree is defined as the sum of all nodes' tilt. Example: Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1 Note: The sum of node values in any subtree won't exceed the range of 32-bit integer. All the tilt values won't exceed the range of 32-bit integer. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNod

Sliding Window Maximum @LeetCode

June 21, 2017

PROBLEM : Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3. Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Therefore, return the max sliding window as [3,3,5,5,6,7]. Note: You may assume k is always valid, ie: 1 = k = input array's size for non-empty array. Follow up: Could you solve it in linear time? -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class So

Kth Largest Element in an Array @LeetCode

June 21, 2017

PROBLEM : Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 = k = array's length. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> pq(nums.begin(),nums.end()) ; k-- ; while(k--) pq.pop() ; return pq.top() ; } }; --------------------------------------------------------------------------------

Does array represent Heap

June 21, 2017

PROBLEM : Given an array, the task is to check if the given array represents a Binary Max-Heap. Examples: Input: A[] = {90, 15, 10, 7, 12, 2} Output: 1 The given array represents below tree 90 / \ 15 10 / \ / 7 12 2 The tree follows max-heap property as every node is greater than all of its descendants. Input: A[] = {9, 15, 10, 7, 12, 11} Output: 0 The given array represents below tree 9 / \ 15 10 / \ / 7 12 11 The tree doesn't follows max-heap property 9 is smaller than 15 and 10, and 10 is smaller than 11. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of input contains an integer N denoting the size of the array. Then in the next line are N space separated values of the array. Output: For each test case in a new line print 1 if the array could represent the max h

Can Place Flowers @LeetCode

June 20, 2017

PROBLEM : Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule. Example 1: Input: flowerbed = [1,0,0,0,1], n = 1 Output: True Example 2: Input: flowerbed = [1,0,0,0,1], n = 2 Output: False Note: The input array won't violate no-adjacent-flowers rule. The input array size is in the range of [1, 20000]. n is a non-negative integer which won't exceed the input array size. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public: bool canPlaceFlowe

K-Sum Paths

June 20, 2017

PROBLEM : A binary tree and a number k are given. Print the count of every path in the tree with sum of the nodes in the path as k. Input: First line consists of T test cases. First line of every test case consists of N, denoting the number of Node is Binary tree. Second line consists of N spaced 3 elements denoting the Parent node, Child Node and a character denoting left or right child. Third line of every test case consists of a integer K. Output: Return the Count of number of paths in tree. Constraints: 1<=T<=20 1<=N<=100 Example: Input: 1 4 1 3 L 3 2 L 3 -1 R -1 1 R 4 Output: 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*Complete the function below Node is as follows: struct Node{ int data; Node *left,*right; Node(int d){ data=d; left=right=NULL; } };*/ int CountKSum(Node *,i

Search Insert Position @LeetCode

PROBLEM : Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 -> 2 [1,3,5,6], 2 -> 1 [1,3,5,6], 7 -> 4 [1,3,5,6], 0 -> 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : O(n) Solution -------------------------------------------------------------------------------- class Solution { public: int searchInsert(vector<int>& nums, int target) { if(nums.size()==0) return 0 ; int pos=0 ; for(int i=0;i<nums.size();i++){ if(nums[i]>target) return pos ; if(nums[i]==target) return i ; pos++ ; } return pos ; } }; ---------------

Third Maximum Number @LeetCode

PROBLEM : Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead. Example 3: Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public: int thirdMax(vector<int>& nums) { if(nums.size()==1) return nums[0] ; else if(nums.size()==2) return nums[0]>nums[1]?nums[

Move Zeroes @LeetCode

PROBLEM : Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public: void moveZeroes(vector<int>& nums) { int i ; i=0 ; for(int j=0;j<nums.size();j++){ if(nums[j]!=0) nums[i++]=nums[j] ; } for(int j=i;j<nums.size();j++) nums[j]=0 ; } }; --------------------------------------------------------------------------------

Find All Numbers Disappeared in an Array @LeetCode

PROBLEM : Given an array of integers where 1 = a[i] = n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> vec ; for(int i=0;i<nums.size();i++){ if(nums[abs(nums[i])-1]>0) nums[abs(nums[i])-1]*=(-1) ; } for(int i=0;i<nums.size();i++) if(nums[i]>0) vec.push_back(i+1) ;

Remove Element @LeetCode