https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview
Here's my thought process on the link list questions:
Question 1: Find duplicates. One thing I've learned from the array and strings chapter is that manipulation of the original structure is always better than copying the data from one structure to another.
So there are two parts to this. But reading the slow/fast runner concept racked my brain and I got the follow up solution before the original question.
It's sort of like 2 for loops used when searching for duplicates in an array, but instead here you'll have to use 2 pointers. The slowpointer used for indexing the element to be compared with and the fast pointer to iterate through the list.
Moral: Always manipulate linklist questions with 2 pointers and at various speeds to see what kind of algorithm you can come up with to implement the question.
Here's where the concept of next->next came into my mind.
If you want to delete the node, you'll have to check the data of the next node the fastrunner is on.
If its a match, then it's that node you'll want to delete by setting fastrunner->next=fastrunner->next->next.
Moral: Always think of ways to use next->next instead of implementing more pointers than necessary.
This makes it so much easier than using more pointers than actually necessary.
Question 2: Find kth to last element. I thought of also solving this with the fast and slowrunner concept. One pointer reaches the end and returns a count value of the number of hops.
Start another pointer at the head of the list and traverse for (count-kth element) steps. Your pointer will then reach the kth from end element.
Then I read up on the recursive solution. I liked that much more than what I did. So its basically calling the function over and over. When you reach the end of the list, you'll return a 0. From there, each return value will be incremented by 1. So once the return value reached the kth value, you can print out the data value pointed by the pointer.
Moral: Recursive solutions are less optimal but much more cleaner.
Question 3: Delete the middle of the node given only access to that node. This is just a question to rack your brains. Just copy the next node data into the current node and delete the next node. Easy.
Moral: Copying data can be useful when you've got restrictions in access.
Question 4: Partitioning. I thought of implementing with 4 pointers and keeping 2 lists just like the solution said to do. But it didn't occur to me that if I attached the new nodes to the beginning of the lists rather than the end, I could implement this question with 2 pointers instead of 4.
Moral : Attach your nodes to the beginning of the lists if you want to merge them at the end.
Question 5: Addition. I thought this question was kinda standard-ish. But nothing too complex. The follow up solution was pretty tricky, but I didn't really feel like reading the solution provided. I thought it'd be much easier just to reverse the link list and implement the same way as the original question.
This question may take a bit more time than the others, since you'll have to check for cases if one number is shorter for the other.
Oooo! And don't forget about the zero padding in the follow up!
Question 6: I ABSOLUTELY LOVED THIS QUESTION. It was totally new for me and if you don't want to do these questions I strongly recommend to at least do this one.
I had no clue how to do this.
But they explain the algorithm so well in the book, so I recommend you to read up on it.
Once you get the algorithm, its very easy to implement in code.
Moral: Awesome algorithm here.
If you want to see my explanation of it, you can check my post here : http://cselabintro.blogspot.in/
I made it for those, who are too lazy to read the whole algorithm in the book. My post describes it in 4 steps.
Question 7: Palindrome. I thought maybe copying everything down would be easy. But then I thought to use the runner concept. It became much easier and again nothing complex.
There was a recursive solution, but at the end the author states that "it's ugly". Yeesh. No thanks.
Moral:Same as question 1
Here's my thought process on the link list questions:
Question 1: Find duplicates. One thing I've learned from the array and strings chapter is that manipulation of the original structure is always better than copying the data from one structure to another.
So there are two parts to this. But reading the slow/fast runner concept racked my brain and I got the follow up solution before the original question.
It's sort of like 2 for loops used when searching for duplicates in an array, but instead here you'll have to use 2 pointers. The slowpointer used for indexing the element to be compared with and the fast pointer to iterate through the list.
Moral: Always manipulate linklist questions with 2 pointers and at various speeds to see what kind of algorithm you can come up with to implement the question.
Here's where the concept of next->next came into my mind.
If you want to delete the node, you'll have to check the data of the next node the fastrunner is on.
If its a match, then it's that node you'll want to delete by setting fastrunner->next=fastrunner->next->next.
Moral: Always think of ways to use next->next instead of implementing more pointers than necessary.
This makes it so much easier than using more pointers than actually necessary.
Question 2: Find kth to last element. I thought of also solving this with the fast and slowrunner concept. One pointer reaches the end and returns a count value of the number of hops.
Start another pointer at the head of the list and traverse for (count-kth element) steps. Your pointer will then reach the kth from end element.
Then I read up on the recursive solution. I liked that much more than what I did. So its basically calling the function over and over. When you reach the end of the list, you'll return a 0. From there, each return value will be incremented by 1. So once the return value reached the kth value, you can print out the data value pointed by the pointer.
Moral: Recursive solutions are less optimal but much more cleaner.
Question 3: Delete the middle of the node given only access to that node. This is just a question to rack your brains. Just copy the next node data into the current node and delete the next node. Easy.
Moral: Copying data can be useful when you've got restrictions in access.
Question 4: Partitioning. I thought of implementing with 4 pointers and keeping 2 lists just like the solution said to do. But it didn't occur to me that if I attached the new nodes to the beginning of the lists rather than the end, I could implement this question with 2 pointers instead of 4.
Moral : Attach your nodes to the beginning of the lists if you want to merge them at the end.
Question 5: Addition. I thought this question was kinda standard-ish. But nothing too complex. The follow up solution was pretty tricky, but I didn't really feel like reading the solution provided. I thought it'd be much easier just to reverse the link list and implement the same way as the original question.
This question may take a bit more time than the others, since you'll have to check for cases if one number is shorter for the other.
Oooo! And don't forget about the zero padding in the follow up!
Question 6: I ABSOLUTELY LOVED THIS QUESTION. It was totally new for me and if you don't want to do these questions I strongly recommend to at least do this one.
I had no clue how to do this.
But they explain the algorithm so well in the book, so I recommend you to read up on it.
Once you get the algorithm, its very easy to implement in code.
Moral: Awesome algorithm here.
If you want to see my explanation of it, you can check my post here : http://cselabintro.blogspot.in/
I made it for those, who are too lazy to read the whole algorithm in the book. My post describes it in 4 steps.
Question 7: Palindrome. I thought maybe copying everything down would be easy. But then I thought to use the runner concept. It became much easier and again nothing complex.
There was a recursive solution, but at the end the author states that "it's ugly". Yeesh. No thanks.
Moral:Same as question 1
No comments:
Post a Comment