Fragen im Vorstellungsgespräch bei Google: You are given a linked list w... |

Frage im Vorstellungsgespräch

Software Engineer-Vorstellungsgespräch München, Bayern

You are given a linked list with each node containing one

  extra pointer. Extra pointer points to any random node in the list.. Create a copy of this list..

Antwort im Vorstellungsgespräch

3 Antworten


I created a hash map which stores the mapping of corresponding nodes in the original list and the copied list.. iterate through the entire list starting from the first node, check if it exists in the map, otherwise create new and add it to the map.. Time complexity O(n), space Complexity O(n)..
Better approach (which I couldn't think in the interview). There is a cleverer solution to this problem which doesn't require hash map. Basically you can use the extra pointer to point to the corresponding node in the copied list..

Bewerber im Vorstellungsgespräch am 29.02.2016

it sou

Anonym am 01.03.2016

it sounds like a graph to me , using BFS to traverse each other and copying each of them would be right ?

Anonym am 01.03.2016

Antwort oder Kommentar posten

Um dies zu kommentieren, bitte anmelden oder Konto anlegen.