In both the Android and iOS classes, we created a simple Twitter client using Twitter’s API to authenticate a user to log them in and to fetch tweets from a user’s timeline to display them on the screen.
In the Android app, I also displayed the relative timestamp (e.g. how long ago a tweet was posted) next to each Tweet and implemented pull to refresh. I also tried to be a bit more creative with theming the app:
I also implemented pull to refresh in the iOS version of the Twitter client. In addition, I was able to implement persistent login and the ability to logout:
This week, I worked on improving both the Android and the iOS versions of the Flixter.
In the Android app, I added a RatingBar that converted a movie’s score out of 10 to stars on a view for a particular movie. Using YouTubePlayerView, I also added the ability to play a movie’s trailer video in full screen:
In the iOS app, I added the ability to view a grid layout of movie posters matching a certain genre using a CollectionView and I also added the ability to tap on a TableView cell in order to view a detailed screen about a particular movie.
I’ve resumed teaching high school CS full-time, but I am also now working towards an advanced certificate in web and mobile applications development.
I was perhaps a little overzealous and enrolled in too many interesting classes initially:
Linear Algebra (this wasn’t required for my CS degree, but a lot of grad CS courses require it, if I choose to go on to a Masters/PhD)
Advanced Web Frameworks (part of the web and mobile applications program)
Android Development (a free course through CodePath)
iOS Development (another free course through CodePath)
I have decided to drop the linear algebra course since it is the only one that requires specific meet times, which made things a bit challenging since the course meets right after I finish teaching, when my brain was ready for a nap.
Here’s the first Android assignment I’ve completed, Flixter. It uses NYT’s Movie API to populate a TableView with information fetched from a query.
You can find more details about the app and its source code on Github!
We also did the Flixter assignment in the iOS class using Swift.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. These are the operations you should implement for this data structure.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
get_min() -- Retrieve the minimum element in the stack.
# Design a minstack class with the following functionality:
# push(x) -- pushes element x onto stack
# pop() -- removes the element on top of stack
# top() -- returns the top element
# get_min() -- returns the min element in stack
## Example:
# min_stack = new MinStack()
# min_stack.push(-2)
# min_stack.push(0)
# min_stack.push(-3)
# min_stack.get_min() # Returns -3.
# min_stack.pop()
# min_stack.top() # Returns 0.
# min_stack.get_min() # Returns -2.
2. Match
# Can use a list to implement the stack
# Since we're interested in also returning
# the minimum element, we can sacrifice space
# for time by storing tuples containing a pair:
# the element added to the stack and the current min
3. Plan / Pseudocode
# MinStack objects have a single class variable:
# a list of tuples
# Functions:
## push(x)
# If the list is empty, just append (x, x)
# since x will also be the current minimum
# Otherwise, check if x is less than the current min
# (will be located at [-1,1] or the second value
# in the last tuple in the list)
## pop()
# If the list isn't empty,
# remove the last item in list
## top()
# If the list isn't empty,
# Return element at [-1.0] or the first
# value in the last tuple in the list
## get_min()
# Return the element at [-1,1] or the second
# value in the last tuple in the list
If I had just pushed the elements to the stack instead of a collection of the element and the current min, I would have had to have implemented the get_min function differently.
The get_min function would have had a time complexity of O(N) because I would have had to have traversed the entire list to compute the minimum value. However, by using additional space O(2N), still technically O(N), to store the current minimum every time a new element was pushed to the stack, the time complexity of the get_min function is constant time O(1) since it will always be in the last tuple in the list.
One common pattern when using hash tables requires building a Map whose values are Collection instances. In this challenge, we’ll take the output of the previous challenge and invert it.
Write a program that takes as its input a HashMap<String,Integer> and returns a HashMap<Integer,HashSet<String>> containing the same data as the input map, only inverted, such that the input map’s values are the output map’s keys and the input map’s keys are the output map’s values.
Example:
Consider the example output for Hash Table Word Count. Using that map as the input, the output for this challenge would be:
# Write a function that takes the output from getFreqDict
# (a dictionary with String:Int key:value pairs)
# and returns a dictionary with Int:HashSet<String> key:value
# pairs where the int is the unique counts and the
# Set is the set of unique words that have that count
# For example, for the string input
# "To be or not to be, that is the question."
# The output of this function would be the dictionary:
# 2 → ["to", "be"]
# 1 → ["or", "not", "that", "is", "the", "question"]
2. Match
# This is a HashMap / dictionary problem
# We already created a dictionary of all the unique words
# and their counts. We need to iterate on each of these entries
# to create a new dictionary with unique counts as keys
# and a set of words that have these counts as the value
3. Plan/Pseudocode
# Need a new empty dictionary to store results
# Take the dictionary we get from getFreqDict() as input
# Iterate on each entry and check if the value (count) already
# exists as a key in our new dictionary.
# If it doesn't, add the count as the key in this new dictionary
# and a Set containing the word as the value
# If it does exist, add the newly encountered word to the
# set existing at this key
# return the new dictionary after iteration halts
4. Implement
5. Review
Output for the sentence “To be or not to be, that is the question.”:
Write a program which takes as its input a String of natural language text and outputs a HashMap<String,Integer> whose keys are the unique words in the input and whose values are the number of times those words occur. The algorithm should be case-insensitive (e.g. “Program” and “program” would count as the same word) and ignore punctuation and whitespace.
Example:
Given the input "To be or not to be, that is the question", the outputted HashMap would contain 8 entries, with two words having a count of 2 and six words having a count of 1:
# Write a program that takes a String as input
# And outputs a dictionary with String:Int key:value pairs
# The keys are unique words (case insensitive
# and ignoring whitespace and punctuation)
# Values are frequency counts of that word in the string
## Example input: "To be or not to be, that is the question"
## Should output:
# "to" → 2
# "be" → 2
# "or" → 1
# "not" → 1
# "that" → 1
# "is" → 1
# "the" → 1
# "question" → 1
2. Match
# This is a string processing problem
# Can use Python's split() function to get individual words
# in a list and use .lower() to convert each word to lowercase
# and strip() to strip whitespace and punctuation
3. Plan / Pseudocode
# Start with empty dictionary and input string
# First, convert string to a list with split()
# Second, iterate through each word in the list and:
# * convert to lowercase lower()
# * strip whitespace and punct strip()
# * check if its in the dictionary
# * if it's not, add it with a value of 1
# * if it is, increment the value associated with the key
# return the dictionary
4. Implement
5. Review
6. Evaluate
Currently all non-alphabetical characters are stripped from the string by using regex.
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)
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.
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.
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).
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!