Editing 2483: Linked List Interview Problem
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==Explanation== | ||
− | + | {{incomplete|Created by a LINKED LIST. Please mention here why this explanation isn't complete. Do NOT delete this tag too soon.}} | |
− | + | {{w|Linked_list|Linked lists}} are a common way of working with data pointers in what's called a graph, making it a common interview question involving manipulating or otherwise interacting with a linked list. Possibly because programmers in the current day rarely work with a linked list directly, Randall suggests that such structures belong in a "technology museum," and thinks it would be more beneficial to mankind to email the list to such a museum rather than perform any useful work with it. Low-level software development is slowly getting replaced by automated code generation, but it is still very important to understand how it works. | |
− | A linked list is a way to store | + | A linked list is a way to store data in a computer. Each piece of data is stored with a pointer to the next piece. This makes it very easy to add new data in the middle, since only one existing pointer must change to point to the new data. The drawback of a naive implementation can be that finding data may require following the entire chain. Technical programming interviewers like to see if applicants are familiar with the structure and the computational complexity concept itself. |
− | Linked lists are, historically, one of the two main data structures that represent sequential data, along with arrays. Unlike arrays, they have the theoretical advantage of | + | Linked lists are, historically, one of the two main data structures that represent sequential data, along with arrays. Unlike arrays, they have the theoretical advantage of O(1) insertions and deletions thanks to not needing to reallocate the entire structure, but have O(n) random access (see {{w|Linked_list#Linked_lists_vs._dynamic_arrays|comparisons}}). However, modern processors' cache structure favors data that are located next to each other, pre-fetching the adjacent items, and modern processors can perform bulk memory moves, making resize operations faster. Finally, using linked lists usually implies dynamic allocation of each list member, which adds overhead, particularly for smaller data items; many small allocations also tend to fragment memory, which can lead to it being wasted and unavailable to the app later, particularly in long-running processes such as web servers. These properties tend to make linked lists poorly suited for most system programming applications in which a programmer might write algorithms to manipulate data structures, instead of using existing libraries. |
Modern programming languages usually provide abstractions (often named "array," "vector" or "list") which interact with the sequential data at the memory level, providing access to this data while using arrays, linked lists, hybrids of the aforementioned technologies, or other approaches, and the programmer doesn't necessarily need to care one way or another. Knowing the underlying concepts is still useful, however, when creating fast running code which scales well to large data, avoiding (e.g.) traversing the list over and over again, or performing particularly inefficient operations. | Modern programming languages usually provide abstractions (often named "array," "vector" or "list") which interact with the sequential data at the memory level, providing access to this data while using arrays, linked lists, hybrids of the aforementioned technologies, or other approaches, and the programmer doesn't necessarily need to care one way or another. Knowing the underlying concepts is still useful, however, when creating fast running code which scales well to large data, avoiding (e.g.) traversing the list over and over again, or performing particularly inefficient operations. | ||
− | + | In the title text, a {{w|Linked_list#Singly_linked_list|singly linked list}} contains pointers to traverse the list in only one direction; namely, from the head to the end. By contrast, each element in a {{w|Linked_list#Doubly_linked_list|doubly linked list}} contains pointers to both the "next" and "previous" elements, enabling traversal in either direction. Randall continues the implication that such lists are obsolete by implying that traversing such a list would be akin to time travel to the past. Without the "previous element" pointers, Randall is concerned he would not be able to reverse the time travel, as he could not traverse the list in the reverse direction. | |
− | + | ==Transcript== | |
+ | {{incomplete transcript|Do NOT delete this tag too soon.}} | ||
− | + | [Cueball is seen writing on a whiteboard, Ponytail is standing next to him. Above it, a piece of code is written, which apparently is what Cueball is writing on the whiteboard. The text reads:] | |
− | |||
− | + | define traverseLinkedList(headPointer): | |
− | myId="''<illegible scribbling>''" | + | myId="''<illegible scribbling probably containing a user ID>''" |
− | authToken="''<illegible>''" | + | authToken="''<illegible scribbling containing an auth token>''" |
− | museumAddress="''<illegible>''@''<illegible>''.''<illegible>''" | + | museumAddress="''<illegible address>''@''<illegible domain>''.''<illegible tld>''" |
client=mailRestClient(myID, authToken) | client=mailRestClient(myID, authToken) | ||
client.messages.send(to=museumAddress, | client.messages.send(to=museumAddress, | ||
subj="Item donation?", body="Thought you | subj="Item donation?", body="Thought you | ||
might be interested: "+str(headPointer)) | might be interested: "+str(headPointer)) | ||
− | return | + | return |
− | + | Ponytail: ''Hey.'' | |
− | + | [Caption beneath the panel:] | |
− | + | Coding interview tip: Interviewers get really mad when you try to donate their linked lists to a technology museum. | |
{{comic discussion}} | {{comic discussion}} | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
+ | [[Category:Programming]] | ||
[[Category:Tips]] | [[Category:Tips]] | ||
− | |||
− | |||
− | |||
− |