Software Testing

Testing Terminology

• software testing is the activity of evaluating a software item to detect the differences between the item‘s required response and its actual response for a given set of input conditions
• input, software item, response
• scope of a test is the collection of underlying software components that will be tested
• object-oriented software is tested, the scope could be a class, one or more methods in a class, a group of classes, or the entire system
• dynamic testing: executing the software
• static testing: often performed both on software components and certain work products
• Fault-directed tests are designed to try and expose faults in the item under test.
• Conformance-directed tests are designed to demonstrate that the item under test satisfies its requirements.
• A test-case is a specific set of input data, events and interactions, and associated expected results, that is applied to the item under test.
• test set is a collection of one or more test cases applied to the item under test
• Regression testing involves repeating a subset, and sometimes a complete set, of previously-executed tests after a change has been made to the item under test.

Testing Perspectives

• Black box testing is an approach or strategy that focuses on designing test cases based on the requirements for a product.
• There are three key drivers to how effective a black box testing effort will be:
• the test design techniques used
• the quality of the requirements
• the level of subject matter expertise there is on the test design team
• lack of a systematic testing process
• testing too late in life cycle
• poor requirements
• unclear responsibilities
• data first test cases

Testing Principles

• One major misconception is that software testing can prove that a software product is free from defects.
• In order for dynamic testing to prove the correctness of a software product we would have to do exhaustive testing.
• Testing activities should begin as early as the requirements phase
• Test plans should be driven by, and linked to, the product requirements
• States the components of a test case
• Test case should be as repeatable as possible.
• Keep a test repository
• Regression testing
• In practice, more defects are generally found during testing in projects where an independent test team participates.
• Testing effectiveness can be improved by including people with business expertise on the test team.
• Tester should never assume that software is correct.

Testing Activities and Work Products

• In most software project life cycles, there is a phase devoted to testing
• If a waterfall life cycle model is used, defect detection and repair costs can be significant. If an incremental life cycle model is used, defect detection and repair costs are not as extensive provided that the timeline for delivering increments is short.
• incremental delivery is one way to help mitigate these costs.
• life cycle approach to testing
• Some type of testing is performed at each major phase of the software life cycle
• testing activities are performed essentially in parallel to development activities
• There is more frequent error detection and repair activity and some error detection and correction feedback at every major life cycle phase.
• Major testing issues that can be addressed at the requirements phase include requirements completeness, requirements testability, and requirements ambiguity.
• The type of testing that would be used at this point in a project would be static testing...namely conducting requirements walkthroughs or inspections.
• A tester‘s interest in those reviews would be to assure that the three issues are addressed
• During the design phase, the main design issues are typically correctness and completeness.
• Two deliverables that would be produced under the life cycle approach are a test plan and a test description document.
• In terms of timing, a test plan would be scheduled for delivery about half way through the design phase, or at the end of preliminary design if a preliminary design phase is used.
• The test descriptions would be scheduled for delivery ideally by the end of the design phase.
• A similar set of correctness and completeness issues applies during the coding through testing phases.
• Of course, we would be performing dynamic testing during this period, but static testing could also be performed on additional test deliverables, and developers could also perform static testing on the code.
• Traceability might also be applied to trace test cases back to requirements
• Testing tools might also be used during this period to help generate the actual test case data and to verify the extent to which tests actually cover code components.
• Additional testing work products might be test procedures, possibly test reports, and what are typically called problem reports.

Testing Levels and Responsibilities

• Black Box Testing focuses on designing tests based upon the requirements for the item under test.
• The code for the item under test is not needed or used in the design of tests.
• White Box Testing focuses on designing tests based upon examination of the structural logic for the item under test.
• It is also called structural testing, logic-based testing, clear box testing and glass box testing
• Object-oriented designs tend to be driven by class responsibilities and collaborations rather than by functional decomposition.
• Unit testing in object-oriented development projects works a little differently.
• Since the individual methods belong to a class, some or all of the methods are developed and then individual methods of the class are tested one at a time.
• A test driver simply creates a class instance and invokes one or more of its methods.
• If a method calls another method in the same class, either a stub is used or the actual method is used. If a method calls a method in another class, a stub may be used if the other class is not yet developed.
• In object-oriented integration testing, there really isn’t a functional-decomposition hierarchy, so we typically look at class collaborations, dependencies, and architectural layers.
• Object-oriented design architecture is layered, so maybe these four classes constitute the application layer of the architecture.
• We may then use a test driver to simulate the user-interface layer during the integration increments and while the actual GUI components are still under development.
• Depending on the level of test that is being done, the testing strategies will be different.
• At the unit level, both black box and white box tests are used.
• As we go into integration testing, tests generally become mostly black box in nature, and at the system and acceptance levels where the software product is tested in its entirety...the tests should be all black box.
• When it comes to object-oriented testing, the responsibilities are the same, and the objectives at the system and acceptance levels are the same...but there are additional types of testing that need to be done at the lowest levels.
• There are different types of relationships that exist between classes in object-oriented software development, and those relationships require that more types of testing be done.
• Also, object-oriented projects tend to be use case driven, so it is common for the use cases to serve as the basis for system and acceptance testing...at least for a product‘s functional requirements.

Requirements Based Test Design

