[Topic:] Introduction to data structures. There are two types of data that are normally found in programming languages, primitives and data structures. Data structures are usually composed of primitives and other data structures. Primitives represent the lowest level of data in a given language. As an example, a number can be a primitive. Let's actually motivate a data structure using primitives. Person might have an age and might also have an indicator for whether they're employed or not. If you wanted to create a more complex person representation in a programming language, we could create a data structure called person that has a primitive property called age which is a number. And another property called is employed, which is a boolean which can be either true or false. As mentioned before, a data structure can be composed of primitives and other data structures. An example of a data structure that composes with other data structures can be a book, where a book might have an author data structure where the author data structure represents the author of the book, and it might contain the first name of the author and the last name of the author. Data structure interview questions generally ask you to select the correct non-primitive data structure to achieve the goal of the requirement. Here's a quick description of data types and their corresponding complexities for the operations performed on them. First, let's take a look at a linked list. To motivated real life example, let's think about contact tracing when you're trying to establish patient zero for a virus. Usually how this works is an investigator will find an infected patient, ask him who they've been in touch with. They will follow up with the people who have been in touch with and the goal is by following person to person to person, they will ultimately end up at patient zero. The similar intuition is applied to a linked list, where a link list is composed of multiple nodes. A node will contain data and will also contain information about where to find the next node in the chain. And so in this way you can build out a chain in a computer's memory to represent a list of items. To motivate a natural example that a computer might use a linked list for, think of a word processor. When you do various operations and keystrokes, and you undo it. If you think about the operations that you're doing, you can actually think of him as a set of chain operations. You type one letter that you type another letter, then you hit the Enter key. If you want to undo, you can simply look at the last element in the chain and get rid of it, and you'll be at the previous state. Let's look at a type of linked list: A singly link list. A singly linked list consists of one or more nodes. The first note is called the head and is the only node the computer directly is aware of. Starting from the head, you can follow the next node that the head node points to -- to get to the next node. And in this way you can follow the chain to go around the entire link list. Lets take some common operations on the linked list. One operation might be to traverse the entire linked list. You could start by printing all of the fruit in the linked list. Since the computer only sees the head, it must follow the next pointer and print that fruit, then it can follow that next pointer, so on and so forth until you get to the end, usually denoted by null. The time complexity of traversing a link list is O(n). If we bring it back to the rationale from before you have to visit every single node in order to print them all out. So by definition, traversing has to be O(n). Searching a link list is another common operation. You might have a list of objects, and you might want to search and see is a certain object part of this list. In this example, again, you might want to know if an apple is part of the link list. Remember that a computer usually only keeps track of the head node, so it has to start at the beginning of the list. If you want to figure out if an apple is there or not, you have to look at the first node and check. Is this an apple? No. Let's go to the second node. Is this an apple? No. Now let's go to the third is an apple? Yes. And that way searching a link list by definition again because you have to go to every single one has to be O(n). As a question, ask yourself, can you implement a efficient binary search using the singly linked list? Inserting a node before the head. Another common operation for a linked list is to insert a node. If you want to insert a node before the head node, which is the beginning of the list, you would create a new node and you would point it to the current head. This is an example of a constant time operation because regardless of how big the rest of the list is, you just need to create a new node, and you need to point it at the head node that's currently there. If you want to insert a node anywhere after the head. Fr example, you want to insert a banana between a pair, an apple. Since the only node computer sees, is the head we have to 1st get to the pair, then splice that where we create a new banana, half the pair point to the banana and then half the banana point to the apple. In order to do this we have to 1st get to the right point. And in order to get to the right point because we have to start from the beginning again, the time complexity is n. Now let's talk about deleting a node. There's two possibilities here. Let's assume you want to delete the cherry node. We have immediate access to it because it's the head, it's the beginning. So what we can do is we can get rid of it and we can make the next node the new head. This would take O(1). However, in the generalized case, if you want to delete any node in that list, we first have to again get to the right one. In order to get to the right one because you have to always start from the beginning, it will take O(n). Next, a common interview question is to actually detect a cycle in a linked list. A cycle is a case where the linked list has a loop. In this particular example, if apple, instead of pointing to null, its next pointed back to cherry, that would be an example of a cycle. To motivate an example like this, imagine you in a friend or actually doing a race. Your friend is very fast and runs roughly twice as fast as you do. Let's say you guys are both starting on a track at the same point. If the track is straight and the friend is running twice as fast as you are, you're never going to catch up to your friend and your friend will never see you again. However, if the track is circular, and your friend is running twice as fast as you are, there will be a point where the friend catches up to you and laps go. We can apply that same intuition or these linked lists. Can start two pointers both at cherry when incrementing one pointer increments to pair the other pointer instead of incrementing by one increments by two at a time. So we both started cherry. The first one goes to pair, the second one goes to pair and then goes to apple next. The first pointer goes from pair to apple. The bottom one goes by two again. So it would go to cherry and then pair. Let's increment again. The first one is now at apple. This one went incremented, would go around the cherry. The second one is at pair when incremented twice would go and come to cherry. Now the second one is lapped the first one and were both at the same node, which means we detected a cycle. Next, let's answer an actual interview question. This was from Microsoft: Design a method that removes every other node from a linked list. Let's think about this. First, draw several linked lists like in our picture here. Consider edge cases such as a linked list with only one, two or three nodes as follows. Second, clarify with interviewer where the deletion operation should start. Does it start from the head and you start deleting every other node starting from head? Or does the algorithm accept a custom node to start from and starts deleting every other from that custom node? It's always good to clarify so that you're implementing exactly what the interviewer wants versus something that you have going on in your own head. Third, explain how you would start from the head with two pointers and carry out deletions until you run into null. Show how this works in all of your diagrams. This has the added benefit of showing to the interviewer that you're thinking through all your edge cases and that you're thorough in your implementation. Special cases: there is another type of linked list called a doubly linked list. In the previous example, every node had a arrow pointing to another node, and in that way they formed a chain. In a doubly linked list, not only does node have an arrow to the next node, every node also has an arrow to the previous node that's referring to it. Now, ask yourself what might be the benefit of having a doubly linked list. One thing I can tell you right off the bat is in a singly linked list you can go one direction. If at any given point in time you want to go the opposite direction, you can't because you don't have a way of going backwards. With a doubly linked list, you can go backwards. Now, doubly linked lists are less commonly tested, but more commonly used. Let's look at two special forms of a list that frequently come up an interview questions. One is a stack. To intuitively think about a stack, think about plates. If you were to stock up a set of plates, the first plate that you put in is not the plate that you would take out when you wanted a plate. It would actually be the last plate on the stack. This is what we call a first in last out or last in first out operation order. A queue is the opposite. Imagine a line of people. The first person to come in is the first person to be served, the last person to come in is the last person to be served. This is what we call first in first out operation order or last in last out. As an exercise, think about how you would implement a queue and stack using the linked list structure that we've just learned about.
