Home
/
Blog
/
Developer Insights
/
How do giant sites like Facebook and Google check Username or Domain availability so fast?

How do giant sites like Facebook and Google check Username or Domain availability so fast?

Author
Arpit Mishra
Calendar Icon
March 9, 2017
Timer Icon
4 min read
Share

Every time you try to create a new account on any of the websites, you begin with your name and, more often than not, you get the response “Username is already taken.”

Then, you add “your name + date of birth”, to realize it also has been “already taken” to finally end up with “your name + date of birth + license plate + graduation” to create the account.

I’m sure a lot of you are nodding and saying “been there, done that.”

Username, Usename taken, Username unavailable, how companies find username,

But how many of you have wondered how these giant sites like Facebook, Instagram, and Gmail verify whether the username is taken or not?

Let’s start with the two possible approaches

A linear search may not be a good idea

Let’s assume that Facebook stores all the data in its directory.

And the software simply checks each name on the list one at a time and if it doesn’t find a match, it tells you your desired username is available.

Doesn’t sound sensible, does it?

The software has to look at each name every time a username needs to be verified.

The technique is unreasonable when you compare it with the Facebook database, which has over 1.5 billion users, and Twitter, which has 300 million users.

What if they use a Binary search?

This makes more sense, with all the brains working at Facebook.

Facebook keeps all the data sorted and arranged in an alphabetized list.

The list is 1.5 billion characters long, stored like a, aa,aaa……xyy, XYZ, yaa,yaa,yxz, zaa, zac and is very similar to your dictionary.

When you enter a name, it matches the entry with the username exactly in the middle of the list. If it matches, the software rejects the new username.

If it doesn’t match (which has a lot of possibilities), the next question the software addresses are “ If searched alphabetically, does the requested username come before or after this username in the middle?”

If it comes before, then the software knows that all the 750 million people after the username found in the middle of the list is of no use for the current search.

That eliminates 750 million possibilities in a single comparison.

If the desired username comes after the name in the middle (alphabetically), it eliminates all the names before it.

Either way, the software eliminates almost 750 million names for search in the first comparison.

Next, it takes the selected half of the list and immediately matches the requested username with the name in the middle of the remaining list.

If it matches, the requested name is rejected and if it doesn’t, the requested name is again checked for the possibility of it occurring before or after the name in the middle.

If it is before, reject the 350 million names after the name.

And go ahead with divide and conquer for the rest of the names as done earlier.

If the requested name is after the middle string, reject the names before it and try with the 350 million remaining names.

By dividing the list every time, you can compare the required username with the names in the list quite quickly…

But the question is…how quickly?

You will continue dividing the list into two until you can no longer do so.

And when you are left with one name in the database, you match it with your desired username.

This would be the last step before you find whether the username “chosen” is available or not.

For data as big as 1.5 billion, this method would need no more than 30 steps. 2 to the power of 31 gives you 2.14 billion, which is closest to our expectation of 1.5 billion users on Facebook.

This means fewer steps and complications for the same data when searched with a linear search.

What if the developers are very smart and use a Bloom filter as the solution?

Before you understand Bloom filters, you need to understand the concept of Hashing.

Hashing is like the license plate of your car.

A hash function takes data of any length as input and gives you a smaller identifier of a smaller, fixed length, which is often used to identify or compare data.

Bloom filters work simply – Test and Add.

Test whether the element is present in the list:

  • If it returns false, the element is definitely not on the list.
  • If it returns true, the element might probably be on the list. This false positive (will discuss it below) is a function of the Bloom filter and depends on the size and is independent of the hash function used.

A Bloom filter divides the memory area into buckets, which are filled with various hashes generated from one or many hash functions.

Let’s understand with an example.

Suppose, you have a memory bucket of size 10 and 3 hash functions which will give you three unique identifiers.

Suppose, you enter Ronaldo into this memory bucket.

Ronaldo, when passed through these hash functions, gives the value of 1,4, and 5. The filter quickly fills the memory in the bucket with these identifiers.

1 4 5

Now, you enter Messi into the memory bucket. Messi, when passed through the hash function, gives its own unique identifier. In this case, it is 3,7, and 8 and the filter fills the bucket.

1 3 4 5 7 8

As the functions always return the same value for similar inputs, we can be sure that when the name Ronaldo is given to the filter, it would check in locations 1,4, and 5 to find it full, which means that the name Ronaldo is already on the list.

Let’s continue with another example of entering Rooney into the memory.