• The first technique that will help us to design tests is called input space partitioning.
• Input space partitioning is used to partition the input side of a function into a set of equivalence classes that can help us identify test conditions.
• An equivalence class is a subset of the input domain such that any values in that class will result in an equivalent system response.
• Boundary testing focuses on identifying test conditions at the extreme points of the equivalence classes.
• model-driven test design: started with a requirement, modeled its business rules, and then used the model to help generate test cases

Code Based Test Design

• WHITE BOX TESTING focuses on designing tests based upon examination of the structural logic for the item under test.
• It is also called structural testing, logic-based testing, clear box testing and glass box testing.
• When we deal with code-based testing, one of the things we want to include as part of our testing goals is something called a coverage criteria.
• Including a coverage criteria ensures that the code under test is adequately exercised.
• three different levels of coverage criteria: statement coverage, branch coverage, and decision/condition coverage.
• Statement coverage involves writing enough tests so that each programming statement in the component under test is exercised at least once.
• For branch coverage we need to write enough tests so that each true/false branch is exercised at least once.
• The next type of coverage criteria is decision/condition coverage. This requires that we write enough tests so that each true/false decision branch is executed at least once and all combinations that can cause a decision to be true and false be tested.
• Basis Path Testing: Utilizes the flowgraph for a method in conjunction with the cyclomatic complexity metric to generate a set of test paths that yield a very high degree of code coverage.

Assuring Software Quality

Objectives of Software Quality Reviews

• A review is basically some type of meeting.
• Software quality review is a type of review in which we examine a work product that is produced during the course of a project
• work product could be a project plan, a requirements document, a design document, code, a test plan
• The work product is a key component of a software quality review
• only be a few objectives for a software quality review
• identify any defects that exist in the work product, to remove the defect
• shouldn’t be used to share information, to inform stakeholders about what our strategy and direction are, to challenge project scope, to talk about project schedules or project, or anything else
• round-robin review
• work product is circulated around to a team of reviewers
• Each reviewer reviews the work product in isolation and makes comments
• Eventually, the document gets circulated back to the author.
• potential advantages of this review model are that reviewers can fit the review into their own schedule for the most part
• disadvantages of this review model are several: there is often a lack of consistency and rigor
• another potential disadvantage is that if the review team doesn’t provide timely feedback, the project schedule can be delayed
• And finally, in many reviews of this type the work product author is under no obligation to implement the reviewer comments
• informal walkthrough model
• walkthrough model is appropriate for all major project work products
• This review model is synchronous. The review team will meet in-person or virtually over the Internet
• formal inspection model
• more structured, rigorous, and formal than the walkthrough model
• industry best practice

Software Quality Reviews

• Effective use of quality reviews has shortened project schedules by 10 to 30 percent.
• Rework consists of unplanned repeating of tasks that were already performed
• All of those studies have found that the cost of finding and fixing defects increases over time in an exponential-like way.
• Performing software quality reviews can range from 5 percent to 15 percent of total project effort, depending upon the type of review process used and how many reviews need to be performed.
• In fact, unless reviews are effective they will add to the project cost and they will cause schedule increases.

Defect Detection & Repair Costs

• Error amplification is a phenomenon that exists on every single software project.
• Additional drivers are size and complexity.

Informal Walkthrough

• Used as a software quality review, the objectives of a walkthrough are to detect and remove defects in a work product, and to ensure that the work product meets its requirements.
• The review is implemented as a meeting, either in- person or virtual
• The work product author leads the review team through the work product, usually summarizing and paraphrasing chunks of material.
• Reviewers, who ideally have looked through the work product as part of their pre-review meeting preparation, can ask questions, make comments, and raise defect issues.
• The issues should be logged and resolved after the walkthrough meeting.
• In this model, the work product author acts as both a presenter, literally walking the review team through the work product, and also typically serves as the meeting facilitator.
• important guideline
• minimize the objectives to include only those mentioned earlier
• invite only those who can directly contribute to the review’s objectives
• communicate objectives and expectations in advance
• use a checklist to help reviewer focus attention
• limit review meeting time
• produce an issue list
• include a follow-up step
• log issues but limit discussion of solutions

Formal Inspection

• considered to be an industry best practice for finding defects in software work products
• Inspections have the highest defect detection rate of any defect identification technique
• average defect detection rates of 60-90 percent, whereas the more informal walkthrough model averages 30-60 percent
• There are specialized roles that some of the reviewers play
• there are more steps than just the inspection meeting
• there are rules for conducting
• the inspection meeting
• there is mandatory preparation and follow-up.
• Inspections require that some participants play specialized roles
• The moderator is responsible for ensuring that all the steps in the inspection process are followed and that all the inspection process rules are complied with
• The moderator is also responsible for facilitating the inspection meeting
• The author is responsible for answering questions posed by the inspection team, for providing clarifying information, and for resolving any issues for which he or she is the designated owner
• An issues list is a mandatory inspection work product, and the person assigned to play the role of recorder is responsible for logging the issues
• someone other than the author is selected to do walks the review team through the work product, presenter
• Anyone else on the inspection team falls into the category of general inspector.
• inspectors are relevant stakeholders and perhaps subject matter experts who evaluate the work product for defects and ensure the work product meets its requirement
• The steps help to give the inspection process structure and repeatability
• The kick-off step starts the inspection process for a given work product.
• The author and moderator meet to verify that the work product is ready for inspection, the inspection team is selected, and the inspection meeting is scheduled
• The moderator decides whether the overview step is necessary.
• The preparation step is a mandatory step in the inspection process, because advance preparation is essential if the inspection meeting is to be effective.
• Participants are also typically asked to record and report their preparation times.
• During the inspection meeting, the work product is presented, issues are logged, and the inspection outcome is determined.
• outcomes of an inspection meeting are defined in advance
• conditional acceptance, re-inspect, or the inspection is not yet finished and requires another meeting

