Q: Write a function in Python to find the longest substring without repeating characters in a given string.

To find the longest substring without repeating characters, you can use a sliding window approach with two pointers. Here's how you can implement this in Python: ```python def longest_unique_substring(s): char_map = {} left = 0 max_length = 0 start = 0 for right, char in enumerate(s): if char in char_map and char_map[char] >= left: left = char_map[char] + 1 char_map[char] = right if right - left + 1 > max_length: max_length = right - left + 1 start = left return s[start:start + max_length] # Example usage print(longest_unique_substring('abcabcbb')) # Output: 'abc' print(longest_unique_substring('bbbbb')) # Output: 'b' print(longest_unique_substring('pwwkew')) # Output: 'wke' ``` This function iterates over the string with the `right` pointer, while the `left` pointer marks the start of the current substring without duplicates. The dictionary `char_map` keeps track of the last occurrence of each character. When a duplicate character is found within the current window, the `left` pointer moves to the right of the last occurrence of that character to ensure all characters in the window are unique. The longest substring is updated accordingly.

Question 1

Demonstrate how to reverse a string in Java without using built-in methods.

Accepted Answer

To reverse a string in Java without using built-in methods like `StringBuilder.reverse()`, you can use a character array. Here's how:

```java
public class StringReversal {
    public static String reverseString(String input) {
        if (input == null || input.isEmpty()) {
            return input;
        }

char[] characters = input.toCharArray();
        int left = 0;
        int right = characters.length - 1;

while (left < right) {
            char temp = characters[left];
            characters[left] = characters[right];
            characters[right] = temp;
            left++;
            right--;
        }

return new String(characters);
    }

public static void main(String[] args) {
        System.out.println(reverseString("Meta")); // Output: ateM
    }
}
```

This code effectively reverses the string by swapping characters from the ends towards the center, ensuring O(n) time complexity.

Question 2

Write a function in Python to find the longest substring without repeating characters in a given string.

Accepted Answer

To find the longest substring without repeating characters, you can use a sliding window approach with two pointers. Here's how you can implement this in Python:

```python
def longest_unique_substring(s):
    char_map = {}
    left = 0
    max_length = 0
    start = 0

for right, char in enumerate(s):
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1
        char_map[char] = right
        if right - left + 1 > max_length:
            max_length = right - left + 1
            start = left

return s[start:start + max_length]

# Example usage
print(longest_unique_substring('abcabcbb'))  # Output: 'abc'
print(longest_unique_substring('bbbbb'))    # Output: 'b'
print(longest_unique_substring('pwwkew'))   # Output: 'wke'
```

This function iterates over the string with the `right` pointer, while the `left` pointer marks the start of the current substring without duplicates. The dictionary `char_map` keeps track of the last occurrence of each character. When a duplicate character is found within the current window, the `left` pointer moves to the right of the last occurrence of that character to ensure all characters in the window are unique. The longest substring is updated accordingly.

Question 3

What are SQL subqueries and nested queries, and how can you use them to retrieve records in a database table with specific conditions? Provide an example.

Accepted Answer

SQL subqueries are queries nested inside another query. They can be used to perform operations that require multiple steps, such as filtering data based on aggregated results. A common use case is finding employees with a salary above the average salary in their department.

```sql
SELECT employee_id, employee_name
FROM employees
WHERE salary > (
    SELECT AVG(salary)
    FROM employees
    WHERE department_id = employees.department_id
);
```
In this query, the subquery calculates the average salary for each department, and the outer query retrieves employees whose salary is above their department's average.

Question 4

Discuss a backend developer interview question from Meta involving database design.

Accepted Answer

A common question might involve designing a database schema for a social networking application. Candidates should focus on identifying entities, such as users, posts, and comments. Considerations for relationships (e.g., one-to-many between users and posts) and normalization are important. Here's a simple schema example using SQL:

```sql
CREATE TABLE Users (
  user_id SERIAL PRIMARY KEY,
  name VARCHAR(100),
  email VARCHAR(100) UNIQUE
);

CREATE TABLE Posts (
  post_id SERIAL PRIMARY KEY,
  user_id INTEGER REFERENCES Users(user_id),
  content TEXT,
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE Comments (
  comment_id SERIAL PRIMARY KEY,
  post_id INTEGER REFERENCES Posts(post_id),
  user_id INTEGER REFERENCES Users(user_id),
  content TEXT,
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
```
This schema ensures referential integrity and supports efficient querying for user activity on the platform.

Question 5

Explain how you would implement a recursive algorithm to generate the Fibonacci sequence. Include an analysis of its time complexity.

Accepted Answer

To implement a recursive algorithm for generating the Fibonacci sequence, you define a function that calls itself with the previous two Fibonacci numbers until it reaches the base case. Here's a basic implementation in Python:

```python
# Recursive Fibonacci Implementation
def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Test cases
print(fibonacci(5))  # Output: 5
print(fibonacci(10)) # Output: 55
```

This implementation has a time complexity of O(2^n) because it recalculates Fibonacci numbers multiple times. To optimize, memoization or iterative methods should be considered.

SarthiQ

Interview Preparation Guide

Meta
Questions & Answers

Document Details

Need Help?

Top Meta Interview Questions

Meta Interview Questions

A Software Engineer was asked

A Software Engineer was asked

Software Engineer

Backend Developer

Interview Preparation Guide

MetaQuestions & Answers

Document Details

Need Help?

Top Meta Interview Questions

Meta Interview Questions

A Software Engineer was asked

A Software Engineer was asked

Software Engineer

Backend Developer

Meta
Questions & Answers