The Magic HackerEarth Nirvana solutions Hiring Challenge

Navi got a task at school to collect N stones. Each day he can collect only one stone. As N can be a very large number so it could take many days to complete the task, but then he remembers that his mother gave him a magic that can double anything (i.e if he has 2 stones, the magic will make them to 4 stones). Navi can use this magic any number of time on the collected stone on a particular day and add this to the previously collected stones. Remember that he wants exactly N stones and he can't throw any stone. If he gets more than N stones then he gets 0 marks, of course he doesn't want 0 marks. Help him to collect exactly N stones in minimum number of days.

Input

First line of input will contain number of test cases (T). Then next T lines contains a single number N, which is number of stones Navi has to collect.

Output

For each test case, Print a single number which is the minimum number of days taken by Navi to complete the task.

Constraints

1 <= T <= 10^5

0 <= N <= 10^9

Check if an array has duplicate numbers in O(n) time and O(1) space

We have array  a[ ]= {1, 2, 3, 4, 5, 6, 7, 8, 4, 10};
And we need to find a number which is duplicate in O(n) and Space complexity O(1)

Practo Hiring Experience

Started from Written Test on HackeEarth

1) http://www.hackerearth.com/problem/algorithm/divide-to-three-33/
Code Solution Click : http://ideone.com/7M1o9j
2) http://www.hackerearth.com/problem/algorithm/good-times-vs-bad-times-3/
Code Solution Click : http://ideone.com/xj7o49

Maximum of all subarrays of size k

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
SubArray : [1,2,3] , [2,3,1], [3,1,4] .....
Output :
3 3 4 5 5 5 6

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Example : 00001111
Output : 4

Method 1 : in O(n) we can do it . with sequential search.

Method 2 : Binary search.
Yes binary search is useful, as data is sorted.
Just we need to change its conditions for 0 and 1.
lets have a look at Function firstOccurance.

Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance k from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

           [1]
          /   \
       [2]     [3]
      /  \     /  \
    [4]  [5] [6]  [7]
    /
  [8]

Here Output should be 1, and 2 for K=2 as both are at 2 distance from leaf nodes.
1 is at K=2 distance from 5 and  2 is K=2 distance from 8.

TicTacToe Game As Asked in Flipkart

Write a running code in any language to implement the famous tic-tac-toe game.
Decide which basic functions which would be required to implement the same. 

Then try to code it your self else basic code is given. below

Get Minimum element in O(1) from input numbers

Question : Get Minimum element in O(1) from input numbers..

- With any traditional way we can't get minimum element in O(1)
- so we need to come up with different data structure.
- As its very old and famous question We are directly explaining logic

Find min element in Sorted Rotated Array (With Duplicates)

Problem: Find the minimum element in a sorted and rotated array if duplicates are allowed:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2}   output: 0
Algorithm:

CodeChef Code SGARDEN

This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand.
Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.
Now the Sheriff asks the question: How many times has he whistled?

Find Percentage of Words matching in Two Strings

There are two strings s1 and s2. Find the maximum of percentage word matching from s1 to s2 and s2 to s1.

Where, percentage word matching= (Total words matched in s2/total number of words in s1) *100

CodeChef' RRCOPY

Def: 
You had an array of integer numbers. You also had a beautiful operations called "Copy-Paste" which allowed you to copy any contiguous sub-sequence of your array and paste it in any position of your array. For example, if you have array [1, 2, 3, 4, 5] and copy it's sub-sequence from the second to the fourth element and paste it after the third one, then you will get [1, 2, 3, 2, 3, 4, 4, 5] array. You remember that you have done a finite(probably zero) number of such operations over your initial array and got an array A as a result. Unfortunately you don't remember the initial array itself, so you would like to know what could it be. You are interested by the smallest such array. So the task is to find the minimal size(length) of the array that A can be obtained from by using "Copy-Paste" operations.