Happy Numbers

What is an happy number can be shown in the following example:

19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

http://www.programcreek.com/2014/04/leetcode-happy-number-java/
http://getprogramcode.com/2013/12/java-program-to-check-for-a-happy-number/

Match two board configurations of tic-tac-toe problem

How will you match two board configurations of tic-tac-toe problem?

Strategy:

This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills.
The trick in this question is that any board configuration is rotation invariant and what we mean by that is

all three the configurations shown above are similar and must match in the logic we use for checking board configurations.

Any given configuration of the board can have 7 other configurations which will be identical to it in terms of rotation invariance. These can be obtained by rotating the matrix either left or right 4 times. And then taking the mirror image of the matrix and again rotating it.

So the entire problem breaks down to reducing the first board configuration to matrix and then rotating it one by one and matching it with the other configuration.
Rotation of the elements of a matrix can be done in multiple ways and we are going to discuss two methods here.
Method 1: Given a matrix we can take it's transpose and to rotate it left exchange the rows and to rotate right, exchange the columns.

           1) original matrix

             1 2 3

             4 5 6

             7 8 9

           2) transpose

             1 4 7

             2 5 8

             3 6 9

           3-a) change rows to rotate left

             3 6 9

             2 5 8

             1 4 7

           3-b) or change columns to rotate right

             7 4 1

             8 5 2

             9 6 3

Method 2: We can use the following pesudo-code which directly does the work which is being done while taking transpose and exchanging columns. This works for a given square matrix A of dimension NxN

  for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

Bit stream has an alternating pattern or not

Write a function that returns true if the bit stream has an alternating pattern.
For example 000000101010 would return true and 0000001010000 would return false. Also write test cases for the function.

Strategy:

bool patternCheck(int a)
{
int b=a>>1;
/*if a=000000101010 then b=0=00000010101,,,,rightshift of a by 1*/
//now xor of a and b
int n=(a^b)+1;//n is in 2^n format if alternate bits are there
if(n & (n-1)) == 0) return true;
return false;
}

Draw a circle

Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all

Mirror Puzzle !

Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?

Convert unknown base to decimal

Given an integer, write a program that converts the given number to a number (in base 10). The base of the given number is unknown.

Strategy:
The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3, 4, 5 - or base 6. 

Working on this assumption, it becomes fairly simple to code a function that will return a number for the given string representation of the number. The following JAVA code sample does the same, extending the above assumption to include digits 0 to 9 and characters A to Z, where A represents 10, B represents 11 and so on.

Code:

