SDE - 1

You are given an array consisting of 'N' positive integers where each integer is either 0 or 1 or 2. Your task is to sort the given array in non-decreasing order.

Note :

1. The array consists of only 3 distinct integers 0, 1, 2.
2. The array is non-empty.

You’re given an array/list 'ARR' of N elements, where each element is at most K away from its target position(Position if the array was sorted). Now, your task is to devise an algorithm that sorts the given array in O(N log K) time.

For example:

Let us consider 'K' is 3, an element at index 4 in the sorted array, can be at indexes 1, 2, 3, 4, 5, 6, 7 in the given array, because the absolute difference of all these indices with 4 is at most 3.

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Given an array of integers ‘arr’ of size ‘n’ and an integer ‘k’. You need to find the count of distinct elements in every sub-array of size ‘k’ in the given array. Return an integer array ‘count’ that consists of n - k + 1 integers where ‘count[i]’ is equal to the number of distinct elements in a sub-array of size ‘k’ starting from index ‘i’.

Note:

1. The sub-array of an array is a continuous part of the array.
2. Consider ‘0’ based indexing.
3. ‘k’ will always be less than or equal to ‘n’.
3. Don’t print anything, just return the integer array ‘count’.

What are your strengths and weaknesses?
Why do you want to work at our company?
What is the difference between confidence and over confidence?