Categories
Career Programming

How to solve coding interview questions: Linked lists, part 1

Programmer Humor, How, and Coding: Me: I can't wait for my first coding
 interview!
 The interviewer:
 I'm about to end this man's whole career
That’s how it works
Okay, maybe coding interviews aren’t that bad.
But they’re close!

If you’re interviewing for a position that requires you to code, the odds are pretty good that you’ll have to face a coding interview. This series of articles is here to help you gain the necessary knowledge and skills to tackle them!

Over the next couple of articles in this series, I’ll walk you through a classic computer science staple: linked lists. And by the end of these articles, you’ll be able to handle this most clichéd of coding interview problems, satirized in the meme below:

r/ProgrammerHumor - Reverse it right now

You’ve probably seen the ads for AlgoExpert with the woman pictured above, where she asks you if you want a job at Google and if you know how to reverse a linked list.

But before you learn about reversing linked lists — or doing anything else with them — let’s first answer an important question: what are they?

What are linked lists?

A linked list is a data structure that holds data as a list of items in a specific order. Linked lists are simple and flexible, which is why they’re the basis of many of the data structures that you’ll probably use in your day-to-day programming.

Linked list basics

Nodes

The basic component of a linked list is a node, which is diagrammed below:

A node in a linked list.
Tap to view at full size.

In its simplest form, a node is a data structure that holds two pieces of information:

  • data: This holds the actual data of the list item. For example, if the linked list is a to-do list, the data could be a string representing a task, such as “clean the bathroom.”
  • next: A linked list is simply a set of nodes that are linked together. In addition to the data it holds, a node should also know where the next node is, and that’s what its next property is for: it points to the next item in the list. In languages like C and Go, this would be a pointer, while in languages like C#, Java, JavaScript, Kotlin, Python, and Swift, this would be a reference.

Here’s a Python implementation of a node. We’ll use it to implement a linked list:

# Python

class Node:
    
    def __init__(self, data):
        self.data = data
        self.next = None
        
    def __str__(self):
        return f"{self.data}"

With Node defined, you can create a new node containing the data “Hello, world!” with this line of code:

new_node = Node("Hello, world!")

To print the data contained inside a node, call Node’s print() method, which in turn uses the value returned by its __str__() method:

print(new_node)
# Outputs “Hello, world!”

Assembling nodes into a linked list

You create a linked list by connecting nodes together using their next properties. For example, the linked list in the diagram below represents a list of the first four letters of the alphabet: a, b, c, and d, in that order:

A linked list of nodes.
Tap to view at full size.

The diagram above features the following:

  • Four nodes, each one for a letter in the list.
  • A variable called head, which is a pointer or reference to the first item in the list. It’s the entry point to the list, and it’s a necessary part of the list — you can’t access a linked list if you can’t access its head.
  • An optional variable called tail, which is a pointer or reference to the last item in the list. It’s not absolutely necessary, but it’s convenient if you use the list like a queue, where the last element in the list is also the last item that was added to the list.

Let’s build the linked list pictured above by putting some nodes together:

# Python

# Let’s build this linked list:
# a -> b -> c -> d

head = Node("a")
head.next = Node("b")
head.next.next = Node("c")
head.next.next.next = Node("d")

That’s a lot of nexts. Don’t worry; we’ll come up with a better way of adding items to a linked list soon.

Here’s an implementation that creates the same list but doesn’t rely on chaining nexts:

# Python

# Another way to build this linked list:
# a -> b -> c -> d

head = Node("a")

node_b = Node("b")
head.next = node_b

node_c = Node("c")
node_b.next = node_c

node_d = Node("d")
node_c.next = node_d

To see the contents of the list, you traverse it by visiting each node. This is possible because each node points to the next one in the list:

# Python

print(head)
print(head.next)
print(head.next.next)
print(head.next.next.next)
print(head.next.next.next.next)

Here’s the output for the code above:

a
b
c
d
None

Of course, the code above becomes impractical if you don’t know how many items are in the list or as the list grows in size.

Fortunately, the repetition in the code — all those prints and nexts — suggests that we can use a loop to get the same result:

# Python