public Double convertUnknownBaseNumberToBase10(String number) {
  // null check
  if(number == null || number.length() == 0) {
   return null;
  }
 
  // turn to upper case - so that our logic below is easy
  number = number.toUpperCase();

  // scan through the string to find out the maximum number or the character
  int maxAscii = 0;
  for(int i = 0; i < number.length(); i++) {
   int ascii = number.charAt(i);
   if(!(((ascii >= '0') && (ascii <= '9')) || ((ascii >= 'A') && (ascii <= 'Z')))) {
    System.out.println("Illegal number, can have only digits (0-9) and letters (A-Z)");
    return null;
   }
   maxAscii = Math.max(ascii, maxAscii);
  }
 
  // check if the number has letters or not
  double finalNumber = 0;
  int length = number.length();
  if(maxAscii >= 'A') {
   int maxNumber = maxAscii - 'A' + 10 + 1;
   for(int i = 0; i < length; i++) {
    int charCode = number.charAt(i);
    if(charCode >= 'A') {
     charCode = charCode - 'A' + 10;
    }
    int num = charCode;
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  } else {
   int maxNumber = maxAscii - '0' + 1;
   // just iterate over a normal loop
   for(int i = 0; i < length; i++) {
    int num = number.charAt(i) - '0';
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  }
 
  return finalNumber;
 }

50 Trucks with Payload

 Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.

Trailing zeros in 100!

Question: How many zeros are there in 100! (100 factorial)?

Strategy:
A trailing zero is formed when a multiple of 5 is multiplied with a multiple of 2. Now all we have to do is count the number of 5′s and 2′s in the multiplication.
Let’s count the 5′s first. 5, 10, 15, 20, 25 and so on making a total of 20. However there is more to this. Since 25, 50, 75 and 100 have two 5′s in each of them (25 = 5 * 5, 50 = 2 * 5 * 5, …), you have to count them twice. This makes the grand total 24. For people who like to look at it from a formula point of view

Number of 5′s = 100/5 + 100/25 + 100/125 + … = 24 (Integer values only)

Moving on to count the number of 2′s. 2, 4, 6, 8, 10 and so on. Total of 50 multiples of 2′s, 25 multiples of 4′s (count these once more), 12 multiples of 8′s (count these once more) and so on… The grand total comes out to

Number of 2′s = 100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 + 100/128 + … = 97 (Integer values only)

Each pair of 2 and 5 will cause a trailing zero. Since we have only 24 5′s, we can only make 24 pairs of 2′s and 5′s thus the number of trailing zeros in 100 factorial is 24.

All possible combination of digits

Find all possible combination of digits ranging 1 to 9 whose sum is 10
No digit should be repeated in any combination.

1234
127
136
145
19
235
28
37
46

Find Next Higher Number With Same Digits

Given a number, find the next higher number using only the digits in the given number. For example if the given number is 12543, next higher number with same digits is 13245.

Strategy:

Simple without thinking :Generate the numbers with all digit permutations and sort them. Then find the given number in the sorted sequence and return the next number in sorted order.
The complexity of this approach is pretty high though, because of the permutation step involved. A given number N has logN+1 digits, so there are O(logN!) permutations. After generating the permutations, sorting them will require O(logN!loglogN!) operations. We can simplify this further, remember that O(logN!) is equivalent to O(NlogN). And O(loglogN!) is O(logN). So, the complexity is O(N(logN)^2).

Efficient thinking:
Let’s visualize a better solution using an example, the given number is 12543 and the resulting next higher number should be 13245.
Step 1:We scan the digits of the given number starting from the tenths digit (which is 4 in our case) going towards left. At each iteration we check the right digit of the current digit we’re at, and if the value of right is greater than current we stop, otherwise we continue to left. So we start with current digit 4, right digit is 3, and 4>=3 so we continue. Now current digit is 5, right digit is 4, and 5>= 4, continue. Now current is 2, right is 5, but it’s not 2>=5, so we stop. The digit 2 is our pivot digit.

Step 2:From the digits to the right of 2, we find the smallest digit higher than 2, which is 3.We swap this digit and the pivot digit, so the number becomes 13542. Pivot digit is now 3. We sort all the digits to the right of the pivot digit in increasing order, resulting in 13245.So we got the answer!

Improvement:
We can also reverse the elements from the point we place the next highest or equal number with the current number.This way we can avoid sorting. But we should also be careful during swapping, for example if the original number is 136442. We’ll swap the pivot 3 with 4, and which 4 we swap with is important if we’re going to reverse later. We should swap with the rightmost one, otherwise we won’t get the next higher number.
Time complexity:O(n)

Note:

If the digits of the given number is monotonically increasing from right to left, like 43221 then we won’t perform any operations, which is what we want because this is the highest number obtainable from these digits.The same case occurs when the number has only a single digit, like 7. We can’t form a different number since there’s only a single digit.

Complexity: O(n)

The complexity of this algorithm also depends on the number of digits, and the sorting part dominates. A given number N has logN+1 digits and in the worst case we’ll have to sort logN digits. Which happens when all digits are increasing from right to left except the leftmost digit, for example 1987. For sorting we don’t have to use comparison based algorithms such as quicksort, mergesort, or heapsort which are O(KlogK), where K is the number of elements to sort. Since we know that digits are always between 0 and 9, we can use counting sort, radix sort, or bucket sort which can work in linear time O(K). So the overall complexity of sorting logN digits will stay linear resulting in overall complexity O(logN). This is optimal since we have to check each digit at least once.

maximum subset of Cuboid boxes that can fit into one another

Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*Struct defining cube*/
typedef struct
{
    int l;
    int b;
    int h;
}Cube;

/*Cube compare function */
int cube_compare(const void *x, const void *y)
{
    const Cube *a = x;
    const Cube *b = y;

    if(a->l == b->l)
    {
        if(a->b == b->b)
            return a->h - b->h;

        return a->b - b->b;
    }
    return a->l - b->l;

}

/*Struct to hold successor info*/
typedef struct
{
    int next;
    int chainLength;
}Successor;


/*Checks whether cube 'a' fits into cube 'b' */
inline int cube_fits(Cube *a , Cube *b)
{
    return (a->l < b-> l)  && (a->b < b->b) && (a->h < b->h);
}

/*Prints all the cubes which fits into one another */
void max_fit_cubes(Cube cubes[], int n)
{

    //Fill the chain
    Successor nextCube[n];

    memset(nextCube, 0, sizeof(nextCube));

    int i = n - 1, j;

    while(i--)
    {
        for(j = i + 1; j < n; j++)
        {
            if(cube_fits(cubes + i, cubes + j))
            {
                if((nextCube[j].chainLength + 1) > nextCube[i].chainLength)
                {
                    nextCube[i].chainLength = nextCube[j].chainLength + 1;
                    nextCube[i].next = j;
                }
            }
        }
    }

    //find the max chain
    int m = i = n - 1;

    while(i--)
    {
        if(nextCube[i].chainLength > nextCube[m].chainLength)
            m = i;
    }


    //Now print the max chain

    printf("Max Chain Length: %d, m: %d\n", nextCube[m].chainLength, m);

    do
    {
        printf("(%d,%d,%d) =>", cubes[m].l, cubes[m].b, cubes[m].h);
        m = nextCube[m].next;
    }while(m);

    printf("\n");
}

int main()
{
    int n;

    scanf("%d", &n);

    Cube cubes[n];

    int i;

    for(i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &(cubes[i].l), &(cubes[i].b), &(cubes[i].h));
    }

    qsort(cubes, n, sizeof(Cube), cube_compare);

    max_fit_cubes(cubes, n);
    return 0;
}

Programming Puzzles

The following links are useful for programming teasers / simple puzzles.

http://www.coderanch.com/forums/f-71/Programming
http://www.geekinterview.com/talk/brainteasers/

BIT Manipulation puzzles

Convert number 2 --> 37 without using any other operator but bitwise ? 

Solution:
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
   int x = 2;
    printf("X before :%d\n",x);
    x = (x<<x<<x) |  x<<!!x | !!x ;
    printf("X After  :%d\n",x);
     getchar();
     return(0);
} 

