Questions were (won't make sense to ppl who didn't take the test):
2a. Big-O times for add(String element) and getUniqueElements()?add would have been O(n) because it just for-looped through the arraylist, I got that one thankfully >_>
getUniqueElements would have been O(n log n) because it used a merge sort. My smart self said it was O(n) because I thought merge sorts were just O(log n) and not O(n log n) making the method O(n+log n) -> O(n).
2b. Write the FastStringBag class with add(String element) being O(log n) and getUniqueElements() being O(n)This is where it gets sad. For some reason, I forgot that I can FRIGGIN USE METHODS THAT AREN'T LISTED (facepalm) and spent like 30 minutes forgetting how to write a binary search. Of course even though I got the search correct (I think, probably not actually), add still wouldn't have been O(log n) because I used a freaking arraylist as my data structure (which most of the class did as well, haha). The correct code should've used a TreeMap, and should have went something like this (I think -_-;; ):
- Code:
-
public void add(String element)
{
//entries is the TreeMap variable that holds the values you //add
if(entries.keySet().contains(element))
entries.set(element,entries.get(element)+1);
else
entries.put(element,1)
}
and getUniqueElements should've looked simply like
- Code:
-
public String[] getUniqueElements()
{
String[] ans = new String[entries.keySet().size()];
int count = 0;
for(String a: entries.keySet())
ans[count++] = a;
return ans;
}
Question 3 was a GridWorld problem where you had to write a TimidCritter. I didn't really get to this question because, as you know, I spent a majority of the time phailing at CompSci and being unable to write a binary search that STILL would have been the incorrect answer. It still wasn't particularly difficult though. TimidCritter had to store its first 10 moves, then repeat the moves backwards for moves 11-20, then repeat the entire process from there (erasing any rocks or other normally indestructible actors in the spaces in went). That's it.
It was pretty simple, but since I had no time (-_-;; ) I rushed and fudged the move methods and ended basically with a pile of junk and wasted ink. Go me.
//setRantMode(false);
The code above is correct right Michael? I'ma feel pretty damn stupid if even kinda going over the test I still got them wrong -_-;;
Home 
