VG Scribbles

VG Scribbles

Long time .... but I'm back here again. Wanted to hide for a while and I succeded. So many things in my heart to come out and looking for words to be written. I would again start writing abt my experiences soon. I wish I would continue it forever.
Bye
good night [:)]

String .. continued

Three types of functions exist in the string library:
the mem functions manipulate sequences of arbitrary characters without regard to the null character;
the str functions manipulate null-terminated sequences of characters;
the strn functions manipulate sequences of non-null characters.

strcat:
char *strcat(char * restrict s1, const char * restrict s2);
It appends a copy of the string pointed to by s2 (including the terminating null byte) to the end of the string pointed to by s1. The initial byte of s2 overwrites the null byte at the end of s1. If copying takes place between objects that overlap, the behavior is undefined. The function returns s1.
This function is used to attach one string to the end of another string. It is imperative that the first string (s1) have the space needed to store both strings.Before calling strcat(), the destination must currently contain a null terminated string or the first character must have been initialized with the null character (e.g. str[0] = '\0';)
he strchr function

strchr:
char *strchr(const char *s, int c);
It locates the first occurrence of c (converted to a char) in the string pointed to by s. The terminating null byte is considered to be part of the string. The function returns the location of the found character, or a null pointer if the character was not found.It is used to find certain characters in strings.
char *(strchr)(const char *s, int c)
{
/* Scan s for the character. When this loop is finished,
s will either point to the end of the string or the
character we were looking for. */
while (*s != '\0' && *s != (char)c)
s++;
return ( (*s == c) ? (char *) s : NULL );
}

strcpy:
char *strcpy(char *restrict s1, const char *restrict s2);
It copies the string pointed to by s2 (including the terminating null byte) into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. The function returns s1. No value is used to indicate an error.
Imp: When you call this function, you must ensure that the destination is able to contain all the characters in the source array. Not doing so can have very serious consequences including compromising the security and integrity of your entire computer. This is also true with some of the other functions such as strcat(). This is very unlikely and in most cases a problem will simply result in the program crashing, or not functioning correctly.

strstr:
char *strstr(const char *s1, const char *s2);
It locates the first occurrence in the string pointed to by s1 of the sequence of bytes (excluding the terminating null byte) in the string pointed to by s2. The function returns the pointer to the matching string in s1 or a null pointer if a match is not found. If s2 is an empty string, the function returns s1.
char *(strstr)(const char *s1, const char *s2)
{
size_t s2len;
/* Check for the null s2 case. */
if (*s2 == '\0')
return (char *) s1;
s2len = strlen(s2);
for (; (s1 = strchr(s1, *s2)) != NULL; s1++)
if (strncmp(s1, s2, s2len) == 0)
return (char *) s1;
return NULL;
}

Difference between strcpy and memcpy
strcpy ends copying of data when it reaches NULL character (Say, '\0' or 0) and then copies NULL at the end of destination data. It is specifically used to copy strings (char[]).
memcpy can be used to copy any type of data (void*). It terminates at the byte position specified by the third parameter.memcpy copies the specified number of bytes of src to dest.

Reversing a string:
char *reverse(char *s)
{
char *temp;
int len=strlen(s);
temp = malloc(strlen(s) +1);
temp = temp+strlen(s) - 1;
while(*s != '\0') {
*temp = *s;
printf("%c %c\n", *temp , *s);
temp--;
s++;
}
temp++;
temp[len]='\0';
return temp;
}

I hope this is sufficient for a string related interview questions.Try to check all the programs before going for any interview as sometimes a small error can cost u a lot.Anyway coming topic is Sorting.

"They say I am FOOL ... This is just a step to prove them WRONG"

Sorting Algorithms and Analysis

