Software Development

You are given an array consisting of N positive integers, and your task is to sort the array in decreasing order of count of set bits in the binary representation of the integers present in the array.

In other words, you have to modify the array such that an integer with more number of set bits should appear before the integer which has lesser number of set bits in its binary representation.

The number of set bits is nothing but the number of 1s present in the binary representation of the integer. For example, the number of set bits in 5(0101) is equal to 2.

Note :

1. If any two numbers have the same count of set bits, then in the sorted array they will appear in the order in which they appear in the original array. For example, let the array be { 2, 4, 3}, in this case, both 2 and 4 have the same number of set bits so the answer will be {3, 2, 4} and not {3, 4, 2}, because in the original array 2 appears before 4.

2. The array may contain duplicate elements.

You are given a string 'S' containing dots(.) and asterisks(*) only, where the dot represents free spaces, and the asterisk denotes lamps. A lamp can lighten up its own cell as well as its immediate neighboring cells. You need to determine the minimum number of extra lamps that have to be installed at some free spaces in the string so that the whole string will be illuminated i.e. all the indices of the string can have access to the light of some lamp.

Note :

If a lamp is present at index 'I', then it illuminates index 'I' - 1, 'I' and 'I' + 1.

If a lamp is present at index 0, then it illuminates only 0 and 1.

Given that the length of the string is greater than or equal to 2.

If a lamp is present at the last index, then it illuminates the last and the second last index, given that the length of the string is greater than or equal to 2.

The length of each string is guaranteed to be at least 1.

You are given ‘N’ binary tree nodes numbered from 0 to N - 1 where node ‘i’ has two children LEFT_CHILD[i] and RIGHT_CODE[i]. Return ‘True’ if and only if all the given nodes form exactly one valid binary tree. If node ‘i’ has no left child then 'LEFT_CHILD[i]' will equal -1, similarly for the right child.

Example:

Let’s say we have n=4 nodes, 'LEFT_CHILD' = {1, -1, 3, -1} and 
RIGHT_CHILD = {2, -1, -1, -1}. So the resulting tree will look like this:

It will return True as there is only one valid binary tree and each node has only one parent and there is only one root.

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?