Last IQODs #12/13

hmm well it seems posting these C++ interview questions is an exercise in futility since unfortunately they're getting too advanced. What i've posted so far have been just the tip of the iceberg at an absolute beginners level and only really dealt with understanding Pointers.

I'm not going to post stupid 'riddle 'questions like MS likes to ask because to me they don't relate to the job at hand. Just talk to Why06 about how insanely stupid those are (I asked him two yesterday haha)

I haven't even gotten into actual 'whiteboard coding' yet, nor broader software development topics a Software Engineer applying for a job is supposed to know. (Networking,Databases,Datastructures, UI Development etc etc)

Just for kicks here's a pair of questions of that type for those who feel daring - NO Wikipedia / Google / MSDN etc allowed in interviews, just off the top of your head - but this will probably be the last of my IQOD posts unless I find the time to make up some simpler ones again

IQOD #12
a) What is a Linked List? and explain the difference between a singly-linked list and a double-linked (or doubly-linked) lists

b) Implement a basic doubly-linked list and write a function to reverse it:

Code:

//Your code goes here

IQOD #13
Consider the following:

Code:

class A
{
     //Fully implemented Class
};

class B : public A
{
     //Fully implemented Class
};

Class C : public A
{
     //Fully implemented Class
}

void DoSomething(A* pArg)
{

//Your code goes here

}

Complete the function 'DoSomething' to detect if 'pArg' is a pointer to an instance of a Class A, B or C object.

Good Luck!

i might answer these tomorrow, my wrist is killing me

Should I post a possible answer to this?

IQOD #12
a) What is a Linked List? and explain the difference between a singly-linked list and a double-linked (or doubly-linked) lists

A Linked list a data structure that is a collection of objects(data-records) in which each object has a a pointer to the next item in the list.
Imagine: A->B->C->D->NULL

a singly-linked list has 1 link , namely to the next item in the list. a Doubly linked listed has 2 pointers: One to the Next Item, but also one to the previous Item which makes traversing the list much easier
Imagine if you will: NULL<-A<->B<->C<->D->NULL

b) Implement a basic doubly-linked list and write a function to reverse it:

First the basic implementation would be something like this:

Code:

struct MPGHNode
{
    int         iData; //Whatever Data we store in this thing, lets do int
    MPGHNode* pPrev; //Previous Node
    MPGHNode* pNext; //Next Node
}

We have a pointer to the next and previous nodes in the list and our 'data' for this node , in this case an int.

Now this is a very convenient data structure because if you wanted to step through all the nodes from beginning to end you could simply do this:

Code:

MPGHNode* current = A;
while(current!=NULL)
{
         //do something with current->iData;
         
        //Now move to the next node
        current = current->pNext;

}

To understand how to reverse it let's imagine we have some data.
I'll write it out step by step (& very inefficiently

) so you can follow what is going on to make this list:

Code:

        MPGHNode* A = new MPGHNode();
	MPGHNode* B = new MPGHNode();
	MPGHNode* C = new MPGHNode();
	MPGHNode* D = new MPGHNode();

	A->pPrev = NULL;
	A->pNext = B;
	A->iData = 1;
	B->pPrev = A;
	B->pNext = C;
	B->iData = 2;
	C->pPrev = B;
	C->pNext = D;
	C->iData = 3;
	D->pPrev = C;
	D->pNext = NULL;
	D->iData = 4;

        //Now set a pointer to the beginning of our list and call our reverse
	MPGHNode* pList = A;
	Reverse(&pList);

Ok so now we have to reverse it.. when you think about it for a while the easiest method becomes:
THe Last Node(called the tail) becomes the First Node (called the head), and all the Prev/Next Pointers are swapped..

Code:

void Reverse(MPGHNode** head)
{
    // Empty list or 1 item in the list
    if(!*head || !(*head)->pNext)
    {
        return;
    }

    // Set first element in the temporary list
    MPGHNode* temp_Head = *head;
    MPGHNode* currentNode = NULL;
    *head = (*head)->pNext;
    temp_Head->pNext = NULL;

    while(*head)
    {
        currentNode = *head;
        *head = (*head)->pNext;

        // Insert node at the front of
        // the temporary list
        currentNode->pNext = temp_Head;
        currentNode->pPrev = NULL;
        temp_Head->pPrev = currentNode;
        temp_Head = currentNode;
    }

    // Update head with the temporary
    // list
    *head = temp_Head;
}

Before we call Reverse you'll notice that in order the value of each iData member is 1,2,3,4.
Now when we returned it's 4,3,2,1. We passed in the Address of our 'pList' Pointer to the reverse
method because we need to change where it points to.

Post some feedback if this makes sense to you guys or if you're having a hard time understanding and i'll try to explain more

IQOD #13
Consider the following:
Complete the function 'DoSomething' to detect if 'pArg' is a pointer to an instance of a Class A, B or C object.

Code:

class A
{
     //Fully implemented Class
};

class B : public A
{
     //Fully implemented Class
};

Class C : public A
{
     //Fully implemented Class
}


void DoSomething(A* pArg)
{



}

Ok so let's say we have:

Code:

A *pA = new A;
B *pB = new B;
C *pC = new C;

Since both B and C are derived from A we can now call DoSomething like this :

Code:

DoSomething(pA);
DoSomething((A*)pB);
DoSomething((A*)pC);

We at this point inside of DoSomething need to figure out what pArg was originally. This is actually quite simple:

Code:

void DoSomething(A* pArg)
{
    B* pWasB = dynamic_cast<B*>(pArg);
    C* pWasC = dynamic_cast<C*>(pArg);
    if(B!=null)
         cout << "It was B!" << endl;
    else if(C!=null)
         cout << "It was C!" << endl;
    else   //both B And C are NULL 
         cout << "It must've been A!" << endl;
}

dynamic_cast<type*>(Pointer to argument) is an interesting thing.
It takes your pointer to an argument and tries to cast it to "type*"
if it works then it returns a pointer of the new type, if not it returns null.

So the 'short/smart ass' answer would've been: oh just use a dynamic cast

oh damnit, completely forgot to answer to these.

I knew about the linked lists, but #13 would've been a struggle, dont think iwould've been able to solve that one

OK at this point in time, i think it is wise that BlackAngel starts to write some epic tutorials on more difficult or obscure concepts. =D .

I just started C++ around 3 months ago. thus i really don't know much of the nuances of the language or programming in general. I haven't even finished my book =< (school snuck up on me and stole my free time.) I'm still trying to learn as much as i can, and reading the book when i have time though.

Either way point is, a tutorial by BlackAngel Would be awesome! =D

Duly Noted (and i've considered doing that for a while now

)

Last IQODs #12/13

Post a Reply

Similar Threads

Tags for this Thread