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
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 both constructing the solution and matching a query.
Data Structures: Trie Algorithm: Construct a trie on the song names using character at each node. Conveniently store how many words use a prefix represented by a value at that node. Runtime: Θ(NM) for construction and Θ(K) for query
BearbnBeats runs a subsidiary company, BearBnb, an online marketplace for housing rentals. Bearbnb has a database of N Trips. Each Trip represents a room reservation and has the following attributes: Integer customerId, Double reservationCost, and Date reservationDate. Muskerjobs, a champion for Big Data, wants to run analytics on Bearbnb’s database and query for all Trips requested within a range of dates for a given customer. Optimize for both constructing the solution and matching a query.
Data Structures: HashMap<Integer, ArrayList<Trip>> Algorithm: For each customer, make a mapping from its customerId to an ArrayList<Trip> sorted by reservation date for that product. At query time, look up the appropriate list and do a binary search for the indices corresponding to the endpoints. Return a view of that range. Runtime: Θ(N logN) for construction and Θ(logN) for query. (The worst case is all reservations are for the same customer)
Design a DataType that can add items and return all added items in sorted order. DataType dt = new DataType(); dt.add(10); dt.add(4); dt.add(3); dt.add(8); dt.sorted(); // 3 4 8 10 dt.add(5); dt.add(7); dt.sorted(); // 3 4 5 7 8 10 Assume the DataType already contains N items Choose from Linked List, Fixed-size array, Red-black tree, Binary heap, Hash table and report worst case runtimes for add and sorted.
Red-black tree. If there are N items in DataType, then the height of the tree will be logN. Adding an item into the tree will take logN time Sorted order of all the items will be an inorder traversal of the red-black tree, which will take N time.
Course Overview (Personal experiences) - [Su16] CS 70: Discrete Math & - [Sp17] CS 61C: Machine Structures Probability - C, assembly language - Learn about how computers work! - Proofs for things we’ve seen so far - Caching, MapReduce, parallelism - Problem set every week - Stable marriage, modular arithmetic, - [Sp17] CS 186: Databases graph theory, etc. - Learn SQL and how databases keep - [Fa16] CS 170: Algorithms track of all your data, Java - “Chill”, though exam was tough this time - Learn to analyze runtimes, write around…, some projects algorithms - Guest speakers from the industry - Problem set every week, end of semester project; generally seen as “must take” - DP, LP, graphs, etc. - [Fa16] CS 188: Artificial Intelligence - Learn AI alg and apply to Pacman projects - One of easier upper divs, though exams can be tough
Course Overview (Personal experiences) - [Fa17] MATH 110: Linear Algebra - [Sp18] CS 162: Operating Systems - Early morning class - Learn about processes, threads, - Average workload (no homework!) concurrency, file systems, distributed - [Fa17] CS 168: Networking systems - Learn about the Internet and design - Project based with the same group of 4 - Offered in the Fall, Scott Shenker - Essential to understand your computer teaches and helped design Internet and how to code efficiently - Low workload - High workload - [Sp18] EECS 126: Probability and Random Processes - Learn more about probability - Very high workload, but one of the coolest classes I’ve taken!
Course Overview (Personal experiences) - [Fa18] EE 16A - Average to high workload - Linear algebra, circuits - [Fa18] CS 161: Security - Average to high workload - Learn about hacking and computer security with applicable projects - [Fa18] CS 194-26: Computational Photography - https://inst.eecs.berkeley.edu/~cs194-26/fa18/upload/files/proj3/cs194-26-act/ - https://inst.eecs.berkeley.edu/~cs194-26/fa18/upload/files/proj4/cs194-26-act/ - https://inst.eecs.berkeley.edu/~cs194-26/fa18/upload/files/proj6B/cs194-26-act/ - [Sp19] CS 189: Machine Learning - Very cool topic, long problem sets (start early!!), do some real world stuff - Tip: Join EECS 101 Piazza! - Course recommendations, student experiences, instructor input, etc. - https://piazza.com/class/hyq0br1u3kx7dg
Course Overviews (16x) - CS 160: UI/UX - Good for learning basics of UI design and conducting user studies - Usually taught in Android and project heavy - CS 161: Security - Practical programming course; learn how to keep your computer secure - CS 164: Compilers - Learn about programming languages and how they’re compiled - Good if you thought the Scheme project was interesting - Project heavy, taking with Hilfinger is a rite of passage - CS169: Software Engineering - Learn Ruby on Rails to build app - Good for if you want experience to help get an internship Credit to Michelle Tian
Course Overview (17x) - CS172: Computability and Complexity - CS174: Combinatorics and Discrete Probability - CS176: Algorithms in Computational Biology Credit to Michelle Tian
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!