System requirements

Functional:

Shorten URL:the system should allow userst to submit

a long URL and receive a shortened URL

Redirect: user should be able to access the original URL by visiting the shortened URL.If it points non-existing URL,the system should return HTTP 404.
Analytics: the system should provide users with statistics on the usage of their shortened URLs: total visits, and visits per day.
Validate URL: check if the given URL is to access the live HTTP page otherwise, the system should return the error.
Expiration : allow for URLs to have an expiration date,if url is expired the backend should remove it and notify the user about it.
User management:user can create account, log in, and manage their shortened URLs.

Additional requirements:

API Access: there should be an API that allows third-party applications to generate and retrieve shortened URLs.
Link preview: When a user hovers over or clicks on the shortened URL, the system may provide a preview of the long URL.
Bulk Shortening: the user can send a batch of URLs to shorten.If one
Custom aliases: user can create a shortened URL with a custom alias instead of a randomly generated one.

Here are several common approaches used to create shortened URLs:

1. Random String Generation

In this approach, a random string of characters is generated whenever a user submits a long URL. This string serves as the unique identifier (or short code) for the original URL. The string can consist of alphanumeric characters (both letters and numbers) and can vary in length.

Implementation Steps

Character Set Definition: Define the character set from which the random strings will be generated. A common choice is to use:
- Lowercase letters: abcdefghijklmnopqrstuvwxyz
- Uppercase letters: ABCDEFGHIJKLMNOPQRSTUVWXYZ
- Numbers: 0123456789
- Optionally, you could include special characters to create an even larger set.
For example, a character set may look like this: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.
Short Code Length: Decide on the length of the short code. Common lengths range from 5 to 8 characters:
- Example: A length of 6 characters can generate (62^6 \approx 56.8) million unique combinations when using A-Z, a-z, and 0-9.
Random Generation:
- Create a function that randomly selects characters from the defined character set to create the short code.
- Ensure that the selection is random to avoid predictable patterns.
Collision Detection:
- Before finalizing the short code, check the database to ensure that the generated code does not already exist (i.e., it’s unique).
- If a collision is detected, generate a new string until a unique one is found. This might require a loop to repeat the string generation and checking process.
Mapping:
- Store the mapped long URL and its corresponding short code in the database, allowing for redirection when the short URL is accessed.
Redirection:
- When a user accesses a shortened URL, retrieve the long URL using the short code and perform a redirect.

Pros and Cons

Pros:

Simplicity: The approach is easy to understand and implement, making it a popular choice for many services.
Efficiency: Random string generation can quickly produce short codes with minimal computational overhead.

Cons:

Collision Risk: As the volume of URLs increases, the chance of generating duplicate short codes rises, necessitating a robust collision detection mechanism.
Lack of User Control: Users cannot customize their short codes, which might reduce memorability compared to custom aliases.

2. Base Encoding

Base encoding converts a numeric identifier (often an auto-incrementing integer that represents the original URL in the database) into a shorter string representation, which can be used as the short URL code. The most common bases used are Base62, Base64, and Base36, with Base62 being especially popular for its balance between brevity and readability.

How Base Encoding Works

Base Definition:
- Base62 includes characters from 0-9, a-z, and A-Z, allowing for 62 unique characters.
- Base64 includes A-Z, a-z, 0-9, +, and /, allowing for 64 unique characters. However, the + and / characters often complicate URL usage, so Base62 is more commonly employed.
Mapping Auto-Incrementing IDs:
- Each time a new URL is stored in the database, it is assigned a unique integer ID (auto-incremented).
- When generating a short code, this integer ID is converted into a Base62 string.
Conversion Algorithm:
- The conversion involves repeatedly dividing the integer by the base (62) and recording the remainder to produce the corresponding character from the Base62 character set.
- The process continues until the quotient is zero, and the characters can be reversed to obtain the final short code.

Example of Base62 Encoding

Let's break down how Base62 encoding would work with a simple example:

Mapping Character Set:

Base62 Char Set: 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Convert ID to Base62: For example, let's say the auto-incrementing ID for the URL is 12345. Here's how you would convert it to Base62:

1. 12345 ÷ 62 = 199 remainder 37 → 'b' 2. 199 ÷ 62 = 3 remainder 13 → 'd' 3. 3 ÷ 62 = 0 remainder 3 → '3' Result (reversed) = '3db'