Software Metrics

• A metric is a measurement of something.
• metrics can provide useful visibility into project status
• provide feedback to management, staff, and stakeholders
• Feedback may also be in the form of quality indicators
• Process metrics measure something associated with a process
• total effort spent on each phase in a project life cycle
• estimate of time remaining for project completion
• Product metrics measure something associated with a product
• Quality metrics measure something that is associated with the quality characteristics of a process or product
• Quality requirement’s visibility

Specifying & Measuring Software Quality

• At the top is the quality requirement that needs to be satisfied, such as testability
• The next level defines product or process attributes that lead to a product having that quality characteristic.
• Then, for each of the defined product and process attributes, one or more metrics is defined.
• Simplicity is a characteristic of a products design and code. Are they implemented in a straightforward manner.
• Self-descriptiveness also applies to the design and code. Are they easy to understand by visual inspection.
• Modular applies to the design and code as well. Is it easy to see which components of the product perform certain functions.
• Traceability has to do with the ease of relating test cases to the requirements that are being tested and to the specific product components that implement those requirements.
• Support has to do with the infrastructure that is in place to support the testing effort.

Sample Software Quality Metrics

• Coupling is a measure of inter-dependence between software components.
• Loose coupling is good. Tight coupling is not good.
• Cohesion is a measure of how single-purposed or well-defined a software component is.
• High cohesion is good. Low cohesion is not good.
• Cyclomatic complexity is a metric that measures how complicated the control flow logic for a software component is.
• Halstead’s Information Volume metric. how much information is contained in a software component based on a count of operators and operands.

Software Quality

Software Quality

• meets requirements
• useful for situations in which the requirements were stated in terms of things that could be measured
• typically be quality inspectors at various points in the assembly line
• requirements are usually written in the form of stories or use cases
• should be traceability between the requirements and the goals of the stakeholder: Vision documents
• Achieving quality: doing things that build a quality product
• Assuring quality: convincing ourselves and others that we are building, or have built a quality product
• Return On Investment

Defects

• Error: A conceptual, syntactic or clerical discrepancy which results in one or more faults in the software
• Fault: A specific manifestation of an error. A discrepancy in the software which can impair its ability to function as intended. An error may be the cause for several faults
• Failure: A software failure occurs when a fault in the computer program is evoked by some input data, resulting in the computer program not correctly computing the required function in an exact manner.
• Defect: Either a fault or discrepancy between code and documentation that results in mischief in the testing, installation, maintenance, or use of software
• errors cause defects, which, in turn, can result in failures
• multiple ways to detect defects
• Reviews are performed by a group of people, including the developer of the code
• An informal review is called a walkthrough.
• A more formal type of review is a formal inspection
• root cause analysis
• Starting with a failure, we ask why did it happen? What was the defect that led to the failure?
• why did the defect occur? What error led to the defect?
• Handling Defects
• Record and categorize the defect
• Identify and record the error
• Look for similar defects and errors
• Categories of Defects
• by nature
• severity
• priority
• Removing Defects
• Change control: When we fix a defect, we are changing the software
• Regression testing: If you make a change to the software, you need to re-run some of the test cases to make sure you haven’t accidentally broken something else.
• Ripple effect: We need to do a careful job of analyzing the changes we make to the software to avoid ripple effects.
• Preventing Defects
• Defect tracking and cataloging
• Continuous Process Improvement

The Quality Triangle

• People, Processes, and Tools
• People
• Software is a labor-intensive operation
• Hire good people.
• Retain good people.
• Train your staff to keep their skills up to date.
• Management:
• Project managers.
• People managers.
• Technical staff:
• Analysts.
• Designers.
• Programmers.
• Quality Assurance Function.
• Testers.
• Configuration Management.
• Software Quality Assurance.
• Processes
• document our processes and standards.
• Based on our own experience
• Based on industry standards
• Maintain
• Train
• Ensure we are following the standards
• This is the role of Software Quality Assurance.
• Tools
• Reduces errors
• Increases productivity and efficiency
• Makes job easier
• Saves money in the long run

Quality Assurance

• People: Quality Organization
• Configuration Management:
• responsible for version control of the artifacts being produced by the developers
• code, of course, but also requirements and design documentation
• Testing
• developers themselves are responsible for unit testing of their own pieces of work
• separate group of people responsible for larger scale testing
• Software Quality Assurance.
• managerially Independent from the developers, as well as configuration management and testing
• ensures that standards are in place and are approved
• ensure that the standards are placed under configuration control
• runs periodic reviews to ensure that the standards are being followed
• assures all stakeholders of the quality of the workmanship of the rest of the team
• Process: Standards
• Standards are embodiments of best practices
• Government standards
• IEEE standards
• ISO standards
• Tools
• Computer-Aided Software Engineering
• Upper CASE tools
• Planning and estimating.
• Project management.
• Requirements analysis.
• Analysis and design.
• Lower CASE tools
• Coding and reuse.
• Analyzing code.
• Testing.
• Configuration management.
• Metrics.
• Documentation.
• Maintenance.

