Frage im Vorstellungsgespräch

Vorstellungsgespräch für eine Beschäftigung als Software Engineer

-München, Bavaria, Bayern

Google

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

Antworten zu Vorstellungsgespräch

3 Antworten

0

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..

Anonym am

0

it sou

Anonym am

0

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

Anonym am

Antwort oder Kommentar posten

Um dies zu kommentieren, bitte anmelden oder Konto anlegen.