Whiteboard Challenges

[[)roi(]]

There's been a fair amount of opinions shared over the last period about the merits of data structure and algorithm questions in a technical interview; specifically the type of questions that require you to step up to a whiteboard and flesh out in front of an audience.

This is not another one of those; rather in this thread I'm going to turn it into a question vs. answer session on:

• The most common and/or challenging questions being asked in programming related interviews, and then follow this up with a solution.
• Naturally it'd be great if this isn't one sided; solutions to the problems should be open to anyone willing to try.

So why should we bother? Well it's closing on interview season; so preparedness is probably the main reason for anyone wishing to switch, not forgetting benefits for first timers.

So to start, I'm going to open with a question that a few colleagues approached me on; more specifically on how I'd go about solving it & it just happens to be also one that's come up fairly frequently in discussion on twitter, namely:

• Singly Linked Lists, or more specifically reversing one of these.

Naturally these questions assume you have prior knowledge; you certainly can't easily attempt something you don't understand. Some interviewers may be willing to provide a description, but that's not a guarantee, so preparedness is probably your best bet. I'm going to provide a short description, and a link to where you can find more information.

Singly Linked List (re Wikipedia)

• A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer.
• It's a data structure consisting of a group of nodes which together represent a sequence.

https://en.wikipedia.org/wiki/Linked_list

In short; it's a way to sequentially store data, albeit not a very efficient one; aside from being able to quickly prepend another node.

As for the solutions; I'm going to focus on providing answers in Swift, and I intend to leave the other languages for anyone else willing to take up the challenge.

First off let's define the type. If we look at the image of the Singly Linked List (SLL), we should be able to see that it's repetitive: 1st node linked to 2nd node, etc. Another name for repetitive is recursive. So my first choice will be to use a recursive data type. In Swift the first one that comes to mind is enums or more specifically indirection with enums. Swift enums are very different from those found in traditional C style languages; Swift enum implementation is far closer to Tagged Unions (also called Discriminated Unions).

Well onto the code... Here's the recursive enum type for Singly Linked Lists(SLL):

enum SLL<T> {
  case None
  indirect case Node(T, SLL<T>)
}

Basically we have two possibilities with a SLL node; it can either be None (the end of the list), or it can be a Node (which contains a value, and a link to the next node). The indirect keyword on the node case informs the compiler that we are creating a recursive link from this case.

Now let's look at how we would use this SLL type to initialise a list with the letters of the word REVERSE.

let list: SLL = .Node("R", .Node("E", .Node("V", .Node("E", .Node("R", .Node("S", .Node("E", .None)))))))

That's kind of busy to look at, so let's add some code to print a more friendlier version. So going to back to the original definition for the enum, we are going to change the default way that structure is printed (this is equivalent of the toString in e.g. C#)

enum SLL<T>: CustomStringConvertible {
  case None
  indirect case Node(T, SLL<T>)
  
  // Recursive String Conversion Property
  var description: String {
    func iterate(_ lhs: SLL<T>, _ result: String) -> String {
      var result = result
      switch lhs {
      case .None:
        result += ".eoll."
      case let .Node(l, r): result = "\(l) → " + iterate(r, result)
      }
      return result
    }
    return iterate(self, "")
  }
}

Basically we've added a protocol (Interface) compliance (CustomStringConvertible); this informs Swift that we intend to override it's default output format. Next we are required to redefine the description property. The code includes a recursive function called iterate that iterates through the nodes of the SLL, until it reaches None, at each step we append the result of the Node value to result, and then pass this new result to the next iteration.

Here's what the output from this looks like:

print(list) // R → E → V → E → R → S → E → .eoll.

Next let's get onto the main question; that of reversing the SLL, here's the code, added as an extension to the our SLL type:

extension SLL {
  func reversed(_ lhs: SLL<T> = .None, _ rhs: SLL<T> = .None) -> SLL<T> {
    if case .None = lhs, case .None = rhs {
      return reverse(self, .None)
    }
    
    switch lhs {
      case .None: return rhs
      case let .Node(l, r): return reverse(r, .Node(l, rhs))
    }
  }
}

Again I've used a recursive function that starts with the 1st if statement i.e. by default the parameters lhs & rhs are set to .None, so we start with self (the instance of our SLL), and .None for the value. Basically when we reverse the list we are starting from the bottom so the 1st element (at the bottom), will have a value of None to which we'll linked the values in reverse order. Let's call that function and see it's output.

print(list.reversed()) // E → S → R → E → V → E → R → .eoll.

// equivalent to: Node("E", .Node("S", .Node("R", .Node("E", .Node("V", .Node("E", .Node("R", .None)))))))

Anyway that's it, problem solved.

Please post your common whiteboard programming questions, and hopefully someone will provide a solution (in the language of their choosing); failing which I'll follow up with a Swift solution (after ~1 week, or sooner if you're hasty for an answer). Naturally I encourage you to try and solve these yourself.