Patterns, Implementation, Maintenance & Reuse

Design Patterns

• Solution to a commonly occurring design problem that can be applied over and over again in many different project context.
• A formal design pattern has a name, a description of the problem it solves, and a solution strategy
• Design patterns also incorporate best practices in their solutions, and result in very flexible, and reusable designs.
• Creational patterns
• address design issues that focus on how to make a system independent of how its objects are created which results in designs very robust in response to changes.
• Structural patterns
• describe ways to design objects that work with each other in very robust ways to realize new functionality
• Behavioral patterns
• deal with how to assign responsibilities to objects and how objects communicate with one another

Sample Design Patterns

• Singleton pattern
• used when we want to ensure that only a single instance from a class is instantiated
• class constructor is not made public.
• static variable “instance”, which in this case is a pointer to a Singleton object
• static method named Instance, that returns a pointer to the unique Singleton object
• Façade pattern
• can be used to provide a unified, more simplified interface that hides any complex relationships that might exist
• Observer pattern
• publish-subscribe pattern
• very useful pattern in situations where an object needs to notify other objects whenever its state changes

Implementation

• component reuse
• framework reuse
• level of reuse
• clear box: we can’t see the code
• translucent box: Not only can we see
• the code, but we can make changes to it
• black box: can see can’t change

Benefit of reuse

• Software reliability, as well as hardware reliability, is measured as “mean time to failure,” or MTTF.
• There are two main reasons why reused software has higher reliability than hand-crafted software.
• if I am building some software that I know will be reused by other people; I will take more care to do a good job.
• software has higher reliability is because of something we will cover in our module on assuring software quality
• less expensive
• capture expert knowledge
• standardization
• less develop time

Impediments to Reuse

• creating components
• paying
• not exact fit
• legal
• trust

Software maintenance

• why we need to do maintenance
• The better products actually received bigger maintenance budgets than the poorer ones
• Corrective maintenance is fixing bugs
• Adaptive maintenance is when we make changes to keep up with new technology such as new hardware or operating systems.
• perfective maintenance
• cost maintenance
• 60% to 80% of the total life cycle cost of software is in maintenance
• Another thing to keep in mind is that we are continually building more software that will need to be maintained.
• The only thing we can do is to reduce the unit cost of maintenance.

Object-Oriented Analysis and Design II

Dynamic Analysis Modeling

• Dynamic modeling means that we model things changing over time
• System operations
• System operations are behaviors that are visible from outside the system
• They describe what the system does as a step in a use case
• A system operation is invoked by an actor during a use case scenario
• A system operation is an elementary unit of functionality that is performed by the system, as seen from the outside.
• It can’t be decomposed any further at the requirements level of abstraction.
• The next level of decomposition requires an understanding of what is inside the system to make it work.
• This is the level of abstraction that we are at during analysis.
• State changes
• System operation typically results in a change in state of the system.
• We will specify a system operation in terms of the state of the system before and after the execution of the system operation.
• These changes can be documented as preconditions and postconditions.
• What we mean by system state is the values of all of the information stored within the system.
• The only way to change the state of the system is to invoke a system operation.
• The invocation of the system operation is called a “trigger.”
• The only kinds of system state changes that can occur are these five.
• Creation of an object instance
• Destruction of an object instance
• Creation of a link connecting two object instances together
• Destruction of a link
• Modification of attribute values within an object instance
• model how the system gets from the before state to the after state

UML Activity Diagrams

• Activity diagrams provide us with a notation for describing the dynamic collaborations of the objects graphically.
• Activity diagrams are good at showing the sequence of actions inside the system when a system operation is being executed.
• The actions in the activity diagram correspond to the execution of operations on individual object instances inside the system.
• What activity diagrams do not show is how the objects communicate.
• There are two particular nodes in an activity diagram. They are the start and end nodes.
• The start is represented as a solid circle with a flow coming out of it.
• The end, or activity final, node is a solid circle with a ring around it, and only one flow coming into it.
• There are decision nodes in activity diagrams.
• A decision node has one incoming flow and multiple outgoing flows.
• Each of the outgoing flows is annotated with a Boolean expression, called a guard.
• Guards are enclosed within square brackets and are placed near the flows emanating from the decision node.
• At the point in the flow when the decision is reached, the guards are evaluated.
• The outgoing flow corresponding to the guard that is true is the path that is taken.
• It is generally, then, a good idea for all of the guards to be disjoint.
• It is also a good idea for there to be no gaps in the set of guards.
• Corresponding to a decision node is a merger node.
• The merge is also a diamond shaped node, also with nothing inside it.
• The purpose of the merge node is to merge all of the paths that were created at the decision node back together into a single flow once again.
• A construct that is structurally quite similar to the decision and merger is the fork and join.
• We use the same icon for both the fork and the join.
• It is a straight bold line. The fork has a single flow coming in, and multiple flows coming out.
• The join has multiple flows coming in, and a single flow coming out.
• Unlike with the decision-merge structure, where only one flow is executed, with the fork and join, all of the flows emanating from the fork are executed.
• They are preformed asynchronously.
• This means that they could be executed at the same time, or they could be executed in any order.
• All of the flows that come out of a fork are joined back together again at the join.
• The behavior of the join is that it won’t resume with the outgoing flow until all of the incoming flows have finished executing and control for each flow has arrived at the join.
• A nice feature of activity diagram modeling is the partition, or sometimes called the “swim lane.”
• While keeping all of the flows intact, it is possible to rearrange the actions so that they are in groups based on who performs them.
• The “who” in this case might be actors, or subsystems, or object instances.
• The partitions are labeled with a name indicating who performs the actions in the partitions.

