Memory allocation in C

In a C program we can have three types of variables


static variables, global variables {initialized + uninitialized}, automatic variables


a computer program memory is divided into three sections


data segment {DATA + BSS + HEAP}
stack
code segment


1) Data segment :


a)DATA : contains
----> global and static variables used by the program that are initialized.
Ex: static int i = 10 will be stored in data segment and global int i = 10 will be stored in data segment.


can be further divided into
=> initialized read-only area
e.g. const char* string = "hello world" makes the string literal "hello world" to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.
=> initialized read-write area.
string defined by char s[] = "hello world" in C and a C statement like int debug=1 outside the main would be stored in initialized read-write area.


b)BSS
The BSS segment also known as uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code. For instance a variable declared static int i; would be contained in the BSS segment.


c)Heap
The Heap area is managed by malloc, realloc, and free, The Heap area is shared by all shared libraries and dynamically loaded modules in a process.


2) Stack
The stack area is just below the heap area and they grow the opposite direction.
The stack area contains the program stack, a LIFO structure, A "stack pointer" register tracks the top of the stack; it is adjusted each time a value is "pushed" onto the stack.
stores local (auto) variables, passing function arguments, storing return address, etc


3) Code segment,
also known as a text segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.
It has a fixed size and is usually read-only. If the text section is not read-only, then the particular architecture allows self-modifying code.


links
http://www.bravegnu.org/gnu-eprog/c-startup.html
http://blog.ooz.ie/2008/09/0x03-notes-on-assembly-memory-from.html
http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap
http://www.maxi-pedia.com/what+is+heap+and+stack

difference between pointers and arrays

Are these two things same?

char* firstname = "rohit;

char secondname[] ="jangid";

answer is NO, they are not same .

why ?

suppose both these lines are there in a program hello.c.
two things happen

memory to "rohit" is allocated in a write protected area of the program also called "data section" of the program, means that we can't make any changes in "rohit". obviously firstname is only pointing to this memory section and we can use firstname++ without any error

whereas memory to "jangid" is actually allocated in a local stack, in array secondname.
here secondname can be treated as const pointer, which means that we can's use secondname++, but we can modify the string "jangid" without any error as it is not protected.

longest increasing subsequence

problem: given an integer array, find the longest increasing subsequence in it.

solution : trivial dp problem.

code // ->

finding binomial coefficient

problem: find the coefficient of x^r in the expansion of (x+1)^n . nCr basically

solution : using dynamic programming

8 queens problem

problem : you have to place 8 queens on a chess board in such a way that no two queens are able to kill each other. generate all such ways

solution : use backtracking to trace all the possible ways to do this. there are 92 such ways

note: there is no need to use 2d array to represent chess board , here chess board can be represented as single dimension array chess[], where chess[i] = j implies a piece is there on i'th row and j'th column.

tree from inorder and preorder

problem : given preorder and inorder traversal of a binary tree , generate the tree from it.

solution:

lets take the basic case first

given: inorder and preorder traversals of a tree in array form

assuming tree to be having unique elements only

returns the head pointer to the tree generated



output at code on ideone

E R data model

consists of sets of entities and set of relationships between those entities.

entity ==> set of attributes

relationship ==> an association between several entities

note: a function that an entity plays in a relationship is called its role

relationship's attributes are called descriptive attributes

mapping cardinalities : better explained in korth

weak entity sets : entity that cannot be uniquely identified by its attributes alone; therefore, it must use a foreign key in conjunction with its attributes to create a primary key. The foreign key is typically a primary key of an entity it is related to.
a weak entity set is indicated by a bold rectangle (the entity) connected by a bold type arrow to a bold diamond (the relationship). This type of relationship is called an identifying relationship

Relational data model

relational model consists of collection of tables (relations) . table contain columns and rows. row in a table represents the relationship between the set of values.
we can say that basically table is collection of relationships(specified by rows)

note : n-tuple means a tupe with n values where tuple means a row .

main topics

keys :
definitions

super key : is a set of one or more attributes that , taken collectively , allow us to identify uniquely a tuple in the relations , so there can be many different super keys in a relation

candidate keys : a super key whose no subset is a super key ( basically minimal superkey)

