2D sorted array. Element search.

A 2D integer array is such that each row and column in it is in ascending order. How will you search for a specific element in it ?

Clue: A simple implementation in O(m+n) can be done.  

A more complex recursive approach using diagonals as breakpoints of recursion can also the thought off. Basically, recursively spitting a matrix into sub-square matrices for the search on the diagonal. Am yet struggling with the complexity analysis part. 

Rom/Column Inversion

You are given a matrix m*n (need not be square) of positive/negative integers. The only operations permitted are you invert the signs of an entire row or an entire column. And that is counted as one step. The goal is the to reach the maximum sum possible (of all elements) of the matrix with such a series of operations. 

Q. Does the process converge. If yes, then what is the complexity ?

Clue: When would you do such an operation ? And when you do that what happens to the total sum? What is the max sum which can be reached. 

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?