Problem

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

```          1
/ \
2   3
/ \
4   5
```

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

The length of the diamer of the binary tree can pass through the root of the binary tree or not.
In case that it passes.
The diameter is the height of the left subtree + the height of right subtree + 1 that is the root.
height of the left subtree + the height of right subtree + 1
is it not necesary that the path of the diameter passes throught the root.
In case that it dosn’t passes.
You need to calculate the diameter of the left and right subtree and the right subtree.
Now lets consider the new tree, for the new tree ldiameter will be the height of the left subtree. and repeat for rdiameter.
if it does not pass throught root we need to pass the left subtree and right subtree through the recursive function. and out of that leftsubtree and right rubstring reconsider the greater and pick that one.
height of the left subtree + the height of right subtree + 1,
max (ldiameter, rdiameter) )
you have to calculate both of this scenarios because we are not sure wheter or not we pass throught the root.
max(height of the left subtree + the height of right subtree + 1,
max (ldiameter, rdiameter) ))

solution

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.left = nil
*         self.right = nil
*     }
* }
*/
class Solution {
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
guard root != nil else{return 0}
return diameter(root: root)
}
func diameter(root: TreeNode?) -> Int {
guard root != nil else{return 0}
var rootDiameter:Int = heightOfBinaryTree(root: root?.left) + heightOfBinaryTree(root: root?.right) + 1
print("\(rootDiameter)")
var leftDiameter:Int = diameter(root: root?.left)
var rightDiameter:Int = diameter(root: root?.right)

return max(rootDiameter, max(leftDiameter, rightDiameter))
}

