IP#4 : LinkedList improvement

 LinkedList improvement
Ashur Baroutta

    In the previous submission, we worked on a LinkedList problem and got our solution to a point where the run time was very fast, though our memory management was ranked quite low in comparison. That didn't sit well, so today we try to tackle optimizing it in terms of memory efficiency. Our original solution for the problem, deleting duplicates, is as follows.


So while the solution is acceptable, it exposed a weakness in my line of thinking. Fewer lines of code, or fewer words, does not inherently mean fewer resources utilized while code is compiled and executed. It seemed natural to think but I need to break this idea. 

After working through different types of solutions and researching a better way to solve the problem in terms of speed and memory usage. I was able to manage the following. 


Originally, I just started with one node and iterated through the list with a basic while loop. This time, what I did is had a node pointing to head (head is the first node in a list) and a second node pointing to heads.next reference (in other words the node after head). 

The logic itself is very similar though reading it you can see it digests a bit different. So with this solution we move the links of both nodes linearly through the list. However, once the value fields in both nodes are equal(b.val -- a.val), what we do is change the links for both nodes by first setting the b node to its next reference and only then setting a's next reference to the b node. Since we set be prior to resetting a's reference, when we reestablish the link between nodes, we've jumped over the node needing to be deleted thus removing it. 

While not drastically different, our speed and memory was able to make a giant leap in terms of ranking. Our stats for this submissions rankings are as follows. I am very pleased with the improvement, and look forward to working more with this data structure as i continue my prep.


Comments

  1. EricaMarch 30, 2022 at 5:08 PM

    Great job with the pivot! Always such a rewarding feeling. Enjoy!

    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