Extc Resources

Given a directed graph you need to complete the function  topoSort  which returns an array having the topologically sorted elements of the array and takes two arguments . The first argument is the Graph graph  represented as adjacency list and the second is the number of vertices  N  . Company: OYO Rooms, Moonfrog Labs, Microsoft, Flipkart, Amazon,Accolite Note :  There can be multiple topological sorts of a Graph.  The driver program that calls your function doesn't match your output element by element, but checks whether the output produced by your function is a valid topological sort or not. Input: The first line of input takes the no of test cases then T test cases follow . Each test case contains two lines . The first  line of each test case  contains two integers E and N representing no of edges and the no of vertices . Then in the next line are E  pairs of integers u v representing an edge from u to v in ...

CODE:  import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { int graph[][] = new int[][] {{0, 2, 0, 6, 0},                                     {2, 0, 3, 8, 5},                                     {0, 3, 0, 0, 7},                                     {6, 8, 0, 0, 9},                                     {0, 5, 7, 9, 0},                                    };     primMST(graph);                       ...

Company: MakeMyTrip, GreyOrange, Boomerang, Amazon, Adobe, Accolite, Walmart-Labs, VMWare, Snapdeal, Qualcomm, OYO Rooms, Microsoft, Wooker. Question:  Given a binary tree, return true if it is  BST , else false. For example, the following tree is not BST, because 11 is in left subtree of 10.         10      /     \    7       39      \       11 Input: The task is to complete the method which takes one argument, root of Binary Tree. The struct Node has a data part which stores the data, pointer to left child and pointer to right child. There are multiple test cases. For each test case, this method will be called individually. Output: The function should return 1 if BST else return 0. Constraints: 1 <=T<= 30 1 <= Number of nodes<= 100 1 <= Data of a node<= 1000 Example: Input: 2 2 1 2 R 1 3 L 4 10 20 L 10 30 R 2...

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′. Insert Remove Replace All of the above operations are of cost=1. Both the strings are of lowercase. Company: Amazon Input: The First line of the input contains an integer T denoting the number of test cases. Then T test cases follow. Each tese case consists of two lines. The first line of each test case consists of two space separated integers P and Q denoting the length of the strings str1 and str2 respectively. The second line of each test case coantains two space separated strings str1 and str2 in order. Output: Coreesponding to each test case, pirnt in a new line, the minimum number of operations required. Constraints: 1<=T<=50 1<= Length(str1) <= 100 1<= Length(str2) <= 100   Example: Input: 1 4 5 geek gesek Output: 1 CODE: import java.util.*; impo...

Company: Paytm, Goldman-Sachs, Amazon Question: Given an array of integers, sort the array into a wave like array and return it.  In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example Given [1, 2, 3, 4] One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2]  NOTE : If there are multiple answers possible, return the one thats lexicographically smallest.  Input: The first line contains an integer T, depicting total number of test cases.  Then following T lines contains an integer N depicting the size of square matrix and next line followed by the value of array. Output: Print the array into wave like array. Constraints: 1 ≤ T ≤ 30 1 ≤ N ≤ 100 0 ≤ A[i] ≤ 100 Example: Input 1 5 5 7 3 2 8 Output 3 2 7 5 8 CODE: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) {     Scanner sc = ne...

Given a number N, print all its unique prime factors and their powers in N. N = 100 Factor Power 2 2 5 2 N = 35 Factor Power 5 1 7 1 Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N. Output: Print all prime factors and their powers separated by spaces.  The output should be printed in increasing order of prime factors. Constraints: 1 ≤ T ≤ 200 2 ≤ N ≤ 10000 Example: Input: 2 100 35 Output: 2 2 5 2 5 1 7 1 CODE: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int m = sc.nextInt(); for(int  mi=0;mi<m;mi++){    int n = sc.nextInt();    primeFact(n);    System.out.println(); } } public static void primeFact(int n){    int num=n;    int count[]= new int[n+1]; ...

Company: MakeMyTrip, Amazon, Accolite Question: Given a string of character, find the length of longest proper prefix which is also a proper suffix. Example: S = abab lps is 2 because, ab.. is prefix and ..ab is also a suffix. Input: First line is T number of test cases. 1<=T<=100. Each test case has one line denoting the string of length less than 100000. Expected time compexity is  O(N) . Output: Print length of longest proper prefix which is also a proper suffix. Example: Input: 2 abab aaaa Output: 2 3 CODE: import java.util.*; import java.lang.*; import java.io.*; class Solution{ public static void main (String[] args) { Scanner sc = new Scanner (System.in); int m = sc.nextInt(); for(int mi=0;mi<m;mi++){    String s= sc.next();    int i=0, max=0;         for (int j=1;j<s.length();j++){         {if (s.charAt(i)== s.charAt(j))        ...

Company:Amazon Question: Given a binary string, count number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.   Input: The first line of input contains an integer T denoting the number of test cases. Each test case consist of an integer 'n' denoting the string length and next line is followed by a binary string . Output: Print the number of substring starting and ending with 1 in a separate line. Constraints: 1 ≤ T ≤ 40 1 ≤ |s| ≤ 1000 Example: Input: 1 4 1111 Output: 6 CODE: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int m = sc.nextInt(); for(int mi=0;mi<m;mi++){    int n = sc.nextInt();    String s= sc.next();    int count=0;    char c[]= s.toCharArray();    for(...

Company: VMWare, MakeMyTrip, Amazon Question: Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase. Input: First line of the input contains no of test cases   T ,the  T  test cases follow. Each test case consist of 2 space separated integers  A  and  B  denoting the size of string  str1  and  str2 respectively The next two lines contains the 2 string  str1  and  str2  . Output: For each test case print the length of longest  common subsequence of the two strings . Constraints: 1<=T<=200 1<=size(str1),size(str2)<=100 Example: Input: 2 6 6 ABCDGH AEDFHR 3 2 ABC AC Output: 3 2 Explanation LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS of "ABC" and "AC" is "AC" of length 2 CODE: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void ma...