Note:
These are not to be brain teaser questions but rather the typical questions that come up in interviews.

/Edit After @cguy's comments, I have changed the function name from reverse() to reversed() re Swift's naming convention / API guidelines for differentiating between in place (mutating: reverse) operation vs. new list (reversed: non-mutating).

This solution as @cguy surmised is non-mutating i.e. a new list created (old memory is freed, new memory is allocated), whereas mutating would imply the use of the existing memory allocation. However Swift enums are value types, meaning they are specific designed to not permit any mutation i.e. Functional Programming Paradigm. Should you wish to do an in-place reverse of the SLL, you would have to redesign this using a reference type like classes.

Why does this matter?
The process of allocating, freeing and reallocating memory comes at a cost, this cost is significantly reduced with an in-place reversal. So if resource management is key, or your SLL is significantly large, you may want to opt for references types to perform an in-place reversal of the reference pointers.

Swift btw tends to provide both options for the majority of the collection types, for example:

• sorted() - is a non-mutating (new copy) sort.
• sort() - is a mutating (in-place) sort for memory / performance reasons.

So why would you ever use the non mutating option?
Parallel processing is a complex topic that many either never master or get significantly wrong.
Value types (non-mutating) makes it easy; because every thread and/or processing node has a unique dataset that is unaffected by what is happening on the other threads / nodes. For example: massively parallel sequence processing.

As for the problems encountered with mutable data types and threading, I suggest you do some research on the broader topic of "data races":

• https://en.wikipedia.org/wiki/Race_condition
• https://github.com/google/sanitizers/wiki/ThreadSanitizerPopularDataRaces (Google summary of some most "popular" data races)

 

[[)roi(]]

Let me start the challenge with another question I found in a similar thread on interviews; one that @cguy had put forward: http://mybroadband.co.za/vb/showthr...ssessments?p=11657963&viewfull=1#post11657963

My favourite question is: "Implement the fastest dot product function you can."

This simple question (and simple function) touches on so many areas when one goes deep enough.

Without more details I'm assuming this was in reference to the algebraic dot product of two vectors e.g. a = [a1, a2, ..., an] and b = [b1, b2, ..., bn] is defined as:

 

[cguy]

Let me start the challenge with another question I found in a similar thread on interviews; one that @cguy had put forward: http://mybroadband.co.za/vb/showthr...ssessments?p=11657963&viewfull=1#post11657963


Yup, that's the definition
Without more details I'm assuming this was in reference to the algebraic dot product of two vectors e.g. a = [a1, a2, ..., an] and b = [b1, b2, ..., bn] is defined as:
View attachment 402146

Yup, your assumption about the definition I was referring to is correct. Good thread.

 

[Raithlin]

Following for now. If I can input answers I will.

 

[[)roi(]]

Yup, your assumption about the definition I was referring to is correct. Good thread.

I take it fastest, implies an expectation of parallel processing? Which should work re part of the formula is associative. Yet unless we're talking about vectors with a sizeable quantity of coordinates, I'm not all that sure it's worth the effort.

 

[cguy]

I take it fastest, implies an expectation of parallel processing? Which should work re part of the formula is associative. Yet unless we're talking about vectors with a sizeable quantity of coordinates, I'm not all that sure it's worth the effort.

Yes, that is one part of the question: How big would it have to be for multiple threads to be worthwhile? Before that can be properly answered though, one has to be able to calculate how long it takes a single core to do a dot product of length k, which is another part of the question.

 

[cguy]

BTW, Droid, the SLL reverse question is usually about reversing a SLL "in place" - your implementation seems to create a new reversed list.

 

[[)roi(]]