primary key : a candidate key chosen by the database designer as the principle means of identifying the tuples ( example as roll_no)

foreign key : if a relation(referencing relation) contains within its attribute the primary key or even the super key of another relation(referenced relation) than that attribute is called foreign key.
a row in the referencing table cannot contain values that don't exist in the referenced table (except potentially NULL).

note : A FOREIGN KEY constraint can reference columns in tables in the same database or within the same table. These are called self-referencing tables. For example, consider an employee table that contains three columns: employee_number, employee_name, and manager_employee_number. Because the manager is also an employee, there is a foreign key relationship from the manager_employee_number column to the employee_number column.

note: The constraint enforces referential integrity by guaranteeing that changes cannot be made to data in the primary key table if those changes invalidate the link to data in the foreign key table. If an attempt is made to delete the row in a primary key table or to change a primary key value, the action will fail when the deleted or changed primary key value corresponds to a value in the FOREIGN KEY constraint of another table. To successfully change or delete a row in a FOREIGN KEY constraint, you must first either delete the foreign key data in the foreign key table or change the foreign key data in the foreign key table, which links the foreign key to different primary key data.


Relational operations :

join
Cartesian product
union
intersection
and set difference

DBMS: basics

dbms ==> database management system basically comprises of (database + a program to manage it)

to better categorize the database, there are certain types of data model

relational :
there are tables to represent data + the relationships between them, table contain columns, tables are also called relations and columns as attributes.

ER model : contain set of entities( like objects ) and set of relationships among these objects

object oriented : not that much important will deal in later posts :-)


to specify database obviously we need a language : this language comprises of two parts
1) data definition language (DDL) specifies schema
2) data modification language (DML) database queries and updates.

they are basically implemented as different types of statements in one general language like SQL

lets not go into the details of DML for now, and focus on DML

every data has some sort of constraints on like, roll number of students can't be negative , cell numbers can't be zero digit etc
so while specifying database we need some way to specify these contraints as well. this is done in DDL,
some contraints are

1) domain constraints
2) referential integrity
3) assertions
4) authorizations

DDL is an interpreted language and its output is stored in a data dictionary which contains metadata.

now we have some good basics , so lets dive into some detailed topics

? what is database design?

basically database design means that you have to design schema for database

design process : ( from korth )

1) understand the user requirements
2) and decide the data model (quite obvious)
3) using the model, transform user requirements into conceptual schema of database
if model is relational decide tables, columns.
use normalization enter the set of attributes and get the tables as output
or we can use ER model as well .

the widely (particularly for large scale) used data model is the ER model .
ER model has some mapping cardinalities which are the additional rules to be satisfied by the database contents, ( the number of entities to which another entity can be associated )

the concept of normalization : gives us the benefit of auto generated tables with no lesser redundancy but on the cose of extra information required called functional dependencies

two bad things that can go while designing a database is

1) information can get repeated
2) we may get unable to represent certain desired information

definitions

atomicity : all or none
consistency : same everywhere
isolation
durability : persistance even after the system failure
transaction : collection of operations that perform a single logical function.

Jumping in array

problem statement : An Array Contains values greater than or equal to zero. from any index "i" you can jump in a range of 1 to array[i] .Find Minimum Number of such Jumps to get from Start to Last Position.

solution using dynamic approach



solution using greedy approach

Permutations of a String

Problem : given a string as input, print its all the permutation

ex: input "abc"
output : abc, bca, cba, acb, cab, bac.

concept : use backtracking to traverse all the paths

Paragraph edit

problem statement : given a paragraph string, remove the extra spaces
for example = " welcome       to      linux ! "
output = "welcome to linux !"

concept : traverse the string and set flag when one space is encountered , skip the input till next non space character is found, reset the flag..
quite simple but useful program



time complexity O(n)

25 horses , fastest five

This is a different version of fastest 3 horses from 25 when there is no stop watch
for fastest 5 , the solution is 8 races.
the solution is found to be somewhat dependent on outcomes of subsequent steps .
since I don't know the exact answer so solution may be more than 8 as well.
verifications are welcome

Duck in the pond

