Cracking Eggs Problem
You have a 100 story building and You are now given 2 identical eggs. There is some floor below which the egg will not break if dropped. What is the worst case upper bound on the number of drops you must make to determine this floor?

Answer:
Suppose our upper bound is k. For our first drop we could try a floor as high as floor k because at the worst case when the first egg breaks, we still have the second egg and k-1 remaining drops to determine the threshold floor. If the egg doesn't break, we keep moving up and we can now move (k­-1) floor (=k+k-1) further because we have k-1 drops left. So eventually we move up as high sum(k,k-1,...,1) =(k+1)*k/2

The smallest value of k such that this value will be # 99 is 14.
- posted by Pop @ 10:17 PM

 
Abstract Computer
[Question]
You have an abstract computer, so just forget everything you know about computers, this one only does what I'm about to tell you it does. You can use as many variables as you need, there are no negative numbers, all numbers are integers. You do not know the size of the integers, they could be infinitely large, so you can't count on truncating at any point. There are NO comparisons allowed, no if statements or anything like that. There are only four operations you can do on a variable.
1) You can set a variable to 0.
2) You can set a variable = another variable.
3) You can increment a variable (only by 1), and it's a post increment.
4) You can loop. So, if you were to say loop(v1) and v1 = 10, your loop would execute 10 times, but the value in v1 wouldn't change so the first line in the loop can change value of v1 without changing the number of times you loop.
You need to do 3 things.
1) Write a function that decrements by 1.
2) Write a function that subtracts one variable from another.
3) Write a function that divides one variable by another.
4) See if you can implement all 3 using at most 4 variables. Meaning, you're not making function calls now, you're making macros. And at most you can have 4 variables. The restriction really only applies to divide, the other 2 are easy to do with 4 vars or less. Division on the other hand is dependent on the other 2 functions, so, if subtract requires 3 variables, then divide only has 1 variable left unchanged after a call to subtract. Basically, just make your function calls to decrement and subtract so you pass your vars in by reference, and you can't declare any new variables in a function, what you pass in is all it gets.

[Answer]

int dec(int a)  //if a==0, return 0 else return a-1
{ 
    int b = 0; 
    loop(a) { a = b; b++; } 
    // in the loop, the new a will be 0, 1, 2, ..., a-1
    return a; 
} 

Based on decreament, substraction looks like

int sub(int a, int b) 
{ 
    loop(b)   {  dec(a); } 
    return a; 
} 

The other trick is how to implement if (!a) b++;
It is

   loop(a) {a=0;a++;} //when a==0, a=0 else a=1
   loop(a) {b++;}     //when a==0, do nothing, else b++

Therefore we have

int Div(int a, int b) 
{
   int r=0; //store result
   loop(a) 
   { 
      a = sub(a,b);
      d = a;
      // if (!d) r++
      loop(d) {d=0;d++;};
      loop(d) {r++;}  
   }
   return r;
}

- posted by Pop @ 12:27 PM

 
Something about C

In C/C++, the memory layout of struct is aligned to integer. 
For example
struct xxx { char c1; int i1; char c2; }
struct yyy { char c1; char c2; int i1; }
have different size. 
sizeof(xxx)==12 while sizeof(yyy)==8

In C, struct xxx only declares a name, so sizeof(xxx)=1
In C++, struct xxx defines a variable, so sizeof(xxx)=12

This feature can be used to distinguish C and C++ at runtime

#include 
char xxx;
char yyy;
int main()
{
  struct xxx {
    char c;
    int i1;
    char c2;
  };

  struct yyy {
    int i1;
    char c;
    char c2;
  };

  printf("size of xxx = %d\n",sizeof(xxx));
  printf("size of yyy = %d\n",sizeof(yyy));
  printf("compiled by %s\n", sizeof(xxx)==1?"C":"C++");
}

- posted by Pop @ 8:36 PM

 
More on bit

http://www.ee.surrey.ac.uk/Personal/D.Carey/teaching/cs154/Lectures1-4.ppt#257,1,Slide 

1. How to implement conditional operator ? without if...then...else, only use ~,!,&,^,+

x?y:z when x==0 return z else return y
suppose x?y:z equals
y=f(x) + z&g(x)
then
when x==0 f(x)=0,g(x)=-1 (0xffffffffffffffff)
else f(x)=-1,g(x)=0


notice that
1. ~o = -1, ~(-1) = 0,
2. !x=1 when x==0,
=0 else
3. -x = ~x + 1