Scan for a bit pattern in a stream of bits

We need to scan for a 16 bit word in a bit stream. It is not guaranteed to be aligned on byte or word boundaries.
There are various brute force methods; using tables and/or shifts.But what is the best way to do this ?

Find parity of an unsigned integer

Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.

Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.

Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

Example:
 Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1

Code:

# include <stdio.h> # define  bool int bool getParity(unsigned int n) {     bool parity = 0;     while (n)     {         parity = !parity;         n      = n & (n - 1);     }            return parity; } int main() {     unsigned int n = 7;     printf("Parity of no %d = %s",  n,              (getParity(n)? "odd": "even"));           getchar();     return 0; }

Above solution can be optimized by using lookup table.
Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).
Uses: Parity is used in error detection and cryptography.

Representation of things in memory

How does the computer store things in Memory

You probably know that everything on a computer is stored as strings of bits (binary digits; you can think of them as lots of little on-off switches). Here I'll explain how those bits are used to represent the letters and numbers that your computer is crunching.

Word Size :-
Before we can go into this, you need to understand about the word size of your computer. The word size is the computer's preferred size for moving units of information around; technically it's the width of your processor's registers, which are the holding areas your processor uses to do arithmetic and logical calculations. When people write about computers having bit sizes (calling them, say, "32-bit" or "64-bit" computers), this is what they mean.

The computer views your memory as a sequence of words numbered from zero up to some large value dependent on your memory size. That value is limited by your word size, which is why programs on older machines like 286s had to go through painful contortions to address large amounts of memory.

Numbers

Integer numbers are represented as either words or pairs of words, depending on your processor's word size. One 64-bit machine word is the most common integer representation.
Integer arithmetic is close to but not actually mathematical base-two. The low-order bit is 1, next 2, then 4 and so forth as in pure binary. But signed numbers are represented in twos-complement notation. The highest-order bit is a sign bit which makes the quantity negative, and every negative number can be obtained from the corresponding positive value by inverting all the bits and adding one. This is why integers on a 64-bit machine have the range -2⁶³ to 2⁶³ - 1. That 64th bit is being used for sign; 0 means a positive number or zero, 1 a negative number.
Some computer languages give you access to unsigned arithmetic which is straight base 2 with zero and positive numbers only.
Most processors and some languages can do operations in floating-point numbers (this capability is built into all recent processor chips). Floating-point numbers give you a much wider range of values than integers and let you express fractions. The ways in which this is done vary and are rather too complicated to discuss in detail here, but the general idea is much like so-called ‘scientific notation’, where one might write (say) 1.234 * 10²³; the encoding of the number is split into a mantissa (1.234) and the exponent part (23) for the power-of-ten multiplier (which means the number multiplied out would have 20 zeros on it, 23 minus the three decimal places).

