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

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, 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: Times-Internet, Snapdeal, Morgan Stanley,Microsoft, Amazon, Adobe Question: A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it. Expected Time Complexity:  O(Log n) Input: The first line of input contains a single integer T denoting the number of test cases. Then   T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array. The second line of each test case contains N space separated integers denoting array elements. Output: Corresponding to each test case, in a new line, print the minimum element in the array. Constraints: 1 ≤ T ≤ 200 1 ≤ N ≤ 500 1 ≤ A[i] ≤ 1000 Example: Input 1 5 4 5 1 2 3 Output 1 CODE: Naive solution import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Sca...

Company:Adobe Question:  Given an integer K,return the kth row of pascal triangle. Pascal's triangle is a triangular array of the binomial coefficients formed by summing up the elements of previous row. Example of pascal triangle: 1 1 1 1 2 1 1 3 3 1   for K=3, return 3rd row i.e 1 2 1   Input: The first line contains an integer T,depicting total number of test cases.  Then following T lines contains an integer N depicting the row of triangle to be printed. Output: Print the Nth row of triangle in a separate line. Constraints: 1 ≤ T ≤ 50 1 ≤ N ≤ 25 Example: Input 1 4 Output 1 3 3 1 CODE: import java.util.*; import java.lang.*; import java.io.*; import java.math.BigInteger; 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();      for(int r=0;r...

Company: Qualcomm, Juniper Networks, Cisco, Adobe, Brocade Question: Given a positive integer  N , print count of set bits in it. For example, if the given number is 6, output should be 2 as there are two set bits in it. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow.  The next T lines will contain an integer  N . Output: Corresponding to each test case, in a new line, print count of set bits in it. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 1000000 Example: Input: 2 6 11   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++){    int n = sc.nextInt();    String a = Integer.toBinaryString(n);   // System.out.println(a);    //String ar= new Str...