so we have
f(x) = ~(!(!x))+1
g(x) = ~(!x) + 1

Thinking one more step: How would you implement Logical Not (!) without branch
like if...then...else

The trick is x^-x will set the sign bit (Left Most Bit) unless x==0
Assuming value x has N bits, then we have
!x = (((x^-x)>>N-1)&1)^1
- posted by Pop @ 8:06 PM

 
Hard Puzzle: 100 prisons and 1 bulb
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293;start=360
- posted by Pop @ 11:12 PM

 
Play with Bit
A good one at http://graphics.stanford.edu/~seander/bithacks.html

It is very useful. Some common questions like:
Many tricks are based on 
1. sign = v >> (sizeof(int) * 8 - 1); // if v < v =" ~v" v="1100"> 1000

(1) abs() 
     cwd  //get the sign of [ax] into dx: -1 when <0 ax =" [ax]">0 else -([ax])-1    
     sub ax,dx   // ax = [ax] when >0 else -([ax])-1-(-1);

(2) power of 2
f = !(v & (v - 1)) && v;

(3) Counting bit set
Brian Kernighan's way
  unsigned int v; // count the number of bits set in v
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; v; c++)
  {
    v &= v - 1; // clear the least significant bit set
  }
parallel sideway addition
  unsigned int v; // count bits set in this (32-bit value)
  unsigned int c; // store the total here
  const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
  const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

  c = v;
  c = ((c >> S[0]) & B[0]) + (c&B[0]);
  //add adjacent one bits 1,1->10 1,0->01 0,1->01 0,0->00
  c = ((c >> S[1]) & B[1]) + (c&B[1]); //
  //add adjacent two bits 00,00->0000 00,01->0001 01,00->0001 etc...
  c = ((c >> S[2]) & B[2]) + (c&B[2]);
  //add adjacent four bits 0000,0000->00000000, etc
  c = ((c >> S[3]) & B[3]) + (c&B[3]);
  //add adjacent eight bits
  c = ((c >> S[4]) & B[4]) + (c&B[4]);
  //add adjacent sixteen bits


(4) increament without "+" or "-"
(~a) * (~0)
[equiv] (-a-1) * (-1) = a+1
-0 = ~0 + 1 ==> ~0 = -1

(5) Modulo 3 without equation X-X/3
Given x = v>>2 we have
v= 4*x + v&3 = 3*x + x + v&3
with v mod 3 == (3*x + x + v&3) mod 3 == (x+v&3) mod 3 == (v>>2+v&3) mod 3
so we have
int Modulo3(const int x)
{
  int v = x;
  while (v > 3)v = v>>2 + v&3;
  if (v>2) v=v-3;
  return v;
}
the same idea fits Modulo 5
int Modulo5(const int x)
{
  int v = x;
  while (v>15)
  {
    v = v >>4 + v&15;
    // given x = v>>4;
    // v mod 5 == (16*x+v&15) mod 5
    // == (15*x + x + v&15) mod 5
    // == (x+v&15) mod 5 == ( v>>4+v&15) mod 5
  }
  while (v>4)
  {
    v = v - 5;
  }
  return v;
}

- posted by Pop @ 10:20 PM

 
Select() on socket
With select(), instead of having a process for each request, there is usually only one process that "multi-plexes" all requests, servicing each request as much as it can.

One major disadvantage of using select(), is that your server cannot act like there's only one client, like with a fork()'ing solution. Starveling Problem.

http://www.lowtek.com/sockets/select.html
- posted by Pop @ 9:26 AM

 
.NET reflection introduction paper
About the author
Name :Bipin Joshi

.NET assemblies
Assemblies are the building blocks of any .NET application. All functionality of .NET application is exposed via assemblies. Assemblies form a unit of deployment and versioning. Assemblies contain modules which in turn contain various types (classes, structures, enumerations etc.).

Getting started
Before obtaining any information about types contained in an assembly we must first load the assembly.

Assembly myassembly = Assembly.LoadFrom("employee.dll");

This statement loads an assembly called employee.dll. You can substitute your own path here. Assembly class has a static method called LoadFrom that loads the specified assembly in memory. The method returns an instance of assembly class itself.

The next step is to obtain a list of various types contained in the assembly.

Types mytypes[] = myassembly.GetTypes();
Type mytype=myassembly.GetType("Company.Employee");

There are two methods to get type information . The method GetTypes returns an assay of System.Type objects. The method GetType returns a type object having details of specified object.

