SDE - Intern

The interviewer gave me a random question Rate Limiter in which I had to design the Rate Limiter in which a unique customer can ping into a website only at max 2 times in 1 second. The input was given in form of vector pair in which the first was representing the customer id and the second was the time in which he logged in (milliseconds) we have to return a vector of boolean values telling whether the following i-th input is true or false. Time was 1 hr.

Project Discussion.

Previous internships experience.

The Ninjas of Ninjaland are very excited about their annual Ninja Festival, which is about to happen. So this time, they decided to paint their house such that exactly the ‘M’ neighbourhood group could be formed.

A Neighbourhood group is a continuous group of houses having the same color. For example, if the colors of house is [2,2,2,3,1,1,1]. There exist 3 neighbourhood groups [2,2,2], [3], [1,1,1].

You are given a 2-D array ‘COST’ where COST[i][j-1] denotes the cost for painting the i’th house with j’th color. There are ‘N’ houses and ‘K’ colours available for painting these houses.

You are given a ‘HOUSES’ array where ‘HOUSES[i]’ denotes the current colour of i’th house. If HOUSES[i] = 0, it means that the house is not coloured, so Ninja has to colour it. Otherwise, the already painted houses should not be painted again. Your task is to find the minimum cost for colouring these houses so that exactly ‘M’ neighbourhood groups can be formed if it is impossible to paint them in this manner, print -1.

For Example

If the given ‘HOUSES’ array is [0,2,1,2,0] and ‘COST’ array is [ [1,7],[1,1],[1,1],[1,1],  [5,1] ] and ‘M’ = 3. 
 The minimum cost will be 7+1 =8. We will colour the first house with colour 2 and the last house with colour 1.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

Let the array = [ 4, 2, 1, 5, 3 ]
Let pivot to be the rightmost number.

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

Write a program to do basic string compression. For a character which is consecutively repeated more than once, replace consecutive duplicate occurrences with the count of repetitions.

Example:

If a string has 'x' repeated 5 times, replace this "xxxxx" with "x5".
The string is compressed only when the repeated character count is more than 1.

Note:

Consecutive count of every character in the input string is less than or equal to 9. You are not required to print anything. It has already been taken care of. Just implement the given function and return the compressed string.