Given an array A[] and a number x, check for pair in A[] with sum as K

Let’s say the array is of size N. The naive way to solve the problem, for each element checking whether k-element is present in the array, which is O(N^2). This is of course far from optimal and you might not want to mention it during an interview as well. A more efficient solution would be to sort the array and having two pointers to scan the array from the beginning and the end at the same time. If the sum of the values in left and right pointers equals to k, we output the pair. If the sum is less than k then we advance the left pointer, else if the sum is greater than k we decrement the right pointer, until both pointers meet at some part of the array. The complexity of this solution is O(NlogN) due to sorting.

The O(N) algorithm uses the set data structure. We perform a linear pass from the beginning and for each element we check whether k-element is in the set of seen numbers. If it is, then we found a pair of sum k and add it to the output. If not, this element doesn’t belong to a pair yet, and we add it to the set of seen elements. The algorithm is really simple once we figure out using a set. The complexity is O(N) because we do a single linear scan of the array, and for each element we just check whether the corresponding number to form a pair is in the set or add the current element to the set. Insert and find operations of a set are both average O(1), so the algorithm is O(N) in total. Here is the code in full detail:

#include<iostream>
#include<set>

void printPair(int *array,int size,const int K)
{
std::set<int> intset;
std::set<int>::iterator itr;
for(int i=0;i<size;i++)
{
int temp=array[i];
if((itr=intset.find(temp))!=intset.end())// this now no element is there.
{
intset.insert(K-temp);
}
else
std::cout<<”Pain(i,j) is sum to K”<<”(“<<temp<<”,”<<K-temp<<”)”<<std::endl;
}
}

Posted in Uncategorized | Tagged | Leave a comment

Casting Operators of C++ (Static Cast).

This is the first casting operator provided in c++. Syntax for using this operator is

var=static_cast<type_id>expression

static_cast can perform conversions between pointers to related classes, not only from the derived class to its base, but also from a base class to its derived. This ensures that at least the classes are compatible if the proper object is converted, but no safety check is performed during runtime to check if the object being converted is in fact a full object of the destination type. Therefore, it is up to the programmer to ensure that the conversion is safe. On the other side, the overhead of the type-safety checks of dynamic_cast is avoided.

class CBase {};
class CDerived: public CBase {};
CBase * a = new CBase;
CDerived * b = static_cast<CDerived*>(a);




Example:- 
class B {
public:
   virtual void Test(){}
};
class D : public B {};

void f(B* pb) {
   D* pd1 = dynamic_cast<D*>(pb);
   D* pd2 = static_cast<D*>(pb);
}

If pb really points to an object of type D, then pd1 and pd2 will get the same value. They will also get the same value if pb == 0.

If pb points to an object of type B and not to the complete D class, then dynamic_cast will know enough to return zero. However, static_cast relies on the programmer’s assertion that pb points to an object of type D and simply returns a pointer to that supposed D object.

Consequently, static_cast can do the inverse of implicit conversions, in which case the results are undefined. It is left to the programmer to verify that the results of astatic_cast conversion are safe.

This behavior also applies to types other than class types. For instance, static_cast can be used to convert from an int to a char. However, the resulting char may not have enough bits to hold the entire int value. Again, it is left to the programmer to verify that the results of a static_cast conversion are safe.


static_cast can also be used to perform any other non-pointer conversion that could also be performed implicitly, like for example standard conversion between fundamental types:

double d=3.14159265;
int i = static_cast<int>(d); 

Or any conversion between classes with explicit constructors or operator functions as described in “implicit conversions” above.

The static_cast operator cannot cast away the constvolatile, or __unaligned attributes. There is a special casting operator (const_cast) for information on removing these attributes.

Posted in cpp facts | Tagged | Leave a comment

Memory Layout of C Programs

A typical memory representation of C program consists of following sections.

1. Text segment
2. Initialized data segment
3. Uninitialized data segment
4. Stack
5. Heap


A typical memory layout of a running process

1. Text Segment:
A text segment , also known as a code segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.

As a memory region, a text segment may be placed below the heap or stack in order to prevent heaps and stack overflows from overwriting it.

Usually, the text segment is sharable so that only a single copy needs to be in memory for frequently executed programs, such as text editors, the C compiler, the shells, and so on. Also, the text segment is often read-only, to prevent a program from accidentally modifying its instructions.

