Interview Question Practice Series: Pt. 1

It's been a while since I've posted here - I've been doing functional QA work to pay the bills, but it's time to get back to iOS development topics (I've been keeping my Swift skills sharp and discussing them here helps reinforce everything I learn). This series will cover algorithm challenges and other domain specific knowledge (I've also been covering some front-end stuff, so I'll be including HTML, CSS & JS specific questions here). 

Note that these have been taken from person experience in interviews, glassdoor questions listed by big companies (largely Facebook), and a few are questions I just made up myself as personal challenges. 

Let's look at the questions and cover the answers for each. You can follow along with the code on my github repo.

 

Question 1

(FB FE engineering question) Given a multi-dimensional array, write a function to flatten it ie. Given let arr = [1, "hello", [26, "bye, 3, [5, 29]]];
the output should be: [1, "hello", 26, "bye", 3, 5, 29];
  1. We should start with an empty array that can hold objects of type <Any>.
  2. The next step is to loop through elements in the array using a range for i in 0..<input.count. We can also just use a for element in input loop if we want.
  3. Capture the current element in a variable - we need to check if it's an array or not. If it isn't an array, we can append it to our output array. If it is an array, we need to flatten it again by recursively calling our method.
  4. Feel free to use a ternary operator here for elegance! If data is an array, call our method and make sure to cast the element as a generic array (the function is expecting that as an input). If not, just append to our output array.
  5. Return the array and that's it. My posted code includes a few other methods includes a tail optimized recursive solution and a way to avoid writing loop code (makes use of dropFirst())

  1. For an iterative solution, we need to treat the input array as a stack which we'll perform pops on. We pop the first element off and check it to see if it's an array.
  2. Since we're popping off values from our array and capturing them, we're mutating the array. Items passed in as arguments cannot be mutated, so we need to create a mutable copy of the input array and work with that. Our loop will be a while loop that checks that the value of our mutable array is >= 0.
  3. If the element is an array, leave it as is and append the rest of the mutable array to it. This maintains element order. Set the mutable array to be equal to this new array and the loop will continue.
  4. If the element isn't an array, just append it to our output array.
  5. I foolishly didn't check the Array documentation to look for a "pop" function (you can use array.removeAt(n) to capture an element at a certain index. Instead, I just wrote a "shift()" Array extension function. Use self.first to capture the first element, set the array to be equal to itself.dropFirst() and return the captured first element.

Question 2

(FB iOS engineering question) Recursively and iteratively pairwise swap linked list nodes. If the number of nodes in the list is odd, leave the last node alone. Assume you have to write the code to build out a linked list and node structure. If you start with
var testList = 2->5->9->15->5 then the output should be: 5->2->15->9->5. Change the list in place instead of creating a new list and copying over nodes.
  1. Let's reference the above image. The first thing to think about is how this conceptually works. We need our second node to point to our head node, and our head node to point to the fourth (which will then point to the third). Swapping the first and second nodes is easy - what happens if we do that before grabbing a reference to the third node? The second node.next will point to the first and not the third, and we have lost any pointer to that third node. Therefore, we grab a reference to the third node and call it "temp".
  2. Second.next will point to the head, the head will point to temp.next (fourth node) but now what? We must reassign our nodes with the "node1 pointer" now pointing to our temp node. The same rules apply here - we'll have a node2 pointer that points to node1.next (fourth node in the entire list), and the temp node will point to the fifth node (not pictured).
  3. We can do this iteratively with a while(true) statement. We break when we reach a nil node (end of the list). We assign the variables before the loop, make the swaps within the loop and at the end of the loop reassign the variables.

  1. For a recursive solution, we need a reference to the second node in the list (or the second node in the pair, to be more precise). We can assign it to a variable called newNode (let newNode = listHead.next).
  2. The "swap" operation here involves two things - having the newNode point to the listHead (2->1), and having the listHead point to the rest of the (swapped) list. We must first point the listHead to the rest of a swapped list (which we'll swap recursively) by setting listHead.next equal to a recursive call to our function (this time passing in listHead.next.next as the node). We can then finish by fulfilling the second operation and saying that newNode.next is equal to the listHead.
  3. Remember that newNode is listHead.next so for the first function call, it would be 2, and in the second call, since our listHead is being passed in as 3, newNode would be 4. We're setting listHead.next equal to the function call return value, and 1 (listHead in the first function call) needs to point to 4 (newNode in the second call). Thus, we should finish our function by returning newNode.
  4. That's it!

 

Question 3

(I made this one up) Write an algorithm to create a linked list (using the code written for problem #2) from an array that is passed in (possibly multi-dimensional). You can either include this as an extension method or an init method for your list structure.

  1. As pseudocode, this is easy. Loop through your array and pass each element to your linked list function to create a node and add it to the list. You can even use inputArray.map{pushValueToList($0)} to make use of higher order functions.
  2. This isn't TOO challenging but it does test domain knowledge of protocols in Swift. First of all, we can use the flatten function we created earlier on to make sure that if our input is a multidimensional array, we're handling it properly. We get an error message here if we automatically try and do this that says "Type 'Node' does not conform to protocol 'Sequence'". Once this challenge is tackled, the problem is essentially solved.
  3. In writing out Swift code, this somewhat tests your knowledge of how initializers might work (default and convenience) - we can create a blank init method and a convenience init that takes a generic array as an argument. The convenience init must, of course, call the default init.
  4. We can then loop through the elements in the array and for each one, call our pushValueToList method.

Question 4

Hearst iOS Engineer Interview I was given this in a later interview round with Hearst. Given an array and a "sum" integer, write a function to determine whether two values exist in the array that can add up to the sum. Pay attention to performance.
The final solution is, in my opinion, really elegant. I don't think I'd be able to come up with code like that on a first attempt while writing it in front of somebody evaluating my performance. In fact, I didn't even have to make my code compile because I wrote it out with pen and paper.

  1. This one is fun because it's more straightforward than the others in terms of "algorithmic challenges" (in that it has nothing to do with writing Swift code and dealing with things like generics and unwrapping optionals and conforming to protocols). We also get to focus on performance!
  2. We know that in looking at an array element, we need to determine what other number is needed to reach the sum. This means we're looping through the array at least once (worst case), so we're at O(n) right off the bat. Let's try to make sure performance doesn't get worse than that.
  3. For each element, we want to be able to check if we've already encountered the other partner in the sum pair. If we have, we can break early and return true if our output is a Bool value. Otherwise, we can just return a tuple representing the sum pair.
  4. We know we're looking things up at every iteration of the array, so what data structure do we know has constant lookup time? A hash table! In this case, we're going to use a Swift Dictionary.
  5. Let's think about this conceptually. For each array element we're looking at, we want to see if the counterpart already exists in the dictionary. We need to know what key to look for, as that is what gets hashed and is what gives us constant lookup time. How can we know what to check for at each iteration? We can just check for the sum counterpart!
  6. We can set our key:value pairs to be counterPart:currentElement. That way, for each iteration, we know what key to check because it'll be (sum-currentElement). During each iteration - if let _ = dict[element] {return true}
    else {dict[sum-element]=element}
  7. The problem is deceptively simple - it can take a bit of thought to organize it all but the code is very straightforward. It just tests if you understand how hash tables and their lookup works.
  8. SIDE NOTE: I tried using a ternary operator here to see if I could make the code a one-liner (something along the lines of
    let _ = dict[element] != nil ? return true : dict[sum-element] = element ).
    At one point I thought about trying to use a ternary operator to make the code more concise (if we restructured the code to return a tuple) - it took to long to try and work around and clearly wasn't worth the time spent on it. That's a code smell to me - it would involve forced, inelegant workarounds that wouldn't be clear to somebody looking at it. The ternary expressions are too different to try and link together in such an operator (either returning a tuple or inserting a dictionary entry).
  9. Try modifying the code to return a tuple (sum pair). This shouldn't take more than a minute or two. Good practice, either way!

Question 5

(I made this one up) Using the linked list you designed, implement a simple LRU (least recently used) cache in Swift.

  1. We're not writing any code for this problem. It's too lengthy, in my opinion. I think it would be satisfactory for an interviewer to ask you to just talk about how you would implement an LRU using the linked list you previously wrote (or you could use an array - see number 3 below).
  2. An LRU is essentially set with a capacity and when memory is low, it evicts the least recently used item. We could potentially put this in the AppDelegate didReceiveMemoryWarning() method if we want. The other way it could work is that when we reach cache capacity, if we try to add another item to it, it will add that new item and just evict the least recently used one. Getting and settings values should be done in O(1) time.
  3. If getting and setting needs to be done in O(1), that should immediately make you think of a hashtable (dictionary in this case). We can use a dictionary to look up the address of a value and then access it using a queue. The reason we need a queue is beause order matters here (recently accessed items on the front and oldest at the back) and hash tables cannot handle that. If we want to use an array as the queue, we can just create an array of a certain size and maintain a pointer to the first and last element. You can't beat an array time complexity when it comes to random access - however, if an item in the middle of the array is used, we need to move it to the beginning of the list since it was recently used and shouldn't be evicted. That would involve removing it, adding it, and shifting all the elements after it one to the left. This is memory intensive, whereas with a linked list, we could just drop the node and swap pointers. For that reason, we'll use a doubly linked list.
  4. The hash entries look like "resource identifier: queue node address". When a resource is requested, we check the has to see if it exists. If it does, retrieve it and add it to the beginning of the queue. If it doesn't and the queue has room, create a node and add it to the beginning. If there isn't enough room, delete the last node in the queue, remove it from the hash, make the second to last the tail and add the new node to the beginning.
  5. If we're using this for caching images, we can set the hash key to be the filename and the value to be the new node that contains the file data as the node data.

You can find the second part of the interview series here.