Area visible outside in a hyper cube

In K-dimensional space, if a hyper cube of size N^k is formed with N^k unit hypercubes, how many hyper cubes are visible from outside?

There is a three dimensional cube of size NxNxN formed with NxNxN cubes. How many cubes are visible from outside?

For example,
In one dimensional space (i.e., in a line), there are two visible points.

In two dimensional space, for 3x3 square, there are 8 squares visible from outside.

In three dimensional space, for 3x3x3 cube, there are 26 cubes visible from outside.

If it is in k-dimensional space, how many hyper cubes are visible?




Answer

The hypercube is in K-Dimensional space. There are two visible sides in each dimension. The length of one side is N. If we remove the two visible cubes that are visible from outside, the remaining length is N-2. If we do the same in all the dimensions, then in all the dimensions, the length would be reduced to N-2. The volume of the remaining is (N-2)^k, and this is not visible. The original volume is N^k. So, the no.of hyper cubes that are visible is N^k - (N-2)^k.

Find whether a number is divisible by 3 or not

Given an array of bits, find out whether the number represented by the binary number is divisible by 3 or not.

If the difference of the no.of 1's in even position and odd position is divisible by 3, then the no.is divisible by 3.

For example, for 18, the binary number is 10010. We can count either from left or right. That will not make any difference. If we count from left, there is one 1 in odd position, and one 1 in even position. The difference is Zero, which is divisible by 3. So, the number 10010 is divisible by 3.

If we take the number 37, the binary number is 100101. The number of 1's in odd position is 1, and the no.of 1's in even position is 2. The difference is 1, and it is not divisible by 3. So, 37 is not divisible by 3.

// Returns non-zero number, if it is divisible. Zero, otherwise. 
int divisible(int array[], int n)
{
   int i, even=0, odd=0;
   for(int i=0; i < n; i++) {
      if(array[i]==1) {
          if(i%2==0)
               even++;
          else 
               odd++;
      }
   }
   return ((even-odd)%3==0);
}

Find the count of the characters in a string

void findChars(char s[])
{
   int count[128];
   int l=strlen(s);
   for(int i=0; i<128; i++)
      count[i]=0;
   for(int i=0; i<l; i++)
      count[s[i]]++;
   for(int i=0; i<128; i++) {
      if(count[i]!=0) 
         printf("%c - %d\n", i, count[i]);
   }
}

River crossing by 3 cannibals and 3 humans

There are three cannibals and three humans need to cross the river, and there is only one boat. There can be only two people at a time while crossing the river. If the number of cannibals become more than number of humans in the bank of the river then they will eat the human. How should they cross the river?

Side 1	Side 2
CCCHHH
CCHH	CH
CCHHH	C
HHH	CCC
HHHC	CC
HC	HHCC
HHCC	HC
CC	HHHC
CCC	HHH
C	HHHCC
CC	HHHC
	HHHCC

Findout the switches for the bulbs

There are three bulbs inside a house of one floor and switches are there in different floor. How will you conclude which switches is for which bulb?

Solution
Switch on one bulb; keep the switch off for another bulb. This way you can detect two bulb’s switch. To find the third one is the trick. Keep the third switch on for some times and then switch it off so that the temperature gets increased for the third bulb and you can detect the switch.

Crossing the bridge by four people

Four people need to cross the bridge in the night time with a single flashlight. The bridge can accommodate two people at a time.
The speed of all the people is different.
A can cross in 1 min
B can cross in 2 min
C can cross in 5 min
D can cross in 10 min
What is the minimum time to cross the bridge?



Solution
A & B cross (2min)
B comes back (2min)
C & D cross (10min)
A comes back (1min)
A & B cross (2min)
Total time=2+2+10+1+2=17min

Let me know if you have better solution.

Increase the probability of picking red and blue balls

You have two bags, 50 red balls and 50 blue balls. How will you arrange the balls in two bags such that probability of picking up red ball is maximum?

There are different ways to keep the balls. If you mix the balls equally then probability would be same for both the balls from both the bags. If you keep different balls in different bag then also probability becomes 50-50 as one bag has 100% chances whereas another has 0% chance.

So in order to increase the probability of picking up red ball, put only one red ball in one bag and rest of the red and blue ball in another bag. So here the probability of picking up a red ball becomes 100% for one bag and approximately 49% for second bag. So the 100%-49% probability is better than other solution of 50%-50% and 100%-0%.
Let me know if you have more optimize solution.

Sudoku Solver

#include <stdio.h>