func heightOfBinaryTree(root: TreeNode?) ->Int {
if(root == nil){
return 0
}else{
return max(heightOfBinaryTree(root: root?.left), heightOfBinaryTree(root: root?.left)) + 1
}
}

}
```

reference

https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/529/week-2/3293/

Best Time to Buy and Sell Stock II

I joined leet code 30 days of code challenge and this is the 5th challenge. I would like to give some of the insight I found while solving this problem with swift. The problem as follows.

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

```Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
```

Example 2:

```Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
```

Example 3:

```Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.```

The first approach consist in taking advantage of the moment we find a valley and immediately after take into account its adjacent peak. now we add the difference.

```class Solution {
func maxProfit(_ prices: [Int]) -> Int {
if prices.count == 0 {return 0}
var maxProfit: Int = 0
var valley: Int = prices[0]
var peak: Int = prices[0]
var i: Int = 0
print(prices.count)
while i < prices.count - 1{
while i < prices.count - 1  && prices[i] >= prices[i+1]{
i += 1
}
print("this is  a valley \(prices[i]) ")
valley = prices[i]

while i < prices.count - 1 && prices[i] < prices[i+1]{
i += 1
}
print("this is a peak \(prices[i])")
peak = prices[i]

maxProfit += peak - valley
}
}
```

The second solution takes advantage of the fact that the sum of every incremental value can be uses to simulated the highest peak. So the sum of small increment A, B and C are equals to the largest increment to the peak.

```class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var diff: Int = 0
if prices.count == 0 || prices.count == 1 {return 0}
for i in 1...prices.count-1{
print(i)
if prices[i] > prices[i-1]{
diff += prices[i] - prices[i-1]
}
}

return diff
}
}
```

Software Construction

The construction process might include some aspects of planning, designing, and checking your work, but mostly “construction” refers to the hands-on part of creating something.

in the short time software development has existed researchers have identified numerous distinct activities that go into software development. They include:

■ Problem definition
■ Requirements development
■ Construction planning
■ Software architecture, or high-level design
■ Detailed design
■ Coding and debugging
■ Unit testing
■ Integration testing
■ Integration
■ System testing
■ Corrective maintenance

And thats a lot of red tape.

Putting construction in its context with other activities helps keep the focus on the right tasks during construction and appropriately emphasizes important nonconstruction activities.

Construction is mostly coding and debugging but also involves detailed design, construction planning, unit testing, integration, integration testing, and other activities.

Why Is Software Construction Important?

• Construction is a large part of software development. Depending on the size of the project, construction typically takes 30 to 80 percent of the total time spent on a
project.
• Construction is the central activity in software development. Requirements and
architecture are done before construction so that you can do construction  effectively.
System testing (in the strict sense of independent testing) is done after construction
to verify that construction has been done correctly
• Construction’s product, the source code, is often the only accurate description of the software. Requirements specifications and design documents can go out of date, but
the source code is always up to date. Consequently, it’s imperative that the source
code be of the highest possible quality
• Construction is the only activity that’s guaranteed to be done. The ideal software project goes through careful requirements development and architectural design before construction begins. The ideal project undergoes comprehensive, statistically
controlled system testing after construction. Imperfect, real-world projects, however,o ften skip requirements and design to jump into construction.
References.
McConnell, S. (2004). Code complete (2nd ed). Microsoft Press.

The Seams model

A program can seem like a large sheet of text. Changing a little text can cause the meaning of the whole document to change, so people make those changes carefully to avoid mistakes.

Superficially, that is all true, but what about modularity? We are often told it is better to write programs that are made of small reusable pieces, but how often are small pieces reused independently? Not very often. Reuse is tough. Even when pieces of software look independent, they often depend upon each other in subtle ways.

Seam
A seam is a place where you can alter behavior in your program without editing in
that place.

Reference

Michael, C. (2008). Feathers. Working Effectively with Legacy Code.

Sensing and separation

Generally, when we want to get tests in place, there are two reasons to break dependencies: sensing and separation.

1. Sensing—We break dependencies to sense when we can’t access values our code computes.

2. Separation—We break dependencies to separate when we can’t even get a piece of code into a test harness to run.

There are many techniques for Separation but one dominant technique for sensing.

FAKING COLLABORATORS

One of the big problems that we confront in legacy code work is dependency. If we want to execute a piece of code by itself and see what it does, often we have to break dependencies on other code. But it’s hardly ever that simple. Often that other code is the only place we can easily sense the effects of our actions. If we can put some other code in its place and test through it, we can write our tests. In object orientation, these other pieces of code are often called fake objects.

Reference

Michael, C. (2008). Feathers. Working Effectively with Legacy Code.

different Rightmost Bit

You’re given two integers, `n` and `m`. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of `2position_of_the_found_bit` (0-based).

Example

• For `n = 11` and `m = 13`, the output should be
`differentRightmostBit(n, m) = 2`.`1110 = 10112``1310 = 11012`, the rightmost bit in which they differ is the bit at position `1` (0-based) from the right in the binary representations.
So the answer is `21 = 2`.
• For `n = 7` and `m = 23`, the output should be
`differentRightmostBit(n, m) = 16`.`710 = 1112``2310 = 101112`, i.e.

``````00111
10111
``````

So the answer is `24 = 16`.

``````int differentRightmostBit(int n, int m) {
System.out.println(Integer.toBinaryString(n^m));
System.out.println(Integer.toBinaryString((~(n^m))));

return (~(n^m)+1)&(n^m);
}``````

this is a similar problem to the last bitwise problem I posted this week.

• Turning all the different bits to 1 is straightforward with xor:
n XOR m
• Turning all the bits to 0 is also straightforward with AND and NOT:
(n XOR m) AND (NOT(x XOR m))

if you n & ~n you get 0 but if you  n & ~n+1 you get the first value that was 1.

https://catonmat.net/low-level-bit-hacks

Second rightmost zero

This is a problem excersice from codesignal platform.

problem

Presented with the integer `n`, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

Return the value of `2position_of_the_found_bit`.

Example

For `n = 37`, the output should be
`secondRightmostZeroBit(n) = 8`.

`3710 = 1001012`. The second rightmost zero bit is at position `3` (0-based) from the right in the binary representation of `n`.
Thus, the answer is `23 = 8`.

```/*
You have to get rid of the rightmost 0
To fill in the rightmost 0 with 1 using x | (x + 1)
10111100  (x)
|   10111101  (x + 1)
--------
10111101
Isolate the new rightmost 0
To isolate it use ~x & (x + 1)
// now x is the value after step 1

10111101  (x)
--------
01000010  (~x)
&   10111110  (x + 1)
--------
00000010
in short
return ~(n|(n+1)) & ((n|(n+1))+1) ;
*/
```

Working with feedback

Changes in a system can be made in two primary ways.

Edit and Pray is pretty much the industry standard. When you use Edit and Pray, you carefully plan the changes you are going to make, you make sure that you understand the code you are going to modify, and then you start to make the changes. When you’re done, you run the system to see if the change was enabled, and then you poke around further to make sure that you didn’t break anything. The poking around is essential. When you make your changes, you are hoping and praying that you’ll get them right, and you take extra time when you are done to make sure that you did.

Cover and Modify is a different way of making changes. The idea behind it is that it is possible to work with a safety net when we change software. The safety net we use isn’t something that we put underneath our tables to catch us if we fall out of our chairs. Instead, it’s kind of like a cloak that we put over code we are working on to make sure that bad changes don’t leak out and infect the rest of our software. Covering software means covering it with tests.

Cover and modify means coding with tests, when we have a good set of test around a piece of code we can make changes and find out very quickly whether the effects were good or bad. Testing this way is “testing to attempt to show correctness“.

“Testing to detect change” is called regression testing. We periodically run tests that check for known good behavior to find out whether our software still works the way it did in the past.

Unit testing is one of the most important components in legacy code work. System-level regression tests are great, but small, localized tests are invaluable. They can give you feedback as you develop and allow you to refactor with much more safety. And we want unit testing because large tests have the following issues.

Issues with larger tests:

1. error localization
2. execution time
3. Coverage. Its hard to see the connection between a piece of code and the values that exercise it.

Here are qualities of good unit tests:

1. They run fast.
2. They help us localize problems.

The main issue when making unit testing is the breakage of dependencies, legacy code can or cannot be as easy to segment as one might think sometimes but when we are looking for change we have to leave the aesthetics to the side some of the time, if you come around code that was altered this way you can heal the scar.

THE LEGACY CODE CHANGE ALGORITHM

When you have to make a change in a legacy code base, here is an algorithm you can use.

1. Identify change points. Where is the code you need to change?
2. Find test points. Where is the place to put your test?
3. Break dependencies. How to get past dependencies problems.
4. Write tests.
5. Make changes and refactor.

Reference

Michael, C. (2008). Feathers. Working Effectively with Legacy Code.

Changing Software

Changing code is a complicated task, there are ways we can come up to make the code extremely difficult to read for other developers on the other hand there is also ways to make it easier for future developers to understand.

But why do we change software ?

four main reasons.

2. fixing a bug
3. improving the design
4. optimizing resources

Adding features and fixing a bug are only different in which point of view you are looking at it, for the customer something trivial may be a bug because he dosnt want it that way but for developers it may mean a new feature, never the less they have the same basic mechanic, we change the behavior in our application.

Behavior is the most important thing about software. It is what users depend on. Users like it when we add behavior (provided it is what they really wanted), but if we change or remove behavior they depend on (introduce bugs), they stop trusting us.

The act of improving design without changing its behavior is called refactoring. The idea behind refactoring is that we can make software more maintainable without changing behavior if we write tests to make sure that existing behavior doesn’t change and take small steps to verify that all along the process.

Optimization is the same as improving the design only with a different goal, we want to make the resource of a program low being this time or memory.

In general, three different things can change when we do work in a system:

1. structure,
2. functionality,
3. and resource usage.

Preserving existing behavior is one of the largest challenges in software development. Even when we are changing primary features, we often have very large areas of behavior that we have to preserve.

Risky change

To make good code we have to embrace change, if we avoid making new classes, making or new methods then the current ones are gonna get bigger and larger to the point where they became imposible to understand.

Another advantage that comes with changing code is that we get better developers, experienced developers that are not afraid of doing code changes and making changes with good insight of the code make it easier to maintain a team that knows what they are making.

Reference

Michael, C. (2008). Feathers. Working Effectively with Legacy Code.

Introduction to legacy code

The code must be flexible enough to accommodate to change, change is a constant matter in software development and is such an important task that many if not most of the developers that join the software forces at the moment are tasked primarily with the task of maintain software and not many of them will ever get to write code or

develop new features or applications.

But what is legacy code?

In the industry, legacy code is often used as a slang term for difficult-to-change code that we don’t understand. But over years of working with teams, helping them get past serious code problems, I’ve arrived at a different definition.

To me, legacy code is simply code without tests. I’ve gotten some grief for this definition. What do tests have to do with whether code is bad?

Code without tests is bad code. It doesn’t matter how well written it is; it doesn’t matter how pretty or object-oriented or well- encapsulated it is. With tests, we can change the behavior of our code quickly and verifiably. Without them, we really don’t know if our code is getting better or worse.

Michael, C. (2008). Feathers. Working Effectively with Legacy Code.