Wednesday 26 January 2011

Swap two variables without using third and in one line

Couple of weeks back I was interviewing a fresh graduate. Even though they are taught programming, I am not sure if they take it seriously and learn or practice it well. One of the questions I asked was to swap 2 numbers without using a temp variable.

Looking back now, I think it may be a bigger challenge to ask to swap numbers without using a temp variable and in one line. Below are my three different approaches but I would advise you to try it yourself before looking at the answer.


//Program to swap 2 numbers without using 3rd variable and in one line
//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace
std;

void
approach1(int& a, int& b)
{

cout<<"\nApproach 1"<<endl;
a^=b^=a^=b;
}


void
approach2(int& a, int& b)
{

cout<<"\nApproach 2"<<endl;
//b=(a+b)-(a=b); - This should work but doesnt, why?
a =((a = a + b) - (b = a - b));
}


void
approach3(int& a, int& b)
{

cout<<"\nApproach 3"<<endl;
a = ((a = a * b) / (b = a / b));
}




int
main()
{

int
a = 13, b = 29;
cout<<"\nOriginal"<<endl;
cout<<"a = "<<a<<", b = "<<b<<endl;

approach1(a, b);
cout<<"a = "<<a<<", b = "<<b<<endl;

a = 13, b = 29;
approach2(a, b);
cout<<"a = "<<a<<", b = "<<b<<endl;

a = 13, b = 29;
approach3(a, b);
cout<<"a = "<<a<<", b = "<<b<<endl;

return
0;
}


The output is as follows:
Agreed that the above would be applicable only for integers.

Wednesday 19 January 2011

'sizeof' a class

Continuation from last week. What is the sizeof of a class? Wrote a simple program as follows:


//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace
std;

class
A
{

int
a;
};


class
B
{

int
b;
int
someFunc(void) {return b;}
};


class
C
{

void
someFunc1(void) {};
void
someFunc2(void) {};
};


class
D : public A
{

void
someFunc(void) {};
};



int
main()
{

cout<<"Size of class A = "<<sizeof(A)<<endl;
cout<<"Size of class B = "<<sizeof(B)<<endl;
cout<<"Size of class C = "<<sizeof(C)<<endl;
cout<<"Size of class D = "<<sizeof(D)<<endl;
}



The output is as follows:

After finishing this, I found this interesting article here.

Wednesday 12 January 2011

Checking the 'sizeof' doubts

I noticed sometime back that one of my programs behaved unexpectedly in certain scenarios which was traced to an incorrect use of sizeof. As a result, I made a small program to make sure that my understanding of sizeof is correct. Here is the program:



//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace
std;

int
main()
{

char
a[]="";
cout<<"Size of a[] = "<<sizeof(a)<<endl;

char
b[]=" ";
cout<<"Size of b[ ] = "<<sizeof(b)<<endl;

char
c[10];
cout<<"Size of c[10] = "<<sizeof(c)<<endl;

char
* d;
cout<<"Size of d = "<<sizeof(d)<<endl;

char
* e = c;
cout<<"Size of e = "<<sizeof(e)<<endl;

char
f[] = "123456";
cout<<"Size of f = "<<sizeof(f)<<endl;

char
g[] = {'1','2','3','4','5','6'};
cout<<"Size of g = "<<sizeof(g)<<endl;

return
0;
}



The output is as follows:
A lot of interviewers love the sizeof questions.

Have you come across any interesting sizeof problems? Please feel free to add them in comments.

Wednesday 5 January 2011

C++ example of Linked List implementation

It is debatable if Linked lists are needed in C++, especially because STL can do a very good job for the same functionality for which Linked Lists are required. Nevertheless sometimes it maybe convenient to know linked lists.



//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <string>
#include <istream>
#include <limits>

using namespace
std;

class
Node
{

public
:
Node() : next(NULL) {}; //default constructor
Node(const string& s1) : info(s1), next(NULL) {};
string info;
Node* next;
};