current = head

while current is not None:
    print(current)
    current = current.next

Here’s the output for the code above:

a
b
c
d

A linked list class

Working only with nodes is a little cumbersome. Let’s put together a linked list class that makes use of the Node class:

# Python

class LinkedList:
    
    def __init__(self):
        self.head = None
        
    def __str__(self):
        if self.head is None:
            return('Empty list.')
        
        result = ""
        current_node = self.head
        while current_node is not None:
            result += f'{current_node}\n'
            current_node = current_node.next
        return result.strip()
    
    def add_last(self, data):
        new_node = Node(data)

        # If the list is empty,
        # point `head` to the newly-added node
        # and exit.
        if self.head is None:
            self.head = new_node
            return
        
        # If the list isn’t empty,
        # traverse the list by going to each node’s
        # `next` node until there isn’t a `next` node...
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        
        # If you’re here, `current_node` is
        # the last node in the list.
        # Point `current_node` at
        # the newly-added node.
        current_node.next = new_node

This LinkedList class has the following members:

  • head: A property containing a pointer or reference to the first item in the list, or None if the list is empty.
  • __init__(): The class initializer, which initializes head to None, meaning that any newly created LinkedList instance is an empty list.
  • __str__(): Returns a string representation of the contents of the linked list for debugging purposes. If the list contains at least one item, it returns the contents of the list. If the list is empty, it returns the string Empty list.
  • add_last(): Given a value, it creates a new Node containing that value and adds that Node to the end of the list.

With this class defined, building a new list requires considerably less typing…

# Python

list = LinkedList()
list.add_last("a")
list.add_last("b")
list.add_last("c")
list.add_last("d")

…and displaying its contents is reduced to a single function call, print(list), which produces this output:

a
b
c
d

Coming up next:

  • JavaScript implementations
  • Adding an item to the start of a linked list
  • Finding an item in a linked list
  • Will you ever use a linked list, and why do they ask linked list questions in coding interviews?

Previously in this series

Categories
Career Programming

How to solve coding interview questions: Finding the first NON-recurring character in a string in Swift

This reminds me of what happened in my worst interview.

In previous posts, I’ve presented Python, JavaScript, and TypeScript solutions for the coding interview challenge: “Write a function that returns the first NON-recurring character in a given string.” In this post, I’ll show you my solution in Swift.

Here’s a table that provides some sample input and corresponding expected output for this function:

If you give the function this input……it should produce this output:
aabbbXccddX
a🤣abbbXcc3dd🤣
aabbccddnull / None / nil

The algorithm

I’ve been using an algorithm that takes on the problem in two stages:

In the first stage, the function steps through the input string one character at a time, counting the number of times each character in the string appears in a “character record”. Because we’re looking for the first non-recurring character in the input string, the order in which data is stored in the character record is important. It needs to maintain insertion order — that is, the order of the character record must be the same order in which each unique character in the input string first appears.

For example, given the input string aabbbXccdd, the function should build a character record that looks like this:

CharacterCount
a2
b3
X1
c2
d2

Given the input string a🤣abbbXcc3dd, it should build a character record that looks like this:

CharacterCount
a2
🤣1
b3
X1
c2
31
d2

Given the input string aabbccdd, it should build a character record that looks like this:

CharacterCount
a2
b2
c2
d2

Once the function has built the character record, it’s time to move to the second stage, where it iterates through the character record in search of a character with a count of 1, and:

  • If the function finds such a character, it exits the function at the first such occurrence, returning that character. For the input string aabbbXccdd, it returns X, and for the input string a🤣abbbXcc3dd, it returns 🤣.
  • If the function doesn’t find any characters with a count of 1, it exits the function, having gone through every character in the character record, returning a null value (which in the case of Swift is nil).

Using a Swift OrderedDictionary

The character record is the key to making the algorithm work, and the key to the character record is that must be an ordered collection. If I add a, b, and c to the character record, it must maintain the order a, b, c.

This isn’t a problem in Python. While Python dictionaries have traditionally been unordered, as of Python 3.7, dictionaries maintain insertion order. In the previous articles covering this coding interview question, my Python solutions used a regular Python dictionary.