BTW, Droid, the SLL reverse question is usually about reversing a SLL "in place" - your implementation seems to create a new reversed list.

Functional Programming, It's all the rage... In place is easy...
Btw, that level of detail never came up on twitter; is there a reference source?

/edit
Maybe this is a good opportunity for someone else to try their hand at a solution.
Hint: reference types are a must.

Hope I'm not spoiling anyone's attempt at the in-place reverse. Anyway here's the code for an in-place reverse of a Singly Linked List using a mutable structure, using a recursive function.

import Foundation

public class MSLL<T>: CustomStringConvertible {
  public let element: T
  public private(set) var node: MSLL<T>?
  
  public init(_ element: T, node: MSLL<T>? = nil) {
    self.element = element
    self.node = node
  }
  
  public var description: String {
    func iterate(from: MSLL<T>, result: String ) -> String {
      return from.node == nil ? result + " => \(from.element) => .eomsll." :
        iterate(from: from.node!, result: result + " => \(from.element)")
    }
    return self.node == nil ? "\(self.element) => .eomsll." :
      iterate(from: self.node!, result: "\(self.element)")
  }
  
  // In-place reversal, returns "new" root instance
  public func reverse() -> MSLL<T> {
    if self.node == nil { return self }
    func swap(_ parent: MSLL<T>, _ child: MSLL<T>?) -> MSLL<T> {
      let nextChild = child?.node
      child?.node = parent
      return nextChild == nil ? child! : swap(child!, nextChild)
    }
    let nextChild = self.node
    self.node = nil
    return swap(self, nextChild)
  }
}

Quick explanation of what's happening. We're given the root, first thing we do is to save the child node reference; we then set the reference to nil, because in reverse it will be at the bottom of the LL. I created a internal swap function which accepts two parameters: parent & child: current non reversed order; with the swap function we again save the child node's child, and then link the parent reference to this child (basically we swapped the roles), we then check to see if we reached the end of LL (child == nil), if not we recursively call the swap function passing in the child which became parent, and it's saved child reference.

Note: we're simply swapping and updating reference pointers, so no memory needs to be freed or reallocated.

Btw this type of recursive function calling is known as a tail call recursive function & most languages / compilers are usually able to optimize away the stack cost of these calls, so we shouldn't hit the dreaded stackoverflow. If however your language doesn't either support tail call optimization or is unable to properly optimized your code re complexity, then don't worry, FP has a solution for this called trampolines. Trampolines essentially are a kind of loop that iteratively invokes thunk-returning functions; in a continuation-passing style that is very common in FP code.

Usage:

let list2 = MSLL("R", node: MSLL("E", node: MSLL("V", node: MSLL("E", node: MSLL("R", node: MSLL("S", node: MSLL("E")))))))

print(list2) // R => E => V => E => R => S => E => .eomsll.
print(list2.reverse()) // E => S => R => E => V => E => R => .eomsll.

FYI. In case you wondering about what the <T> is. It a generic placeholder, we could have used any letter or word as generic substitute. Basically these LL structures will work for any data type, no further changes required. Generics is also falls under the banner of Polymorphism, or more specifically parametric polymorphism.
Also if you needed a LL structure in your own code, you want to expand the features of this to include, prepending / suffixing and midfixing values, sorting, etc.

 

[[)roi(]]

To clarify the open challenge is to:

• Implement the fastest dot product function you can.

Details here: http://mybroadband.co.za/vb/showthr...Challenges?p=18702536&viewfull=1#post18702536

In addition:

• How big would it have to be for multiple threads to be worthwhile? Before that can be properly answered though, one has to be able to calculate how long it takes a single core to do a dot product of length k, which is another part of the question.

 

[cguy]

Minor nit. In your "in place" swap, it doesn't leave the list in a valid state:

print(list2) // R => E => V => E => R => S => E => .eomsll.
print(list2.reverse()) // E => S => R => E => V => E => R => .eomsll.
print(list2) // R => E => V => E => R => S => E => .eomsll.

The 3rd line simply prints "R".

 

[[)roi(]]

Minor nit. In your "in place" swap, it doesn't leave the list in a valid state:

print(list2) // R => E => V => E => R => S => E => .eomsll.
print(list2.reverse()) // E => S => R => E => V => E => R => .eomsll.
print(list2) // R => E => V => E => R => S => E => .eomsll.

