Finding all palindromes in a string (BTW Half Century)

#include
#include
#include
#include

void substring(char *stng, int from, int to){
char sstr[to-from+2];
for(int i=0; i<=(to-from+1); i++){ sstr[i] = stng[i+from]; } sstr[to-from+1] = '\0'; printf("%s\n", sstr); } void palin(char *string){ int len; len = strlen(string); for(int i=1; i=0;j--,k++){
if(string[j] == string[k]){
substring(string, j, k);
}
else
break;
}
}

for(int i=0; i=0; j--,k++){
if(string[j] == string[k]){
substring(string,j ,k);
}
else
break;
}
}
}
}

int main(){
char str[] = "ABRARBABACDDCABABRARBA";
//printf("Length = %d\n", strlen(str));
palin(str);

getch();
return 0;
}

Algorithm: to find the median of two sorted arrays

1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
4) Repeat the above process until size of both the subarrays
becomes 2.
5) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
Implementation:

?
#include

int max(int, int); /* to get maximum of two integers */
int min(int, int); /* to get minimum of two integeres */
int median(int [], int); /* to get median of a single array */

/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */

/* return -1 for invalid input */
if(n <= 0) return -1; if(n == 1) return (ar1[0] + ar2[0])/2; if (n == 2) return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2; m1 = median(ar1, n); /* get the median of the first array */ m2 = median(ar2, n); /* get the median of the second array */ /* If medians are equal then return either m1 or m2 */ if(m1 == m2) return m1; /* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */ if (m1 < m2) return getMedian(ar1 + n/2, ar2, n - n/2); /* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
return getMedian(ar2 + n/2, ar1, n - n/2);
}

/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;

getchar();
return 0;
}

/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}

int min(int x, int y)
{
return x > y? y : x;
}

/* Function to get median of a single array */
int median(int arr[], int n)
{
if(n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
Time Complexity: O(logn)
Algorithmic Paradigm: Divide and Conquer

some some

The extern in a function's declaration is sometimes used to indicate that the function's
definition is in some other source file, but there is no difference between
extern int function_name();
and
int function_name();

Inline functions are similar to macros because they both are expanded at compile time, but the macros are expanded by the preprocessor, while inline functions are parsed by the compiler. There are several important differences:
Inline functions follow all the protocols of type safety enforced on normal functions.
Inline functions are specified using the same syntax as any other function except that they include the inline keyword in the function declaration.
Expressions passed as arguments to inline functions are evaluated once. In some cases, expressions passed as arguments to macros can be evaluated more than once.

run this code:

#include
/*
int foo(int a);
int foo2(int a, int b);
*/
int main(int a)
{
int (*fp)(int a);
a = foo();
a = foo2(1);
exit(0);
}
int foo(int a)
{
return(a);
}
int foo2(int a, int b)
{
return(a+b);
}

run this again by removing /* and */. Understand the difference.

Whats short-circuiting in C expressions?
What this means is that the right hand side of the expression is not evaluated if the left
hand side determines the outcome. That is if the left hand side is true for || or false for
&&, the right hand side is not evaluated.

i = i++ /// invalid

• auto - local variables.
• static - variables are defined in a nonvolatile region of memory such that they
retain their contents though out the program's execution.
• register - asks the compiler to devote a processor register to this variable in order
to speed the program's execution. The compiler may not comply and the variable
looses it contents and identity when the function it which it is defined terminates.
• extern - tells the compiler that the variable is defined in another module.

How can I convert numbers to strings (the opposite of atoi)?
Use sprintf()
Note!, since sprintf() is also a variable argument function, it fails badly if passed with
wrong arguments or if some of the arguments are missed causing segmentation faults.


http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

Brilliant example on dynamic programming

http://www.careercup.com/question?id=2445

Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;

white = 0 black = 1
1. construct a row and a col matrix to record the # of consecutive "1" from current node to left, and up, respectively.
e.g.:
Original (A):
11111
11101
10111
01011
row:
12345
12301
10123
01012
col:
11111
22202
30313
01024

int maxsize = 0;
for i=0; ifor j=0; j    if (A[i,j]==1){
	for (int k=min(i,j); k>maxsize; k--){ //min(i,j) is the maximum possible square size from i,j to 0,0 
	   if ((row[i,j] - row[i,j-k] == k) && 
	   (row[i-k,j] - row[i-k,j-k] == k) && 
	   (col[i,j] - col[i-k,j] == k) &&	
	   (col[i-k,j] - col[i-k,j-k] == k) &&
	   )
	   maxsize=k;
	   break;
	}
    }
}

some basics again

In Java, Objects are passed by reference, and primitives are passed by value.

This is half incorrect. Everyone can easily agree that primitives are passed by value; there's no such thing in Java as a pointer/reference to a primitive.

However, Objects are not passed by reference. A correct statement would be Object references are passed by value.

This may seem like splitting hairs, bit it is far from it. There is a world of difference in meaning. The following examples should help make the distinction.

refer : httx://javadude.com/articles/passbyvalue.htm

When the method or constructor is invoked , the values of the actual argument expressions initialize newly created parameter variables, each of the declared Type, before execution of the body of the method or constructor. The Identifier that appears in the DeclaratorId may be used as a simple name in the body of the method or constructor to refer to the formal parameter.

Given an class with Synchronized method A and B, a normal method C, there are 2 threads, one instance, can these two threads call A at the same time? call A and B at the same time? A & C at the same time?

A and B cannot be called together because they are locking on the same object(this). A and C can be called together.

In Java, static means that it's a variable/method of class, it belongs to the whool class but not to one of its certain objects.

It means that static keyword can be used only int a 'class scope' i.e. it doesn't have any sence inside methods. The variables you declare in an instance method are not instance variables -- they are local variables, whose scope is limited to the method that declares them. They are not attached to the object. Likewise, in a static method, the variables you declare are local variables, too.

Observer Design Pattern: Observer registers with subjects and any update on subject will be updated to the Observers

see http://www.youtube.com/watch?v=jsFhBvIeHrk&feature=autoplay&list=ULxlJTutQggvY&index=19&playnext=2

hashCode

public int hashCode()
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Returns:
a hash code value for this object

protected  void

finalize()           Called by the garbage collector on an object when garbage collection determines that there are no more references to the object.

Ref: http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode()

Exceptions

We can actually use if else blocks to check exceptions. But it becomes too messy and unreadable. So we use try catch blocks. When an exception occurs an object of the corresponding exception class is instantiated. So, if not handled, will result in the program to crash. So, we catch that exception in the catch block.

A try can have many catches but only a finally block. Finally block always execute. And when u r catching a class and its child class exceptions, child class should be written in catch block before the parent.

Help me. Some thing is wrong with my quick sort. Help is appreciated

#include
#include

int* quicksort(int a[],int start,int end)
{
int i = start;
int j = end;
int pivot = rand()%(end-start+1);
if(a[start]
start++;
if(a[end]>a[pivot])
end--;
printf("num to swap %d and %d\n",a[start],a[end]);
if(start
{
int temp = a[start];
a[end]=a[start];
a[start] = temp;
quicksort(a,i,(i+j)/2);
quicksort(a,((i+j)/2)+1,j);
printf("array is %d\n",a[0]);
}
else
return a;
}

int main()
{
int A[5] = {34,564,78,9,2};
int *B = quicksort(A,0,4);
printf("%d\n",*(B+1));
return 0;
}

SAN vs NAS. iSCSI vs Fibre

First acronyms.
SAN - storage across network
NAS - Network attached Storage

Consider a situation where u have many computers at your home. u want to access files of one system from another. NAS offers the solution. NAS is a storage device where you can store your data and set setting such that other machines can access it. You can also backup your data on NAS.

Whereas SAN is a storage device where your servers can access certain amount of memory from. i.e servers can do 1:1 map with the disks present on the NAS. Suppose, you have bought 3 servers thinking that 500GB disk in each will do. But, one server may be using just 100 GB, the other 200GB and the third may require 1TB more. SAN provides the solution for this. As the disks are now available on SAN you can adjust the memory requirements successfully.

SCSI - Small Computer System Interface. It is the connection between these devises and servers. SCSI runs on ethernet and can be deployed on any ethernet card. Whereas Fibre is a direct connection. Fibre offers 4GBPS, but is costly whereas ethernet offers 1GBPS but is cheaper.

Beauty and Java

String class in immutable, i have already mentioned in the previous post. StringBuffer class is mutable. Mutable means it can be changed. We can declare a string in two ways.

1.String s = "hi"; or 2.String s = new String("hi");
During 1 memory for "hi" is allocated at the free pool of memory which is in the method area whereas in 2 it allocated in heap area.
Suppose, another string is declared 3. String s1 = "hi" then s1 will not be allocated new memory. The address of s is copied into s1. so s==s1 returns true. where as 4. String S1 = new String("hi") will allocate new address and s == s1 returns false.

We generally do s+="bye". to make the string "hibye". But, as I have mentioned String class is immutable and you cannot change it. What actually happens is JVM internally creates a StringBuffer object. StringBuffer class has append(), insert(), replace etc. the code is
s = new StringBuffer().append("bye").toString. The object class has a toString method which converts all the objects into String object. the address in s will now be changed to new value which points to hibye. Garbage collector picks the previous "hi".
BTW garbage collector not only works on heap are but also method area.

String class has the following methods:
charAt(), indexOf(),compareTo(),equals(), equalsIgnoreCase(), subString(start, end). for ex: "hello world".subString(3,6) will return "lo ". (end -1) inclusive.

Wrapper classes: They exist for every primitive data type. The uses of them are: type casting and passing primitive data types as objects.
 Any input form keyboard, may be a int or float, will be received as string. So, these wrapper classes have methods like parseInt(), parseFloat(), which will be invoked internally.
Suppose, theres a method
int i = 10;
void objectparam(object o)

we cannot pass i into it. so we should create object by instantiating Integer class.

CLASS CLASS

A class class has the following methods:
 String getClass()
Class getSuperClass() return the object of the super class
Interface[] getInterfaces() returns the array of objects of interfaces it implemented
Methods[] getMethods() ...... return all public methods right from the Object class to the current class
Methods[] getDeclaredMethods() ..... returns all methods of all access types of the current class

We need to import Java.Lang.Reflect to access getMethods(),getFields(), getConstructors()

SYSTEM CLASS

System class has static methods like:
PrintStream out,err
InputStream in
arrayCopy
gc     invokes the garbage collector by my not be immediate
exit
getProperty
loadLibrary

JAVAAAAAA

courtesy : careercup 

intern() method of String class returns canonical representation for the string object from string pool.

so even if two string object have same value and return false on == comparision
string1.intern()==string2.intern() returns true.

daemon thread is a low priority thread that is terminated as soon the vm exits.
It is generally used to do all the house keeping work like gc thread is a daemon thread.
It can be set using
thread.setDaemon(true);
And then start the thread.
The main thread terminates it if it is finished.

courtesy: http://glenmccl.com/perfj_025.htm

final class A {}

 means that A cannot be further extended or subclassed. 
This feature has a couple of big implications. One is that it allows control over a class, so that no one can subclass the class and possibly introduce anomalous behavior. For example, java.lang.String is a final class. This means, for example, that I can't subclass String and provide my own length() method that does something very different from returning the string length. 

access specifiers

        Within Class  |    Same PKg.     |        Subclass      | Different Pkg
                      | Outside The Class|  Same Pkg.|Diff Pkg.| But not Subclass

PUBLIC                               | yes | yes | yes | yes | yes

PROTECTED                     | yes | yes | yes | yes | No

DEFAULT                          | yes | yes | yes | No | No

PRIVATE                            | Yes | No | No | No | No

courtesy  http://stackoverflow.com/questions/1123044/when-should-your-destructor-be-virtual

1. You need virtual destructor when at least one of class methods is virtual.

This is because the reason for virtual method is that you want to use polymorphism. Meaning you will call a method on the base class pointer and you want the most derived implementation - this is the whole point of polymorphism.

Now if you did not have virtual destructor and through the pointer to base class you call destructor you end up calling base class destructor. In this case you want polymorphism to work on your destructor as well, e.g. through calling destructor on your base class you want to end up calling destructor of your most derived class not your base class.

class A{
   virtual void f() {}
   ~A() {}
}
class B : public A{
   void f() {}
   ~B() {}
}

A * thing = new B();
thing->f(); // calls B's f()
delete thing; // calls ~A(), not what you wanted, you wanted ~B()

having ~A() virtual turns on polymorphism

virtual ~A() {}

So when you now call

delete thing;

~B() will be called.

You would declare virtual destructors when you design class as an interface e.g. you expect it to be extended or implemented. A good practice in that case is to have a interface class (in the sense of Java interfaces) with virtual methods and virtual destructor and then have concrete implementation classes.

You can see that STL classes don't have virtual destructors so they are not supposed to be extended (e.g. std::vector, std::string ...). If you extend std::vector and you call destructor on base class via pointer or reference you will definitely not call your specialized class destructor which may lead to memory leaks.