After helping iOS developers prepare for technical interviews, I like to reconnect with folks to discuss tough questions that they were asked. Recently, I came across an interesting challenge that involved binary notation and thought it worthy of a review. Even though it’s rare for hiring managers to ask candidates questions on this topic, this one has less to do with the notation and more to do with data management. For example:
For this challenge, our goal is to convert the binary value of 1001 to its regular base-10 equivalent. For our implementation, we’ll somehow manipulate our structure to return an Int value of 9. As part of our analysis, we can see the binary value isn’t a regular String but is organized through a singly linked list.
Review & Analysis
This challenge involves a few key areas that we can break down into more detail. To start, since our goal is to return a base-10 value, we should do a quick refresher on how this conversion process works. Many of us (myself included) consider bitwise operations to be an advanced topic, but much of it is based on regular addition and multiplication. Even though Swift has default functions for doing these types of operations, let’s review how this works:
As shown, each binary digit (e.g. 0 or 1) converts to a base-10 equivalent based on its numeric position. Ideally, it would be super to somehow recreate this multiplication/addition process for each item stored in our linked list. As the arrows in our structure indicate, each list item can only access the next node. This is contrary to the more flexible doubly linked list, where previous and next pointers would be accessible by each item.
Order of Operations
With a better understanding of the challenge, it’s clear the order of operations will determine a correct outcome. One “brute force” technique would be to iterate through the linked list, obtain the resulting binary value, then calling the Swift SDK to do the numeric conversion process. However, an alternate solution would be to push our nodes into a Stack. Since Stacks work based on last-in/first-out order, binary values popped from this structure could be easily converted to their base-10 equivalent in the correct order:
In Swift, this can be represented as follows:
Like this article? Get more content like this when you sign-up for the weekly iOS Computer Science Lab.
extension LinkedList {
//returns base-10 value from binary
func baseTen() -> Int {
//trivial check
guard head.tvalue != nil else {
return 0
}
var current: LLNode? = head
//establish stack
var stack = Stack<T>()
//push items to stack
while let item = current {
if let value = item.tvalue
current = item.next
}
var pos: Int = 1
var total: Int = 0
while stack.count != 0 {
//pop next item from stack..
guard let node = stack.pop() else
//convert to base-10
if let base = node as? Int {
total += base * pos
pos = pos * 2
}
}
return total
}
}