Rooney, when passed through the hash function, returns 2,6, and 8. The filters check the memory to find that though 8 is full 2 and 6 are empty, which means you don’t have Rooney in the memory.

Therefore, the name is available.

But when the name Neymar is passed through the hash functions, it returns the value of 1,3 and 7 which eventually makes the filter believe that the name Neymar is already present on the list.

This scenario explains the concept of false positives used in Bloom filters. One can control the false positive by controlling the size of the Bloom filter.

More space is inversely proportional to false positives.

Each of the above-mentioned techniques comes with its own advantages and disadvantages.

With technology and computers getting smarter and faster every day, even the brute-force method seems feasible.

But with space and time complexity, many companies, such as Reddit, prefer Binary search, whereas some others, such as Medium, use Bloom filters smartly to suggest articles for you without repeating them again on your timeline.

Register now before your username is taken on the HackerEarth platform.

Subscribe to The HackerEarth Blog

Get expert tips, hacks, and how-tos from the world of tech recruiting to stay on top of your hiring!

Author
Arpit Mishra
Calendar Icon
March 9, 2017
Timer Icon
4 min read
Share

Hire top tech talent with our recruitment platform

Access Free Demo
Related reads

Discover more articles

Gain insights to optimize your developer recruitment process.

Vibe Coding: Shaping the Future of Software

A New Era of CodeVibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today,...

A New Era of Code

Vibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today, when code is produced quickly through AI, the true value lies in designing, refining, and optimizing systems. Our role now goes beyond writing code; we must also ensure that our systems remain efficient and reliable.

From Machine Language to Natural Language

I recall the early days when every line of code was written manually. We progressed from machine language to high-level programming, and now we are beginning to interact with our tools using natural language. This development does not only increase speed but also changes how we approach problem solving. Product managers can now create working demos in hours instead of weeks, and founders have a clearer way of pitching their ideas with functional prototypes. It is important for us to rethink our role as developers and focus on architecture and system design rather than simply on typing code.

The Promise and the Pitfalls

I have experienced both sides of vibe coding. In cases where the goal was to build a quick prototype or a simple internal tool, AI-generated code provided impressive results. Teams have been able to test new ideas and validate concepts much faster. However, when it comes to more complex systems that require careful planning and attention to detail, the output from AI can be problematic. I have seen situations where AI produces large volumes of code that become difficult to manage without significant human intervention.

AI-powered coding tools like GitHub Copilot and AWS’s Q Developer have demonstrated significant productivity gains. For instance, at the National Australia Bank, it’s reported that half of the production code is generated by Q Developer, allowing developers to focus on higher-level problem-solving . Similarly, platforms like Lovable enable non-coders to build viable tech businesses using natural language prompts, contributing to a shift where AI-generated code reduces the need for large engineering teams. However, there are challenges. AI-generated code can sometimes be verbose or lack the architectural discipline required for complex systems. While AI can rapidly produce prototypes or simple utilities, building large-scale systems still necessitates experienced engineers to refine and optimize the code.​

The Economic Impact

The democratization of code generation is altering the economic landscape of software development. As AI tools become more prevalent, the value of average coding skills may diminish, potentially affecting salaries for entry-level positions. Conversely, developers who excel in system design, architecture, and optimization are likely to see increased demand and compensation.​
Seizing the Opportunity

Vibe coding is most beneficial in areas such as rapid prototyping and building simple applications or internal tools. It frees up valuable time that we can then invest in higher-level tasks such as system architecture, security, and user experience. When used in the right context, AI becomes a helpful partner that accelerates the development process without replacing the need for skilled engineers.

This is revolutionizing our craft, much like the shift from machine language to assembly to high-level languages did in the past. AI can churn out code at lightning speed, but remember, “Any fool can write code that a computer can understand. Good programmers write code that humans can understand.” Use AI for rapid prototyping, but it’s your expertise that transforms raw output into robust, scalable software. By honing our skills in design and architecture, we ensure our work remains impactful and enduring. Let’s continue to learn, adapt, and build software that stands the test of time.​

Ready to streamline your recruitment process? Get a free demo to explore cutting-edge solutions and resources for your hiring needs.

Guide to Conducting Successful System Design Interviews in 2025

What is Systems Design?Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.Systems Design, in its...

What is Systems Design?

Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.

Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.

Systems Design, in its essence, is a blueprint of how software and applications should work to meet specific goals. The multi-dimensional nature of this discipline makes it open-ended – as there is no single one-size-fits-all solution to a system design problem.

What is a System Design Interview?

