SDE - Intern

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes he encoded each character of the string to its numeric value, that is, A = 1, B = 2, C = 3, till Z = 26 and combined them as a single sequence (SEQ) of digits of length N. Let's say the message was "LA", Ninja encoded it as 121 for L=12 and A=1.

Today, when he read the encoded secret message, he realised that he was not able to decode the original string. So, the Ninja is wondering in how many ways he can decode the numeric sequence to some valid string.

A valid string is a string with characters from A to Z and no other characters.

Example:

Let the encoded sequence be 121,

The first way to decode 121 is:
1 = A
2 = B
1 = A
Thus, the decoded string will be ABA.

The second way to decode 121 is:
12 = L
1 = A
Thus, the decoded string will be LA.

The third way to decode 121 is:
1 = A
21 = U
Thus, the decoded string will be AU.

So, there will be 3 ways to decode the sequence 121 i.e. [(ABA), (LA), (AU)].

Note:

The input sequence will always have at least 1 possible way to decode.    

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up:

Can you solve this using constant extra space?

Bob has been given a binary tree having N nodes. He has been asked to check if all the leaf nodes are at the same level.

Your task is to help Bob in checking if all the leaf nodes are at the same level or not. Return true if all the leaf nodes are at the same level otherwise return false.

A binary tree is a hierarchical data structure in which each node has at most two children.

Any node whose left and right child are null is called a leaf node in a binary tree.

Example:

Consider the given binary tree:

For the given tree the leaf nodes are 5, 4, 7, 6. All these nodes are on the same level. So the output will be True. 

You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the given array/list.

Note:

A subsequence of an array/list is obtained by deleting some number of elements (can be zero) from the array/list, leaving the remaining elements in their original order.

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.

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way: 

In first walk, the person toggles every door 

In second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, … 

In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, …

In 100th walk, the person toggles 100th door. 

Which doors are open in the end? 

Tell the difference between Mutex and semaphores.

What is Indexing, why it is done and explain all the types of Indexing?

Given employee and dept table find the no of employees in each dept(Question on Joins).

Difference between function overloading and function overriding with example. And also about runtime and compile time binding while overriding.