2. Initialized Data Segment:
Initialized data segment, usually called simply the Data Segment. A data segment is a portion of virtual address space of a program, which contains the global variables and static variables that are initialized by the programmer.

Note that, data segment is not read-only, since the values of the variables can be altered at run time.

This segment can be further classified into initialized read-only area and initialized read-write area.

For instance the global string defined by char s[] = “hello world” in C and a C statement like int debug=1 outside the main (i.e. global) would be stored in initialized read-write area. And a global C statement like 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.

Ex: static int i = 10 will be stored in data segment and global int i = 10 will also be stored in data segment

3. Uninitialized Data Segment:
Uninitialized data segment, often called the “bss” segment, named after an ancient assembler operator that stood for “block started by symbol.” Data in this segment is initialized by the kernel to arithmetic 0 before the program starts executing

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.
For instance a global variable declared int j; would be contained in the BSS segment.

4. Stack:
The stack area traditionally adjoined the heap area and grew the opposite direction; when the stack pointer met the heap pointer, free memory was exhausted. (With modern large address spaces and virtual memory techniques they may be placed almost anywhere, but they still typically grow opposite directions.)

The stack area contains the program stack, a LIFO structure, typically located in the higher parts of memory. On the standard PC x86 computer architecture it grows toward address zero; on some other architectures it grows the opposite direction. A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.

Stack, where automatic variables are stored, along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.

5. Heap:
Heap is the segment where dynamic memory allocation usually takes place.

The heap area begins at the end of the BSS segment and grows to larger addresses from there.The Heap area is managed by malloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size (note that the use of brk/sbrk and a single “heap area” is not required to fulfill the contract of malloc/realloc/free; they may also be implemented using mmap to reserve potentially non-contiguous regions of virtual memory into the process’ virtual address space). The Heap area is shared by all shared libraries and dynamically loaded modules in a process.

Examples.

The size(1) command reports the sizes (in bytes) of the text, data, and bss segments. ( for more details please refer man page of size(1) )

1. Check the following simple C program

#include <stdio.h>

int main(void)
{
    return 0;
}

[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960        248          8       1216        4c0    memory-layout

2. Let us add one global variable in program, now check the size of bss (highlighted in red color).

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    return 0;
}

[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         12       1220        4c4    memory-layout

3. Let us add one static variable which is also stored in bss.

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    static int i; /* Uninitialized static variable stored in bss */
    return 0;
}

[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         16       1224        4c8    memory-layout

4. Let us initialize the static variable which will then be stored in Data Segment (DS)

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}

[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         252         12       1224        4c8    memory-layout

5. Let us initialize the global variable which will then be stored in Data Segment (DS)

#include <stdio.h>

int global = 10; /* initialized global variable stored in DS*/

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}

[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         256          8       1224        4c8    memory-layout


References:-
http://www.geeksforgeeks.org/archives/14268

Posted in Uncategorized | Leave a comment

Adding more to function overloading in c++

Predict the output of following C++ program.

#include<iostream>
using namespace std;
class Test
{
protected:
    int x;
public:
    Test (int i):x(i) { }
    void fun() const
    {
        cout << "fun() const called " << endl;
    }
    void fun()
    {
        cout << "fun() called " << endl;
    }
};
int main()
{
    Test t1 (10);
    const Test t2 (20);
    t1.fun();
    t2.fun();
    return 0;
}

Output: The above program compiles and runs fine, and produces following output.

fun() called
fun() const called

The two methods ‘void fun() const’ and ‘void fun()’ have same signature except that one is const and other is not. Also, if we take a closer look at the output, we observe that, ‘const void fun()’ is called on const object and ‘void fun()’ is called on non-const object.
C++ allows member methods to be overloaded on the basis of const type. Overloading on the basis of const type can be useful when a function return reference or pointer. We can make one function const, that returns a const reference or const pointer, other non-const function, that returns non-const reference or pointer. See this for more details.

What about parameters?
Rules related to const parameters are interesting. Let us first take a look at following two examples. The program 1 fails in compilation, but program 2 compiles and runs fine.

// PROGRAM 1 (Fails in compilation)
#include<iostream>
using namespace std;
void fun(const int i)
{
    cout << "fun(const int) called ";
}
void fun(int i)
{
    cout << "fun(int ) called " ;
}
int main()
{
    const int i = 10;
    fun(i);
    return 0;
}

Output:

Compiler Error: redefinition of 'void fun(int)'
// PROGRAM 2 (Compiles and runs fine)
#include<iostream>
using namespace std;
void fun(char *a)
{
  cout<<"non-const fun() called";
}
void fun(const char *a)
{
  cout<<"const fun() called";
}
int main()
{
  const char *ptr = "GeeksforGeeks";
  fun(ptr);
  return 0;
}

Output:

GeeksforGeeks

C++ allows functions to be overloaded on the basis of const-ness of parameters only if the const parameter is a reference or a pointer. That is why the program 1 failed in compilation, but the program 2 worked fine. This rule actually makes sense. In program 1, the parameter ‘i’ is passed by value, so ‘i’ in fun() is a copy of ‘i’ in main(). Hence fun() cannot modify ‘i’ of main(). Therefore, it doesn’t matter whether ‘i’ is received as a const parameter or normal parameter. When we pass by reference or pointer, we can modify the value referred or pointed, so we can have two versions of a function, one which can modify the referred or pointed value, other which can not.

As an exercise, predict the output of following program.

#include<iostream>
usingnamespacestd;
voidfun(constint&i)
{
    cout << "fun(const int &) called ";
}
voidfun(int&i)
{
    cout << "fun(int &) called ";
}
intmain()
{
    constinti = 10;
    fun(i);
    return0;
}
References:
Posted in cpp facts | Leave a comment

“Hello World” JNI

Steps to be follow to compile a hello world program on ubuntu

1) Create java file    — MyPro.java