Introduction to object-oriented design

• In design, our focus changes
• When we were doing analysis, we were trying to get an understanding of what classes needed to be built and how the object instances of those classes interacted to carry out the system operations.
• In design, we are concerned about how those classes should be implemented in code.
• The requirements models specify the system as a black box.
• The analysis models specify the classes within the system as smaller black boxes.
• Design, on the other hand, is an abstraction of the code. It models the implementation at a higher level of abstraction.
• Analysis is a more concrete view of the requirements while design is a more abstract view of the code.
• During analysis we weren’t too concerned with control strategy.
• We were more interested in understanding the behavior of the objects themselves.
• In design, control is a big issue because it affects the code.
• In analysis, we only modeled just the domain, or entity classes.
• In the design, we will see that we will need a lot of what I call “helper” classes.
• One thing that we will have to decide on is the control strategy.
• When one object sends a message to another, it must have a reference or pointer to that object.
• Design is when we begin to be concerned about performance.
• Performance can be used as a driver for making design decisions.
• In design, we need to worry about boundary conditions or software faults.
• We begin to be influenced by the programming language and the operating system at design time.

Static Object Orient Design Modeling using UML Class Diagram Notation

• In fact, many of the decisions that we are forced to make in programming are in fact design decisions. 
• Most of the entity classes in the analysis class diagram will appear in the design class diagram as well.
• However, there may be some good reasons why one or more of the analysis classes is not part of the design.

Implementing association

• In design, ALL information, whether it is attributes or link information, all information is stored as attributes inside objects.
• So, linkage information must be stored as attributes in the design model.
• The linkage information is stored as object references or pointers.
• An object reference is a piece of data. It can be stored in a variable.
• The data type of that variable is the class of the object being referenced
• the data type of the variable can be either the class of the object being references, or any of the ancestor classes up the inheritance hierarchy.
• since an object reference is data, it can be passed around as an argument or return result in the invocation of an operation.

Directionality

• when we make the decision about where the object reference is to be stored, we will represent that information by putting an arrow head on one end of the association line.
• This directed association looks like a pointer from the class where the object reference is stored to the class being referenced.
• If the multiplicity on each end of the association is 1, then storing the link is easy. You just put a referential attribute variable in the referencing class.
• But if the multiplicity is greater than one, an object instance of the one class has to be able to point to many object instances of the second class. This means that the object must store a collection of references. This collection is a set, by default. There is no left to right order of the links.
• If you wanted the links to be ordered in some way, then you would have placed a constraint such as {ordered} or {FIFO} on the association.

Aggregations and compositions

• aggregation is just a special kind of association that has the inherent meaning, “contains” or “part of.
• It has a special symbol, an open diamond on the aggregator end of the association.
• So the way we deal with multiplicity is exactly the same as for regular associations.
• If the multiplicity on the far side of the relationship is greater than one, then you’ll need a collection of object references.
• Once again, by default this collection is an unordered set. If you need order, then you can use an ordered collection, such as a list.

Compositions

• Compositions are much more highly constrained than aggregations.
• The composite fully encapsulates the parts.
• The lifetime of the parts is completely controlled by the composite.
• This also means that the directionality of the composite relationship must always be from the composite to the parts.
• The links are stored in he composite.
• Usually the multiplicity on the part end of the relationship has a multiplicity of greater than one.

Object Lookup

• Each object instance of a particular class will have a unique key value associated with it, and stored as an attribute.
• The object instance can then be located by using that unique key.
• We will need an operation to translate a key value into an object reference.
• In order for other objects in the system to be able to invoke this lookup operation, it needs to be visible to all of them
• The best way to accomplish this is to make the lookup operation globally visible.
• One would be to put the lookup operation in a singleton object.
• The other option, and the one we will choose here, is to add the lookup operation as a static operation to the class of the objects we want to look up.

Generalization-specialization

• This use of aggregation rather than generalization is called the state pattern.
• Sometimes we can introduce inheritance at design time.
• During analysis, we identify classes in the problem domain.
• At design time, consider dividing some of the classes into two parts, a general part and a specific part.
• The general part becomes an abstract superclass.
• The specific part becomes a concrete subclass.
• More subclasses can be easily added later if you discover other specializations.

Dynamic Design