The final short code for ID 12345 would be 3db.

Implementation Steps

Store URLs with Auto-Incrementing IDs: Each time a URL is shortened, it gets stored in the database with an auto-incrementing primary key.
Base62 Conversion Function:
- Implement the conversion function to translate the integer ID into a Base62 string for generating the short URL.
Redirection Logic:
- When a user accesses the shortened URL, decode the short code back into its corresponding integer ID and look it up in the database to retrieve the long URL.

Pros and Cons

Pros:

Uniqueness: Guarantees unique short codes based on the database ID.
Efficiency: Generates shorter URLs compared to random string generation, especially with larger databases.
Decodable: The system can easily reverse the encoding to retrieve the original ID.

Cons:

Predictability: As IDs are sequential, the generated short codes might be predictable, which could be an issue for some users desiring obscurity.
Scaling: If not properly managed, a large number of entries could lead to longer base-encoded strings, though this would typically be mitigated by the nature of Base62.

3. Custom Aliases

User Input:
- Provide a field in the user interface for entering a custom alias.
- Include validation to ensure that the alias follows specific rules (e.g., character limitations, length restrictions).
Uniqueness Check:
- When the user submits the custom alias along with the long URL, check the database to ensure that the alias is unique and not already in use by another URL.
- If the alias already exists, notify the user and possibly suggest alternative aliases.
Storage:
- If the alias is valid and unique, store the custom alias along with the original long URL in the database. If not provided, fallback to the random string generation or Base Encoding method to create a unique short code.
Mapping:
- Store the URL and its corresponding custom alias in the database just as you would with other short codes.
Redirection Logic:
- When a user accesses the shortened URL with the custom alias, retrieve the associated long URL from the database.

Example Workflow

Let's say a user wants to shorten the URL http://example.com/great-article with the custom alias greatarticle.

User submits:
- Long URL: http://example.com/great-article
- Custom Alias: greatarticle
Uniqueness Check:
- Database query checks if greatarticle exists.
- If it doesn’t, proceed to store.
Storage:
- Store a record that links greatarticle to http://example.com/great-article.

Code Example in Pseudocode

Here’s a simplified pseudocode implementation of the custom alias logic:

function shortenURL(longURL, customAlias): if customAlias is provided: if existsInDatabase(customAlias): return "Error: Alias already in use. Please choose another." else: storeInDatabase(longURL, customAlias) return customAlias else: randomShortCode = generateRandomShortCode() while existsInDatabase(randomShortCode): randomShortCode = generateRandomShortCode() storeInDatabase(longURL, randomShortCode) return randomShortCode

Pros and Cons

Pros:

Memorability: Users can create meaningful short URLs that are easier to remember and share.
Branding: Custom aliases help promote branding by allowing users to incorporate their brand names or descriptive keywords into the short URL.
User Engagement: Provides a more personalized experience, likely increasing user satisfaction and willingness to use the service.

Cons:

Uniqueness Management: Requires additional checks and management to ensure that custom aliases are unique, which can complicate the logic.
Potential for Misuse: If not regulated, users might create offensive or misleading aliases.
Input Validation: Requires strict validation rules around the format and characters allowed in aliases, which could frustrate some users.

4. Hashing Algorithms

Select a Hashing Algorithm:
- Choose an appropriate hashing algorithm. While SHA-256 is widely trusted for its security, it produces a long output. MD5, while shorter, is less secure and susceptible to collisions. Depending on the context and requirement for security, you can choose the right algorithm.
Generate the Hash:
- When a user submits a long URL, compute the hash of the URL. This creates a long string that uniquely represents the URL.
Truncate the Hash:
- Since the full hash value may be lengthy (e.g., 64 characters for SHA-256), truncate it to a feasible length (e.g., first 6 or 8 characters) to form the short code.
- Ensure the truncated part is still unique, and if needed, perform additional checks before finalizing the short code.
Collision Detection:
- Even though hashing algorithms are designed to minimize collisions, you should still check the database to ensure the short code has not already been used.
- If a collision occurs (i.e., another URL has resulted in the same short code), re-hash the original URL, or use a different approach to ensure uniqueness.
Store and Redirect:
- Store the long URL along with its corresponding hash-based short code in the database.
- When users access the shortened URL, take the hash, fetch the corresponding long URL, and perform a redirect.