Because JavaScript runs in so many places in so many versions, I decided not to trust that everyone would be running a later version, which preserves insertion order. In the previous article, I wrote a JavaScript solution that implemented the character record using Map, a key-value data structure that keeps the items stored in the order in which they were inserted.

Swift’s built-in Dictionary does not keep the items in any defined order. Luckily, the Swift Collections package provides OrderedDictionary, which gives us both key-value storage and insertion order.

You’ll need to add Swift Collections to your project in order to use it. To do this, select FileAdd Packages…

The dialog box for adding packages will appear:

Do the following:

  • Enter swift-collections into the search field.
  • Select swift-collections from the package list.
  • Click Add Package.

You’ll be presented with a list of products within the Swift Collections package:

For this exercise, you’ll need only OrderedCollections, so check its box and click Add Package, which will add the package to your project.

Implementing the solution

Now we can implement the solution!

// We need this for `OrderedDictionary` 
import OrderedCollections

func firstNonRecurringCharacter(text: String) -> String? {
  var characterRecord = OrderedDictionary<Character, Int>()
   
  for character in text {
    if characterRecord.keys.contains(character) {
      characterRecord[character]! += 1
    } else {
      characterRecord[character] = 1
    }
  }
  
  for character in characterRecord.keys {
    if characterRecord[character] == 1 {
      return String(character)
    }
  }
 
  return nil
}

characterRecord, which keeps track of the characters encountered as we go character by character through the input string, is an OrderedDictionary. Note that with Swift, which is both statically and strongly typed, we need to specify that characterRecord’s keys are of type Character and its values are Ints.

After that, the implementation’s similar to my Python and JavaScript versions.

Previously in this series

Categories
Career Programming

How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string

In the previous installment in the How to solve coding interview questions series, I showed you my Python solution for the challenge “Find the first NON-recurring character in a string,” which is a follow-up to the challenge “Find the first recurring character in a string.”

A couple of readers posted their solution in the comments, and I decided to take a closer look at them. I also decided to write my own JavaScript solution, which led me to refine my Python solution.

“CK”’s JavaScript solution

The first reader-submitted solution comes from “CK,” who submitted a JavaScript solution that uses sets:

// JavaScript

function findFirstNonRepeatingChar(chars) {
    let uniqs = new Set();
    let repeats = new Set();
    
    for (let ch of chars) {
        if (! uniqs.has(ch)) {
            uniqs.add(ch);
        } else {
            repeats.add(ch);
        }
    }
    
    for (let ch of uniqs) {
        if (! repeats.has(ch)) {
            return ch;
        }
    }
    
    return null;
}

The one thing that all programming languages that implement a set data structure is that every element in a set must be unique — you can’t put more than one of a specific element inside a set. If you try to add an element to a set that already contains that element, the set will simply ignore the addition.

In mathematics, the order of elements inside a set doesn’t matter. When it comes to programming languages, it varies — JavaScript preserves insertion order (that is, the order of items in a set is the same as the order in which they were added to the set) while Python doesn’t.

CK’s solution uses two sets: uniqs and repeats. It steps through the input string character by character and does the following:

  • If uniqs does not contain the current character, it means that we haven’t seen it before. Add the current character to uniqs, the set of characters that might be unique.
  • If uniqs contains the current character, it means that we’ve seen it before. Add the current character to repeats, the set of repeated characters.

Once the function has completed the above, it steps through uniqs character by character, looking for the first character in uniqs that isn’t in repeats.

For a string of length n, the function performs the first for loop n times, and the second for loop some fraction of n times. So its computational complexity is O(n).

Thanks for the submission, CK!

Dan Budiac’s TypeScript solution

Dan Budiac provided the second submission, which he implemented in TypeScript:

// TypeScript

function firstNonRecurringCharacter(val: string): string | null {

    // First, we split up the string into an
    // array of individual characters.
    const all = val.split('');

    // Next, we de-dup the array so we’re not
    // doing redundant work.
    const unique = [...new Set(all)];

    // Lastly, we return the first character in
    // the array which occurs only once.
    return unique.find((a) => {
        const occurrences = all.filter((b) => a === b);
        return occurrences.length === 1;
    }) ?? null;

}