• As far as the dynamics are concerned, we are interested in not only what the operations are, and in what order they are executed, but also how they get executed
• We care about an object having a reference to another object when it needs to send a message to that object.
• So we will need to design the access to the object reference in addition to the use of the reference to send the message.
• We will be using the UML Sequence Diagram notation to design these dynamics.
• For each system operation, we need to identify a controller.
• This controller may be one of the existing entity classes, or it may be a made up class, especially constructed for the purpose of controlling the system operation.
• If we choose an existing entity class, it usually is one with the same name as the actor that initiates the system operation.
• It is important to note that the controller is an operation, not an object or a class.
• Thus, if we choose the option of creating a special controller class, it probably would only have just that one operation, and no attributes.
• It would just be a holder for the controller operation.
• There are two main ways the customer actor can communicate with the system.
• One is for the actor to send the actual customer object instance as a serialized object
• This could be done with some kind of remote procedure call or remote method invocation mechanism
• We would need a boundary class to handle communication to and from the actor.
• The boundary class would reconstitute the customer object and then execute the addItem operation.
• More frequently, the communication between the actor and the boundary object is done via text message.
• Sequence diagrams model the code more closely than activity diagrams do.
• If the reference is stored as a referential attribute in an object, it may be used to send a message.
• Frequently the multiplicity of these referential attributes is greater than one.
• This means that there is a collection of referential attributes.

UML Sequence Diagrams

• Sequence diagrams show the object instances that are involved in the system operation.
• Object instances that exist at the start of the system operation are shown along the top of the diagram.
• To represent an object over time, we extend a dashed line, called a lifeline, below it.
• Time goes down the page.
• A message is represented as a solid line with an arrow head from the lifeline of the sender to the lifeline of the receiver.
• The message is annotated with the name of the operation being invoked in the receiver object.
• Optionally, you can include arguments being passed to the operation.
• Usually we show the operation signature on the line, including the formal parameter names and their types.
• Returned results are indicated by a dashed line with an arrow head.
• We can show the creation of an object instance by drawing the constructor message being sent to the object instance box at the point in the timeline when the object is being created.
• We can show the destruction of an object by terminating its lifeline with a large X.
• We can show a message being sent to a class if we realize that a class is technically an object instance of the meta-class, Class.

Structuring Sequence Diagrams

• A frame is a rectangle containing part (or all) of a sequence diagram.
• It has a pentagon in the upper left corner.
• This pentagon is called the heading. It indicates the purpose of the frame.
• There are many kinds of frames. Some of the more popular types are reference, looping, decision, and parallelism.
• The frame with ref in the pentagon is a reference frame.
• It contains the name of another sequence diagram.
• It serves the same purpose as the rake in our activity diagrams.
• To indicate looping, we use a loop frame.
• The top of the frame contains a predicate in square brackets.
• You can use keywords such as for and while in the predicate.
• Whatever messages are inside the frame are repeated based on the predicate.
• The word in the pentagon is alt, for alternative behaviors.
• There may be any number of parts.
• Each part has a predicate
• You use the keyword else on the last one if you want.
• It is a good idea for all of the predicates to be disjoint and to cover the entire domain
• The keyword here is par, for parallel.
• There are multiple parts.
• Each part is executed in parallel with the others.
• The rules for parallel execution here are similar to those in activity diagrams.
• Each of the parallel regions must wait for all of the others to terminate before the frame terminates.
• Frames may be nested to any depth.
• Frame borders may not cross – that is, a frame must be fully contained within another frame.
• This leads to a nice hierarchical structure in the diagrams.

222. Count Complete Tree Nodes

222. Count Complete Tree Nodes

給定一個完全二叉樹的根節點，返回樹中節點的數量。

根據維基百科，在完全二叉樹中，除了最後一層外，每一層都是完全填滿的，並且在最後一層的所有節點都盡可能地向左排列。它在最後一層 h 可以有介於 1 到 2^h 個節點（包含兩端）。

設計一個算法，其運行時間複雜度小於 O(n)。

範例：

輸入:

root = [1,2,3,4,5,6]

輸出:

6

Python

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def countNodes(self, root: Optional[TreeNode]) -> int:

# Helper function to compute the depth of the tree

def get_depth(node: TreeNode) -> int:

depth = 0

while node:

node = node.left

depth += 1

return depth

if not root:

return 0

left_depth = get_depth(root.left)

right_depth = get_depth(root.right)

if left_depth == right_depth:

# Left subtree is complete

return (1 << left_depth) + self.countNodes(root.right)

else:

# Right subtree is complete

return (1 << right_depth) + self.countNodes(root.left)

21.78MB, 22ms

C++

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int countNodes(TreeNode* root) {

if (!root) {

return 0;

}

int leftDepth = getDepth(root->left);

int rightDepth = getDepth(root->right);

if (leftDepth == rightDepth) {

// Left subtree is complete

return (1 << leftDepth) + countNodes(root->right);

} else {

// Right subtree is complete

return (1 << rightDepth) + countNodes(root->left);

}

}

private:

int getDepth(TreeNode* node) {

int depth = 0;

while (node) {

node = node->left;

depth++;

}

return depth;

}

};

29.33MB, 21ms

Javascript

/**

* Definition for a binary tree node.

* function TreeNode(val, left, right) {

* this.val = (val===undefined ? 0 : val)

* this.left = (left===undefined ? null : left)

* this.right = (right===undefined ? null : right)

* }

*/

/**

* @param {TreeNode} root

* @return {number}

*/

