SDE - 1

You are given a list of “N” strings A. Your task is to check whether you can form a given target string using a combination of one or more strings of A.

Note :

You can use any string of A multiple times.

Examples :

A =[“coding”, ”ninjas”, “is”, “awesome”]  target = “codingninjas”
Ans = true as we use “coding” and “ninjas” to form “codingninjas”

You are given a reference/address of a node in a connected undirected graph containing N nodes and M edges. You are supposed to return a clone of the given graph which is nothing but a deep copy. Each node in the graph contains an integer “data” and an array/list of its neighbours.

The structure of the graphNode class is as follows:

class graphNode 
{  
    public:
        int data;
        vector<graphNode*> neighbours;
}

Note :

1. Nodes are numbered from 1 to N.

2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.

Which of the following is a command of DDL?
1) Alter
2) Delete
3) Create
4) All of the Above

To avoid deadlock ____________
a) there must be a fixed number of resources to allocate
b) resource allocation must be done only once
c) all deadlocked processes must be aborted
d) inversion technique can be used

Which of the following layers is an addition to the OSI model when compared with the TCP IP model?
a) Application layer
b) Presentation layer
c) Session layer
d) Session and Presentation layer

Implement a Trie Data Structure which supports the following three operations:

Operation 1 - insert(word) - To insert a string WORD in the Trie.

Operation 2-  search(word) - To check if a string WORD is present in Trie or not.

Operation 3-  startsWith(word) - To check if there is a string that has the prefix WORD.

Trie is a data structure that is like a tree data structure in its organisation. It consists of nodes that store letters or alphabets of words, which can be added, retrieved, and deleted from the trie in a very efficient way.

In other words, Trie is an information retrieval data structure, which can beat naive data structures like Hashmap, Tree, etc in the time complexities of its operations.

The above figure is the representation of a Trie. New words that are added are inserted as the children of the root node. 

Alphabets are added in the top to bottom fashion in parent to children hierarchy. Alphabets that are highlighted with blue circles are the end nodes that mark the ending of a word in the Trie.

For Example:-

Type = ["insert", "search"], Query = ["coding", "coding].
We return ["null", "true"] as coding is present in the trie after 1st operation.

You are given a circular array 'a' of length 'n'.

A circular array is an array in which we consider the first element is next of the last element. That is, the next element of 'a[n - 1]' is 'a[0]'.

Find the Next Greater Element(NGE) for every element.

The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.

If no greater elements exist to the right of 'x', consider the next greater element as -1.

Example:

Input: 'a' = [1, 5, 3, 4, 2]

Output: NGE = [5, -1, 4, 5, 5]

Explanation: For the given array,

- The next greater element for 1 is 5.

- There is no greater element for 5 on the right side. So we consider NGE as -1.

- The next greater element for 3 is 4.

- The next greater element for 4 is 5, when we consider the next elements as 4 -> 2 -> 1 -> 5.

- The next greater element for 2 is 5, when we consider the next elements as 2 -> 1 -> 5.

Design and implement a Least Frequently Used(LFU) Cache, to implement the following functions:

1. put(U__ID, value): Insert the value in the cache if the key(‘U__ID’) 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 frequently used item before inserting the new item.

2. get(U__ID): Return the value of the key(‘U__ID’),  present in the cache, if it’s present otherwise return -1.

Note:

  1) The frequency of use of an element is calculated by a number of operations with its ‘U_ID’ performed after it is inserted in the cache.

  2) If multiple elements have the least frequency then we remove the element which was least recently used. 

You have been given ‘M’ operations which you need to perform in the cache. Your task is to implement all the functions of the LFU cache.

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

Example:

We perform the following operations on an empty cache which has capacity 2:

When operation 1 2 3 is performed, the element with 'U_ID' 2 and value 3 is inserted in the cache.

When operation 1 2 1 is performed, the element with 'U_ID' 2’s value is updated to 1.  

When operation 2 2 is performed then the value of 'U_ID' 2 is returned i.e. 1.

When operation 2 1 is performed then the value of 'U_ID' 1 is to be returned but it is not present in cache therefore -1 is returned.

When operation 1 1 5 is performed, the element with 'U_ID' 1 and value 5 is inserted in the cache. 

When operation 1 6 4 is performed, the cache is full so we need to delete an element. First, we check the number of times each element is used. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1-time operation of type 1). Element with 'U_ID' 1 is used 1 time (1-time operation of type 1). So element with 'U_ID' 1 is deleted. The element with 'U_ID' 6 and value 4 is inserted in the cache.