The 3rd line simply prints "R".

nitpicking btw is encouraged, but so too participation.
let variable declarations btw are not mutable, also the specification is as follows:

Write a function for reversing a linked list ↴ . Do it in-place ↴ .
Your function will have one input: the head of the list.
Your function should return the new head of the list.

The only part that is a bit strange is that the original instance variable has a reference link to the tail instead of the new head; easy fix though.

To address the nitpick.
The call chaining or pipelining that occurs within Swift is immutable, meaning that an internal class function cannot simply reassign it's own reference pointer, the self reference passed into these functions is let declared as opposed to var or inout.

We can however explicitly pass a reference pointer that we can mutate as another parameter; similar to how it would have been done in C. Anyway here's how this would look:

public func reverse(self s: inout MSLL<T>) -> MSLL<T> {
    if self.node == nil { return self }
    func swap(_ parent: MSLL<T>, _ child: MSLL<T>?) -> MSLL<T> {
      let nextChild = child?.node
      child?.node = parent
      return nextChild == nil ? child! : swap(child!, nextChild)
    }
    let nextChild = self.node
    self.node = nil
    let result = swap(self, nextChild)
    s = result
    return result
  }

Calling this now is also slightly different:

var list2 = MSLL("R", node: MSLL("E", node: MSLL("V", node: MSLL("E", node: MSLL("R", node: MSLL("S", node: MSLL("E")))))))

print(list2) // R => E => V => E => R => S => E => .eomsll.
print(list2.reverse(self: &list2)) // E => S => R => E => V => E => R => .eomsll.
print(list2) // E => S => R => E => V => E => R => .eomsll.

We must declare list2 with the var keyword i.e. Mutable and we have to pass the reference pointer into the function as an inout parameter i.e. Mutable parameter

This is atypical for class functions, if required the function probably should be modelled outside of the class, either in global scope or within e.g. another static type. Basically the function would then be defined like this:

public func reverse<T>(_ self: inout MSLL<T>) -> MSLL<T> {
  if self.node == nil { return self }
  func swap(_ parent: MSLL<T>, _ child: MSLL<T>?) -> MSLL<T> {
    let nextChild = child?.node
    child?.node = parent
    return nextChild == nil ? child! : swap(child!, nextChild)
  }
  let nextChild = self.node
  self.node = nil
  self = swap(self, nextChild)
  return self
}

And called like this:

print(list2) // R => E => V => E => R => S => E => .eomsll.
print(reverse(&list2))  // E => S => R => E => V => E => R => .eomsll.
print(list2)  // E => S => R => E => V => E => R => .eomsll.

Alternatively, you can simply assign the result of the function to the list2 variable, essentially assigning the returned reference pointer, for example:

var list2 = MSLL("R", node: MSLL("E", node: MSLL("V", node: MSLL("E", node: MSLL("R", node: MSLL("S", node: MSLL("E")))))))

print(list2) // R => E => V => E => R => S => E => .eomsll.
list2 = list2.reverse()
print(list2) // E => S => R => E => V => E => R => .eomsll.
print(list2) // E => S => R => E => V => E => R => .eomsll.

 

[[)roi(]]

A few more questions:
Pick anyone you like, or simply try to rewrite any existing solutions in your preferred language, or contribute a question.

Reverse a Singly Linked List in place (Google)

• Question: Write a function that reverses the order of Singly Linked List in-place.

---

The missing integer (Amazon, Microsoft)

• Question: Write a function that takes a sorted array of integers which contains all integers between 0 and N except one value as a parameter and find the missing integer in that array.
• Example: if you are passed [0,1,2,3,5], this is an array between 0 and 5, it is sorted. However, the number 4 is missing. Your function would need to return (4).

---

The mystery function (Unattributed)
Question: You need to read the function below and tell us what you think it does:

bool mystery (unsigned int num) {
    unsigned int other = num - 1;
    bool result = ((num & other ) == 0);
    return result;
}

Question: Also, which value would this function return an incorrect result for?
Note: This type of question has been to assess ability to interpret code just by looking at it. Naturally the answer is much more obvious once you run the code.

---

Print the Fibonacci numbers(Amazon, Google, Microsoft)