Conducting a System Design interview requires recruiters to take an unconventional approach and look beyond right or wrong answers. Recruiters should aim for evaluating a candidate’s ‘systemic thinking’ skills across three key aspects:

How they navigate technical complexity and navigate uncertainty
How they meet expectations of scale, security and speed
How they focus on the bigger picture without losing sight of details

This assessment of the end-to-end thought process and a holistic approach to problem-solving is what the interview should focus on.

What are some common topics for a System Design Interview

System design interview questions are free-form and exploratory in nature where there is no right or best answer to a specific problem statement. Here are some common questions:

How would you approach the design of a social media app or video app?

What are some ways to design a search engine or a ticketing system?

How would you design an API for a payment gateway?

What are some trade-offs and constraints you will consider while designing systems?

What is your rationale for taking a particular approach to problem solving?

Usually, interviewers base the questions depending on the organization, its goals, key competitors and a candidate’s experience level.

For senior roles, the questions tend to focus on assessing the computational thinking, decision making and reasoning ability of a candidate. For entry level job interviews, the questions are designed to test the hard skills required for building a system architecture.

The Difference between a System Design Interview and a Coding Interview

If a coding interview is like a map that takes you from point A to Z – a systems design interview is like a compass which gives you a sense of the right direction.

Here are three key difference between the two:

Coding challenges follow a linear interviewing experience i.e. candidates are given a problem and interaction with recruiters is limited. System design interviews are more lateral and conversational, requiring active participation from interviewers.

Coding interviews or challenges focus on evaluating the technical acumen of a candidate whereas systems design interviews are oriented to assess problem solving and interpersonal skills.

Coding interviews are based on a right/wrong approach with ideal answers to problem statements while a systems design interview focuses on assessing the thought process and the ability to reason from first principles.

How to Conduct an Effective System Design Interview

One common mistake recruiters make is that they approach a system design interview with the expectations and preparation of a typical coding interview.
Here is a four step framework technical recruiters can follow to ensure a seamless and productive interview experience:

Step 1: Understand the subject at hand

  • Develop an understanding of basics of system design and architecture
  • Familiarize yourself with commonly asked systems design interview questions
  • Read about system design case studies for popular applications
  • Structure the questions and problems by increasing magnitude of difficulty

Step 2: Prepare for the interview

  • Plan the extent of the topics and scope of discussion in advance
  • Clearly define the evaluation criteria and communicate expectations
  • Quantify constraints, inputs, boundaries and assumptions
  • Establish the broader context and a detailed scope of the exercise

Step 3: Stay actively involved

  • Ask follow-up questions to challenge a solution
  • Probe candidates to gauge real-time logical reasoning skills
  • Make it a conversation and take notes of important pointers and outcomes
  • Guide candidates with hints and suggestions to steer them in the right direction

Step 4: Be a collaborator

  • Encourage candidates to explore and consider alternative solutions
  • Work with the candidate to drill the problem into smaller tasks
  • Provide context and supporting details to help candidates stay on track
  • Ask follow-up questions to learn about the candidate’s experience

Technical recruiters and hiring managers should aim for providing an environment of positive reinforcement, actionable feedback and encouragement to candidates.

Evaluation Rubric for Candidates

Facilitate Successful System Design Interview Experiences with FaceCode

FaceCode, HackerEarth’s intuitive and secure platform, empowers recruiters to conduct system design interviews in a live coding environment with HD video chat.

FaceCode comes with an interactive diagram board which makes it easier for interviewers to assess the design thinking skills and conduct communication assessments using a built-in library of diagram based questions.

With FaceCode, you can combine your feedback points with AI-powered insights to generate accurate, data-driven assessment reports in a breeze. Plus, you can access interview recordings and transcripts anytime to recall and trace back the interview experience.

Learn how FaceCode can help you conduct system design interviews and boost your hiring efficiency.

How Candidates Use Technology to Cheat in Online Technical Assessments

Impact of Online Assessments in Technical Hiring In a digitally-native hiring landscape, online assessments have proven to be both a boon and a bane for recruiters and employers. The ease and...

Impact of Online Assessments in Technical Hiring


In a digitally-native hiring landscape, online assessments have proven to be both a boon and a bane for recruiters and employers.

The ease and efficiency of virtual interviews, take home programming tests and remote coding challenges is transformative. Around 82% of companies use pre-employment assessments as reliable indicators of a candidate's skills and potential.

Online skill assessment tests have been proven to streamline technical hiring and enable recruiters to significantly reduce the time and cost to identify and hire top talent.

