[quiz] inverseaza o lista simplu inlantuita

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

[quiz] inverseaza o lista simplu inlantuita

Post by Marius Bancila » 30 Jun 2010, 12:00

O mica problema pentru cine e curios.

Sa presupunem ca avem o lista simplu inlantuita, ceva elementar de genul:

Code: Select all

struct Node
{
   int value;
   Node* next;
};

typedef Node* LinkedList;
pentru care avem cateva functii simple de adaugare, afisare, stergere:

Code: Select all

LinkedList push_front(LinkedList list, int value)
{
   Node* crt = new Node;
   crt->value = value;
   crt->next = list;

   return crt;
}

void release(LinkedList list)
{
   Node* crt = list;
   while(crt != NULL)
   {
      Node* next = crt->next;
      delete crt;
      crt = next;
   }
}

void print(LinkedList list)
{
   Node* crt = list;
   while(crt != NULL)
   {
      cout << crt->value << endl;
      crt = crt->next;
   }
}
Sa se scrie o functie de inversare a listei:

Code: Select all

LinkedList revert(LinkedList list)
{
  ???
}
astfel incat programul urmator:

Code: Select all

int main()
{
   LinkedList list = NULL;

   list = push_front(list, 1);
   list = push_front(list, 2);
   list = push_front(list, 3);
   list = push_front(list, 4);

   cout << "list originala" << endl;
   print(list);

   list = revert(list);

   cout << "list inversata" << endl;
   print(list);

   release(list);

	return 0;
}
sa afiseze:
list originala
4
3
2
1
list inversata
1
2
3
4
Si partea interesanta, incercati sa cronometrati cat timp va ia pana scrieti aceasta functie.


Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

User avatar
zlatomir
Membru++
Membru++
Posts: 282
Joined: 04 Jul 2009, 23:59
Location: Arad
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by zlatomir » 30 Jun 2010, 17:34

Code: Select all

LinkedList revert(LinkedList list){
	LinkedList temporara = list;
	LinkedList inversa = NULL;
	while(temporara != NULL){
		list = list->next;
		temporara->next = inversa;
		inversa = temporara;
		temporara = list;
	}
	return inversa;
}
Trebuie sa recunosc ca mi-a luat ceva vreme :oops: , dar nu va spun cat (fara google search)
Misto quiz :thumbsup:

User avatar
Andreas
Membru
Membru
Posts: 117
Joined: 09 Nov 2008, 12:13
Judet: Timiş
Location: Timisoara

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Andreas » 01 Jul 2010, 11:38

Implementarea la care m-am gandit ar fi cam asa:

Code: Select all

LinkedList revert(LinkedList list)
{
  LinkedList revert_list = NULL;
  Node* crt = list;
  while( crt != NULL)
  {
	  revert_list= push_front(revert_list, crt->value);	  
	  crt = crt->next;
  }
  return revert_list;
}
si in main

Code: Select all

int main()
{
	LinkedList list = NULL;

	list = push_front(list, 1);
	list = push_front(list, 2);
	list = push_front(list, 3);
	list = push_front(list, 4);

	cout << "list originala" << endl;
	print(list);

	LinkedList revert_list = revert(list);

	cout << "list inversata" << endl;
	print(revert_list);

	release(list);
	release(revert_list);

	return 0;	
}
si a luat cam 5 minute ;)...hai 10 cu sorbit din cafea cu tot...

Dragos Cojocari
Membru++
Membru++
Posts: 789
Joined: 11 Jul 2007, 14:11

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Dragos Cojocari » 01 Jul 2010, 12:26

Asta nu e problema de C ci de LISP. :P

User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Marius Bancila » 01 Jul 2010, 13:48

Andreas, si daca push_front() nu exista (am fost eu lenes :) ) si ar fi existat doar push_back() care adauga tot timpul la sfarsit, cum faceai?
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

User avatar
Andreas
Membru
Membru
Posts: 117
Joined: 09 Nov 2008, 12:13
Judet: Timiş
Location: Timisoara

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Andreas » 01 Jul 2010, 16:10

Marius, poate te gandesti la lucruri complicate, nu stiu, double pointers, habar n-am...
Eu incerc sa mentin lucrurile cat se poate de simplu si functional...
In cazul cu push_back sigur as pastra o referinta la primul element din lista:

Code: Select all

#include <iostream>

using namespace std;

struct Node
{
   int value;
   Node* next;
};

typedef Node* LinkedList;

LinkedList push_front(LinkedList list, int value)
{
   Node* crt = new Node;
   crt->value = value;
   crt->next = list;

   return crt;
}

LinkedList push_back(LinkedList list, int value)
{   	
	if( list == NULL)
	{
		list = new Node;   
		list->value = value;
	}
	else
	{
		list->next = new Node;
		list = list->next;
		list->next = NULL;
		list->value = value;
	}

   return list;
}

void release(LinkedList list)
{
   Node* crt = list;
   while(crt != NULL)
   {
      Node* next = crt->next;
      delete crt;
      crt = next;
   }
}