• Question: Write a function that recursively prints the Fibonacci numbers below a ceiling value.

---

Mirror image of itself (Google)

• Question: Write a function that returns true if a binary tree is a mirror image of itself provided the root of that tree.

---

Rotate a 2D Array (Unattributed)

• Question: Write a function that rotates a square 2D Array clockwise by 90 degrees in-place

---

Invert a Binary Tree (Left becomes Right, Right becomes Left: Horizontal Flip) (Google)

• Question: Write a function that flips the nodes of a binary tree (left to Right, Right to Left)
  Example (Visually picture this rotated 90 degrees clockwise), before and after:
  
  

---

2nd Largest element in a Binary Search Tree(Google)

• Question: Write a function to find the 2nd largest element in a binary search tree

---

Balanced Binary Tree(Amazon)

• Question: Write a function to see if a binary tree balanced. A tree is "superbalanced" if the difference between the depths of any two leaf nodes is no greater than one.

---

Highest Product Of 3(Amazon)

• Question: Given a list_of_ints, Write a function to find the highest_product you can get from three of the integers. The input list_of_ints will always have at least three integers.

 

[MagicDude4Eva]

Question: What companies ask those type of questions. I have been in development/architecture for over 20 years, worked with all major fin/telco locally and did some international stints in automative and then classified military and government work and never ever come across any of this.

We generally focused on practical work where candidates need to prepare a project and then demonstrate as part of the interview. Most interviews purely focused on the candidates fit and background (if you are smart and willing you will achieve anything). Interestingly enough during an interview for the classified projects, a candidate presented a solution to a problem during the interview which has been implemented across most guidance systems.

With the current skillset and candidates mostly coming from Discovery/banks/Telcos I have yet to come across anyone one (despite their salaries being in the 70-80K range) who would be able to solve the missing integer question. Fibonacci who you say? Never worked with him - that would be pretty much the standard response.

The reason why I ask about those companies? Well, the big corporates will have architecture and design teams which solve all those issues and would produce specs right down to class-diagrams, SQL queries and the developer is just a typist. I can only think of startups or companies in the engineering/scientific areas asking questions like this.

 

[[)roi(]]

Question: What companies ask those type of questions. I have been in development/architecture for over 20 years, worked with all major fin/telco locally and did some international stints in automative and then classified military and government work and never ever come across any of this.

We generally focused on practical work where candidates need to prepare a project and then demonstrate as part of the interview. Most interviews purely focused on the candidates fit and background (if you are smart and willing you will achieve anything). Interestingly enough during an interview for the classified projects, a candidate presented a solution to a problem during the interview which has been implemented across most guidance systems.

With the current skillset and candidates mostly coming from Discovery/banks/Telcos I have yet to come across anyone one (despite their salaries being in the 70-80K range) who would be able to solve the missing integer question. Fibonacci who you say? Never worked with him - that would be pretty much the standard response.

The reason why I ask about those companies? Well, the big corporates will have architecture and design teams which solve all those issues and would produce specs right down to class-diagrams, SQL queries and the developer is just a typist. I can only think of startups or companies in the engineering/scientific areas asking questions like this.

I've edited the questions to indicate origins; unattributed are questions I haven't yet been able to confirm the origins.

Nevertheless the point is that whether we agree with the practice or not; it is something that is part of many well known companies' interview process. Long debates on twitter re this. However this thread is not about the debate or the validity but rather about preparedness.

As for me personally: I've been employed as a developer for >30 years and seen enough to know that large enough number of companies like technical styled interviews. As for the questions, that's the purpose of this thread i.e. to give developers an opportunity to try to solve one or more, and naturally I'm going to continue to contribute.

Ps. Aside from the @cguy's parallel processing question and the mystery function; the others are what I would consider easier to solve. Naturally some assume prior knowledge like linked lists, and binary trees; but as I've heard (& read) more than once, those that don't know their algorithms are going to struggle to find placement in certain well known companies.

 

[P924]

Nice questions, not difficult. Except the binary tree one, because I don't remember much about trees.

The array rotation should mention in place rotation.

 

[[)roi(]]

Nice questions, not difficult. Except the binary tree one, because I don't remember much about trees.

The array rotation should mention in place rotation.

Thanks I'll update it to include that;
Yet the FP approach (immutable structures) certainly has it's merits and similarities as I demonstrated with the Linked list example.