The Type class has following properties that gives details about the type under consideration :
Name : Gives name of the type
FullName : Give fully qualified name of the type
Namespace : Gives namespace name
IsClass
IsInterface
IsAbstract
IsCOMObject : Indicates if the type is a COM object
IsEnum
IsSealed
IsPublic

Each type may have fields (member variables), properties and methods. The details about each of these types are obtained by following methods of the Type object.

GetMembers() : Gives array of MemberInfo objects
GetFields() : Gives array of FieldInfo objects
GetProperties() : Gives array of PropertyInfo objects
GetMethods() : Gives array of MethodInfo objects

Note that you can also get information about specific method, property or field using GetMethod("mymethod"), GetProperty("myprop") or GetField("myfield") methods.

MethodInfo[] mymethods= mytype.GetMethods();
MethodInfo mymethod = mytype.GetMethod("GetSalary");

Following paragraphs list commonly used properties and methods of above objects. The property and method names are self explanatory. You can refer MSDN for more details.

Properties and methods of MethodInfo Object
Name
IsPrivate
IsPublic
IsStatic
IsConstructor
ReturnType
GetParameters()
Invoke()

Properties and methods of PropertyInfo Object

Name
CanRead
CanWrite
PropertyType
GetValue()
SetValue()

Properties and methods of FieldInfo Object
Name
FieldType
IsPublic
IsPrivate
IsStatic
GetValue()
SetValue()

Invoking a method on a type
We have seen how to get information about various types from an assembly. Reflection also allows us to create instances of these types and invoke methods on them. Following code fragment shows just that.Assembly

Assembly a=Assembly.LoadFrom("employee.dll");
Type t=a.GetType("Company.Employee");
MethodInfo getsalary=t.GetMethod("GetSalary");
object obj=Activator.CreateInstance(t);
object[] p=new object[1];
p[0]="bipin";
object retval=getsalary.Invoke(obj,BindingFlags.DefaultBinding, null,p,null); Console.WriteLine(retval);

Here, we first obtained type of employee class. We then created an instance of it using Activator.CreateInstance() method. There are two forms of Invoke() method :

If your method is not returning any value then you may use following form
Invoke ( obj , obj[])

If your method is returning some value and you want to trap it use following form :
obj = Invoke ( obj , bindingflag, binder , parameters, cultureflag )

For both the forms you pass instance of object on which the method will be called and array of objects that contains method parameters.

The second method shown here is with most commonly used values for BindingFlags, Binder and Culture. For more detailed information on the second syntax of Invoke method please refer MSDN.

Summary
Reflection allows a powerful mechanism to introspect your types. The reflection APIs can be found in System.Reflection namespace. The APIs allow you to inspect types as well as create types on the fly and invoke methods on them.
- posted by Pop @ 10:16 AM

 
Make ssh not prompt
Quick summary of how to make ssh not prompt for a password:

1. Create a public/private key pair (ssh-keygen).
ssh-keygen -t rsa
you do not need to input the passphrase
it will create the id_rsa.pub file under ~/.ssh directory

2. Copy id_rsa.pub file to the remote SSH servers to the ~/.ssh/authorized_keys file.
scp ~/.ssh/id_rsa.pub :~/.ssh/authorized_keys

3. Run ssh-agent if not already running.
4. Run ssh-add.

You can skip 3 and 4 if you create the keys in step 1 without passphrase.
- posted by Pop @ 1:12 PM

 
Grid WorkFlow
In http://www.extreme.indiana.edu/groc/ggf10-ww/
1. Anthony Mayer Workflow Expression: Comparison of Spatial and Temporal Approaches
2. Rania Khalaf Implementing BPEL4WS

http://www.isi.edu/~deelman/wfm-rg/
1. Alek Slominski, Update from the world of BPEL
2. Thomas Soddemann, RZG, "The MiGenAS Workflow Engine"
- posted by Pop @ 5:06 PM

 
Evolution of SOA
From
http://www.ondotnet.com/pub/a/dotnet/2003/08/18/soa_explained.html

Q1. reuse some of the code
A1. modular design

Q2. code maintenance
A2. Object-oriented Programming

Q3. reuse and maintain functionary besides code
A3. Component-based programming

Q4. Application Integration in distributed systems, various platforms, protocols, hardware
A4. SOA

SOA: service provider, service consumer, directory service

1. Service
A service in SOA is an exposed piece of functionality with three properties:
- The interface contract to the service is platform-independent.
- The service can be dynamically located and invoked.
- The service is self-contained. That is, the service maintains its own state.

