SDE - 1

You are given an M X N matrix of integers ARR. Your task is to find the maximum sum rectangle.

Maximum sum rectangle is a rectangle with the maximum value for the sum of integers present within its boundary, considering all the rectangles that can be formed from the elements of that matrix.

A rectangle is a 2-D polygon with opposite sides parallel and equal to each other.

For example:

Consider following matrix:

 1  2 -1 -4 -20
-8 -3  4  2   1
 3  8  10 1   3
-4 -1  1  7  -6

The rectangle (1,1) to (3,3) is the rectangle with the maximum sum, i.e. 29.

 1   2 -1 -4  -20
-8 |-3  4  2 |  1
 3 | 8  10 1 |  3
-4 |-1  1  7 | -6

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.

Now the array is rotated at some pivot point unknown to you.

For example, if 'arr' = [ 1, 3, 5, 7, 8], then after rotating 'arr' at index 3, the array will be 'arr' = [7, 8, 1, 3, 5].

Now, your task is to find the index at which ‘k’ is present in 'arr'.

Note :

1. If ‘k’ is not present in 'arr', then print -1.
2. There are no duplicate elements present in 'arr'. 
3. 'arr' can be rotated only in the right direction.

Example:

Input: 'arr' = [12, 15, 18, 2, 4] , 'k' = 2

Output: 3

Explanation:
If 'arr' = [12, 15, 18, 2, 4] and 'k' = 2, then the position at which 'k' is present in the array is 3 (0-indexed).

A string ‘S’ is said to be special if each of its characters is one of the first ‘P’ letters of the English alphabet and ‘S’ doesn't contain any palindrome contiguous substring of length 2 or more. You will be given a special string ‘S’ of length ‘N’, find the lexicographically next special string of the same length, or else state that such string does not exist. Print the output string if it exists, otherwise, print "NO" (without quotes).

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in a continuous fashion also.

Example: Given a string “cba” and ‘P’ equals 3. So, the next strings which are lexicographically bigger than string ‘S’ are “cbb”, “cbc”, “cca”, “ccb” and “ccc” of size 3. But all of them have a palindrome substring of the size at least 2. So, we will return “NO” as output. If the given string is “cbd” and ‘P’ equals 4 then the next string will be “cda” and it is special. So, we can return an output here.

Note:

It is guaranteed that the input string is special.

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.

Describe your ideal company, location and job.
What are your career options right now?
Explain how would be an asset to this organization?
What are your outside interests?
Would you lie for the company?