I really need to take up TypeScript, by the way.

Anyhow, Dan’s approach is similar to CK’s, except that it uses one set instead of two:

  1. It creates an array, all, by splitting the input string into an array made up of its individual characters.
  2. It then creates a set, unique, using the contents of all. Remember that sets ignore the addition of elements that they already contain, meaning that unique will contain only individual instances of the characters from all.
  3. It then goes character by character through unique, checking the number of times each character appears in all.

For a string of length n:

  • Splitting the input string into the array all is O(n).
  • Creating the set unique from all is O(n).
  • The last part of the function features a find() method — O(n) — containing a filter() method — also O(n). That makes this operation O(n2). So the whole function is O(n2).

Thanks for writing in, Dan!

My JavaScript solution that doesn’t use sets

In the meantime, I’d been working on a JavaScript solution. I decided to play it safe and use JavaScript’s Map object, which holds key-value pairs and remembers the order in which they were inserted — in short, it’s like Python’s dictionaries, but with get() and set() syntax.

// JavaScript

function firstNonRecurringCharacter(text) {
    // Maps preserve insertion order.
    let characterRecord = new Map()

    // This is pretty much the same as the first
    // for loop in the Python version.
    for (const character of text) {
        if (characterRecord.has(character)) {
            newCount = characterRecord.get(character) + 1
            characterRecord.set(character, newCount)
        } else {
            characterRecord.set(character, 1)
        }
    }

    // Just go through characterRecord item by item
    // and return the first key-value pair
    // for which the value of count is 1.
    for (const [character, count] of characterRecord.entries()) {
        if (count == 1) {
            return character
        }
    }

    return null
}

The final part of this function takes an approach that’s slightly different from the one in my original Python solution. It simply goes through characterRecord one key-value pair at a time and returns the key for the first pair it encounters whose value is 1.

It remains an O(n) solution.

My revised Python solution

If I revise my original Python solution to use the algorithm from my JavaScript solution, it becomes this:

# Python

def first_non_recurring_character(text):
    character_record = {}
    
    # Go through the text one character at a time
    # keeping track of the number of times
    # each character appears.
    # In Python 3.7 and later, the order of items
    # in a dictionary is the order in which they were added.
    for character in text:
        if character in character_record:
            character_record[character] += 1
        else:
            character_record[character] = 1
    
    # The first non-recurring character, if there is one,
    # is the first item in the list of non-recurring characters.
    for character in character_record:
        if character_record[character] == 1:
            return character

    return None

This is also an O(n) solution.

Previously in this series

Categories
Career Programming

How to solve coding interview questions: The first NON-recurring character in a string

Welcome back to How to solve coding interview questions! In this series of articles, I’ll walk you through the sort of questions that you might be asked in a coding interview and provide solutions in a couple of programming languages.

In the previous article in this series, I presented you with a challenge to write a function that took a string as an argument and returned either:

  • The first recurring character in the given string, if one exists, or
  • A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

I also provided solutions in Python, JavaScript, and Swift.

The follow-up challenge

Usually in a coding interview, if you succeed at the initial challenge, there’s usually a follow-up that is a more challenging variation on the theme. The “find the first recurring character” challenge is often followed up by looking for its opposite:

Write a Python function named first_nonrecurring_character() or a JavaScript function named firstNonRecurringCharacter() that takes a string and returns either:

  • The first NON-recurring character in the given string, if one exists, or
  • A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

Here are some example inputs for the function, along with what their corresponding outputs should be:

If you give the function this input……it should produce this output:
'aabbbXccdd''X'
'a🤣abbbXcc3dd''🤣'
‘aabbccdd'null / None / nil

One solution

See if you can code it yourself, then scroll down for my solution.

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

Let’s consider the following example string:

"a🤣abbbXcc3dd"

The string is short, and I purposely made the first non-recurring character an emoji so that it would be easy to spot, so a glance is all you need to spot it.

One programmatic approach is to go through the string one character at a time and keep track of the number of times you’d encountered each character. For this example string, you’d end up with this:

