Implement a MinHeap class using a list

Problem: Write a heap class that represents a minimum heap using an array. Implement the insert method for this min heap class.

Example:

min_heap = MinHeap()
min_heap.insert(2)
min_heap.insert(4)
min_heap.insert(1)
# Underlying array should look like: [1, 4, 2]

1. Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

I need to a list to represent a min heap. The insert function should take an integer argument and that should be appended to list. Then this newly appended integer should be “bubbled up” if necessary in order to maintain he properties of a minheap.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a list problem. I can use the existing append function in Python to append the new element to the end of the list. I can use the fact that a node’s parent index = (current index -1) //2 to check if the parent is less than the current node.

3. Plan/Pseudo

# heap_list = [] (list)
# getParent(index) returns parent index (int)
# getLeft(index) returns left child index (int)
# getRight(index) returns right child index (int)
# insert(int) appends int to minheap list then calls checks
# if min heap constraints still hold:
# Root node must be smallest element,
# All parent nodes are less than or equal
# to their children (do this bottom up)

4. Implement

5. Review

min_heap = MinHeap()
min_heap.insert(2)
print(min_heap)
min_heap.insert(4)
print(min_heap)
min_heap.insert(1)
print(min_heap)

6. Evaluate

Space: O(N)

Time: Worst: O(N), Best O(1)

leetcode #61 Rotate List

Problem:

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

1.  Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

The solution will take two inputs: a linked list and a non-negative integer, k. The output will be the linked list rotated to the right k places.

It could be possible that k = 0, in which case we could just return the linked list.

What if k is greater than the length of the linked list? We can rotate by k % length of the list.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a linked list problem. Since we are manipulating the nodes in the linked list, it would be beneficial to have a dummy head to maintain a pointer to the head as the node it references changes.

Since we are rotating the list by k places, we can use two pointers–one to point to the end of the list, and another to point to k % the length of the list away from the end pointer. That way we can make the node of this second pointer the new head and the end can point to the old head.

3. Plan

if head is null or head.next is null, return head
if k is 0, return head

# in case k is larger than the length
# need helper function for length
k <- k % length of linked list 

# check again if k is 0 (if len and k are same)
if k == 0, return head

# dummy head
dummy <- ListNode(0, head)
end <- head
ptr <- head

# move end k spaces away from ptr
for i in range k
  end <- end.next

# move both pointers until the end is reached
while end.next isn't null
  end <- end.next
  ptr <- ptr.next


dummy.next <- ptr.next  # new head
ptr.next <- end.next    # new tail
end.next <- head        # append rest of list

return dummy.next

4. Implement

Use your pseudocode to implement the idea in your chosen programming language

5. Review

Test your code with various input to ensure you get the intended output

I actually did this in combination with the planning phase to ensure my plan was on the right track. However, after implementing, I did notice I needed to check if k == 0 again once I changed it to k % length of the list. In this case, I had to return the head. Otherwise, I’d get the incorrect output (empty list).

6. Evaluate

What is the time/space complexity of your solution? Discuss how it could be improved if possible and if time permits.

Space Complexity: O(n)

Time Complexity: O(n)

leetcode #24 Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

When you begin this problem you are given the following starter code (Java):

The block comment details the ListNode class made available to you for the solution.

Using the UMPIRE method to break the problem down:

1.  Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

As part of understanding the problem, I restated the problem in terms of its input, output, and the desired effect. I asked questions about what would happen when we encounter an odd-length Linked List (no swap will occur). Another consideration is if the Linked List is null or if it has a length of one. In this case, the original LinkedList should be returned.

In addition, we have the constraint that we are not allowed to modify the ListNode value variables directly, only the nodes themselves may be changed. This means we can only change what a node points to via its next variable.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a Linked List problem that can be solved by using multiple pointers and a dummy head:

  • The dummy head can maintain a consistent pointer to the head node even when the node the head refers to changes
  • Multiple pointers can be used to point to key nodes in the linked list for swaps to occur:
    • before: the node before the pair to be swapped
    • node1: first node in the pair to swap
    • node2: second node in the pair to swap
    • after: the node after the pair to be swapped

3. Plan

Start writing pseudocode for your idea

4. Implement

Use your pseudocode to implement the idea in your chosen programming language

Python3 implementation:

5. Review

Test your code with various input to ensure you get the intended output

Here’s an example traced on a whiteboard for the input linked list:
1->2->3->4

6. Evaluate

What is the time/space complexity of your solution? Discuss how it could be improved if possible and if time permits.

