SDE - 1

There is a one-dimensional garden of length 'N'. On each of the positions from 0 to 'N', there is a fountain, and this fountain’s water can reach up to a certain range as explained further. In other words, there are 'N' + 1 fountains located at positions 0, 1, 2, 3, …. 'N' which can be activated in the garden.

You are given an integer 'N' and an array/list 'ARR' of length 'N' + 1, where each index of the array denotes the coverage limit of a particular fountain.

A fountain at index 'i' can water the area ranging from the position 'i' - 'ARR'['i'] to 'i' + 'ARR'['i'].

Your task is to find the minimum number of fountains that have to be activated such that the whole garden from position 0 to 'N' has access to the water from at least some fountain.

Note:

1. 0-based indexing is used in the array.
2. We only care about the garden from 0 to 'N' only. So if i - 'ARR'['i'] < 0 or i + 'ARR'['i'] > 'N', you may ignore the exceeding area.
3. If some fountain covers the garden from position 'A' to position 'B', it means that the water from this fountain will spread to the whole line segment with endpoints 'A' and 'B'.

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').

You are given an array/list ‘arr’ of size ‘N’. Find the maximum sum of the elements of the array you can obtain after flipping the sign of exactly ‘K’ elements

For example :

Let arr = [-2, 0, 5, -1, 2]
and K = 4

We will output 10 as we replace -2 by 2, -1 by 1, 0 by 0, and 0 by 0.

Note :

We can apply the flip operation to the same element multiple times

You are given an array consisting of N positive integers, your task is to count the number of distinct possible values that can be obtained by taking the bitwise OR of the elements of all possible subarrays of the given array

Note:

1) A subarray is a part of the array which is contiguous (i.e. elements in the original array occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of the array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
2) Bitwise OR operation takes two numbers and performs OR operation on every bit of those two numbers. For example, consider two numbers 2 and 3 their bitwise OR will be 3. Because the binary representation of 2 is 10 and the binary representation of 3 is 11. And OR of 10 and 11 will be 11 which evaluates to 3.
3) The array may contain duplicate elements.

You are given a graph with 'N' vertices numbered from '1' to 'N' and 'M' edges. You have to colour this graph in two different colours, say blue and red such that no two vertices connected by an edge are of the same colour.

Note :

The given graph may have connected components.

• The interviewer was a knowledgeable man and had excellent knowledge in every field. He always demanded exact answers.
• The round started with my resume walk-through. Then came open-ended questions followed by a system design question in which I failed miserably.