CharacterNumber of times it appeared in the string
a2
🤣1
b3
X1
c2
31
d2

If you maintain the order in which the characters were encountered, the solution becomes either:

  • The first character that appears 1 time in the string, if one exists, or
  • A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

This was my first pass at a solution in Python:

# Python

def first_non_recurring_character(text):
    character_record = {}
    
    # Go through the text one character at a time
    # keeping track of the number of times
    # each character appears.
    # In Python 3.7 and later, the order of items
    # in a dictionary is the order in which they were added.
    for character in text:
        if character in character_record:
            character_record[character] += 1
        else:
            character_record[character] = 1
            
    # Now that we have a record of the number of times each character appears,
    # create a list containing only those characters that have appeared once.
    non_recurring_character_record = {k:v for (k, v) in character_record.items() if v == 1}
    non_recurring_characters = list(non_recurring_character_record.keys())
    
    # The first non-recurring character, if there is one,
    # is the first item in the list of non-recurring characters.
    if len(non_recurring_characters) == 0:
        return None
    else:
        return non_recurring_characters[0]

What’s the Big O?

In the code above, there are 2 O(n) operations:

  • The for loop that builds a record of the number of times each character appears in the text, and
  • This list comprehension:
# Python

{k:v for (k, v) in character_record.items() if v == 1}

These operations take place one at a time, so the complexity of the code is O(2n). As far as computational complexity is concerned, constants don’t really matter; O(2n) is effectively the same as O(n). So its computational complexity is O(n).

An (unsuccessful) attempt to make the solution a little more time- and space-efficient

In its current form, the code builds a record of the number of times each character appears in the text — even those that appear more than once. Then, in the next step, it goes through that record to create a new record of the characters that appear only once.

I thought: “What if we eliminated that second step by building a record of only characters that appeared once?”

Here’s pseudocode that explains what I mean:

For each character in the text:
    If the current character is already in the record:
        Remove that character from the record
    Otherwise:
        Add that character to the record

At the end of the for loop, the character record contains only the characters that have appeared once.

Here’s my revised implementation:

# Python

def first_non_recurring_character(text):
    character_record = {}
    
    # Go through the text one character at a time
    # but record ONLY those characters that appear once.
    # In Python 3.7 and later, the order of items
    # in a dictionary is the order in which they were added.
    for character in text:
        if character in character_record:
            # We've seen this character before,
            # so remove it from the record.
            del character_record[character]
        else:
            # # We've never seen this character before,
            # so add it to the record.
            character_record[character] = 1        
    
    # character_record contains only those characters
    # that appear ONCE in the string
    non_recurring_characters = list(character_record.keys())
    
    if len(non_recurring_characters) == 0:
        return None
    else:
        return non_recurring_characters[0]

This solution seems like a good idea, but it has a big flaw! As one reader, Hans, astutely pointed out in a comment:

basically it tests if characters appear an odd number of times in a string. For example if a character appears a third time, it was removed the second time and consequently added again to character_record that third time.

This is true — by removing a character from character_record, it’s as if the character was never encountered. I’m going to treat this as a reminder to:

  • Not prematurely discard information, and
  • Write better tests!

So in the end, I should stick with my first solution. Good catch, Hans, and thanks for pointing out my mistake!

Previously in this series

Categories
Humor Programming

TMTOWTDI (“There’s more than one way to do it”)

“Tuxedo Winnie-the-Pooh” meme, where plain Pooh simply declares “public int x” while tuxedo Pooh declares “private int x” and implements a getter and setter.

Categories
Career Programming

Coding interview questions: “First recurring character” in Swift

Earlier this week, I posted the first article in the How to solve coding interview questions series: Find the first recurring character in a string.

Here’s the challenge:

Write a Python function named first_recurring_character() or a JavaScript function named firstRecurringCharacter() that takes a string and returns either:

° The first recurring character in the given string, if one exists, or

° A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

Here’s the Swift version of my solution:

// Swift