2. Message
- Service providers and consumers communicate via messages.
- messages must be agnostic to any specific platform/language

3. Directory service for dynamic service discovery
- The directory service is an intermediary between providers and consumers.
- Decouples consumers from providers
- Allows consumers to choose provider at runtime rather than hard-coding a single provider.
-
- posted by Pop @ 11:32 AM

 
Art of Memory Optimization
Type Sizing
Example 1.
struct BadValueType { char c1; int i; char c2;}
struct GoodValueType { int i; char c1; char c2;}
struct GoodValueType2{ short i; char c1; char c2;}

Properly aligning and sizing this type reduced it from 12,8 to 6 bytes.

Example 2.
Suppose we have a field "state" with type "string" in the Address type, if we ignore the various U.S. territories, then the state field has 50 possible values. It might be worth considering an enumeration here since it would remove the need for a reference type and store the value directly in the class. The base type for the enumeration could be a byte rather than the default int, resulting the field requiring 1 byte rather than 4.

This situation brings to light one of the more common trade-offs in computing: speed versus memory. It is often possible to optimize memory usage at the expense of some CPU cycles, and vice versa.

Object Pooling
This is especially useful when an instance of an object is repeatedly used, or if the object has an expensive initialization aspect to its construction such that it's better to reuse an existing instance than to dispose of an existing one and to create a completely new one from scratch.

we can achieve this by overloading new() operator.

more on:
http://msdn.microsoft.com/msdnmag/issues/05/01/MemoryOptimization/default.aspx

- posted by Pop @ 10:36 PM

 
Write Code to identify C or C++

#include char xxx;
int main(){
  struct xxx {
    char c1;
    int i;
    char c2;
  };
  printf("in %s the size of xxx is %d\n",
     sizeof(xxx)==1?"C":"C++",
     sizeof(xxx));
}

rommel:~/puzzle> g++ -o m.o -c C_Cpp.c
rommel:~/puzzle> g++ -o m m.o
rommel:~/puzzle> ./m
in C++ the size of xxx is 12

rommel:~/puzzle> cc -o m1.o -c C_Cpp.c
rommel:~/puzzle> cc -o m1 m1.o
rommel:~/puzzle> ./m1
in C the size of xxx is 1

Another thing we should notice is the size of struct xxx is 12 not 8(2+4+2)! This is because the integers are laid out on four-byte boudaries.

If we change the defintion to

struct xxx {
   char c1;
   char c2;
   int i;
}

the size of struct xxx will be 8!.
- posted by Pop @ 10:10 PM

 
.NET profiling
http://blogs.msdn.com/ricom/
- posted by Pop @ 8:33 PM

 
Variable-length Template Argument Lists
An paper at
http://www.osl.iu.edu/~jajarvi/publications/papers/vararg_templates_n1483.pdf
and another paper about boost::tuple
http://www.osl.iu.edu/~jajarvi/publications/papers/tuple_proposal.pdf
- posted by Pop @ 4:49 PM

 
interesting puzzles
http://www.podval.org/~sds/puzzles.html

Try the really hard ones if you like
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
- posted by Pop @ 2:07 PM

 
Metaclasses and Reflection in C++
http://www.vollmann.com/en/pubs/meta/meta/meta.html

MOP
Meta object protocol in c++

Copyright 2000, Detlef Vollmann
- posted by Pop @ 11:15 AM

 
Dynamic Class Loading for C++ in Linux

void *dlopen(const char *file, int mode);
void *dlsym(void *handle, char *symbol);
const char *dlerror();
int dlclose(void *handle);

Given that we can use these functions to access functions in a C library, how do we use them to access classes in a C++ library?
1. We must be able to locate the symbols we need in the library.
2. How can we create objects belonging to the classes we load?
3. Finally, how can we access those objects in a useful manner?

The approach in http://www2.linuxjournal.com/article/3687
1. define a base class for all Dynamic Classes such that the dynamic objects can be statically casted (using static_cast()) to instances of base class.
2. In Main(), define a global variable Factory (std::map)
3. In dynamic class, define a proxy class variable, this proxy class variable will register the maker for the dynamic class to the Factory.
4. Using RTLD_NOW flag in dlopen() to instantialize the proxy variable when loading the dynamic class such that the register is automatic.
5. Using gcc/egcs, we would be required to link with the rdynamic option to force the main program to export its symbols to the libraries loaded with dlopen such that the global variable Facotry is accessible by proxy class.
- posted by Pop @ 10:01 AM