Extc Resources

Given an unsorted array of size  N . Find the first element in array such that all of its left elements are smaller and all right elements to it are greater than it. Note:  Left and right side elements can be equal to required element. And extreme elements cannot be required element. Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains an Integer N denoting size of array and the second line contains N space separated array elements. Output: For each test case, in a new line print the required element. If no such element present in array then print -1. Constraints: 1 <= T <= 100 3 <= N <= 10 6 1 <= A[i] <= 10 6 Example: Input: 3 4 4 2 5 7 3 11 9 12 6 4 3 2 7 8 9 Output: 5 -1 7 Explanation: Testcase 1 :  Elements on left of 5 are smaller than 5 and on right of it are greater than 5. Execution Time:0.17

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 can be of two types 1. SET x y :

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 the graph. Output: For each test case output will be 1 if the top

Consider an undirected graph consisting of   nodes where each node is labeled from   to   and the edge between any two nodes is always of length  . We define node   to be the starting position for a BFS. Given   queries in the form of a graph and some starting node,  , perform each query by calculating the shortest distance from starting node   to all the other nodes in the graph. Then print a single line of   space-separated integers listing node  's shortest distance to each of the   other nodes (ordered sequentially by node number); if   is disconnected from a node, print   as the distance to that node. Input Format The first line contains an integer,  , denoting the number of queries. The subsequent lines describe each query in the following format: The first line contains two space-separated integers describing the respective values of   (the number of nodes) and   (the number of edges) in the graph. Each line   of the   subsequent lines contains two spac