func firstRecurringCharacter(text: String) -> String? {
  var previouslyEncounteredCharacters = Set<Character>()
  
  for character in text {
    if previouslyEncounteredCharacters.contains(character) {
      return String(character)
    } else {
      previouslyEncounteredCharacters.insert(character)
    }
  }
  
  return nil
}

The Swift implementation differs from the Python and JavaScript versions due to Swift’s stricter typing

  1. Swift’s Set requires you to specify the type of things that it will store. In this case, we want to store items of type Character.
  2. When looping through the items in a string with a for loop in Swift, you get Character items. That’s why previouslyEncounteredCharacters stores Character items and not String items. Once the function detects the first recurring character, it converts that character into a string and returns that value.

Previously in this series

Categories
Programming What I’m Up To

Fix the ChromeDriver 103 bug with ChromeDriver 104

The ChromeDriver 103 bug

If you had an application or script that uses Selenium and ChromeDriver to control or automate instances of Chrome or Chromium, it’s probably not working right now. Instead, you’re probably seeing error messages that look like this:

Message: unknown error: cannot determine loading status
from unknown error: unexpected command response
  (Session info: chrome=103.0.5060.53)
Stacktrace:
0   chromedriver                        0x000000010fb6f079 chromedriver + 4444281
1   chromedriver                        0x000000010fafb403 chromedriver + 3970051
2   chromedriver                        0x000000010f796038 chromedriver + 409656

...and on it goes...

The culprit is ChromeDriver 103, and I wrote about it a couple of days ago in a post titled Why your Selenium / ChromeDriver / Chrome setup stopped working.

ChromeDriver 103 — or more accurately, ChromeDriver 103.0.5060.53 — works specifically with Chrome/Chromium 103.0.5060.53. If you regularly update Chrome or Chromium and use ChromeDriverManager to keep ChromeDriver’s version in sync with the browser, you’ve probably updated to ChromeDriver 103.0.5060.53, which has a causes commands to ChromeDriver to sometimes fail.

The fix

Luckily, the bug has been fixed in ChromeDriver 104, which works specifically with Chrome 104. This means that if you update to Chrome and ChromeDriver 104, your Selenium / ChromeDriver / Chrome setup will work again.

The challenge is that Chrome 104 is still in beta. As I’m writing this, the Google Chrome Beta site is hosting an installer for Chrome 104, or more accurately, Chrome 104.0.5112.20. The application has the name Google Chrome Beta and is considered a separate app from Google Chrome. This means that you can have the current release and the beta version installed on your machine at the same time.

Once you’ve installed Chrome Beta, you just need to make your Selenium/ChromeDriver application or script use the appropriate version of ChromeDriver. Here’s how I did it in Transmogrifier, my Python script that helps me assemble the Tampa Bay Tech Events list:

from selenium import webdriver
from selenium.webdriver.chrome.options import Options
from selenium.webdriver.chrome.service import Service
from webdriver_manager.chrome import ChromeDriverManager


// 1
option = Options()
option.binary_location='/Applications/Google Chrome Beta.app/Contents/MacOS/Google Chrome Beta'

// 2
driver = webdriver.Chrome(service=Service(ChromeDriverManager(version='104.0.5112.20').install()), options=option)

Here are some explanation that match the number comments in the code above:

  1. These lines create an instance of the Options class, which we’re using to specify the directory where the Chrome beta app can be found. We’ll use the instance, options, when we create driver, the object that controls the Chrome beta app.
  2. This constructor creates a WebDriver.Chrome object which will control the Chrome beta app. The service parameter specifies that the driver should be an instance of ChromeDriver 104, and that it should be installed if it isn’t already present on the system. The options parameter specifies that ChromeDriver should drive the version of Chrome located at the directory path specified in the option object: the Chrome beta app.

Once that’s done, I can proceed with my script. Here’s a simplified version of the start of my Transmogrifier script:

from bs4 import BeautifulSoup

// Load the web page whose URL is `url` into
// the browser under script control
driver.get(url)

// Execute any scripts on the page so that
// we can scrape the final rendered version
html = driver.execute_script('return document.body.innerHTML')

// And now it’s time to scrape!
soup = BeautifulSoup(html, 'html.parser')
// ...the rest of the code goes here...

Hope this helps!