Category: Programming
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 namedfirstRecurringCharacter()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’sNone, or Swift’snil.
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
Setrequires you to specify the type of things that it will store. In this case, we want to store items of typeCharacter. - When looping through the items in a string with a
forloop in Swift, you getCharacteritems. That’s whypreviouslyEncounteredCharactersstoresCharacteritems and notStringitems. Once the function detects the first recurring character, it converts that character into a string and returns that value.
Previously in this series
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:
- These lines create an instance of the
Optionsclass, which we’re using to specify the directory where the Chrome beta app can be found. We’ll use the instance,options, when we createdriver, the object that controls the Chrome beta app. - This constructor creates a
WebDriver.Chromeobject which will control the Chrome beta app. Theserviceparameter 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. Theoptionsparameter specifies that ChromeDriver should drive the version of Chrome located at the directory path specified in theoptionobject: 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!
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’sNone, or Swift’snil.
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 NoneHere’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 namedpreviouslyEncounteredCharacters. - 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 (
Nonein Python,nullin 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.
- The spec for JavaScript’s
includes()method shows that it searches through an array one element at a time, which makes it 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 falseSo 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”:
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 NoneThe 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
previouslyEncounteredCharacterswas changed to aSetconstructor. - We changed the array
includes()method to the sethas()function. - We also changed the array
push()method to the setadd()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?
Update: You’ll also want to see this follow-up article — Fix the ChromeDriver 103 bug with ChromeDriver 104.
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:
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
3 chromedriver 0x000000010f7833c8 chromedriver + 332744
4 chromedriver 0x000000010f782ac7 chromedriver + 330439
5 chromedriver 0x000000010f782047 chromedriver + 327751
6 chromedriver 0x000000010f780f16 chromedriver + 323350
7 chromedriver 0x000000010f78144c chromedriver + 324684
8 chromedriver 0x000000010f78e3bf chromedriver + 377791
9 chromedriver 0x000000010f78ef22 chromedriver + 380706
10 chromedriver 0x000000010f79d5b3 chromedriver + 439731
11 chromedriver 0x000000010f7a147a chromedriver + 455802
12 chromedriver 0x000000010f78177e chromedriver + 325502
13 chromedriver 0x000000010f79d1fa chromedriver + 438778
14 chromedriver 0x000000010f7fc62d chromedriver + 828973
15 chromedriver 0x000000010f7e9683 chromedriver + 751235
16 chromedriver 0x000000010f7bfa45 chromedriver + 580165
17 chromedriver 0x000000010f7c0a95 chromedriver + 584341
18 chromedriver 0x000000010fb4055d chromedriver + 4253021
19 chromedriver 0x000000010fb453a1 chromedriver + 4273057
20 chromedriver 0x000000010fb4a16f chromedriver + 4292975
21 chromedriver 0x000000010fb45dea chromedriver + 4275690
22 chromedriver 0x000000010fb1f54f chromedriver + 4117839
23 chromedriver 0x000000010fb5fed8 chromedriver + 4382424
24 chromedriver 0x000000010fb6005f chromedriver + 4382815
25 chromedriver 0x000000010fb768d5 chromedriver + 4475093
26 libsystem_pthread.dylib 0x00007ff81931a4e1 _pthread_start + 125
27 libsystem_pthread.dylib 0x00007ff819315f6b thread_start + 15It turns out that there’s a bug in version 103 of ChromeDriver, which works specifically with version 103 of Chrome. This bug causes commands to ChromeDriver, such as its get() method, which points the browser to a specific URL, to sometimes fail.
The quick solution
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.
Here’s the code where the bug became apparent:
print(f"Processing Meetup URL: {url}")
driver.get(url)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:
- 0:00 Intro
- 0:24 Topic Intro
- 0:59 Reasons for In-Person Gathering
- Working remotely still requires some in-person gathering, because as they saying goes, sometimes, “you have to be there.”
- 4:19 Team Bonding, Positive Vibes
- 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.
- 8:40 Work, Life, & Sustainability
- 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.
- Brian: “Jack Welch said a lot of stuff.”
- 15:50 Interviews: Vetting Companies
- During a job interview, you shouldn’t be the only one being interviewed. You should also be interviewing them!
- How can you tell if a manager is a “Rick” looking for another “Morty” to add to his “Morty Army?”
- I talk about a Chris Voss technique where you look at the reactions on the face of the person who isn’t speaking to get the truth.
- 19:55 Segue on Microsoft
- 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.
- 25:51 Learning
- A story from how I landed my job at Auth0, where I had to learn about an unfamiliar platform very quickly.
- 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.
- 31:12 Time to Think
- Protecting “quiet time” and “building introspective into a retrospective.”
- A quick mention of StartupBus, where I’ll be a conductor this year.
- 37:34 Evolution of Technology & Skills
- 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.”
- 44:55 Solving Problems
- 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.
- 47:51 Personal Agility
- Between the pandemic and the current economic situation, you need to develop personal agility to survive and thrive in the current job market.
- A number of people who participated in the Great Resignation left their jobs without having another job to jump to.
- 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.”
- 53:24 Monkeys, a Banana, and a Ladder
- When talking about organizational culture, you’ll eventually come across the “Five Monkeys Experiment,” which we discuss.
- How office architecture mirrors office organization, culture, and hierarchy — and how remote work systems’ architecture will do the same.
- The new generation of workers will probably have to be more adaptable than any previous generation.
- 1:02:18 Returning to the Office
- The majority of a developer’s day requires focus time, and that isn’t often achievable at the office.
- The true hurdle may not be technology or office space, but organization discipline.
- It’s quite possible to kill time unproductively at the office — we’ve all seen this.
- “If you signed a ten-year [office space] lease in 2018, you’re probably really anxious to get people back in there.”
- “Butts in office chairs” is the new “lines of code” metric.
- 1:08:43 The Future
- 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.”
- 1:13:00 Wrap-Up
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.
The article Get Started with Auth0 Authentication in React Native Android Apps gives you a tutorial where you make an Android app that lets users log in with an app-specific username/password combination or a Google account.
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.
Both articles appear in the Auth0 Developer Blog and were written by guest author Wern Ancheta, with technical editing and additional content by Yours Truly!