SDE - 1

Ninja has been given an array/list ‘ARR’ of even size ‘N’ and an integer ‘K’. Ninja gives his friend a task to divide the given ‘ARR’ into ‘N’/2 pairs such that the sum of each pair should be divisible by ‘K’.

Can you help Ninja to do this task?

For Example :

If ‘ARR’ = [4 5 6 5 7 3] and ‘K’ = 5
Pairs are(4, 6), (5, 5) ,and (7, 3) and the sum of elements of each pair is divisible by ‘K’ i.e 5.

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 are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

You are given a string “S”. Your task is to rearrange the characters of a string “S”, such that it does not contain any two adjacent characters which are the same.

If it is possible to rearrange the string “S”, then print any possible arrangement. else, print “not possible” without quotes.

For Example:

For a string  “qaacde”, This string has two same adjacent characters.
So, one possible way to rearrange the string is “qacade”. Now, this string does not have two adjacent characters that are the same. 

Explain Primary Key, Foreign Key and the relationship between them. (Learn)

When do you prefer NoSQL DB over SQL DB? Explain Why? (Learn)

Given a Railway Station. What are all the classes and the relationship between those classes?
Implement them quickly and explain.

You are given an undirected graph G(V, E), where ‘V’ is the number of vertices and ‘E’ is the number of edges present in the graph and two integers ‘v1’ and ‘v2’ denoting vertices of the graph, find and print the path from ‘v1’ to ‘v2’ (if exists) in reverse order. Print an empty list if there is no path between ‘v1’ and ‘v2’.

Find the path using BFS and print the first path that you encountered.

Note:

Vertices are numbered through 0 to V - 1.

What is Load Balancing? How would you implement it, and what data structures would you use? (Learn)