int row[9],col[9],box[3][3];
int g[9][9];
bool test(int & x,int j) { return (x & (1<<j)) >0 ;}
void set(int & x,int j) { x |= (1<<j) ;}
void unset(int & x,int j) { x &= (~(1<<j)); }
bool doit(int x,int y)
{
 if(x==9) return true;
 if(g[x][y]) return doit(x+(y==8),(y+1)%9);
 for(int i=0; i<9; i++) {
  if(!test(row[x],i) && !test(col[y],i) && !test(box[x/3][y/3],i)){
   set(row[x],i);
   set(col[y],i);
   set(box[x/3][y/3],i);
   if(doit(x+(y==8),(y+1)%9)) {
    g[x][y] = i+1;
    return true;
   }
   unset(row[x],i); unset(col[y],i); unset(box[x/3][y/3],i);
  }
 }
 return false;
}
main()
{
 for(int i=0; i<9; i++) {
  for(int j=0; j<9; j++){
   int k;
   scanf("%d",&k);
   if(k--){
    g[i][j] = k+1;
    row[i] |= (1<<k);
    col[j] |= (1<<k);
    box[i/3][j/3] |= (1<<k);
   }
  }
 }
 if(doit(0,0)){
  for(int i=0; i<9; i++) {
   for(int j=0; j<9; j++) 
    printf("%d%s", g[i][j], (j==8?"\n":(j%3==2?" | ":" ")));
   if(i != 8 && i%3==2){
    printf("---------------------\n");;
   }
  }
 }
 else{
  printf("No Solution!\n");
 }
}

Thanks to Lakshmi Subrahmanyam for providing the solution.

Reversing an array

Let A[1...n] be an array of n distinct numbers. Write a simple linear time algorithm to reverse the order in which the numbers appear on A[1...n]. Use as little additional space as possible. (For example, do not copy the array.)

void reverse(int a[], int n)
{
   int i, t;
   for(i=0; i < n/2; i++) {
       t = a[0];
       a[0] = a[n-i-1];
       a[n-i-1] = t;
   }
}

Find the middle point in a linked list by traversing only once

Node findMiddlePoint(Node list)
{
    Node m = list;
    while(list != NULL && list->next != NULL) {
        m = m->next;
        list = list->next->next;
    }
    return m;
}

If the list contains odd elements, it returns middle point. If the list contains even elements it returns the first element in the second half of the list. i.e., if the elements are (1, 2, 3, 4), it returns 3.

Reversing a Linked List

Node reverseLinkedList(Node list)
{
   Node present, prev, t;
   present = list;
   prev = NULL;
   while(present != NULL) {
      t = present->next;
      present->next = prev;
      prev = present;
      present = t;
   }
   return prev;
}

Searching a string in a set of strings

Given a string, search it in a set of strings (say among 1000s of string). What data structure would you use to store those 1000 strings and get the results fastest?

Solution 1 : Simple, but not best solution
Create a hashtable, and store all the strings in that hashtable. For the given string, search in that hashtable. In the worst case, if we get same hashcode for all the strings, then we have to compare with all the strings.

Solution 2 : Best solution
Create a Trie structure, and search for the string in that trie. Depending upon how we construct the trie, the complexity varies from O(n) to O(n*m) where n is the no.of characters in the given string, and m is the no.of different characters that we have in all the strings.

In the trie, for each node, if we create children for all the possible characters, then the complexity will be O(n), where n is the no.of characters in the given string. The memory requirement will be high in this case.

If we don't create children for all the possible characters, and create children only for the strings that exist in our set, then at each level, we have to search among the children to find the string. So, the complexity would be O(n*m) where n is the no.of characters in the given string, and m is the no.of different characters that we have in all the strings. In this case, we will not use extra memory.

Generating unique random numbers

How to generate unique random numbers from 0 to N-1 given a random number generator which generates a random number between 0 to M-1 for a given M?

void generateRandomNumbers(int x[], int n)
{
   int i, j, t;
   for(i=0; i < n; i++)
      x[i] = i;
   for(i=0; i < n; i++) {
      j = random(n-i);
      t = x[i];
      x[i] = x[j];
      x[j] = t;
   }
}

The complexity of this solution is O(n).

Welcome to Interview Questions

I started this blog to share all the interview questions and solutions on Algorithms, Programming, and Puzzles.

You can subscribe to the feed for the posts from http://algos.tnsatish.com/feeds/posts/default, and for the comments from http://algos.tnsatish.com/feeds/comments/default.

Please send new problems to tnsatish [at] gmail [dot] com. I will post those in this blog. I may not post the solution immediately, but somebody will post the solution eventually (if exists).

I would like to thank Sumalatha Sekhar for inspiring me to start this blog.