Sorting -- Arranging items in some particular fashion mostly in some numerical or alphabetical order. Sorting can be classified on these basis.
Computational Complexity
Memory Usage
Stabiliy
Comparision - Non comparision sort.
First of all let me define some terms related to sorting that comes often when we define it.
External sorting -- When data being sorted doesnt fit into the main memory of a computing device(usually RAM) and a slower kind of memory(usually a hard drive) needs to be used.Suppose we have 10 MB of RAM and data is 12 MB to be sorted then in this case external sort is used. Merge sort is one example of external sort as a core.
Inplace sorting - It requires very little additional space besides the initial array holding the elements that are to be sorted. For sorting N elements, O(logn) extra space is required.This is reasonable because in a purely mathematical analysis of the algorithms, any sorting algorithm that operates on a contiguous array requires O(log n) extra space, since this is the number of bite required to represent an index into the array.
Stable -If the order of similar objects are maintained as in the given input after sorting.


reference: wikipedia

List of sorting algorithms
In this table, n is the number of records to be sorted and k is the number of distinct keys. The columns "Best", "Average", and "Worst" give the time complexity in each case; estimates that do not use k assume k to be constant. "Memory" denotes the amount of auxiliary storage needed beyond that used by the list itself.
These are all comparison sorts.
Name Best Average Worst Memory Stable Method Notes
Bubble sort O(n) — O(n2) O(1) Yes Exchanging Times are for best variant
Cocktail sort O(n) — O(n2) O(1) Yes Exchanging
Comb sort O(n log n) — O(n log n) O(1) No Exchanging
Gnome sort O(n) — O(n2) O(1) Yes Exchanging
Selection sort O(n2) O(n2) O(n2) O(1) No Selection
Insertion sort O(n) — O(n2) O(1) Yes Insertion
Shell sort O(nlog(n)) — O(nlog2(n)) O(1) No Insertion Times are for best variant
Binary tree O(nlog(n)) — O(nlog(n)) O(1) Yes Insertion
Library sort O(n) O(nlog(n))O(n2) O(n) Yes Insertion
Merge sort O(nlog(n)) — O(nlog(n)) O(n) Yes Merging
In-place merge O(nlog(n)) — O(nlog(n)) O(1) Yes Merging Times are for best variant
Heapsort O(nlog(n)) — O(nlog(n)) O(1) No Selection
Smoothsort O(n) — O(nlog(n)) O(1) No Selection
Quicksort O(nlog(n)) O(nlog(n)) O(n2) O(log n) No Partitioning Naive variants use O(n) space
Introsort O(nlog(n)) O(nlog(n)) O(nlog(n)) O(logn) No Hybrid
Patience sorting O(n) — O(nlog(n)) O(n) No Insertion Finds all the longest increasing subsequences within O(n log log(n))

This table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlog(n)) lower bound.
Name Best Average Worst Memory Stable
Pigeonhole sort O(n+k) — O(n+k) O(k) Yes
Bucket sort O(n) O(n) O(n2) O(k) Yes
Counting sort O(n+k) — O(n+k) O(n+k) Yes
Radix sort O(nk) — O(nk) O(n) Yes

This table describes some sorting algorithms that are impractical for real-life use due to extremely poor performance or a requirement for specialized hardware.
Name Best Average Worst Memory Stable Cmp Other notes
Bogosort O(n) O(n × n!)unboundedO(1) No Yes
Stooge sort O(n2.71)— O(n2.71) O(1) No Yes
Bead sort O(n) — O(n) — N/A No Requires specialized hardware
Pancake sorting O(n) — O(n) — No Yes Requires specialized hardware
Sorting networksO(log n)— O(log n) — Yes Yes Requires a custom circuit of size O(nlogn)

To be continued...

AMAL &%$#@*&#$ made me do this again.

