SDE - Intern

You have been given an undirected star graph in the form of Adjacency List 'EDGES', consisting of ‘N’ nodes labelled from 1 to ‘N’. A star graph is a graph where there is one centre node and exactly ‘N’ - 1 edges that connect the centre node to every other node.

You are given a matrix ‘EDGES’ storing the information about the edges, where each row, ‘EDGES[i]’ contains two integers ‘U’ and ‘V’, which implies that there is an undirected edge between ‘U’ and ‘V’.

For Example :

For the given graph:

Node 1 is connected to all other nodes. Hence node 1 is the centre of this star graph.

You are given an array “nums” of size N. Your task is to find the length of the longest subsequence of array “nums” such that the absolute difference between every adjacent element in the subsequence is one.

For Example:

If “nums” = {2, 1, 3}.

The valid non-empty subsequences of the array are {2}, {1}, {3}, {2, 1}, {1, 3}, {2, 3} and {2, 1, 3}. So, the longest subsequence satisfying the given conditions are {2, 1} and {2, 3}. The length of the longest subsequence is 2. So, the answer is 2.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “nums” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

Note:

Any subsequence of length = 1 is also a valid subsequence.

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.

We had a detailed discussion on the project that i mentioned in my resume like what technologies I used, why I choose these technologies, what difficulties i faced etc. I was also asked to present my project and they some questions regarding the platforms on which i have deployed my website and the other options on which I can deploy it.

What are 4 pillars of OOPS and explain them?
What are different types of inheritance?
What is the role of access specifiers in encapsulation?

Give a introduction of yourself. 

Tell about some of the achievements in college? 

Have you worked in a team project and if yes, please share the experience. 

What are you strengths and weakness? 

Do you have any questions for us?