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
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.
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.
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...
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:
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.
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...
Are you interviewing for job that involves coding or requires coding skills? Then it’s very likely that you’ll be asked to undergo a coding test in the interview.
A long while back, I very badly embarrassed myself in an interview with Google. A Googler friend referred me (referrals are always better than applying yourself) and a handful of days later, I was in the interview, and I did everything wrong. I promised myself that I would never embarrass myself with such a pitiful coding performance at an interview again, and I’d also like to help ensure that it never happens to you either.
The trick, of course, is to practice. In this series, How to solve coding interview questions, I’ll walk you through the sort of questions that you might be asked in a coding interview. Many of the questions you’ll be asked will involve the sort of things that get covered in a “Algorithms and data structures” class and will be designed to test your general problem-solving ability. I’ll show you a solution, and where applicable, I’ll show you some alternate solutions and discuss the pros and cons of each.
You should try coming up with your own answers before looking at mine — after all, it’s the best way to learn!
The “first recurring character” function
This is a classic coding interview question that is often presented to junior developers.
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 are some example inputs for first_recurring_character(), along with what their corresponding outputs should be:
If you give the function this input…
…it will produce this output:
'abcdeefg'
'e'
'abccddee'
'c'
'abcde'
null / None / nil
One solution
See if you can code it yourself, then scroll down for my solution.
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
If you had to perform the function’s job yourself, you’d probably go through the given string character by character and use a piece of paper to jot down the keep track of the characters you’ve already seen.
Here’s a solution that takes this approach, in Python:
def first_recurring_character(text):
previously_encountered_characters = []
for character in text:
if character in previously_encountered_characters:
return character
else:
previously_encountered_characters.append(character)
return None
Here’s the JavaScript version:
function firstRecurringCharacter(text) {
let previouslyEncounteredCharacters = []
for (const character of text) {
if (previouslyEncounteredCharacters.includes(character)) {
return character
} else {
previouslyEncounteredCharacters.push(character)
}
}
return null
}
Both do the following:
They use a built-in data structure to keep track of characters that they have previous encountered as they go through the given string character by character. In the Python version, the data structure is a list named previously_encountered_characters; in the JavaScript version, it’s an array named previouslyEncounteredCharacters.
The use a loop to go through the given string one character at a time.
For each character in the given string, the program checks to see if the current character has been encountered before:
If the current character has been encountered before, it’s the first repeated character. The function returns the current character.
If the current character has not been encountered before, it is added to the data structure of previously encountered characters.
If the function goes through the entire string without encountering a previously encountered character, it returns a null value (None in Python, null in JavaScript).
What’s the Big O?
If you’ve made it this far, you might be asked how you can improve the code. This is a different question in disguise: You’re actually being asked if you know the computational complexity or “The Big O” for your solution.
First, there’s the for loop. For a given string of length n, the worst-case scenario — either the string doesn’t have any recurring characters or the recurring character is at the very end — the loop will have to execute n times. That task’s complexity of O(n).
Next, let’s look inside the for loop. There’s a test to see if the current character is in the collection of previously encountered characters. In Python, this test is performed by the in operator; in JavaScript, it’s performed by the includes() method.
Python’s TimeComplexity page says that using the in operator to find an item in a list is an O(n) operation on average.
That’s because they both use the following algorithm to determine if a given item is in a list or array:
if we are not yet past the last item in the list/array:
get the next item in the list/array
if this item is the one we’re looking for:
return true
if we are at this point and we have not found the item:
return false
So the function is basically an O(n) operation performing an O(n) operation on average, effectively making it an O(n2) operation. As far as computational complexity goes, this is considered “horrible”:
Tap to view at full size.
Can you improve the code?
You’ve probably figured out that the way to improve the code is to try and reduce its time complexity.
You probably can’t reduce the time complexity of the for loop. The function has to find the first recurring character, which means that it needs to go through the characters in the given string in order, one at a time. This part of the function will be stuck at O(n).
But you might be able to reduce the time complexity of check to see if the current character in the loop has been encountered before. In the function’s current form, we’re using a Python list or JavaScript array to keep track of characters that we’ve encountered before. Looking up an item in in these structures is an O(n) operation on average.
The solution is to change the data structure that keeps track of previously encountered characters to one where looking for a specific item is faster than O(n). Luckily, both Python and JavaScript provide a data structure for sets, where the time to look up an item is generally O(1).
Let’s rewrite the function to use sets. Here’s the Python version:
def first_recurring_character(text):
previously_encountered_characters = set()
for character in text:
if character in previously_encountered_characters:
return character
else:
previously_encountered_characters.add(character)
return None
The Python version doesn’t require much changing. We simply changed the initial definition of previously_encountered_characters from an empty array literal ([]) to a set constructor and call on set’s add() method instead of the append() method for arrays.
Here’s the JavaScript version:
function firstRecurringCharacter(text) {
let previouslyEncounteredCharacters = new Set()
for (const character of text) {
if (previouslyEncounteredCharacters.has(character)) {
return character
} else {
previouslyEncounteredCharacters.add(character)
}
}
return null
}
The JavaScript version requires only a little more changing:
The initial definition for previouslyEncounteredCharacters was changed to a Set constructor.
We changed the array includes() method to the set has() function.
We also changed the array push() method to the set add() method.
Changing the data structure that stores the characters that we’ve encountered before reduces the complexity to O(n), which is much better.
Coming up next
In the next article in this series, we’ll tackle a slightly different problem: Can you write a function that returns the first non-recurring character in a string?
If you run applications or scripts that use Selenium to control instances of Chrome via ChromeDriver, you may find that they no longer work, and instead provide you with error messages that look like this:
While this bug exists, the best workaround — and one that I’m using at the moment — is to do the following:
Uninstall version 103 of Chrome.
Install version 102 of Chrome.
Install version 102 of ChromeDriver.
Disable Chrome’s auto-update and don’t update Chrome.
How I encountered the bug
This happened to me on Wednesday. Earlier that day, I saw the “Update” button on Chrome change from green to yellow…
…and my conditioned-by-security-training response was to click it, updating Chrome to version 103.
Later that evening, I started assembling the weekly list of tech, entrepreneur, and nerd events for the Tampa Bay area. You know, this one:
When I started putting this list together back in early 2017, I did so manually by doing a lot of copying and pasting from Meetup and EventBrite pages. However, as the tech scene in Tampa grew, what used to be an hour’s work on a Saturday afternoon starting growing to consume more and more of that afternoon. I’d watch entire feature-length films in the background while I put them together. It became clear to me that it was time to add some automation to the process.
These days, I put together the list with the help of “The Transmogrifier,” my name for a collection of Python scripts inside a Jupyter Notebook. Given a set of URLs for Meetup and Eventbrite pages, it scrapes their pages for the following information:
The name of the group organizing the event
The name of the event
The time of the event
In the beginning, scraping Meetup was simply a matter of having Python make a GET request to a Meetup page, and then use BeautifulSoup to scrape its contents. But Meetup is a jealous and angry site, and they really, really, really hate scraping. So they employ all manner of countermeasures, and I have accepted the fact that as long as I put together the Tampa Bay Tech Events list, I will continually be playing a “move / counter-move” game with them.
One of Meetup’s more recent tricks was to serve an intermediate page that would not be complete until some JavaScript within that page executed within the browser upon loading. This means that the web page isn’t complete until you load the page into a browser, and only a browser. GETting the page programmatically won’t execute the page’s JavaScript.
Luckily, I’d heard of this trick before, and decided that I could use Selenium and ChromeDriver so that the Transmogrifier would take control of a Chrome instance, use it to download Meetup pages — which would then execute their JavaScript to create the final page. Once that was done, the Transmogrifier could then read the HTML of that final page via the browser under its control, which it could scrape.
Creating an instance of Chrome that would be under the Transmogrifier’s control is easy:
# Python
from selenium import webdriver
from selenium.webdriver.chrome.service import Service
from webdriver_manager.chrome import ChromeDriverManager
driver = webdriver.Chrome(service=Service(ChromeDriverManager().install()))
The single line of code after all the import statements does the following:
It launches an instance of Chrome that can be programmatically controlled.
It has ChromeDriver check to see if it is compatible with the Chrome instance. If not, it installs the compatible version of ChromeDriver.
This is where my problem began. ChromeDrive saw that I’d updated to Chrome 103, so it updated itself to version 103.
About one time out of three, this code would do what it was supposed to: print a message to the console, and then make Chrome load the page at the given URL.
But two out of three times, it would end up with this error:
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 the stacktrace goes on from here...)
This happens when executing several driver.get(url) calls in a row, which is what the Transmogrifier does. It’s executing driver.get(url) for many URLs in rapid succession. When this happens, there are many times when Chrome is processing a new ChromeDriver command request after a previous ChromeDriver session (a previous web page fetch) has already concluded and detached. In this case, Chrome responds with a “session not found” error. ChromeDriver gets this error while waiting for another valid command to complete, causing that command to fail. (You can find out more here.)
In the end, my solution was to downgrade to Chrome 102, use ChromeDriver 102, and keep an eye open for Chrome/ChromeDriver updates.
You should be a regular listener/viewer of the Arguing Agile podcast, a YouTube show hosted by Tampa Bay techies Brian Orlando and Om Patel that features local techies talking about software development, agility, and everything in between, completely unscripted and unrehearsed — just real conversations about real tech work. In the past year, they’ve published 66 episodes, the latest of which features…me!
In this episode, titled Personal Agility and the Great Resignation, we talk about doing work in the brave new world of post-2020 and discuss things such as:
The power of team-building ceremonies and exercises, and why they have to be meaningful and not just “doing team stuff for team stuff’s sake.”
In the past couple of months, I’ve had my first chances to meet with my team at Auth0 (Developer Marketing) after working with them for a year and a half — first at a small summit in Salt Lake City, and last week in London.
Earlier in your life, it’s much easier to work ultra-hard in the quest to advance your career, but you can’t do it for an extended period. This is the exact thing that generates mid-life crises, and physical and mental health issues.
We talk about my time at Microsoft where I was a Windows Phone Champion, Albert Shum’s design for its “Metro” UI, and Microsoft’s thinking during the Ballmer era: “The mobile platform is the desktop platform, but lamer.”
I was at a gathering of P2P people at Microsoft in 2001 that was attended by Tim O’Reilly and Dave Winer, where we were told that “IE6 will be the last browser, because the future is applets.”
A story from my time at Cory Doctorow’s startup where how I show how hard it is to predict the future.
The importance of communication when working remotely and keeping Conway’s Law in mind.
Strip away the technology, and a teacher from hundreds of years ago would still recognize a present-day classroom and the lecture format.
We share stories about learning by doing, with Om talking about his daughter at med school and me talking about a story about the Logo programming language, where children learned beyond what they were being taught.
Our first computers: I had an Apple //e and Om had a Spectrum ZX, two serious Generation X machines.
I learned how to program at a computer store that tolerated my hanging out: Batteries Included, in Toronto.
Learning new languages: Python and Lingo, and picking up new languages to get the job done. This may be the first time on the podcast series where the languages Lisp and Prolog get mentioned.
A question that Brian asks during interviews: “Tell me about a time in the last 18 months where you did something to update your skills.”
Software isn’t a what, it’s a how. If you make software for an industry or field, you’re not in the software industry, but the industry or field that you’re making the software for.
About not participating in what Scott Galloway calls “the menace economy”: “I want to earn fair profit for my effort, but I don’t want to do it by stepping on somebody’s neck.”
There’s so much traditional culture force behind the way work is done. Ebenezer Scrooge’s accounting office in A Christmas Carol isn’t all that different from its modern-day counterpart.
Om: “I like to see a sitcom called The Home Office.”
Do you write apps in React Native? Do you want to add authentication — that is, login and logout — to those apps? If so, these articles are for you!
If you’re writing an Android app in React Native and you need users to log in and log out, don’t roll your own authentication! Use Auth0 instead. You’ll get full-featured authentication and have more time to concentrate on your app’s full functionality.
There’s also an iOS-specific version of this article: Get Started with Auth0 Authentication in React Native iOS Apps. Just like the Android version, this article walks you through the process of making an iOS app that lets users log in with an app-specific username/password combination or a Google account.
Five years ago today, I submitted the first of two programming assignments as part of a job interview with a company that makes applications for the trucking industry.
May 2017
My interview at the company’s head office is going well. I’m giving them my Q&A A-game, the back-and-forth is flowing smoothly, and my knowledge of the trucking industry and lore — a combination of having done some research as well as repeated listenings to the Mark Dalton, Trucker/Detective audiobook series — seems to be paying off.
Ninety minutes into the one-hour interview, the CTO puts the brakes on the conversation and proposes a next step.
“We like your breadth of experience,” he says. “Now we’d like to test your depth. If we gave you a quick programming assignment, which would you prefer — writing an iOS app, or an Android app? You should go with the one you’re stronger in.”
I’m a much stronger iOS programmer than an Android one. The smart move would be to answer “iOS,” and be done with it.
But in that moment, I remember the motto: Be like Han.
Tap to view the “Be like Han” philosophy at full size.
Instead, I reply “Yes, but you’re looking for someone to lead a team of both iOS and Android developers. You really should give me both.”
The CTO raises an eyebrow, makes a note on his pad, and says “Hmmm…I think I will.”
This is either a “total baller move” (to borrow a turn of phrase the kids are using these day), or the end of that job prospect. But for the job that they’re trying to fill, taking on that challenge was the right thing to do.
I leave the interview with just one thought: Good thing I don’t have a job. This is going to be a lot of work.
The app
I decided to tackle the iOS version first. The tricky part was that the assignment required that the app be written in the old iOS programming language, Objective-C. In 2017, Swift had been around for 3 years, so it was still reasonable to expect to do some Objective-C development.
Actual code from the project.
I made the leap to Swift as soon as it came out, so it had been 3 years since I’d done any Objective-C coding. It took me a couple of hours to regain my “C legs,” but after a few days’ work, I managed to come up with this app:
Now I’m in the position where I am handing out programming assignments to prospective employees. I keep my 2017 experience in mind, which means:
I try to be respectful of their time. The assignment should be detailed enough to provide a realistic picture of the the candidate’s abilities but not so complex that they have to drop everything — including home/family responsibilities and their current job — to be able to complete it.
I try to be open to communication and responsive. I never want them to have that “ghosted” feeling I got five years ago.