var countNodes = function(root) {

if (!root) {

return 0;

}

const getDepth = (node) => {

let depth = 0;

while (node) {

node = node.left;

depth++;

}

return depth;

};

let leftDepth = getDepth(root.left);

let rightDepth = getDepth(root.right);

if (leftDepth === rightDepth) {

// Left subtree is complete

return (1 << leftDepth) + countNodes(root.right);

} else {

// Right subtree is complete

return (1 << rightDepth) + countNodes(root.left);

}

};

68.76MB, 87ms

221. Maximal Square

221. Maximal Square

給定一個由0和1組成的m x n二進制矩陣，找出只包含1的最大正方形並返回其面積。
範例：

輸入:

matrix = [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]

輸出:

4

Python

from typing import List

class Solution:

def maximalSquare(self, matrix: List[List[str]]) -> int:

if not matrix or not matrix[0]:

return 0

m, n = len(matrix), len(matrix[0])

dp = [[0] * (n + 1) for _ in range(m + 1)]

max_side = 0

for i in range(1, m + 1):

for j in range(1, n + 1):

if matrix[i - 1][j - 1] == '1':

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

max_side = max(max_side, dp[i][j])

return max_side * max_side

19.54MB, 519ms

C++

#include <vector>

#include <algorithm>

using namespace std;

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

if (matrix.empty() || matrix[0].empty()) {

return 0;

}

int m = matrix.size();

int n = matrix[0].size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

int max_side = 0;

for (int i = 1; i <= m; ++i) {

for (int j = 1; j <= n; ++j) {

if (matrix[i - 1][j - 1] == '1') {

dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;

max_side = max(max_side, dp[i][j]);

}

}

}

return max_side * max_side;

}

};

24.88MB, 65ms

Javascript

/**

* @param {character[][]} matrix

* @return {number}

*/

var maximalSquare = function(matrix) {

if (!matrix || matrix.length === 0 || matrix[0].length === 0) {

return 0;

}

let m = matrix.length;

let n = matrix[0].length;

let dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));

let maxSide = 0;

for (let i = 1; i <= m; i++) {

for (let j = 1; j <= n; j++) {

if (matrix[i - 1][j - 1] === '1') {

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;

maxSide = Math.max(maxSide, dp[i][j]);

}

}

}

return maxSide * maxSide;

};

56.02MB, 86ms

220. Contains Duplicate III

220. Contains Duplicate III

給定一個整數數組 nums 和兩個整數 indexDiff 和 valueDiff。

找到一對索引 (i, j) 使得：i != j
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

如果存在這樣的一對索引，返回 true；否則返回 false。

範例：

輸入：nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0 輸出：true 解釋：我們可以選擇 (i, j) = (0, 3)。 我們滿足以下三個條件：i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Python

from sortedcontainers import SortedList

class Solution:

def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:

sorted_list = SortedList()

for i, num in enumerate(nums):

# Check if there's a number in the sorted_list within the range [num - valueDiff, num + valueDiff]

if sorted_list:

pos1 = sorted_list.bisect_left(num - valueDiff)

if pos1 < len(sorted_list) and abs(sorted_list[pos1] - num) <= valueDiff:

return True

# Add current number to the sorted list

sorted_list.add(num)

# Maintain the window of size indexDiff

if i >= indexDiff:

sorted_list.remove(nums[i - indexDiff])

return False

30.86MB, 1132ms

C++

#include <vector>

#include <set>

#include <cmath>

using namespace std;

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {

set<long> sortedSet;

for (int i = 0; i < nums.size(); ++i) {

// Find the position where current num can be inserted

auto pos = sortedSet.lower_bound((long)nums[i] - valueDiff);

// Check if there's a number in the sortedSet within the range [nums[i] - valueDiff, nums[i] + valueDiff]

if (pos != sortedSet.end() && *pos <= (long)nums[i] + valueDiff) {

return true;

}

// Add current number to the sorted set

sortedSet.insert(nums[i]);

// Maintain the window of size indexDiff

if (i >= indexDiff) {

sortedSet.erase((long)nums[i - indexDiff]);

}

}

return false;

}

};

128.6MB, 254ms

Javascipt

/**

* @param {number[]} nums

* @param {number} indexDiff

* @param {number} valueDiff

* @return {boolean}

*/

var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {

const sortedSet = new Set();

for (let i = 0; i < nums.length; i++) {

const num = nums[i];

// Check if there is any number in the sortedSet within the range [num - valueDiff, num + valueDiff]

for (let val of sortedSet) {

if (Math.abs(val - num) <= valueDiff) {

return true;

}

}

// Add current number to the sorted set

sortedSet.add(num);

// Maintain the window of size indexDiff

if (sortedSet.size > indexDiff) {

sortedSet.delete(nums[i - indexDiff]);

}

}

return false;

};

128.6MB, 254ms

219. Contains Duplicate II

219. Contains Duplicate II

給定一個整數數組 nums 和一個整數 k，如果數組中存在兩個不同的索引 i 和 j，使得 nums[i] == nums[j] 且 abs(i - j) <= k，則返回 true。

範例：

輸入：nums = [1, 2, 3, 1], k = 3 輸出：true

Python

class Solution:

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

index_map = {}

for i, num in enumerate(nums):

if num in index_map and i - index_map[num] <= k:

return True

index_map[num] = i

return False

29.97MB, 457ms

C++

#include <vector>

#include <unordered_map>

