#cs challenges

We already know how to detect loops in a singly linked list. Now, we are going to detect the node where the loop starts.

It’s easy to see that if we have two pointers moving one at twice the speed than the other, and if they start at the same time at the beginning of the loop, then they will found each other again at the very same point (with the faster point completing two laps and the slower just one).

What happens if, instead, the head of the singly linked list is not where the loop start. In that case, the slower pointer will give the faster one an advantage of k nodes, where k is the number of nodes from the head to the loop start. But where will the two pointers meet? They will meet k nodes before the end of the loop. Why? Well, by then, the slower pointer would have to walk n - k steps into the loop, and the fast one would have done k + 2(n - k)

Once we get the two pointers at the same node, and because we know they are k nodes away from the finish/start of the loop, all we need to do is to reset one of the pointers to the head of the linked list and move the two at the same speed these time. They will meet again at the start of the loop.

Given an unsigned integer, we want to count how many 1 there are in its binary representation.

The naive approach would be to try to convert the given number (presented in base 10) to binary. But that seems preposterous, after all, the system already represents all integers as binary internally.

We can inspect the bits with bitwise operators. In particular, we can use AND to extract the ones from the original number comparing it to a number of masks.

0110 & 0001 = 0000 0110 & 0010 = 0010 0110 & 0100 = 0100 0110 & 1000 = 0000

If the result of the comparison is not zero, we can increase the ones tally.

extension UInt { func countOnesMultipleMasks() -> Int { let masks:[UInt] = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808] var ones = 0 for mask in masks { if mask & self != 0 { ones += 1 } } return ones } }

The array with hard coded values is distasteful, and we can easily produce it on the go.

extension UInt { static var numberOfBits: UInt { let max = Double(UInt.max) let log = UInt(log2(max)) let numberOfBits = log + 1 return numberOfBits } static func createMasks() -> [UInt] { var masks: [UInt] = [1] let numberOfBits = UInt.numberOfBits for i in 0..<(numberOfBits-2) { masks.append(2 << i) } return masks } }

And, since we are already manipulating bits to build the mask, we can forget entirely about the array, and just update the mask on each iteration.

extension UInt { func countOnesWithMask() -> UInt { let numberOfBits = UInt.numberOfBits var mask:UInt = 1 let upper = numberOfBits - 1 var ones:UInt = 0 for i in 0..<upper { if mask & self == mask { ones += 1 } mask = 2 << i } return ones } }

But even then, we are wasting a few cycles. Most numbers are going to be much smaller than the maximum possible number. Yet, we are checking up 2 ^ (number of bits). We can manipulate the input, moving from the most significant one found, until zero. At that point, the tally is complete.

The idea is to write a couple of helpers to convert a String to a Signed Integer, and back.

Yes, I am aware you can cast values:

let x: Int = 42 var asString = String(x) assert("42" == asString) let asInt = Int(asString) assert(x == asInt)

But let’s try to explore alternative solutions. I will split this into two different posts to keep them concise. String to Integer Conversion and Integer to String Conversion

It turns out, that here, we also have three basic problems, related to the ones we found in String to Integer Conversion.

Recognize if we are dealing with a negative number.

Extract the digits of the original number

Translate each digit into its related character.

To recognize if we are dealing with a negative number is trivial. All we need to do is to check its actual value.

And to translate each digit into a character is also straightforward. We just need to remember that in ASCII (and Unicode UTF8, for instance), characters representing integers are in a contiguous space. If we know how to get to ”0”, we know how to get to the rest.

Which leave us thinking about how to solve 2. It is tempting to think about extracting the digits, and it would be nice, but, unfortunately, even when on screen we might be seeing 42, in reality, integers are represented as binary, ie, 101010. We cannot extract decimal digits from a binary. We need to compute them.

One way to calculate the last digit of any number is to take the modulo of the number and 10. Let’s say we have 1602: 1602 % 10 = 2. How to get the second integer (from right to left)? Let’s divide the input value by 10 on the realm of integers. We are down to 160, and if we get the modulo of 160, we end up with the second digit (0 in this case).

The algorithm is emerging. We take the modulo of the value and 10 to get the digit, and then, we integer divide the value by then before the next lap. Each time, we save the digit into a character buffer. And we keep looping until the value is zero. And, if the negative flag has been raised, we just append the a - to the data store at the end.

In the extract digits portion of the algorithm, special consideration needs to be taken with the zero. Not when obtained as a digit, but when given as a value. Remember we are using it as the stop condition of the loop.

But alas, if we append items into an array like this, we will end up with the values in reversed order (we are reading from right to left). Obviously, we can use a stack to save characters, instead of an array. Or, even easier, we can reverse the array to recover the digits in the correct order.