Node* getNewNode()
{

//Lets flush the input buffer first
istream& in(cin);
in.ignore( numeric_limits<std::streamsize>::max(), '\n' );

//Read the String from console
cout<<"\tEnter a string: ";
istreambuf_iterator<char> eos; // end-of-range iterator
istreambuf_iterator<char> iit (cin.rdbuf()); // stdin iterator
string s2;
while
(iit!=eos && *iit!='\n') s2+=*iit++;

//Call the constructor with the input string
Node* newNode = new Node(s2);

return
newNode;
}


int
main()
{

Node* head = NULL;
bool
contFlag = true;
char
c;

while
(contFlag)
{

cout<<"\n\n";
cout<<"0. Quit"<<endl;
cout<<"1. Traverse and Print"<<endl;
cout<<"2. Insert node at the start"<<endl;
cout<<"3. Insert node at the end"<<endl;
cout<<"4. Insert after specified number of nodes"<<endl;
cout<<"5. Remove node from the start"<<endl;
cout<<"6. Remove node from the end"<<endl;
cout<<"7. Remove node from a specified number"<<endl;

cout<<"\nEnter your choice: ";
cin>>c;

switch
(c)
{

case
'0':
contFlag = false;
break
;
case
'1':
{

Node* tempNode = head;
int
count = 0;
while
(tempNode)
{

cout<<"\tItem "<<count<<" = "<<tempNode->info<<endl;
tempNode = tempNode->next;
count++;
}
}

break
;
case
'2':
{

Node* newNode = getNewNode();
newNode->next = head;
head = newNode;
}

break
;
case
'3':
{

Node* newNode = getNewNode();

Node* endNode = head;
if
(endNode)
{

while
(endNode->next)
endNode = endNode->next;
endNode->next = newNode;
}

else
//In case its the first element
{
head = newNode;
}
}

break
;
case
'4':
{

Node* tempNode = head;
if
(tempNode)
{

unsigned
num;
cout<<"\tInsert after how many nodes? : ";
cin>>num;
Node* newNode = getNewNode();

unsigned
count = 1;
//If less elements are present then insert at the end
while(tempNode->next && (count < num))
{

tempNode = tempNode->next;
count++;
}

newNode->next = tempNode->next;
tempNode->next = newNode;
}

else

{

cout<<"\tNo nodes present yet"<<endl;
}
}

break
;
case
'5':
{

Node* firstNode = head;
if
(firstNode)
{

head = firstNode->next;
delete
firstNode;
}
}

break
;
case
'6':
{

Node* endNode = head;
if
(endNode) //Atleast one element
{
Node* endEndNode = endNode->next;
if
(endEndNode) //Atleast 2 elements
{
while
(endEndNode->next)
{

endNode = endEndNode;
endEndNode = endEndNode->next;
}

endNode->next = NULL;
delete
endEndNode;
}

else
//Only one element
{
head = NULL;
delete
endNode;
}
}
}

break
;
case
'7':
{

Node* tempNode = head;
if
(tempNode)
{

unsigned
num;
cout<<"\tRemove after how many nodes? : ";
cin>>num;

unsigned
count = 1;
//If less elements are present then return
while(tempNode->next && (count < num))
{

tempNode = tempNode->next;
count++;
}

if
(count == num && tempNode->next && tempNode->next->next)
{

Node* nodeToRemove = tempNode->next;
tempNode->next = nodeToRemove->next;
delete
nodeToRemove;
}
}

else

{

cout<<"\tNo nodes present yet"<<endl;
}
}

break
;
default
:
cout<<"Incorrect selection."<<endl;
}
}


return
0;
}



The output is as follows:
You can try more combinations and if you have ideas for improvements please add in the comments section.

Few things to note:
1. This program is for reference and I have not accounted for memory leaks after pressing '0'.
2. For simplicity, getNewNode() is shown as a seperate function. In a real program, it may be better as a method of class Node
3. General Linked Lists use Struct's but in C++, Structs and Classes are nearly the same so its better to use Class.
4. In C++ there is rarely a need to use Linked Lists. Its better to use the STL which already have vectors, stacks, lists, etc.
5. There should be check for memory allocation and try catch blocks that have been ignored for simplicity