using namespace std;

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_map<int, int> index_map;

for (int i = 0; i < nums.size(); ++i) {

if (index_map.find(nums[i]) != index_map.end() && i - index_map[nums[i]] <= k) {

return true;

}

index_map[nums[i]] = i;

}

return false;

}

};

81.23MB, 116ms

Javascript

/**

* @param {number[]} nums

* @param {number} k

* @return {boolean}

*/

var containsNearbyDuplicate = function(nums, k) {

const indexMap = new Map();

for (let i = 0; i < nums.length; i++) {

if (indexMap.has(nums[i]) && i - indexMap.get(nums[i]) <= k) {

return true;

}

indexMap.set(nums[i], i);

}

return false;

};

73.49MB, 95ms

218. The Skyline Problem

 218. The Skyline Problem

一個城市的天際線是從遠處觀看時由該城市所有建築物形成的輪廓。給定所有建築物的位置和高度，返回這些建築物共同形成的天際線。

每個建築物的幾何信息在數組 buildings 中給出，其中 buildings[i] = [lefti, righti, heighti]:

• lefti 是第 i 個建築物左邊緣的 x 坐標。
• righti 是第 i 個建築物右邊緣的 x 坐標。
• heighti 是第 i 個建築物的高度。

你可以假設所有的建築物都是完美的矩形，底部在高度 0 的絕對平坦的表面上。

天際線應該表示為按 x 坐標排序的“關鍵點”列表，形式為 [[x1,y1],[x2,y2],...]。每個關鍵點是天際線中某個水平線段的左端點，列表中的最後一個點總是有 y 坐標 0，用於標記天際線在最右邊的建築物結束的地方。在最左邊和最右邊的建築物之間的任何地面應該是天際線輪廓的一部分。

注意：輸出天際線中不能有連續的高度相同的水平線。例如，[..., [2, 3], [4, 5], [7, 5], [11, 5], [12, 7], ...] 是不可接受的；高度為 5 的三條線應合併為一條，最終輸出應為：[..., [2, 3], [4, 5], [12, 7], ...]。

範例：

輸入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] 輸出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] 解釋： 圖 A 顯示了輸入的建築物。 圖 B 顯示了由這些建築物形成的天際線。圖 B 中的紅點表示輸出列表中的關鍵點。

Python

from typing import List

import heapq

class Solution:

def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:

# Step 1: Create an event list

events = []

for left, right, height in buildings:

events.append((left, -height, right))

events.append((right, 0, 0))

# Step 2: Sort events by position x

events.sort()

# Step 3: Use a max heap to keep track of the tallest building at the current position

result = [[0, 0]]

heap = [(0, float('inf'))] # (height, end)

for x, negH, R in events:

while x >= heap[0][1]: # remove the past buildings

heapq.heappop(heap)

if negH != 0:

heapq.heappush(heap, (negH, R))

if result[-1][1] != -heap[0][0]:

result.append([x, -heap[0][0]])

return result[1:]

21.80MB, 100ms

C++

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

class Solution {

public:

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {

vector<pair<int, int>> events;

vector<vector<int>> result;

// Step 1: Create an event list

for (const auto& building : buildings) {

events.emplace_back(building[0], -building[2]); // left edge

events.emplace_back(building[1], building[2]); // right edge

}

// Step 2: Sort events by position x

sort(events.begin(), events.end());

// Step 3: Use a max heap to keep track of the tallest building at the current position

multiset<int> heights = {0}; // initialize with ground level height

int prevMaxHeight = 0;

for (const auto& event : events) {

int x = event.first;

int h = event.second;

if (h < 0) {

// It's a left edge, add the height

heights.insert(-h);

} else {

// It's a right edge, remove the height

heights.erase(heights.find(h));

}

// Get the current maximum height

int currentMaxHeight = *heights.rbegin();

// If the current maximum height has changed, add a new key point to the result

if (currentMaxHeight != prevMaxHeight) {

result.push_back({x, currentMaxHeight});

prevMaxHeight = currentMaxHeight;

}

}

return result;

}

};

18.66MB, 22ms

Javascript

/**

* @param {number[][]} buildings

* @return {number[][]}

*/

var getSkyline = function(buildings) {

// Step 1: Create an event list

const events = [];

for (const [left, right, height] of buildings) {

events.push([left, -height]); // start of the building

events.push([right, height]); // end of the building

}

// Step 2: Sort events by position x. If x is the same, use height.

events.sort((a, b) => {

if (a[0] !== b[0]) {

return a[0] - b[0];

}

return a[1] - b[1];

});

// Step 3: Use a max heap to keep track of the tallest building at the current position

const result = [];

const heights = [0]; // Initialize with ground level height

let prevMaxHeight = 0;

for (const [x, h] of events) {

if (h < 0) {

// It's a left edge, add the height

heights.push(-h);

} else {

// It's a right edge, remove the height

const index = heights.indexOf(h);

if (index > -1) {

heights.splice(index, 1);

}

}

// Get the current maximum height

const currentMaxHeight = Math.max(...heights);

// If the current maximum height has changed, add a new key point to the result

if (currentMaxHeight !== prevMaxHeight) {

result.push([x, currentMaxHeight]);

prevMaxHeight = currentMaxHeight;

}

}

return result;

};

62.78MB, 388ms