In the realm of online assessments, remote assessments have transformed the hiring landscape, boosting the speed and efficiency of screening and evaluating talent. On the flip side, candidates have learned how to use creative methods and AI tools to cheat in tests.

As it turns out, technology that makes hiring easier for recruiters and managers - is also their Achilles' heel.

Cheating in Online Assessments is a High Stakes Problem



With the proliferation of AI in recruitment, the conversation around cheating has come to the forefront, putting recruiters and hiring managers in a bit of a flux.



According to research, nearly 30 to 50 percent of candidates cheat in online assessments for entry level jobs. Even 10% of senior candidates have been reportedly caught cheating.

The problem becomes twofold - if finding the right talent can be a competitive advantage, the consequences of hiring the wrong one can be equally damaging and counter-productive.

As per Forbes, a wrong hire can cost a company around 30% of an employee's salary - not to mention, loss of precious productive hours and morale disruption.

The question that arises is - "Can organizations continue to leverage AI-driven tools for online assessments without compromising on the integrity of their hiring process? "

This article will discuss the common methods candidates use to outsmart online assessments. We will also dive deep into actionable steps that you can take to prevent cheating while delivering a positive candidate experience.

Common Cheating Tactics and How You Can Combat Them


  1. Using ChatGPT and other AI tools to write code

    Copy-pasting code using AI-based platforms and online code generators is one of common cheat codes in candidates' books. For tackling technical assessments, candidates conveniently use readily available tools like ChatGPT and GitHub. Using these tools, candidates can easily generate solutions to solve common programming challenges such as:
    • Debugging code
    • Optimizing existing code
    • Writing problem-specific code from scratch
    Ways to prevent it
    • Enable full-screen mode
    • Disable copy-and-paste functionality
    • Restrict tab switching outside of code editors
    • Use AI to detect code that has been copied and pasted
  2. Enlist external help to complete the assessment


    Candidates often seek out someone else to take the assessment on their behalf. In many cases, they also use screen sharing and remote collaboration tools for real-time assistance.

    In extreme cases, some candidates might have an off-camera individual present in the same environment for help.

    Ways to prevent it
    • Verify a candidate using video authentication
    • Restrict test access from specific IP addresses
    • Use online proctoring by taking snapshots of the candidate periodically
    • Use a 360 degree environment scan to ensure no unauthorized individual is present
  3. Using multiple devices at the same time


    Candidates attempting to cheat often rely on secondary devices such as a computer, tablet, notebook or a mobile phone hidden from the line of sight of their webcam.

    By using multiple devices, candidates can look up information, search for solutions or simply augment their answers.

    Ways to prevent it
    • Track mouse exit count to detect irregularities
    • Detect when a new device or peripheral is connected
    • Use network monitoring and scanning to detect any smart devices in proximity
    • Conduct a virtual whiteboard interview to monitor movements and gestures
  4. Using remote desktop software and virtual machines


    Tech-savvy candidates go to great lengths to cheat. Using virtual machines, candidates can search for answers using a secondary OS while their primary OS is being monitored.

    Remote desktop software is another cheating technique which lets candidates give access to a third-person, allowing them to control their device.

    With remote desktops, candidates can screen share the test window and use external help.

    Ways to prevent it
    • Restrict access to virtual machines
    • AI-based proctoring for identifying malicious keystrokes
    • Use smart browsers to block candidates from using VMs

Future-proof Your Online Assessments With HackerEarth

HackerEarth's AI-powered online proctoring solution is a tested and proven way to outsmart cheating and take preventive measures at the right stage. With HackerEarth's Smart Browser, recruiters can mitigate the threat of cheating and ensure their online assessments are accurate and trustworthy.
  • Secure, sealed-off testing environment
  • AI-enabled live test monitoring
  • Enterprise-grade, industry leading compliance
  • Built-in features to track, detect and flag cheating attempts
Boost your hiring efficiency and conduct reliable online assessments confidently with HackerEarth's revolutionary Smart Browser.
Top Products

Explore HackerEarth’s top products for Hiring & Innovation

Discover powerful tools designed to streamline hiring, assess talent efficiently, and run seamless hackathons. Explore HackerEarth’s top products that help businesses innovate and grow.
Frame
Hackathons
Engage global developers through innovation
Arrow
Frame 2
Assessments
AI-driven advanced coding assessments
Arrow
Frame 3
FaceCode
Real-time code editor for effective coding interviews
Arrow
Frame 4
L & D
Tailored learning paths for continuous assessments
Arrow
Get A Free Demo