Extc Resources

Company: Hike, Google, Goldman-Sachs, Flipkart, Expedia, Amazon, Adobe, Walmart-Labs, Ola-Cabs, Microsoft, MakeMyTrip, Intuit, Informatica, Yahoo. Question: The task is to design and implement methods of an  LRU cache . The class has two methods get and set which are defined as follows. get(x)   : Gets the value of the key x if the key exists in the cache otherwise returns -1 set(x,y) : inserts the value if the key x is not already present. If the cache reaches its capacity it should invalidate the least recently used item before inserting the new item. In the constructor of the class the size of the cache should be intitialized.   Input: The first line of input contain an integer T denoting the no of test cases. Then T test case follow. Each test case contains 3 lines. The first line of input contains an integer N denoting the capacity of the cache and then in the next line is an integer Q denoting the no of queries Then Q queries follow. A Query...

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

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

Company: Microsoft, Flipkart Question:  Given a Binary Search Tree (BST) and a range, print all the numbers in the BST that lie in the given range. You are required to complete the function  printNearNodes.  You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.   Input (only to be used for Expected Output): The first line of the input contains an integer 'T' denoting the nummber of test cases. Then 'T' test cases follow. Each test case consists of three lines. Description of  test cases is as follows: The First line of each test case contains an integer 'N' which denotes the no of nodes in the BST.   . The Second line of each test case contains 'N' space separated values of the nodes in the BST. The Third line of each test case contains two space separated integers 'l' and 'h' denoting the range, where l ...

Company: Microsoft, Housing.com, Hike, Flipkart, Amazon, Adobe, Accolite, Teradata, PayU, Ola-Cabs Question:  Write a function to print spiral order traversal of a tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7.     Input: The task is to complete the method which takes one argument, root of the 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 print level order traversal in spiral form . Constraints: 1 <=T<= 30 1 <=Number of nodes<= 3000 1 <=Data of a node<= 1000 Example: Input: 2 2 1 2 R 1 3 L 4 10 20 L 10 30 R 20 40 L 20 60 R Output: 1 3 2 10 20 30 60 40 There are two test cases.  First case represents a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 3 and right child of 1 is 2.   Second test case repr...

Company: Myntra, Microsoft, Flipkart, BankBazaar, Amazon, Adobe Given an array, find inversion count of array. Inversion Count   for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.  Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3). 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,N is the size of array. The second line of each test case contains N input C[i]. Output: Print the inversion count of array. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 100 1 ≤ C ≤ 500 Example: Input: 1 5 2 4 1 3 5 Output: 3 CODE: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { ...

Company: Walmart- Labs, Microsoft, Amazon Question: Given an array, print k largest elements from the array.  The output elements should be printed in decreasing order. 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 and k, N is the size of array and K is the largest elements to be returned. The second line of each test case contains N input C[i]. Output: Print the k largest element in descending order. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 100 K ≤ N 1 ≤ C[i] ≤ 1000 Example: Input: 2 5 2 12 5 787 1 23 7 3 1 23 12 9 30 2 50 Output: 787 23 50 30 23 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();     int []ar= new int[n];     int k=sc...