In this post, we will solve this challenge using dynamic programming techniques and property observers.
Dynamic programming approach with property observers
This approach solves the challenge by dividing the problem into small chunks. For each tower, the height of tallest tower to the right is determined by comparing the tower's own height and reported height of tallest tower of the right neighbor, i.e.
tallest2right = max(self.height, rightTower. tallest2right)
And the height of tallest tower to the left is determined in a similar fashion. Each tower does not scan the entire array to determine tallest tower heights to either direction--it simply uses the reported value from neighbor towers to evaluate their own answers. The neighboring towers may use pre-calculated value or perform calculation on as-needed basis. In this implementation, the values are calculated and stored for each topography change (i.e. modifications to leftTower or rightTower), and the change is propagated by notifying neighbor towers.
The initial value of tallest tower to either direction is set to own height. As each tower connects to its neighbors, messages are sent to appropriate towers to update their value of tallest towers in both direction via property observer didSet(). Here's definition for Tower class.
class Tower {
enum Direction {
case LeftNeighbor
case RightNeighbor
}
var height: Int
var tallest2left: Int {
didSet {
// tallest2left changed. Tell right tower to update
if let tower = rightTower {
tower.update(.LeftNeighbor)
}
}
}
var tallest2right: Int {
didSet {
// tallest2right changed. Tell right tower to update
if let tower = leftTower {
tower.update(.RightNeighbor)
}
}
}
var leftTower: Tower? {
didSet {
// After setting left tower, re-calculate tallest2left
var newTallest = height
if let tower = leftTower {
newTallest = tower.tallest2left
}
self.tallest2left = max(height, newTallest)
}
}
var rightTower: Tower? {
didSet {
// After setting right tower, re-calculate tallest2right
var newTallest = height
if let tower = rightTower {
newTallest = tower.tallest2right
}
self.tallest2right = max(height, newTallest)
}
}
var capacity: Int {
return min(tallest2right, tallest2left) - height
}
init(height: Int) {
self.height = height
tallest2left = self.height
tallest2right = self.height
}
func update(fromNeighbor: Direction) {
switch fromNeighbor {
case .LeftNeighbor:
if let tower = leftTower {
if tower.tallest2left > tallest2left {
tallest2left = tower.tallest2left
}
}
case .RightNeighbor:
if let tower = rightTower {
if tower.tallest2right > tallest2right {
tallest2right = tower.tallest2right
}
}
}
}
}
Notice that didSet() property observer is defined for tallest2right, tallest2left, rightTower, and leftTower. The method is called whenever these instance members are changed. When the leftTower or rightTower is changed inside an instance of Tower, the tallest tower height in the appropriate direction is re-evaluated since the topographic has changed. In addition, whenever the instance of Tower calculates a new value of tallest tower heights (tallest2right or tallest2left), the tower object notifies its neighbors that they also need to re-evaluate their own tallest tower heights.
Here's the rest of the code that provides a test input, create and connects Tower objects, and prints the results.
// Function for printing out tower structure and collected water
func printTowers(towers: [Tower]) {
for var height=input.maxElement()! ; height > 0; height-- {
for i in 0..<towers.count {
if height > towers[i].height + towers[i].capacity {
print(" ", terminator: " ")
} else if height > towers[i].height {
print("W", terminator: " ")
} else {
print("*", terminator: " ")
}
}
print("")
}
}
var input = [3, 4, 2, 7, 4, 3, 8, 2, 4] // Test input containing tower heights
var width = input.count
var towers: [Tower] = [Tower]() // array to store tower structure
// instantiate tower objects based on input heights
for var height in input {
towers.append(Tower(height: height))
}
// Connect towers to their neighbors
// As each tower is connected, tallestTower for left and right
// is automatically updated with property observers.
for i in 1..<towers.count {
towers[i].leftTower = towers[i-1]
}
for i in 0..<towers.count-1 {
towers[i].rightTower = towers[i+1]
}
// Print results
// Calculate total water collected
var sum = 0
for tower in towers {
sum += tower.capacity
}
// Print out input and solution
print("Input: \(input)")
print("Output: \(sum) units of water")
// Print graphical representation of input and solution
print("")
printTowers(towers)
And the code prints:
Input: [3, 4, 2, 7, 4, 3, 8, 2, 4]
Output: 11 units of water
*
* W W *
* W W *
* W W *
* W * * W * W *
* * W * * * * W *
* * * * * * * * *
* * * * * * * * *
That's it, folks!
This comment has been removed by the author.
ReplyDeleteThank you for sharing this interesting problem. Technical interview can seem daunting. Algorithms, Design patterns and system design are essential to learn for software engineers while preparing for interviews. Great blog, I appreciate your work. System design interview preparation
ReplyDeleteThe information you've provided is useful because it provides a wealth of knowledge that will be highly beneficial to me. Thank you for sharing that. Keep up the good work. esd workbench
ReplyDelete