Example Workflow

Let’s illustrate how this might work using MD5:

User submits:
- Long URL: http://example.com/some/very/long/url
Hashing the URL:
- Compute the MD5 hash: e99a18c428cb38d5f260853678922e03
Truncation for Short Code:
- Shortened code derived from the hash: e99a18 (first 6 characters).
Uniqueness Check:
- Check if e99a18 already exists in the database.
- If it exists, generate a new short code by appending some counter or salt to the original URL and re-hashing.
Storage:
- Store the mapping of e99a18 to the long URL in the database.

Pros and Cons

Pros:

Deterministic: Hashing provides a deterministic way to generate short codes from URLs, ensuring that the same input always produces the same output.
Simplicity: The implementation is straightforward; hashing libraries are available in most programming languages.
Fixed Size: The output size is constant, regardless of the input length, providing a consistent format for short codes.

Cons:

Collision Potential: Although hashing reduces the likelihood of collisions, they can still occur, especially with a large number of URLs. Proper handling is necessary.
Unwieldy Hashes: The output of certain algorithms may require truncation, which can lead to unique representation issues if not managed properly.
URL Obfuscation: Since hashes can be predictable based on the content, this approach may not entirely obfuscate the original URLs as desired by some users.

5. UUID (Universally Unique Identifier)

A UUID is a 128-bit number represented as a string in a standard format, typically represented as 32 hexadecimal characters, often displayed with dashes separating groups. For example, a UUID could look like this: 550e8400-e29b-41d4-a716-446655440000.

UUIDs can be generated in several versions, with UUIDv4 being one of the most commonly used, as it generates random UUIDs.

Implementation Steps

Generate a UUID:
- Use a library or built-in function to generate a UUID. Most programming languages have libraries for UUID generation (e.g., uuid in Python, java.util.UUID in Java, uuid in Node.js).
Format the UUID:
- You may choose to keep the complete UUID or truncate it to create a shorter URL. While UUIDs are unique, they can be lengthy (36 characters with dashes), which is typically longer than desired for a URL.
Store the Mapping:
- Store the long URL along with the generated UUID in your database, creating a mapping between the two.
Redirection Logic:
- When a user accesses the shortened URL, simply retrieve the long URL based on the UUID, and perform a redirect.

Example Workflow

Let's say a user wants to shorten the URL http://example.com/great-article:

User submits:
- Long URL: http://example.com/great-article.
Generate the UUID:
- Generate a UUID (e.g., d3b57329-7b6a-42eb-8a0b-b55aefb60f8b).
Mapping:
- Store the mapping of the UUID to the long URL in the database.
Create the Short URL:
- The resulting short URL could be something like http://short.ly/d3b57329.
Redirection:
- When a user accesses http://short.ly/d3b57329, the system retrieves the long URL from the database and performs a redirect.

Pros and Cons

Pros:

Guaranteed Uniqueness: UUIDs are designed to be globally unique, making them perfect for scenarios where uniqueness is critical.
No Collisions: With the random nature of UUIDs, the possibility of collisions is extremely low, even across different generating systems.
No Central Authority Required: UUIDs can be generated independently without requiring a central server to coordinate ID allocations.

Cons:

Long Length: UUIDs are longer than traditional short codes, which can create less friendly URLs for sharing and memorization (especially the standard format with hyphens).
Formatting Issues: The formatting of UUIDs may require additional effort in terms of URL handling, especially if they contain dashes or uppercase characters.
Predictability: Depending on the UUID generation method used, predictability may be a concern, though UUIDv4 provides good randomness.

Non-Functional:

Scalability:The system should be able to handle an increasing number of requests as the user base grows. This might involve horizontal scaling and load balancing strategies
Availability: The service should ensure high availability, aiming for an uptime of at least 99.9%.
Performance: The system should respond to requests in a timely manner, ideally in less than a second for URL shortening and redirection.
Security: Implement measures to prevent abuse, such as rate limiting and validation checks for URLs.
Maintainability: : The system should be designed in a way that makes it easy to update, debug, and manage.
Data Consistency: Ensure that the URL mappings are consistent across the database and cache.
Logging and Monitoring:the system should have logging capabilities to track usage patterns, errors, and other performance metrics.

User Experience: the user interface should be intuitive, and the service should provide an API with clear documentation for developers.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10