SDE - Intern

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 have been given a binary tree of integers with N number of nodes. Your task is to check if that input tree is a BST (Binary Search Tree) or not.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example :

Answer :

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtrees for node 5 are empty.

Level 3:

For node 1:
The left and right subtrees for node 1 are empty.
For node 3:
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

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?

Ninjas are often known for their will to never give up no matter how fierce the challenge. One such ninja was challenged by another if they could solve a problem to find the Kth number in a list of given elements (array) comprising of only 3, 5 and 7 as their prime factors. Despite the ninja’s strong will to solve the problem, you know that it could be easily solved with the help of knowledge of programming. Since the ninja does not know that you’ll have to devise an algorithm for solving the problem. Your task is to complete the given function which returns that required Kth element from the array.

For Example:

Input: 'K' = 10
Output: 45

The array will contain elements that only have 3, 5 or 7 as their prime factors i.e. of  the following form:-  3,5,7,9,15,21,25,…. Therefore we can see from the above pattern of elements that 45 would be the 10th element in the array which is our  required answer.