lets print hello world in C language

Here's the snippet

int main() {
    if (/*your code goes here*/) {
        printf("hello");
    } else {
        printf("world");
    }
    return 0;
}

Try printing "helloworld" by just filling in the condition in the if statement ?

Hint:
Ever wondered what printf returns? ;)

pow(2) ?

Given a natural number, how do we check if it is power of 2?

So, lets say, we were given 388. How do we write a program to check if the number is a power of 2?

Hint:
given n, n and (n - 1) don't share any bits in common.
Still don't get it?
if ((n & (n - 1)) == 0) {
//pow of 2!
}
Lets see this with a simple example.
let n = 3.
So, n = 011
and n - 1 = 010
So, n & (n - 1) = 010

Consider 4.
n & (n - 1) = 100 & 011 = 000

So, there u go :)

Door and the wall

You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you do not know how far away the door is and in which direction. You can see the door only when you are right next to it. How do you reach the door by walking at most O(n) steps where n(unknown to you) is the number of steps between your initial position and the door.

Will the order change if you had sequential / random access to the pathway ? That is, for a sequential pathway, you will have to walk from position 1 to 17 using the path 1-2-3-4...-17. For random access you may visit point 17 from point 1 directly without accessing elements 2->16.

Door and wall:

Bit length

How many bits are required to represent a given number N in binary notation ? Can you come up with a formula for the same. For example F(N) for N = 7 is 3, since 111 is the binary representation for 7. F(N) for N=8 is 4.



Spoiler: F(N) = lg (N) + 1

How does the formula change when representing N in decimal notation.

Locker

Imagine you are at a school that still has student lockers. There are 1000 lockers, all shut and unlocked, and 1000 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.
2. The second student then goes along and shuts every other locker beginning with number 2.
3. The third student changes the state of every third locker beginning with number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)
4. The fourth student changes the state of every fourth locker beginning with number 4. Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will be open and which will be closed? Why?

Try the problem for n=10,20 and observe the results.

Hint / Spoiler : http://www.math.msu.edu/~nathsinc/java/Lockers/

A related problem to prove the solution to the one above

How many perfect square factors does the number 46,656 have?

string rotation

Well, given a char * and an integer to rotate it clockwise or counter clockwise, lets c how to rotate it.

Ok. the basic idea to rotate a string counter clockwise is
1 : reverse first n - 1 characters.
2 : reverse the rest of the characters.
3 : reverse the whole string.


Eg:
Consider "hello" and you wanted to rotate it thrice in the counter clockwise direction.
So, here are the stages:
After 1 : "ehllo"
After 2 : "eholl"
After 3 : "llohe"
which is the final answer.

try it out for clockwise rotation before looking at the snippet below. It's fun.

enum
{
 SUCCESS,
 FAILURE
};


int
reverse(char *in, unsigned int start_index, 
unsigned int end_index)
{
 char temp;
 if (in == NULL || start_index > end_index)
  return (FAILURE);
 while (start_index < end_index) {
  temp = in[start_index];
  in[start_index] = in[end_index];
  in[end_index] = temp;
  start_index++;
  end_index--;
 }
 return (SUCCESS);
}


int
rotate_string(char *rotate_me, unsigned int times, 
unsigned int is_clockwise)
{
 unsigned int len = 0;

 if (rotate_me == NULL)
  return (FAILURE);
 //initialize the length;
 len = strlen(rotate_me);
 //if times > len, fix it.
 times %= len;
 //fix if rotation needs to be clockwise
 if (times != 0 && is_clockwise) {
  times = len - times;
 }
 /*
  * First, reverse the times - 1 characters.
  * Now, reverse times to len - 1
  * Finally, reverse the whole string.
  */
 if (times > 0 &&
  (
   reverse(rotate_me, 0, times - 1) == FAILURE ||
   reverse(rotate_me, times, len - 1) == FAILURE ||
   reverse(rotate_me, 0, len - 1) == FAILURE
  )
 ) {
  return (FAILURE);
 }

 return (SUCCESS);
}

and that's the way it's done :)

Stock

You are given an array of stock market values over different days. Return an array as a result which gives the span of the stock value for that day. A span is the number of preceding days from the current day, for which the stock market value was lower. The picture below shows the span for various days

Stock:



Input -> {7,5,4,6,9}

Output -> {-1,1,1,3,-1}

Day 1: No previous days result is -1.
Day 3: On Day 2 the value was 5. Only day 4 is considered for the span which results in 1.
Day 4: Day3 and 2 have a value lower than 6 so they are included in the span. Result -> 3
Day 5: Best stock market day. Must return -1 since there is no day before day 1.

Can this be done better than O(N2) time.

Hint -> What property of day 4 must be used so that unnecessary comparisons can be avoided ? Is it even necessary to compare day 2 and 3 ? If we can save a reference to all the days whose comparisons would yield the correct result it will help with the time constrain.

Hint -> It can be done with a stack in O(N) time.

Spoiler -> http://thinkcs.googlecode.com/svn/trunk/src/com/util/Stock.java

Test cases -> http://thinkcs.googlecode.com/svn/trunk/src/com/tests/TCStockTest.java