After a long time I'm back with my crappy blog.But I promise this wont gonna be an usual stuff as I used to write abt. No heartbreaks , no senti, no complaints, no sad moments nothing of that sort. But to go with the rythm with world I'm here to make one more surprise with a change. Amal raj an &@%$#$%^# made me write it but thanks to him I have started bloggin again. Here are few updates before writing the original things.
It's almost one year I've been in bangalore. Since january I have been enjoying a lot a lot. You cant imagine how much we had fun (of course we had fun but some guys pretend as if they didnt enjoy) since last four months. A ever complaining guy now turned into a sensible one as I have seen the world with different eyes. Why to complain? Just keep urself in place of the person abt whom u r complaining You will realise they are always right and it is you who are wrong and so was I. Anyway almost all the weekends I went out mostly with two M***** hehehehhe guess who?
Chalo ab bahut ho gaya.... kuchh kaam ki baat tho likho. yeah I'm here today to discuss with you about strings in C. Let's start.

String

A character string constant in C represents the address of an area of memory that holds the characters in the constant followed by a null character.
String is an array of char variables, with the last character in the string followed by null.
String is something in double quotes mark. "like this" ... this was u can declare something at the point of its use.
Although they are arrays of char , (not const char), attempting to modify them result into undefined behavior.
whenever a string in quote is seen , it has two effects 1. it provides declaration 2. substitute for a name.It makes a hidden declaration of char array.
Pointers are obviosly not arrays.
C has only only dimensional arrays and size of array must be fixed at compile time.An element of array can be of any type it can be another array thats how multidimensional arrays are implementated in C.
Only two things can be done on array.determine its size and obtain a pointer to its first element.All other array operations are actually done by pointers

i= var[10][20] is equivalent to i = *(*(var + 10) + 20)
Now concatanation.....
char *r;
strcpy(r,s);
strcat(r,s);
It wont work because r is not pointing anywher.it must have place to point somewhere.that memory must be allocated somehow.
now this way...
chat r[100];
strcpy(r,s);
strcat(r,s);
This will certainly work as long as strings pointed to by s and t aren't too big.
again this is another way that will work definitely
char *r,*malloc();
r = malloc(strlen(s) + strlen(t) + 1);
strcpy(r,s);
strcat(r,s);
This might fail only if malloc cant allocate the requested memory, so in that case it will return null.Memory must be freed when we are done with r. Since local we allocate memory this way r[100] then it is automatically freed after the program.But since we have explicitly allocated memory so we have to free it explicitly.
so this final concatanation can be written this way
r = malloc(strlen(s) + strlen(t) + 1);
(!r)
{ complain();
exit(1); }
strcpy(r,s);
strcat(r,s);
free(r); //sometime later

Now possible implementation of strcat
char * mystrcat(char *s,char *t)
{
s = malloc(sizeof(strlen(s) + strlen(t) +1));
while(*s) ++s; //important step
while(*t) { *s++ = *t++; }
return s;
}
char * (char *s,char *t)
{
char *temp = s + strlen(s);
strcpy(temp,t);
return s;
}

There is no way to pass an array to a function directly.Using an array name as an argument immediately converts in to a pointer to the initial element of the array. like char hello[] = "hello";
declares hello as an array of characters.Passing array to a function is precisely equivalent to passing the address to its initial character.
so hello and &hello[0] both are equivalent when passed to a function as argument.
function (char s[]) and function (char *s) are equivalent.
But extern char *hello; is definitely not the same as extern char hello[];
Copying a pointer doesnt copy the thing it addresses.
eg. char *p,*q;
p="abc";
q=p;
now q will point to the same memory location as p was pointing to that means q also points to 'a' i.e first character of abc. Now if we do q[1] = 'Y'; then p as wll as q will now point to memory location containing the string aYc;

Null pointers are not null strings
The result of converting an integer to a pointer is implementation dependent, with one important exception that is constant 0, which is converted to a pointer that is unequal to any valid pointer. Imp point to note here is that when 0 is used as pointer that must never be derefrenced. so it is valid to write if (p== (char *) 0) ..... but its not valid to write if(strcmp (s , (char *) 0) == 0) because strcmp always looks at memory addressed by its arguments. If p is Null pointer then printf(p) and printf("%s" , p) are undefined. It depends on machine. To be continued ......

New Year Memories

