SDE - 1

Given an array “A” of positive integers. Your task is to make the largest number possible formed by concatenating each of the array elements exactly once.

Example:

Let's say the given array is [ 9, 98, 7].

All the possible numbers formed by concatenating each of the array elements are 7989,7998,9879,9897,9987,9798. Among the six numbers, 9987 is the greatest number. Hence the answer is 9987.

Given an integer array ‘arr’ of length ‘n’, return the number of longest increasing subsequences in it.

The longest increasing subsequence(LIS) is the longest subsequence of the given sequence such that all subsequent elements are in strictly increasing order.

Example:

Input: ‘n’ = 5, ‘arr’ = [50, 3, 90, 60, 80].

Output: 2

Explanation: 
In this array, the longest increasing subsequences are [50, 60, 80] and [3, 60, 80]. 

There are other increasing subsequences as well, but we need the number of the longest ones. Hence the answer is 2.

There is a cache that can hold up to ‘N’ elements. Initially, it is empty. There are two types of operations:-

Operation 1: [ 1 ‘U_ID’ ‘VAL’ ] - where 1 represents an insert/update operation is being performed in the cache.

If the element with a particular ‘U_ID’ already exists in cache:
 - Update its mapped value with ‘VAL’. 

If it does not exist and the cache is not full then 
 - Simply insert this element. 

If it does not exist and the cache is already full then 
 - We remove an element and insert this element into the cache. The element to be removed is selected as the least frequently used element.

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. 

Operation 2: [ 2 'UID' ] - where 2 represents, mapped value of this 'UID'

If present in cache otherwise return -1.

You have been given ‘M’ operations which you need to perform in the cache. Your task is to return a vector/list that contains the answer of all the operations of type 2 and in the order in which they were asked.

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 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. 

After years of research, Ninja is finally able to invent the time machine, and now he is back to the good old days when T9 keypads were being used in mobile phones.

Being a curious person, Ninja wants to find out all possible strings that can be formed by pressing the keys of the phone.

Formally, you are given a string S, that consists of digits from 2-9 (both inclusive), your task is to find out all the possible strings that can be formed from the input string by mapping the digits to the letters as in a T9 keypad. Then, print the strings in a lexicographically sorted order.

For Example:

If S = “34”, then all the possible letters that can be formed from string S are {“dg”, “dh”, “di”, “eg”, “eh”, “ei”, “fg”, “fh”, “fi”}.

You are given an array containing ‘N’ words. For each word, you need to find its shortest prefix which can uniquely identify it. For example “abcd” and “abdc” both have the prefix “ab” in common so we can’t uniquely find a word using the prefix “ab”. To uniquely identify both the words we need the prefix “abc” from “abcd” and “abd” from “abdc”.

Note:

You can assume that the words are unique. It means that it is always possible to find a unique prefix for each word.

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

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.

He jumped on my projects. I explained to him and answered all the follow-up questions
After sharing the link to the 1MG website and asked me to design DB for it. He gave me 5-10 min to think and design DB.
Finally, in the end, he asked me standard HR-type questions like where do you see yourself in 2 years, a startup with 2X salary or a stable company with X salary, why you want to join us, etc.