SDE - Intern

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

Given an undirected graph of V vertices and E edges. Your task is to find all the bridges in the given undirected graph. A bridge in any graph is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).

For Example :

If the given graph is :

Then the edge between 0 and 4 is the bridge because if the edge between 0 and 4 is removed, then there will be no path left to reach from 0 to 4.and makes the graph disconnected, and increases the number of connected components.

Note :

There are no self-loops(an edge connecting the vertex to itself) in the given graph.

There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.

You are given a circular array 'ARR' of size 'N', consisting of positive and negative integers. For each index 'i', if ARR[i] is positive then move ARR[i] steps in clockwise direction else move ARR[i] steps in counterclockwise direction.

Assume that the first ( ARR[0] ) and last element ( ARR[N - 1] ) are adjacent to each other i.e. when we move in the counterclockwise direction, the next element for ARR[0] is ARR[N - 1] and similarly, when we move in the clockwise direction, the next element for ARR[N - 1] is ARR[0].

Determine if there is a cycle present in the array or not. A cycle must hold the following conditions:

1. A cycle must start and end at the same index.

2. The cycle’s length should be greater than 1. For example, if the given array is {1,-2,4,1} then there is a cycle of length 1 from index 3 (1 based indexing). 

3. All movements in a cycle must follow a single direction, they should be either in a clockwise or counterclockwise direction.

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.

You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

The test-data is such that the result will fit into a 32-bit integer.

You are given a positive integer N. Return a list of integers of size 2N containing all the integers from 1 to N (both inclusive) twice arranged according to Langford pairing. If no such pairing exists return -1 is the only list element.

Note:

There may be more than one Langford pair possible, you need to return anyone permutation.

For example:

For N = 4, one possible Langford pairing will be:-