Space Complexity: O(n)

Time Complexity: O(n)

Reinventor Nomination

I was nominated for an award for my work with Reinvented Magazine as a volunteer writer last year! If you want to support my nomination, you can fill out this form (you’ll need my email– sara@kazemicode.org).

I was one of the first staff writers at Reinvented, and I wrote a Beginner’s Guide to Hackathons for Issue 1.

Unfortunately, I had to quit writing for Reinvented while writing the feature article on the amazing Limor “ladyada” Fried (Adafruit Industries) for Issue 2, but the reworked article turned out amazing.

I needed to focus on my mental health on top of work/school.

I’m so thrilled that someone was impacted enough by the work I did almost one year ago in order to nominate me!

CST 499 – Week 8

Saturday, June 13th was the Capstone Festival!

The Capstone Festival gave my peers and I an opportunity to showcase the what we have learned throughout the program, and there were so many amazing projects! This is why I am beyond honored that my project was one of two selected as Project of the Year! My spouse and I celebrated with sushi and boba.

I am so excited that I could conclude my CS degree program with a project that promotes social good AND receive recognition for it from the professors and my peers.

CST 499 – Week 7

With my capstone video and final report completed, there is not much to report this week. I am looking forward to presenting at our Capstone Festival on Saturday, June 13th!

I will report back about how the Capstone Festival went in my final Week 8 post.

CST 499 – Week 6

This week I created a video demo of my capstone project. I think I covered all of my bases and that I won’t have to revise anything before the capstone festival.

I’ve also started working on the third and final part of the project report, which seems to be the most lengthy part, so I am glad we have two weeks allocated to that.

This Saturday, I will be taking the ETS Major Field test. I’m not a big fan of standardized tests, nor am I a fan of the spyware I have to install so that someone can virtually proctor the test.

Other than that, the Capstone Festival is coming up in 10 days and we will be finally finished!

CST 499 – Week 5

This week is focused on wrapping up the project and getting usability testing finished. I was able to complete the course scheduling wizard and counselor portal for looking up student wishlists. I’ve deployed the demo site here: http://kazemicode.org/suhi/

While I am still waiting on some more feedback from Counselor users, I got a lot of valuable feedback from Student users:

  • On mobile devices, the collapsible nav bar was not displaying an icon to expand the menu (Fixed)
Mobile view, with fixed “hamburger” icon for collapsible nav bar.
  • When I deployed to a remote server, links on the Graduation Requirements were broken (Fixed)
  • For anonymous users, private temporary storage for the session doesn’t behave as expected (For now, student testers will log in to an authenticated tester account until I can get this sorted)
  • Students would like the ability to add more than one core subject class (e.g. two science classes), so I am currently exploring different solutions for this — likely to be added after the capstone class.

All in all, I’m proud of what I’ve accomplished as Drupal and PHP are both new to me.

Counselor portal with exposed wishlist search form

CST 499 – Week 4

This week I had planned on finishing the scheduling wizard, but I noticed the catalog search feature was not returning all the intended results. After looking into this issue, I determined that the search was only utilizing the course title to fetch results and not utilizing the index I created using “graduation requirements” taxonomy (e.g., mathematics, science, etc). So, for example, when the user searched for “math”, it would not return math classes like “AP Calculus” because “math” is not part of the title. After exploring Drupal’s Search API documentation, I was able to remedy this issue by explicitly mapping an index to the taxonomy’s description rather than the taxonomy object itself.

I also spent a bit of time diving deeper into theming in Drupal, which is a bit less straight forward than writing CSS. In Drupal, you can use Twig files–template files that have an inheritance hierarchy. I was able to refine the appearance of my main web application with a mixture of custom Twig files and CSS.

I also created custom Twig files and CSS for the custom module that drives the Scheduling Wizard.

I have also resumed work n the logic of the Scheduling Wizard, which I hope to be finished with before the end of the working week so I can begin usability testing this weekend. What has slowed me down in this aspect is that there seem to be so many ways of doing one thing in Drupal and it can be challenging to find well-documented examples (and weeding through ones that may be deprecated).

CST 499 – Week 3

This week I focused on learning more about creating custom modules in Drupal 8 that utilizes imported JavaScript libraries. I will need this to polish off my course scheduling wizard. I also touched base with my client to confirm scheduling for usability testing as well as what to expect in terms of procedure. I’ve given myself an extra week of wiggle room to fine-tune anything before usability testing in late May.