IP#3 : LinkedLists Intro


                         LinkedList Intro

                                                               by Ashur Baroutta



    Following up on our interview prep, while we are still working on numerous array problems, it's time to explore the LinkedList data structure problems and start building a strong foundation for those types of use cases. A LinkedList data structure is a list consisting of nodes where each node contains both a data field and a reference(link) to the next node in the list. 

    In the same spirit of our other submission, we will start with a problem statement that says "Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.". The visual representation of the linkedlist and desired output is as follows. 


        So the logic behind removing the duplicates in a linkedlist is a bit different than with an array. Given each node has a data field and a reference, we need to first initialize another node and set it equal to the ListNode being passed in (head). Then the idea is to keep looping until the next link in the list is null as that signifies the end of the list. So as we keep looping we need to work out way through the list and we want to check for when a given iteration's node value is equal to its reference(link) value. That way we can rearrange the links to remove any duplicate node. 

    After spending a few hours relearning how to make/access nodes, I was able to solve the problem and the code submission is as follows. 


    So as we can see, after we check to see if the data fields for the current node are equal to the next node's data, we set the current node's reference to the next node's reference field. Doing this we delete the middle link/duplicate by removing all of its connections!

While we successfully managed to complete the problem, there are issues with the solution. It has a very fast run time, though it is heavy on memory usage beating out only 37% of submissions in terms of memory utilization while being ranked 99% for speed, given we coded in Java there is a better way to manage memory while also completing our objective. I will continue working on the problem to better optimize memory efficiency.


    


Comments

  1. EricaMarch 12, 2022 at 10:18 AM

    Your persistence will continue to pay off, keep it up!!

    ReplyDelete

Post a Comment

Popular posts from this blog

IP #6 : Reversing an Integer

Image
 Reversing an Integer by Ashur Baroutta     The focus of this submission will be on reversing a given integer passed into our function. Our problem statement is as follows "Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 -1], then return 0." Seems simple, though was actually a little odd. My initial reaction is to convert the integer to a string and then just reverse each character. Though in a way that feels like cheating as I don't think that solution is in the spirit of the assignment,  and it takes more resources to complete.      Pivoting my attention to a mathematical solution made the problem a lot more fun. Say our first example for x is 123. The way we attack it is to setup variables to track the reversed total and to track the remainder of a given iteration, we also create a loop iterating through while x does not equal 0.  The ...
Read more

IP#5 : LinkedList Removing Duplicates II

Image
 Removing Duplicates II by Ashur Baroutta         In our last submissions, we worked on removing duplicates, this week we look at the more complicated problem of the same type. Our problem statement is " Given the  head  of a sorted linked list,  delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return  the linked list  sorted  as well ."      So not only do we have to remove duplicates, but we cannot return values that are not distinct, for example, if our list originally contained three 1's, we need to delete all the 1's in our list as even if we delete all but one of them, the number 1 itself is not a distinct value.      This took me about 3 days to think through and complete, the following is our code submission.  We start by first creating a new ListNode called newlist. We set its .next reference pointing to head (the ListNode passed ini...
Read more