void print(LinkedList list)
{
   Node* crt = list;
   while(crt != NULL )
   {
      cout << crt->value << endl;
      crt = crt->next;
   }
}

LinkedList revert(LinkedList list)
{
  LinkedList revert_list = NULL;
  Node* crt = list;
  while( crt != NULL)
  {
	  revert_list= push_front(revert_list, crt->value);	  
	  crt = crt->next;
  }
  return revert_list;
}

LinkedList revert1(LinkedList list)
{
  LinkedList revert_list = NULL;
  Node* crt = list;
  while( crt != NULL)
  {
	  revert_list= push_back(revert_list, crt->value);	  
	  crt = crt->next;
  }

  return revert_list;
}

int main()
{
	LinkedList list = NULL;

	list = push_front(list, 1);
	list = push_front(list, 2);
	list = push_front(list, 3);
	list = push_front(list, 4);

	cout << "list originala" << endl;
	print(list);

	LinkedList revert_list = revert(list);

	cout << "list inversata" << endl;
	print(revert_list);

	release(list);
	release(revert_list);

	LinkedList list1 = NULL;
	LinkedList begin = NULL; 

	list1 = push_back(list1, 1);
	begin = list1;
	list1 = push_back(list1, 2);
	list1 = push_back(list1, 3);
	list1 = push_back(list1, 4);

	cout << "list1 originala" << endl;
	print(begin);

	LinkedList revert_list1 = revert(begin);

	cout << "list1 inversata" << endl;
	print(revert_list1);
	
	release(begin);	
	release(revert_list1);	

	return 0;	
}
ceva de genu...tot cam atat timp ia, mai mult m-am gandit la ce, eventual, urmaresti tu...dar m-am dat batut... :)

User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Marius Bancila » 01 Jul 2010, 17:11

Nu urmaresc nimic anume; sunt doar curios cat de simplu sau complicat e scrierea unei astfel de functii. Desigur ca am scris si eu una prima data; mi-a luat destul de putin timp, dar arata diferit de ce am vazut pana acum.

Cand vorbeam de push_front() si push_back() ziceam ca ca te-ai folosit de un artifact al functiei mele push_front(), si daca n-ar fi existat o astfel de functie, eram curios cu ai fi scris functie de inversare. Cu alte cuvinte eram curios de o functie care nu utilizeaza pe push_front().
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

User avatar
cristianamarie
Membru++
Membru++
Posts: 480
Joined: 12 Mar 2009, 18:47
Judet: Iaşi
Location: Iasi

Re: [quiz] inverseaza o lista simplu inlantuita

Post by cristianamarie » 01 Jul 2010, 19:21

Si varianta recursiva

Code: Select all

LinkedList revert(LinkedList list) {
	if(list == 0) {
		return 0;
	}
	if(list->next == 0) {
		return list;
	}
	Node* next = list->next;
	Node* head = revert(list->next);
	Node* last = head;
	while(last->next != 0) {
		last = last->next;
	}
	last->next = list;
	list->next = 0;
	return head;
}
Nuclear launch detected

Dragos Cojocari
Membru++
Membru++
Posts: 789
Joined: 11 Jul 2007, 14:11

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Dragos Cojocari » 01 Jul 2010, 21:35

head. last - LISP! :) Fara a construi insa o lista noua solutia nu e la fel de eleganta.

Code: Select all

LinkedList revert( LinkedList head, LinkedList tail)
{
   LinkedList reverted = ( tail == NULL ? head : revert( tail, tail->next));
   
   if ( tail) 
	   tail->next = head;

   return reverted;
}

LinkedList revert( LinkedList list)
{
    return revert( NULL, list);
}

User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Marius Bancila » 02 Jul 2010, 09:20

Da, am vazut niste solutii interesante. Dragos, vad ca iti place LISP-ul. ;)

Hai sa pun si eu solutia care am incropit-o in vreo doua minute. Trebui sa recunosc ca prima idee a fost sa fac o functie recursiva, dar apoi m-am gandit ca trebuie sa iasa la fel de simplu (si mai eficient) cu o versiune iterativa. Asa ca am tras un desen si asta e ce-a iesit din el:

Code: Select all

LinkedList revert(LinkedList list)
{
   if(list == NULL)
      return NULL;

   Node* crt = NULL;
   Node* next = list;

   while(next != NULL)
   {
      Node* nextnext = next->next;
      next->next = crt;

      crt = next;
      next = nextnext;
   }

   return crt;
}
Iar daca va intrebati ce mi-a venit, acum vreo cateva zile am citit acest articol Will the real programmers please stand up? in care autorul zice ca:
Here is the question that the vast majority of candidates are unable to successfully solve, even in half an hour, even with a lot of nudging in the right direction:

Write a C function that reverses a singly-linked list.

