Your rich and eccentric uncle has left you alone in his mansion for the evening. He has told you that you have free-reign of the house, with the exception of the library. As your uncle explains, the library is unlike other libraries in that books are not kept on shelves. Instead, they are kept in stacks on the floor. The books have been stacked in a very particular order, and your uncle will easily be able to tell whether or not any books are out of place.
Since you love books and you've never been one to follow rules, you head to the library as soon as your uncle leaves. Despite the fact that you aren't following the rules, you want to be safe and make sure that in case you have an accident that you can put the books into their original order. So before perusing through the books in any of the stacks, you take note of the exact order that the books are in and record this information using a portable computer that you've brought. Unfortunately, after recording the order of the books in one of the stacks, you have an accident, causing the books to become strewn over the floor. Luckily some of the books have stayed "piled together". This means that recreating the original stack of books will be somewhat easier than having to go through each book one at a time. For the books that have stayed piled together, you can pick up the whole "mini-pile" and place it back on the original stack in the appropriate place.
For example, if the stack of books was originally <a,b,c,d,e,f>, where the right end represents the top of the stack, then the mini-piles after knocking the stack over may be <a,b,c>, <d>, <e,f>. To reconstruct the original stack, you start by pushing the mini-pile <a,b,c>, followed by <d>, followed by the mini-pile <e,f>.Your goal is to write a computer program to help you recreate the original stack of books.
Implement a function reconstruct_stack that takes two arguments: original and minipiles. The original argument represents the original stack of books before
you knocked them over and is an instance of class Stack, and minipiles is a list of the mini-piles that exist after the original stack is knocked over. Each element of the list minipiles is a Stack instance representing a fragment of the original stack. The return value is a list representing the order in which the minipiles need to be pushed onto an empty stack in order to recreate the original stack. Each element of the returned list should simply be the top element of the corresponding minipile.
For example, suppose the original stack and the minipiles are constructed as follows:
# the original stack
original = Stack()
original.push('a')
original.push('b')
original.push('c')
original.push('d')
original.push('e')
original.push('f')
# the mini-piles after the stack is toppled
m1 = Stack()
m1.push('a')
m1.push('b')
m1.push('c')
m2 = Stack()
m2.push('d')
m3 = Stack()
m3.push('e')
m3.push('f')
A call to reconstruct_stack(original,[m1,m2,m3]) should return ['c','d','f']. The returned list indicates that the mini-pile with c at the top should be pushed first, followed by d, followed by the mini-pile with f at the top. Note that in this example the order of mini-piles in the second argument matches the order in which they should be pushed onto the stack. Your function should behave correctly even if this isn't the case. For example, reconstruct_stack(original,[m2,m1,m3]) and reconstruct_stack(original,[m3,m2,m1]) should also return ['c','d','f'].
reconstruct_stack function, you must write some unit tests to convince yourself (and us) that your implementation is correct. To get you started with your unit testing, we're providing you with testbooks.py, which contains one test.
reconstruct_stack(original, minipiles) you have to pop elements
from the original stack. (If you're not doing this, then chances are you're doing something wrong.) Explain in detail two different things you can do to avoid having to do this.
reconstruct_stackYou've been tasked with designing a new social networking website. Below is a description of what features are required. You are to perform an object oriented analysis and create a set of candidate classes. Within each class you should describe appropriate attributes, and also define empty methods as necessary. You do not have to implement any of the methods or create any tests.
When a vistor initially arrives at the website, he can either login or register for a user account. A visitor that has a user account can login by supplying a username and password, but otherwise must first register for an account.
When a visitor registers for an account, he must supply a username, password, and email address. After registering, a user account does not become active until after the user has verified his email address (for example, by clicking on a link that is sent to the email address he supplied during registration).
Each user has a list of friends, which is made up of other registered users. When a user is logged in, he can view his list of friends, add a new friend to the list by name, or delete a friend from the list by name.
Each user also has a calendar associated with his account. When a user is logged in, he can add an event to his calendar, look at his calendar, or look at the calendar of any of his friends. Events are either personal events or group events. Personal events have a title, date and time, and duration (in hours). Group events additionally have a list of invitees, which consist of other registered users. When a user enters a group event, it is added to each invitee's calendar. By default, all events in a user's calendar are private, which prevents anyone but the user from seeing the entry. However, a user can make the event public if he chooses.
The website has a messaging system that allows users to send private messages to one another. Each user has an inbox to store messages sent to him, and an outbox to store messages that he has sent to others. A message consists of a message id, a date when the message was sent, a subject, the sender name, a recipient name, and the body of the message. Users can read and delete messages from either their inbox or outbox by message id.
The example that we gave in class was fairly straightforward. The object oriented analysis that you are asked to do here is somewhat more complex since you have to filter out irrelevant information and make some judgement calls when the provided information is ambiguous. If you are completely unsure about some part of the description, you can always ask for clarification.
One thing you should not do is make your design more complicated than necessary. If you're familiar with how websites work in the real world, you may be tempted to make your design more "real" by including extra details. DON'T! For example, when you log into a real website like Facebook, Facebook sends a "cookie" back to your browser that contains a "session id" for tracking your login across multiple requests. We don't want you to try incorporating cookies or session ids into your design! Only focus on the details provided in the above description.