Puzzle : A duck is swimming at the center of circular pond of radius r. given that It can fly only from land and so cannot fly from water . Furthermore, the fox cannot swim. The speed of fox is four times the speed of duck . How should the duck swim to evade the fox and fly eventually. assume both duck and fox to be perfectly smart.

solution ==>

the puzzle is really very simple just make sure that when duck reaches land, fox is not there but wait the fox is four times faster than duck

so duck needs a strategy

1) fox has to travel in circumference i.e. 2*pi*r. time taken by it to complete one circle = 2*pi*r/4v (where v is the speed of duck)

2) now notice that same time will be taken by duck if it swim in a smaller circle , the radius of that circle comes to be r/4

3) the question is solved by now , duck needs to swim in a circle radius slightly lesser than the r/4 and she can make sure that after certain time, she will be exactly opposite to fox

4) at this position duck should start moving towards the shore , distance 3r/4 , time taken is 3r/4v

5) fox also starts moving towards that point , time taken by fox will be pi*r/4v

clearly 3r is lesser than pi*r which is 3.14*r

6) thus duck will reach earlier and fly away

Closest Ancestor in a Tree

Problem : Given a binary tree and two node pointers. Return the pointer to their closest ancestor.

method 1: using recursion.

search for the two nodes and keep a count (initialized to zero) if node 1 is found update it by 1 and if node 2 is found update it by 2. when counter's value becomes 3 , we have found our ancestor node, return it.
It took me some while to understand the recursion in this problem but after understanding this, it is pretty obvious.

Measure 9 hours with hourglasses

puzzle : How will you measure 9 hours using only a 4-hour and 7-hour hourglass?

quite easy puzzle, can be done with hit and trial

Solution ==>

1) start with both the hour glasses fresh.

2) after 4 hours when A is empty , just turn A upside down

we have measured 4 hours by now

3) after 3 hours ,A will be empty and 1 hour sand will be remaining in A, just turn B upside down

we have measured 4+3 = 7 hours by now

4) after 1 hour when A is empty , B has 1 hour sand remaining
turn B upside down

we have measured 7+1 = 8 hours by now

5) after 1 hour B will be empty

we have measured 8+1 = 9 hours

6) done...

Transfer the payload

Puzzle : Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Extend your answer for n trucks
<br/>
solution ==>

point to be kept in mind : it is not given that they have to travel integral distances only .. so don't assume if not given.

in questions like this, usually a series is involved . so keep lookinv for pattern

concept : we should try to minimise the loss of fuel and in the end we should have one truck with full range fuel remaining

we'll have to start with all the trucks in the beginning .
after 2 km notice that we have spent 100 km range fuel and if we drop one truck we'll have 98 km range fuel that can refill all the remaining 49 trucks.

similarly from there after covering every 100 km drop one truck and refill the remaining

for second time , let us travel 'x' km . fuel spent = 49x if we drop one truck we'll have 100 - x fuel and we have to refill 48 trucks to 100 . means
100-x = 48x => x = 100/49

similarly for other distances

we have a series here

100/50 + 100/49 + 100/48 ...+...100/1

it is harmonic progression
approx sum = 450

this is possible only because trucks are allowed to travel non integral distances

final answer is 450 miles

four litre water

This is an easy one

Puzzle : You infinite supply of water and two containers, one 3 liters and other of 5 liters, how would you measure 4 liters?

solution ==>

simply

1) fill the three litre jar

2) empty it in 5 litre jar

3) again fill 3 litre jar and empty it in 5 litre jar, you have 1 ltr left in 3 ltr jar

4) empty 5 litre jar and pour that one litre from 3 ltr jar into it , so now our 5 ltr jar is containing 1 ltr water

5) again fill 3 ltr jar and pour it into the 5 ltr jar.

6) you have 4 ltr of water in 5 ltr jar .

7) the end ....

Tallest of the Smallest...

Puzzle :
16 soldiers are made to stand in a 4*4 matrix.Every soldier has a different height.
Now from every row the tallest soldier is named T1,T2,T3,T4 respectively.
and the shortest among these 4 soldiers is named SG (short guy).
similarly, from every column the shortest soldier is selected and named S1,S2,S3,S4 respectively and tallest among these four is named TG (tall guy).
now you have to tell who is taller SG or TG??? n SG & TG are not the same person
solution ==>
the answer should be independent of the distribution of the soldiers if they are fulfilling the given conditions .
so we can have any one valid configuration
let the config be as shown