So far, we managed to deal with the negative values and to recover the digits. We need to convert them to characters. Well, once we get the digit, we just need to add it to the value of ”0”, and save the corresponding character.

The input would be something like ”42”, or perhaps ”-42”. There are at least three things to consider.

To correctly identify negative numbers

To parse each character as an integer

To construct the actual number value given the integers parsed in 2.

To solve 1. all we need to do is to inspect the first character of the string, looking for the special case ”-”. If we find it, we can raise a flag to remember to convert the number constructed in 3. to its negative.

The solution for 2 is quite interesting, and remind me one of the best books about programming I’ve ever read. I’ve never written a “hello world!” program. And as far as I can remember, the first one I wrote in C was one to print a table of ASCII codes, and their character representation. Why am I digressing like this? Because there you have a way to translate a character to an integer. And, more importantly, in ASCII, the characters representing numbers are all placed together and sorted. In other words, if you happen to know the value of ”0”, then you know that the value of ”1” is the next integer. It doesn’t matter the actual value of ”0”, the difference ”1” - “0” == 1

So far, we managed to translate the string into an array of integers. Now we need to think how to convert the array into an actual number. From grade school, we should remember that the digits of a number tell us a lot from its own value, but tell us even more with its position. The first 2 in 22 is telling us something different than the second one. In particular, given its position, it is telling us that we need to multiply it by 10. In other words, by taking into consideration the position of the digit, we can construct the actual number.

Perhaps the easier way to compute the actual number value would be to go from right to left, as we’ve done in grade school. We can start at the unit column, and as we progress to the left, we should multiply the value found there by an order of magnitude higher.

But there are a couple of issues here. The first one is that we will need to keep track of the position of each value, and then, we need to perform two operations even before starting the sum. We will need to take the exponent of 10, and then we will need to multiply that to the value in the position.

What if, instead of tracking the position, and calculate the exponent in each iteration, we leave that to the actual structure of the buffer. Let’s say we have [1,6,0,2]. If we start looping at the left, we just read 1, make it the value of our number, and move to the next step. Since we are moving to the next position, we multiply our number by 10, and then add to it the number we are reading 6. So far, we have 16. One more lap, and we multiply the number by 10, converting it to 160, and add the read digit. One last loop. The number is converted to 1600 by multiplying it by 10, and by adding 2 we finally get the expected value 1602. And all of that without tracking the position, and saving one operation per loop. The optimization is pretty popular, useful in checksums, and based on the Horner’s Scheme.

For historical reasons, I am converting Unicode to Ascii

The classical setup for the problem is “delete characters from a string”. In the case of Swift, as we already saw, strings are not just characters arrays (like in C). So, let’s rephrase the problem to Efficiently delete elements from an Array. Where the elements to be deleted are also provided as an Array.

The brute force solution would be to create a buffer and to traverse both, the array where we need to find the elements to delete, and the one containing the elements to be deleted, and only copy to the buffer those elements not marked to be deleted.

The running time would be O(n*m), where n is the numbers of elements in the original array, and m the number of elements in the array with elements to be deleted. Here we can improve the running time by transforming the arrays with elements to be deleted to a hash table. Lookup for a hash table is, on average, constant. If we need to traverse m just once to build the hash table, complexity is reduced to O(n+m). There nothing we can do with n. After all, we do need to traverse the original array to check each of its values.

Now, let’s think about the whole buffer array. Let’s consider the array

[1,2,3,4]

From where we want to delete, let’s say, [1,3].

If instead of copying the valid elements to a new array, we swap elements within the array, pushing the unwanted element to the beginning or the end, and then just slice the array, we can ditch the buffer altogether. In C, is easier to slice an array chopping the end. That’s not the case in Swift, but, just for the sake of uniformity, let’s agreed that we are going to shift the elements we want to keep to the beginning of the array (and then chop the unwanted elements from the end).

In our example, we would need to shift 1 all the way to the end, or 4 all the way to the beginning. In the worst case, where we need to delete all the elements of the array, we would need to shift the last element n positions to the beginning, the element before that n-1 positions and so on. We would we running in O(n^2).

Perhaps the buffer idea is not so bad after all. With a buffer, we just need to copy the elements we want to keep to the buffer, and that’s all. We can forget about them. Each time we find an element we want to keep, we move it to the buffer, and we keep moving along the original array. Again, once copied, we can forget about the characters. And the cardinality of the buffer will tell us how many elements we preserved up to any given point.

It turns out, that’s all we need, to know at any given point if we want to keep the element we are inspecting. We don’t really need the buffer, we just need its cardinality. And we can switch elements within the same array, using the buffer cardinality as an index. We can actually use the array we are inspecting as the buffer itself. Once we are done, we slice it up to the buffer cardinality.

