Discussion 14: Misc.onclusion Christine Zhou Agenda Announcements Kahoot Design Q’s! CS Courses Overview Interview Question Tips Announcements Last discussion!! Want to talk about finals or anything else? Send me an email! RRR week announcements on Piazza by the end of this weekend! Project 3 Phase 2 due tonight! Checkoffs start today until Friday Project 3 gold points have been extended to Sunday Announcement to come later today Discussion survey: tinyurl.com/cz-disc14-sp19 Kahooooot https://create.kahoot.it/kahoots/my-kahoots Design! Nice! You got an interview with Oski Muskerjobs, CEO of BearbnBeats, the hot new music streaming startup headquartered in Soda Hall. For each of the following scenarios, determine which data structures (doesn’t have to be strictly Java) would give the best performance and what algorithms would be used. Additionally, give the worst-case runtime for any operations listed. BearbnBeats provides users access to millions of songs. Muskerjobs has a list of N (song, album) pairs. Assuming all album names are unique, find the number of songs in each album. Data Structures: HashMap<String, Integer> Algorithm: Iterate through the list of (song, album) pairs, maintaining a mapping from album name to number of songs, incrementing at each occurrence. Runtime: Θ(N) Muskerjobs has a list of all N song names in BearbnBeats’ database, and wants to query if a given Song is in the database. Optimize for both constructing the solution and matching a query. Data Structures: Set<Song> Algorithm: Iterate through the list of songs, adding each song to the set. Runtime: Θ(N) for construction and Θ(1) for query Muskerjobs wants to start developing auto-complete for search on BearbnBeats’ website. When a user types in the first K characters of a query, we want the website to suggest the number of songs that have the same K character prefix. Assume that no songs have a name longer than M and there are N distinct songs. Optimize for bo