let t1 = SG
TG can be from {S1,S2,S3,S4}
case 1 : TG = s1, clearly from second given condition . SG > TG
case 2 : TG = s2,
let a[0][1] be 'x'. SG>x and x>TG => SG > TG
case 3 : TG = s3, SG>TG (same as case 2)
case 4 : TG = s4, clearly from first given condition . SG>TG
thus for all the cases
SG is always greater than TG

Fastest 3 Horse Puzzle

puzzle : you have 25 horses and a racetrack with 5 lanes which means that at 5 horses can race at a time on that track . you don't have any stopwatch. find the three fastest horses among them

solution

It can be done in 7 races

let the horses by h1,h2,.., h25
h1 h2 h3 h4 h5
h6 h7 h8 h9 h10
h11 h12 h13 h14 h15
h16 h17 h18 h19 h20
h21 h22 h23 h24 h25

make groups of 5 and race them , so we'll have 5 races

1) Remember that the winners are not necessarily containing the fastest three

2) we can eliminate the last 2 horses in each race as in no possible way that can be the fastest three. that eliminates 10 horses. so we have 15 horses left

h1 h2 h3
h6 h7 h8
h11 h12 h13
h16 h17 h18
h21 h22 h23

3) again race the winners of the first five races , let the winners be in the same order as above by chance as this will not affect the answer. ;-)

4) again eliminate the last 2 horses and the horses beaten by them in first 5 races .
that eliminates 2+ 4 = 6 horses , so we are left with 9 more horses

h1 h2 h3
h6 h7 h8
h11 h12 h13

5) we are sure that the winner of 6th race (h1) is the fastest horse. so we can eliminate the horse that came that came third in the other races . that leaves only 5 horses

6) race the last batch of horses and select the first and second horse. they will be the second and third fastest in all

Fox in the hole

There is a fox and 7 holes . The fox lives in one of the hole everyday and during night she moves to a hole either left or right. The farmer comes in the morning and can check any one hole, What strategy should be applied by the farmer to catch the fox in minimum number of days.

solution == >

important thing to notice here is that , on any day fox will be either on an even numbered hole {2,4,6} or odd numbered hole{1,3,5,7}

S1 = {2,4,6}
S2 = {1,3,5,7}

let on morning one, she is in set S1

than we have 3 possible cases

2, {1,3}, {2,4}, {1,3,5}, {2,4,6}

4, {3,5}, {2,4,6}, {1,3,5,7}, {2,4,6}

6, {5,7}, {4,6}, {3,5,7}, {2,4,6}

this are the only possible cases for 5 mornings

now observe this sequence for farmer

2,3,4,5,6

case 1: caught on first morning
case 2: caught on at most fifth morning
case 3: caught on at most fifth morning

proof that this will always work

suppose 2 fails , means she should be in either 4 or 6 , so she will move to either 3,5,7 . if 3 fails means she was in 6 so she moved to either 5 or 7 . so next will be either 4 or 6 . if 4 fails than she was moved to 7 so next she will move to 6 and will eventually get caught.

the above logic is to be processed in mind to be able to solve this question in time :-)

if our base case is wrong, means she is on set S2 on first morning
than also she will be surely in set S1 on 6th morning . so

the complete sequence can be

2,3,4,5,6,2,3,4,5,6

means 10 days will be enough to catch the fox.

but why one should think of the given sequence?

conclusion
their exist 4 sequences in all .
2,3,4,5,6,2,3,4,5,6
6,5,4,3,2,6,5,4,3,2
2,3,4,5,6,6,5,4,3,2
6,5,4,3,2,2,3,4,5,6

note:
divide things into sets when choices are there
use hit and trial after arriving at some reasonable point .

Depth of a binary tree

Calculate the depth of a given binary tree using recursion. concept : start from node and recurse both left and right branches taking the maximum of the two and keep a depth variable to store the current depth