Let’s revisit our example. We start by looping [1,2,3,4]. We find that we don’t want 1, we move to the next element. 2 is one that we want to keep. If we would using a buffer, it would be empty at this point. Its cardinality would be zero. So, let’s switch the element at position 1 (the element currently inspected), with the one at position 0 (the last element of the buffer, if you want). The array when leaving the current loop would be [2,1,3,4]. We are currently in position 2, which points to element 3, we don’t want it. Move to position 3. The 4 is an element we want to keep. So we move it to the last element of the buffer, that is, 1. The array when leaving the loop is [2,4,3,4], and the buffer cardinality is now 2. We reached the end of the array to inspect. All we need to do is to cut the buffer, i.e. the first two elements of the array: [2,4]

Here the implementation where an Array extension returns a slice of itself.

extension Array where Element:Hashable { mutating func deleteElements(_ elements:[Element]) -> ArraySlice<Element> { var toDelete: [Element: Bool] = [:] for e in elements { toDelete[e] = true } var dst = 0 var src = 0 for i in self { let found = toDelete[i, default: false] if !found { self[dst] = self[src] dst += 1 } src += 1 } return self[..<dst] } }

Remember that, an array slice is just a view to the array. We are not copying or creating anything expensive here.

The challenge is to reverse the words in a string. In Swift, the struct offers limited access to the underlying characters array. That means, in order to operate at the character level, we need to get a buffer with it.

let str = "Call me Ishmael." let strArray = Array(str) // ["C", "a", "l", "l", " ", "m", "e", " ", "I", "s", "h", "m", "a", "e", "l", "."]

Now, we can use the array techniques to manipulate the string. For instance, we can reverse the content of the array with two pointers advancing towards each other from both ends.

while down < up { (chars[down], chars[up]) = (chars[up], chars[down]) down += 1 up -= 1 }

By swapping elements like this, the string is going to be completely reversed: .leamhsI em llaC. But the challenge is to reverse the order in which the words appear, not the letters.

One more pass would do the trick. All we need to do is to find the tokens that separate the string into words (let’s say, the space character), and then reverse the characters within each group.

So, next step is to retrieve the indices of all the spaces in the string. In the 70s Donald Knuth and Vaughan Pratt and independently, James H. Morris, conceived an algorithm to search for a substring. It makes little sense to use Knuth–Morris–Pratt here because the cardinality of substring is 1. Knuth–Morris–Pratt perform better when the substring to search is long enough. When we get a mismatch, the substring itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. But, nevertheless, let’s implement.

private func indicesOf(subString: String, searchArray: [String.Element]) -> [Int] { // https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm var indices: [Int] = [] let word = Array(subString) var m = 0 var i = 0 while m + i < searchArray.count { if word[i] == searchArray[m + i] { if i == word.count - 1 { indices.append(m) m += i + 1 i = 0 } else { i += 1 } } else { m += 1 i = 0 } } return indices }

Now, with the indices of the tokens at our disposal ([8, 11]), we can split the string, and reversed the letters within each word.

func reversedWords() -> String { var chars = Array(self) let range = Range(0..<(chars.count-1)) self.reverseChars(chars: &chars, range: range) let indices = self.indicesOf(subString: " ", searchArray: chars) print(indices) var lower = 0 for i in indices { let range = Range(lower..<(i-1)) self.reverseChars(chars: &chars, range: range) lower = i+1 } let lastRange = Range(((indices.last!)+1)..<(chars.count-1)) self.reverseChars(chars: &chars, range: lastRange) return String(chars) }

And we are done: Ishmael. me Call

And, since we already have a singly linked list, let’s try to reverse it.

Let’s consider the very basic structure of a linked list to help us find a solution. In essence, we have just a chain of nodes, each one pointing pointing to the next, and the special case is the last one in the chain (the tail). We indicate the special case by setting the next pointer to nil

Node(1)->Node(2)->Node(3)->Node(4)->Node(5)->Node(6)->Node(7)->Node(8)->Node(9)->Node(10)->nil

The brute force solution would be to traverse the entire linked list until we get to the tail, preserving each step in a data structure (perhaps a stack) and then, produce a new list with the items in the reverse order. Obviously, we would be increasing the space complexity. But let’s get back to the print-out. To reverse the linked list all we need to do is to flip the direction of the arrows.

func reversed() { guard let head = self.head else { return } var previousNode:NodeType? = nil var currentNode:NodeType? = head var nextNode:NodeType? = nil while currentNode != nil { // if there is a `next` node, we keep moving if let next = currentNode?.next { nextNode = next } else { // but if we are at the last node, we reset the head of the list self.head = currentNode nextNode = nil } // Let's change the direction of the next pointer arrow // In the first loop, `previousNode` marking the sentinel of the reversed list currentNode?.next = previousNode // and now, prev is pointing to current, and we move on previousNode = currentNode currentNode = nextNode } }