Characters

Characters are normally represented as strings of seven bits each in an encoding called ASCII (American Standard Code for Information Interchange). On modern machines, each of the 128 ASCII characters is the low seven bits of an octet or 8-bit byte; octets are packed into memory words so that (for example) a six-character string only takes up two memory words. For an ASCII code chart, type ‘man 7 ascii’ at your Unix prompt.
The preceding paragraph was misleading in two ways. The minor one is that the term ‘octet’ is formally correct but seldom actually used; most people refer to an octet as byte and expect bytes to be eight bits long. Strictly speaking, the term ‘byte’ is more general; there used to be, for example, 36-bit machines with 9-bit bytes (though there probably never will be again).
The major one is that not all the world uses ASCII. In fact, much of the world can't — ASCII, while fine for American English, lacks many accented and other special characters needed by users of other languages. Even British English has trouble with the lack of a pound-currency sign.
There have been several attempts to fix this problem. All use the extra high bit that ASCII doesn't, making it the low half of a 256-character set. The most widely-used of these is the so-called ‘Latin-1’ character set (more formally called ISO 8859-1). This is the default character set for Linux, older versions of HTML, and X. Microsoft Windows uses a mutant version of Latin-1 that adds a bunch of characters such as right and left double quotes in places proper Latin-1 leaves unassigned for historical reasons.
Latin-1 handles western European languages, including English, French, German, Spanish, Italian, Dutch, Norwegian, Swedish, Danish, and Icelandic. However, this isn't good enough either, and as a result there is a whole series of Latin-2 through -9 character sets to handle things like Greek, Arabic, Hebrew, Esperanto, and Serbo-Croatian.
The ultimate solution is a huge standard called Unicode (and its identical twin ISO/IEC 10646-1:1993). Unicode is identical to Latin-1 in its lowest 256 slots. Above these in 16-bit space it includes Greek, Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lao, Georgian, Tibetan, Japanese Kana, the complete set of modern Korean Hangul, and a unified set of Chinese/Japanese/Korean (CJK) ideographs.
Recent versions of Linux use an encoding of Unicode called UTF-8. In UTF, characters 0-127 are ASCII. Characters 128-255 are used only in sequences of 2 through 4 bytes that identify non-ASCII characters.

Subsets without consecutive elements

Consider a set S of the first 10 natural numbers.Find the number of subsets that do not contain consecutive elements.

Strategy:

The question is based on pure calculation and some combinatorics.
Subsets of length 0 = 1
Subsets of length 1 = 10
These two cases are straight forward.
Subsets of length 2 =
number of ways we can pick two numbers out of 10 - number of ways in which we can pick two adjacent numbers
10 C 2 - 9
45-9=36
Subsets of length 3 =
the number of ways we can pick 3 numbers out of 10 - number of ways we can pick 3 numbers having 2 adjacent numbers - number of combinations where all 3 are adjacent i.e.
10 C 3 - 56 - 8
the latter case is simple but think over why number of combinations that have two adjacent numbers are 56, there are two special cases to be considered, one where adjacent numbers are in between like 5,6 and the other where they are at boundary i.e. 0,1
similarly
Subsets of length 4 = 35
Subsets of length 5 = 6
We cannot go beyond this because then we will have atleast 2 adjacent numbers.
The total comes out to be 144

Print all sequences of a given length

Given two integers k and n, write a function that prints all the sequences of length k composed of numbers 1,2..n. You need to print these sequences in sorted order.
Examples:

Input: k = 2, n = 3

Output:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Input:  k = 3, n = 4

Output:
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
.....
.....
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4

10 Coins Puzzle

You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which. How do you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.

Solution:

Make 2 piles with equal number of coins. Now, flip all the coins in one of the pile.

How this will work? lets take an example.

So initially there are 5 heads, so suppose you divide it in 2 piles.

Case:

P1 : H H T T T

P2 : H H H T T

Now when P1 will be flipped

P1 : T T H H H

P1(Heads) = P2(Heads)

Another case:

P1 : H T T T T

P2 : H H H H T

Now when P1 will be flipped

P1 : H H H H T

P1(Heads) = P2(Heads)

Stairs and rabbit

A rabbit sits at the bottom of a staircase with n stairs.rabbit can hop up only one or two stairs at a time.how many different ways are there two reach at top of stair.