As for difficulty I agree, but from Twitter it's surprising how many people failed their interviews based on many of these questions.

Btw Binary Tree is not that all that difficult once you consider the mirror part; but if you're looking for more of challenge, you could always try your hand at cguy's question, or I'll be adding another Tree structure one shortly, that you could try.


.

 

[MagicDude4Eva]

I've edited the questions to indicate origins; unattributed are questions I haven't yet been able to confirm the origins.

Thanks - I have only ever come across those type of questions overseas (and never local). For my last 3 jobs I have not had a proper technical interview - it was more a thing of: "your CV covers everything we wanted to know" and in all cases it was the company explaining their current challenges and asked for opinion/solutions. In my current job (bidorbuy) I actually asked if I can spend a day with the staff I would be working with and then came back that afternoon with a lengthy list of what needs to change and how it should be done - I was hired that evening.

FWIW: When I worked in automative overseas I was the least educated (I got matric against my name) and worked in a team of Phd's and scientists - all very brilliant people in their respective fields but completely useless if left to their own devices. My point is that people reading this thread should not become discouraged about not being able to answer the questions posted above and that they are just as capable in any working environment.

 

[kripstoe]

FWIW: When I worked in automative overseas I was the least educated (I got matric against my name) and worked in a team of Phd's and scientists - all very brilliant people in their respective fields but completely useless if left to their own devices. My point is that people reading this thread should not become discouraged about not being able to answer the questions posted above and that they are just as capable in any working environment.

+1

Can confirm. Worked in medical research field. Experienced the same.

 

[[)roi(]]

FWIW: When I worked in automative overseas I was the least educated (I got matric against my name) and worked in a team of Phd's and scientists - all very brilliant people in their respective fields but completely useless if left to their own devices. My point is that people reading this thread should not become discouraged about not being able to answer the questions posted above and that they are just as capable in any working environment.

Sound advise... as with most things "practice breeds perfection". Better to try and fail, than not at all -- rarely anybody just grasps compithex stuff on a first try. Becoming proficient with these types of problems, algorithms, data structures, etc... always has a pay off.

 

[cguy]

Thanks - I have only ever come across those type of questions overseas (and never local). For my last 3 jobs I have not had a proper technical interview - it was more a thing of: "your CV covers everything we wanted to know" and in all cases it was the company explaining their current challenges and asked for opinion/solutions. In my current job (bidorbuy) I actually asked if I can spend a day with the staff I would be working with and then came back that afternoon with a lengthy list of what needs to change and how it should be done - I was hired that evening.

You are correct, in that these are pretty typical at tech (and fin tech) companies overseas. When I was in SA though, I did ask these type of questions (and was asked them), although I was in very tech-centric roles (i.e., the business was the tech, not supported by tech). We never, ever trust what's written on the CV - we always verify it. If one works for a sufficiently in demand company (ours has a 0.03% resume to hire rate), one sees all sorts of things, ranging from outright lies, being very flexible with the truth, to genuine mistakes due to cross-industry misunderstandings (we once had a hardware engineer, who claimed to be an experienced system software engineer - turned out he had never coded anything but a small amount of machine code for a bespoke processor, and had no idea how modern CPUs, operating systems or drivers worked at all).

Also, true story:
"Oh, your number 1 listed skill is Linear Algebra?"
"Yup"
"What can one say about the geometric transform performed by a 0-determinant matrix?"
"Uh... determinant?"
"Thanks, bye."

FWIW: When I worked in automative overseas I was the least educated (I got matric against my name) and worked in a team of Phd's and scientists - all very brilliant people in their respective fields but completely useless if left to their own devices. My point is that people reading this thread should not become discouraged about not being able to answer the questions posted above and that they are just as capable in any working environment.

I've known several people who have excelled in such environments - they didn't work on the same stuff as the PhDs, but they did other work that the PhDs would found "boring", but was still very challenging (just in a different way - less academic, more business focus), and very critical to the business function (one such person is at over $300k/y now with a matric, managing a team of such people). I will say that this kind of success is rare though (overseas at least) - looking a the educational demographics, almost everyone in the top tech firms do have degrees, and that it requires a very special kind of determination to break into the industry proper without one (and that kind of determination is highly valued).