Code Challenge: Understanding Dynamic Programming with Swift / by Wayne Bishop

When faced with a new or difficult coding problem, it can be hard to determine the right approach. For this challenge, our goal is to identify the count of consecutive values in a sequence. Shown below, longestSequence accepts two String parameters and returns an Int:

/*
write a function to identify the largest count of consecutive "1's" in the sequence. e.g. 111000011011 -> 3
*/

func longestSequence(of key: String, list: String) -> Int {
    //code goes here..
}

THE ANALYSIS

Let's approach this challenge using techniques discussed in previous essays. To start, we should scan the question for patterns and discrepancies. One item to note is that hiring managers don't normally provide function signatures (e.g., stubs) when asking questions. Shown above, our goal is to determine the total count of consecutive of 1's, but this question could easily be extended to identify characters or specific alphanumeric sequences. We'll revisit this idea later. 


Another item to note is the pattern of 1's and 0's. Based on the sample data, there are three groups of "1" values - these total 3, 2 and 2 respectively. These values could be stored in a collection to be analyzed. Using a data structure like a max-heap is especially plausible as its main operation works in O(1) - constant time and appears to match the flow of the solution. A standard Swift Array or Dictionary could also be used, but additional logic (e.g. map, filter, reduce) would be needed to calculate the largest value. Expressed as comments, let's review: 

func longestSequence(of key: String, list: String) -> Int {
...

  //1. iterate through input list (e.g. 11100011011) 
  for s in list {
    
     //2. tally the three groups of "1" values (e.g. 3,2,2)     
     //3. store the values in a collection     
  }

  //4. apply logic to determine largest number in the set
...
}

These ideas are technically possible and should be considered. However, it would be ideal to find a solution that provides algorithmic efficiencies for both time and space. Although functional, our current design increases the required space by saving all possible values. As the essay title suggests, we can rewrite our plan using a simpler form of dynamic programming.

 

THE IMPLEMENTATION

Dynamic programming is based on the concept of "data storage for later reuse".  Depending on the scenario, this can take many forms. While saving values to a collection meets our immediate needs, a streamlined solution can save the current number of consecutive values to a single variable. This variable could then be updated depending on the scenario. In Swift, this can be expressed as follows:

func longestSequence(of key: String, list: String) -> Int {
    
    //initial values
    var current: String
    var counter: Int = 0
    var longest: Int = 0
    
    
    //iterate through list - O(n)
    for s in list {
        
        //current iteration
        current = String(s)
        
        if current == key {
            counter += 1
        }
        else {
            counter = 0
        }
        
        //preserve the longest sequence
        if counter >= longest {
            longest = counter
        }
    }
    
    //return count results
    return longest
    
}

longestSequence(of: "1", list: "11100011011")

Beyond providing space efficiencies, an additional benefit is its relatively straightforward syntax. As shown, this approach didn't require any advanced Swift features, structures or specific IOS SDK calls. As a result, such an approach would be feasible to write in a real interview situation (where one may be asked to write the solution on a whiteboard). 

 

REFINEMENT

Lastly, let's return to our first observation regarding the handling of generic input. Even though the original question didn't specifically mention generics, this could be a good opportunity to refine the solution to showcase our expertise:  

extension Array where Element: Comparable {    
    
    //determine the longest sequence of specified generic values
    func longestSequence(of key: Element) -> Int {
        
        //initial values
        var current: Element
        var counter: Int = 0
        var longest: Int = 0
        
        //iterate through list - O(n)
        for s in self {
            
            //current iteration
            current = s
            
            if current == key {
                counter += 1
            }
            else {
                counter = 0
            }
            
            //preserve the longest sequence
            if counter >= longest {
                longest = counter
            }
        }
        
       //return count results 
        return longest
        
    }
}

let list: Array<String> = ["A", "B", "B", "A"]
list.longestSequence(of: "B")