SDE - 1

A number ‘X’ is interesting if the binary representation of ‘X’ (without leading zeroes) has exactly two zeroes.

You are given two positive integers, ‘L’ and ‘R’. Your task is to count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ is interesting (i.e., it has exactly two zeroes in its binary representation).

Example :

L = 2, R = 9
All the numbers between L and R and their binary representations are:
X = 2 => 10
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
X = 7 => 111
X = 8 => 1000
X = 9 => 1001
As 4 and 9 are the only numbers with two zeroes in their binary representations, hence the answer is 2.

A number ‘X’ is interesting if the binary representation of ‘X’ (without leading zeroes) has exactly two zeroes.

You are given two positive integers, ‘L’ and ‘R’. Your task is to count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ is interesting (i.e., it has exactly two zeroes in its binary representation).

Example :

L = 2, R = 9
All the numbers between L and R and their binary representations are:
X = 2 => 10
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
X = 7 => 111
X = 8 => 1000
X = 9 => 1001
As 4 and 9 are the only numbers with two zeroes in their binary representations, hence the answer is 2.

You are present at point ‘A’ which is the top-left cell of an M X N matrix, your destination is point ‘B’, which is the bottom-right cell of the same matrix. Your task is to find the total number of unique paths from point ‘A’ to point ‘B’.In other words, you will be given the dimensions of the matrix as integers ‘M’ and ‘N’, your task is to find the total number of unique paths from the cell MATRIX[0][0] to MATRIX['M' - 1]['N' - 1].

To traverse in the matrix, you can either move Right or Down at each step. For example in a given point MATRIX[i] [j], you can move to either MATRIX[i + 1][j] or MATRIX[i][j + 1].

You have been given an array/list 'HEIGHTS' of length ‘N. 'HEIGHTS' represents the histogram and each element of 'HEIGHTS' represents the height of the histogram bar. Consider that the width of each histogram is 1.

You are supposed to return the area of the largest rectangle possible in the given histogram.

For example :

In the below histogram where array/list elements are {2, 1, 5, 6, 2, 3}.

The area of largest rectangle possible in the given histogram is 10.

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.