First of all I wish u a very very happy new year to those who landed on this unknown page by mistake or by knowingly.
Really when U have anything to share then BLOGGING is the best and only option. This year brought lots of fun so far to me. I personnally enjoyed a lot. The same crowded road of bangalore tht could turn a simple humble guy into a crazy monster , the noisy streets where one can't even think of moving peacefully so irritating , the same dusty road with lods of smokes coming & making this air unconfortable to breathe..... were really fuming us with lods of excitement inside us. These things once we rejected felt like soothing to our uncontrolled mind. All those stupid old items took the shape of new things. Everything was looking new in this approaching new year. Well journey began when we had a plan of going out somewhere. Initially no one except me amal was much interested. But later we became 8 but u know some guys are really &%^$#@! so we were only 6 at the moment we were out.
Now journey of unknown began atleast 4 me because I didnt know nething abt it. I was just prepared for any fun so there was no question of wher to go ... wht to do.. how to do .. n most importantly why to do ........ 4 for it was JUST DO IT DUDE. We reached at Wonder la at nearly 2:00 PM. For those who dont know wht is the place called wondel la .......... It is an amusement park with lots of water games and big jhulas (swings n all). First one was looking very easy and we were all confident. So couldnt wait to take a ride. But I could hardly enjoy as it was just scary n 4 me it was not at all good (must be the same with others too but pretending as if they enjoyed a lot :D).But thnks god it was 4 short duration so could save my a$$. The second ride I knew in advance tht it will be gonna more scary thn the previous one but still took risk though knew tht I wont be enjoyed when I m there on the ride. We sat like kings n came out of tht as we lost the battle of panipath and were craving 4 a deep breathe. Though all were saying we enjoyed and we enjoyed but deep down everyone's heart it was stil some panic hidden inside. Now it was the turn of 3rd ride which was horizontal swing and was looking more scary thn other previous two. I was not willing to go but unfortunately I had to go and for my surprise it was coooool thn other two for me but for others not so cool as I was sitting between amal and sireesh so no tension 4 me from left as well as right cuz they had to take all the tensions. Only tension I had during tht time was if I would be flown out of tht but this was additional fear to others including going right n left.
The fourth ride was cooool no tension I would see clearly into eveyone's eyes tht we all enjoyed it fully no fear no heartbreaking nothing of tht sort. It was just to take rest n to relax 4 a while. Then we went to virtual reality because our heads were still moving. We had another fun there as it was more or less cooool no extra tension. we had some soft drinks then we miled towards other adventure (truely speaking 4 me it was not adventurous as smt wrong was happening in my stomach). We had some more rides along with termite train. Then me and sireesh wanted to have fun with splashing water. Then we made up our minds n went inside the water poool. There we had many rides n games. we also enjoyed artificial water current. Well srry for not introducing who WE were. Me AMal , Sireesh, Kakaji, Anubhav and Swati.
Around 8 we retuned 4 dinner. oh agin forgot I cudnt resist myself going on the dance floor n danced 4 awhile. Well it is worth mentioning here tht Amal n Anu tried all the rides N swati 1 less thn them me n sireesh 1 less thn her and kaka ji 1 less thn me n sireesh. The real adventure started when we were planning 4 our dinner ...... we tried to call some restaurant n wanted to book but No luck thr. we reached to bombay post to personnaly visit but it was a big waiting list there so was the case with others too. Lastly we decided to have pizza n went to pizza hut but we all unlucky till 11 we didnt get the place but some hope came when we saw some places were empty so we had our last dinner of the year there in pizza hut. Though it was last but it was not at all least. it was now 11:40 I guess. we then took an auto n while we were on auto the big hand of the watch crushed the little one and shown its supremacy tht landed us into 2006.
Thats how was our small story of new year celebration after coming we all slept in AMal's room. But since then I had lots of things to share but now time is not premitting so would like to rest my tiny hands with small words......... Erase ur bad memoies of past to protect your sweet memories of future.