That’s it. We’ve turned away people with incredibly impressive resumes (including kernel developers, compiler designers, and many a Ph.D. candidate) because they were unable to code a solution to this problem in any reasonable amount of time.
Mi s-a parut putin exagerat. Cred ca multa lume se descurca sa faca asa ceva. Deasta eram curios de timpul de care ati avut nevoie pentru a scrie asta. Sunt sigur ca e departe de cele 30 de minute de care vorbeste autorul.
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

Dragos Cojocari
Membru++
Membru++
Posts: 789
Joined: 11 Jul 2007, 14:11

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Dragos Cojocari » 02 Jul 2010, 10:08

Marius Bancila wrote:Da, am vazut niste solutii interesante. Dragos, vad ca iti place LISP-ul. ;)

Hai sa pun si eu solutia care am incropit-o in vreo doua minute. Trebui sa recunosc ca prima idee a fost sa fac o functie recursiva, dar apoi m-am gandit ca trebuie sa iasa la fel de simplu (si mai eficient) cu o versiune iterativa.
Solutia recursiva nu as folosi-o in practica dar e mai sexy decat cea iterativa.

User avatar
Andreas
Membru
Membru
Posts: 117
Joined: 09 Nov 2008, 12:13
Judet: Timiş
Location: Timisoara

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Andreas » 02 Jul 2010, 11:56

mai o varianta bazata pe countere:

Code: Select all

LinkedList revertByCounter(int nodes, LinkedList list)
{
	LinkedList head = NULL;
	LinkedList reverted = NULL;	
	Node* node = NULL;
	while(nodes--)
	{
		int nodesnext = nodes;
		node = list;
		while(nodesnext--)		
			node = node->next;		
		
		if(head == NULL)
		{
			reverted = push_back(reverted,node->value);		
			head = reverted;
		}
		else
			reverted = push_back(reverted,node->value);		
	}   

   return head;
}
dupa cum vezi Marius, ma incapatinez sa folosesc functiile de inserare deja existente...
nu, variantele voastre recursive sau cu desfacere de noduri sunt elegante...
problema ridicata in articol este cel putin tendentioasa, si dupa parerea mea a nu fi in stare sa faci in timp record o astfel de problema nu stirbeste capacitatea unui programator avansat, developer de sistem, arhitect de sistem etc....
pun pariu, ca desi majoritatea daca nu chiar toti dintre noi au reusit sa rezolve problema din quiz sau cel putin sa inteleaga solutiile propuse, cei mai multi nu ar fi in masura sa conceapa/scrie, decat foarte greu si daca nu cumva l-a folosit recent sau l-a retinut de la scoala ;) , un algoritm care sa genereze combinari matematice...nu e quiz, evident ...

User avatar
zlatomir
Membru++
Membru++
Posts: 282
Joined: 04 Jul 2009, 23:59
Location: Arad
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by zlatomir » 02 Jul 2010, 17:13

turned away people with incredibly impressive resumes (including kernel developers, compiler designers,
Mie mi se pare ca aici cineva exagereaza...

Si alt lucru "ciudat" e ca nici un alt "junior" nu se "baga" la quiz-uri. Oare de ce?

Curaj baieti!!! //nu ne bate nimeni daca gresim, doar ne invata cum sa facem bine data viitoare.
Si in plus, avem doar de castigat daca incercam, reusim si punem solutia pe site (pentru ca e comentata de baieti cu experienta, poate chiar cei care ne vor pune intrebari asemanatoare la urmatorul interviu ;) )

User avatar
Ovidiu Cucu
Fondator
Fondator
Posts: 3778
Joined: 11 Jul 2007, 16:10
Judet: Iaşi
Location: Iasi
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by Ovidiu Cucu » 02 Jul 2010, 17:30

Marius Bancila wrote:
Here is the question that the vast majority of candidates are unable to successfully solve, even in half an hour, even with a lot of nudging in the right direction:

Write a C function that reverses a singly-linked list.

That’s it. We’ve turned away people with incredibly impressive resumes (including kernel developers, compiler designers, and many a Ph.D. candidate) because they were unable to code a solution to this problem in any reasonable amount of time.
[ off-topic ]
Stau si ma intreb la ce-ar folosi asa ceva majoritatii in afara de exercitiu, fun si bineinteles... interview. :D ;)

User avatar
zlatomir
Membru++
Membru++
Posts: 282
Joined: 04 Jul 2009, 23:59
Location: Arad
Contact:

Re: [quiz] inverseaza o lista simplu inlantuita

Post by zlatomir » 02 Jul 2010, 17:44

Ovidiu Cucu wrote: [ off-topic ]
Stau si ma intreb la ce-ar folosi asa ceva majoritatii in afara de exercitiu, fun si bineinteles... interview. :D ;)
Pentru intervievat juniori, astfel de intrebari probabil au rolul de a vedea daca candidatul intelege pointer-ii.
Si de aici si mirarea mea in legatura cu cine a rezolvat quiz-ul (numai eu nu sunt programator?)

Pentru post de senior nu vad rostul intrebarii (mai ales pentru compilers designers si kernel developers)

Post Reply