2) Compile with javac
javac MyPro.java
output:- MyPro.class

3) Generate .h file for native cpp class using javah
javah -jni MyPro ( class name generated after javac but donot mention “.class”)
output :- MyPro.h (donot change it).

4) Create c file including this MyPro.h in your source code(nativelib.c).

5) Compile and create .so shared library(I am using ubuntu 10.04)
g++ –shared -o libnativelib.so -I/usr/lib/jvm/java-6-sun/include/ -I/usr/lib/jvm/java-6-sun/include/linux nativelib.c -fPIC
output:- libnativelib.so

g++ -fPIC –shared -o libnativelib.so -I<path to java>/jvm/java-6-sun/include/ -I<path to java>/jvm/java-6-sun/include/linux <source file of c/cpp>

6 Interprate the .class file using java command like
java -Djava.library.path=.  MyPro
java -Djava.library.path=. <name of the generated .class name in step 2>

 

References: StackOverflow

Posted in Uncategorized | Leave a comment

JDK setup for building android source code

Many time I face problem while setting build environment for building android. Specially when i format my machine . After  googling a lot  I find that now Sun-java-6 has be removed from the ubuntu repository so it is a big problem for us because android code uses sun-java for building

sudo add-apt-repository ppa:ferramroberto/java

sudo apt-get update

sudo apt-get install sun-java6-jre sun-java6-bin sun-java6-jdk

update-alternatives –config javac

python 2.6.5

$ sudo add-apt-repository “deb http://ppa.launchpad.net/bzr/ppa/ubuntu lucid main”
$ sudo add-apt-repository “deb-src http://ppa.launchpad.net/bzr/ppa/ubuntu lucid main”
$ sudo apt-get update
$ sudo apt-get install python

Posted in android, Java | Leave a comment

mounting network file system on your ubuntu system

There is a interesting thing about Unix, there is no limit of utilities. One of the utility I come to know is that you can mount the network file-system under your local file system.
All of us know about the file /etc/fstab which Unix read at the time of booting for mounting the drives and there partition.
We can also mount the network file-system which one one has shared on network.
Content of /etc/fstab.

I have added the following line to mount a network drive user /media/ys_networkdrive mount point.

//media/ys_networkdrive smbfs defaults,user=,password=,rw 0 0

If the file-system is shared with read-only permission you can use following option

//7.8.8.5/ys /media/ys_networkdrive smbfs user=ys,password=ys,errors=remount-rw 0 0

This will retry to mount the //7.8.8.5/ys under /media/ys_networkdrive mount point when there is any other occur at the the time of mounting.All is done and now you have to run the command if you are sudoer.

$sudo mount -a

This will apply your changes at the current session also. you don’t need to reboot the system.

Referernce:-
Thanks for the content mentioned in following resoruces.
1) http://www.stackoverflow.com
2) man page for fstab.

Regards
Y$

Posted in Unix | Leave a comment