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. 

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 :)

level order tree traversal

How would you print out the data in a binary tree, level by level, starting at the top?

Clue:

How about using a Queue. Relate to Dijkstra's SP algorithm.

Find the previous alphabet.

khanji has a LOT of characters in their alphabet and are using a way of compressing it so that the most common characters are 1 byte and the less common are 2 bytes. If it's a '1 byte' character, it starts with a 0, If it's a 2 byte character, it starts with a 1. If you're at a particular character (at the beginning), how do you find where the previous character begins?

Now this is an interesting question.
Let the currect char be c (irrelevant), and the first bit of every previous byte be denoted by 1s, 2s....etc.

Some hints:
1. If 1s = 1, then previous char is 2 byte long.
2. If 1s = 2s = 0 then ??
3. If 1s = 0 then all (2...n)s = 1 then the problem is undecidable until you hit
a 0, in which case the answer is ??

DP - max subset of dominating pts.

A DP one.

Q. Consider that you have n 2D pts. Find the largest set of pts such that when sorted (by either axis) produce the same sequence.
Okay, the exact wordings of the original problem -
A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower?

My thoughts -
Sort the pts by say x axis co-ordinates. Then the problem reduces to finding the longest increasing subsequence ( or longest decreasing subsequence Note: we hae to consider both ) in y axis co-ordinates. this is a std DP problem.

More questions :
1. Will it produce the same answer when first sorted in y axis co-ordinates. Or we have to do the both and then take the one of max-length ?

2. How would you generalize the problem to pts coming from dimension d > 2. Need to think over that.

An aside :
See if you could relate some parts of the above problem to the following problem.
Given any sequence of mn+1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

ugly numbers

I lifted it from the career cup site
Design an algorithm to find the kth number divisible by only 3 or 5 or 7. That is, the only factors of these numbers should be 3,5 and 7.

What I have in mind -

Generating the numbers which have prime factors as only 3,5, 7 is not a big thing. but doing so in a sorted order is a little tricky.
Let's call the exponents of 3,5,7 as a,b and c repectively.
Claim: The order of numbers with a = b = c = n to a = b = c = n+1 would be unchanged for any n >= 0.
And that gives an idea to program it. We have to find an order between to successive exponents. Lets start with n = 0. Then we have to find all the numbers ordered ( with their exponents known ) less than 105 ( 3*5*7 ) and greater than 1.
Way 1 -
Write a program to generate all the numbers which are factors of 3 or 5 or 7 ( with their factors recorded. And then keep increasing these factors...
For exp if the factors have exponents (a1,b1,c1), (a2,b2,c2)....(am,bm,cm). then the next cycle of increasing numbers will have exp ( a1+1, b1+1, c1+1 )....(am+1, bm+1, cm+1).
Way 2 -
Generale the numbers thru' the exp. Its clear that they are upper bounded, for n = 0, as a < 5, b < 3, c < 3. So 3 for loops and get all numbers which fall below 105, get their corresponding exp and thats it.

Marble / Egg drop

Problem:

You have a staircase and 2 eggs. The staircase is N steps long. You can drop eggs on this staircase at any point between 0 to N. At a point X on the staircase where X >0 and X < N the eggs begin to break. Your mission, if you choose to accept it, it to find the point X in this staircase by making a minimum number of drops.

O O Step 0
|_
...|_
.......|_
..........|_ - The random point X where the egg breaks
..............|_
..................|_

Analysis:

Solution 1: Ugly

The easiest thing to do is to drop the egg at each step and check if it breaks. The worst case running time of such an algorithm is O(N). However there must be a reason we have 2 eggs to solve this problem. So obviously this is not the optimal solution. Lets think a little more.

Solution 2: A lil better

What can we do to use both the eggs ? Hmmm... Lets do this. Take egg 1 and drop it on odd steps. If it breaks then take the other egg and break it on the last even step before the step where egg1 broke. That is if egg 1 broke at step 5, drop egg 2 on step 4 (last even number before 5). If egg 2 breaks then you know that point is X (since the egg did not break at N=3). If it does not break then you know X is the number where egg 1 broke.

The efficiency of this solution is O(N/2) ~ O(N). But we can do better

Solution 3: I will leave it to you to figure this one out

Its possible to have an efficiency of something better than O(N) for this problem. With the last solution the egg can be dropped at odd intervals. What if we can drop the egg at an interval Z ? How will that help us determine the value of X ? Think about that. How should egg 2 be dropped so that for any interval Z, the value of X can be ascertained.

Performance:

To determine the performance for solution 3, consider making an equation F(Z). F(Z) is a function that determines the number of times (worst case) an egg must be dropped to determine the value of X.

Hint: F(Z) contains 2 component. One that is relevant before egg 1 breaks and one that is relevant after egg 1 breaks.

Once you have this equation in place you can determine the best running time for the worst scenario quite easily.

Hint: Differentiation. F(Z)' and F(Z)''.

This problem can be used to solve some practical difficulties. For example you know that you are to receive a 1024 bit number whose values you must calculate. You know that this number is formatted like so 0000000001111111... but you dont know where the 1s begin. This is like the staircase problem. Applying solution 3 can save time and allow you to quickly calculate the 2nd power of the 1024 bit number.

What sorting algorithm does Makefile use?

Most of us know what a makefile is.
It has instructions for creating the a.out file.

If you're new to makefiles, you might want to read this before proceeding further.
So, let me get to the point here.
We write rules on how to compile the programs of the form

target : dependencies
commands

If we see the whole story, the make file produces the target based on dependencies, IN ORDER.
Can you relate this to any algorithm?
Think... What algorithm relates events to happen in a definite sequence to produce the output?

Answer: Topological sort
Think about it. The dependencies are compiled in order.
Lets look at an example.
out : main.o sort.o
gcc -o out main.o sort.o

main.o : main.c
gcc -c main.c

sort.o : sort.h sort.c
gcc -c sort.c

the rule main.o has to be dealt with.
This in turn will compile main.c if:
1: main.o didn't exist.
2: main.c was modified after creation of the previous main.o

Similarly, sort.o will have to be dealt with to produce sort.o
Then, both the main.o and sort.o files will be combined to produce out which can be run using ./out