Алгоритмические задачи на собеседовании QA Automation

1// Решение через HashSet - O(n)
2public List<Integer> findDuplicates(int[] nums) {
3    Set<Integer> seen = new HashSet<>();
4    Set<Integer> duplicates = new HashSet<>();
5    
6    for (int num : nums) {
7        if (seen.contains(num)) {
8            duplicates.add(num);
9        } else {
10            seen.add(num);
11        }
12    }
13    
14    return new ArrayList<>(duplicates);
15}
16
17// Пример использования
18int[] array = {1, 2, 3, 2, 4, 5, 1};
19List<Integer> result = findDuplicates(array);
20// Результат: [1, 2]

1# Python решение
2def find_duplicates(nums):
3    seen = set()
4    duplicates = set()
5    
6    for num in nums:
7        if num in seen:
8            duplicates.add(num)
9        else:
10            seen.add(num)
11    
12    return list(duplicates)
13
14# Пример
15array = [1, 2, 3, 2, 4, 5, 1]
16result = find_duplicates(array)
17print(result)  # [1, 2]

1import java.util.regex.Matcher;
2import java.util.regex.Pattern;
3
4public int findLargestNumber(String text) {
5    Pattern pattern = Pattern.compile("-?\\d+");
6    Matcher matcher = pattern.matcher(text);
7    
8    int maxNumber = Integer.MIN_VALUE;
9    boolean found = false;
10    
11    while (matcher.find()) {
12        int number = Integer.parseInt(matcher.group());
13        maxNumber = Math.max(maxNumber, number);
14        found = true;
15    }
16    
17    if (!found) {
18        throw new IllegalArgumentException("No numbers found");
19    }
20    
21    return maxNumber;
22}
23
24// Примеры использования
25String text1 = "Error code: 404, timeout: 30, retry: 5";
26int result1 = findLargestNumber(text1); // 404
27
28String text2 = "Temperature: -10, pressure: 1013, humidity: 85";
29int result2 = findLargestNumber(text2); // 1013

1import re
2
3def find_largest_number(text):
4    # Находим все числа (включая отрицательные)
5    numbers = re.findall(r'-?\d+', text)
6    
7    if not numbers:
8        raise ValueError("No numbers found")
9    
10    # Преобразуем в int и находим максимальное
11    return max(int(num) for num in numbers)
12
13# Примеры
14text1 = "Error code: 404, timeout: 30, retry: 5"
15result1 = find_largest_number(text1)  # 404
16
17text2 = "Temperature: -10, pressure: 1013, humidity: 85"
18result2 = find_largest_number(text2)  # 1013

1import java.util.*;
2
3public Map<Character, Integer> countCharacters(String text) {
4    Map<Character, Integer> charCount = new HashMap<>();
5    
6    for (char c : text.toCharArray()) {
7        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
8    }
9    
10    return charCount;
11}
12
13// Найти только повторяющиеся символы
14public Map<Character, Integer> findRepeatingChars(String text) {
15    Map<Character, Integer> allChars = countCharacters(text);
16    Map<Character, Integer> repeating = new HashMap<>();
17    
18    for (Map.Entry<Character, Integer> entry : allChars.entrySet()) {
19        if (entry.getValue() > 1) {
20            repeating.put(entry.getKey(), entry.getValue());
21        }
22    }
23    
24    return repeating;
25}
26
27// Пример использования
28String text = "programming";
29Map<Character, Integer> result = findRepeatingChars(text);
30// Результат: {r=2, g=2, m=2}

1from collections import Counter
2
3def count_characters(text):
4    return dict(Counter(text))
5
6def find_repeating_chars(text):
7    char_count = Counter(text)
8    return {char: count for char, count in char_count.items() if count > 1}
9
10# Альтернативное решение без Counter
11def find_repeating_chars_manual(text):
12    char_count = {}
13    
14    # Подсчитываем символы
15    for char in text:
16        char_count[char] = char_count.get(char, 0) + 1
17    
18    # Возвращаем только повторяющиеся
19    return {char: count for char, count in char_count.items() if count > 1}
20
21# Пример
22text = "programming"
23result = find_repeating_chars(text)
24print(result)  # {'r': 2, 'g': 2, 'm': 2}

1// RLE сжатие
2public String compress(String input) {
3    if (input == null || input.isEmpty()) {
4        return input;
5    }
6    
7    StringBuilder result = new StringBuilder();
8    char currentChar = input.charAt(0);
9    int count = 1;
10    
11    for (int i = 1; i < input.length(); i++) {
12        if (input.charAt(i) == currentChar) {
13            count++;
14        } else {
15            result.append(currentChar).append(count);
16            currentChar = input.charAt(i);
17            count = 1;
18        }
19    }
20    
21    // Добавляем последнюю группу
22    result.append(currentChar).append(count);
23    
24    return result.toString();
25}
26
27// RLE декомпрессия
28public String decompress(String compressed) {
29    StringBuilder result = new StringBuilder();
30    
31    for (int i = 0; i < compressed.length(); i += 2) {
32        char character = compressed.charAt(i);
33        int count = Character.getNumericValue(compressed.charAt(i + 1));
34        
35        for (int j = 0; j < count; j++) {
36            result.append(character);
37        }
38    }
39    
40    return result.toString();
41}
42
43// Примеры
44String original = "aaabbccccaa";
45String compressed = compress(original); // "a3b2c4a2"
46String decompressed = decompress(compressed); // "aaabbccccaa"

1def compress_rle(text):
2    if not text:
3        return text
4    
5    result = []
6    current_char = text[0]
7    count = 1
8    
9    for i in range(1, len(text)):
10        if text[i] == current_char:
11            count += 1
12        else:
13            result.append(f"{current_char}{count}")
14            current_char = text[i]
15            count = 1
16    
17    # Добавляем последнюю группу
18    result.append(f"{current_char}{count}")
19    
20    return ''.join(result)
21
22def decompress_rle(compressed):
23    result = []
24    i = 0
25    
26    while i < len(compressed):
27        char = compressed[i]
28        count = int(compressed[i + 1])
29        result.append(char * count)
30        i += 2
31    
32    return ''.join(result)
33
34# Примеры
35original = "aaabbccccaa"
36compressed = compress_rle(original)  # "a3b2c4a2"
37decompressed = decompress_rle(compressed)  # "aaabbccccaa"
38
39print(f"Original: {original}")
40print(f"Compressed: {compressed}")
41print(f"Decompressed: {decompressed}")

1import java.util.regex.Pattern;
2
3public boolean isValidEmail(String email) {
4    if (email == null || email.isEmpty()) {
5        return false;
6    }
7    
8    // Простая регулярка для email
9    String emailRegex = "^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$";
10    Pattern pattern = Pattern.compile(emailRegex);
11    
12    return pattern.matcher(email).matches();
13}
14
15// Альтернативное решение без регулярок
16public boolean isValidEmailManual(String email) {
17    if (email == null || email.isEmpty()) {
18        return false;
19    }
20    
21    // Должен содержать ровно один @
22    int atCount = 0;
23    int atIndex = -1;
24    
25    for (int i = 0; i < email.length(); i++) {
26        if (email.charAt(i) == '@') {
27            atCount++;
28            atIndex = i;
29        }
30    }
31    
32    if (atCount != 1 || atIndex == 0 || atIndex == email.length() - 1) {
33        return false;
34    }
35    
36    // Проверяем наличие точки в домене
37    String domain = email.substring(atIndex + 1);
38    return domain.contains(".") && !domain.startsWith(".") && !domain.endsWith(".");
39}
40
41// Тесты
42System.out.println(isValidEmail("test@example.com")); // true
43System.out.println(isValidEmail("invalid.email")); // false
44System.out.println(isValidEmail("@example.com")); // false

1public boolean isPalindrome(String text) {
2    if (text == null) {
3        return false;
4    }
5    
6    // Приводим к нижнему регистру и убираем пробелы
7    String cleaned = text.toLowerCase().replaceAll("[^a-zA-Z0-9]", "");
8    
9    int left = 0;
10    int right = cleaned.length() - 1;
11    
12    while (left < right) {
13        if (cleaned.charAt(left) != cleaned.charAt(right)) {
14            return false;
15        }
16        left++;
17        right--;
18    }
19    
20    return true;
21}
22
23// Примеры
24System.out.println(isPalindrome("A man a plan a canal Panama")); // true
25System.out.println(isPalindrome("race a car")); // false
26System.out.println(isPalindrome("Madam")); // true

1public void bubbleSort(int[] array) {
2    int n = array.length;
3    
4    for (int i = 0; i < n - 1; i++) {
5        boolean swapped = false;
6        
7        for (int j = 0; j < n - i - 1; j++) {
8            if (array[j] > array[j + 1]) {
9                // Меняем местами
10                int temp = array[j];
11                array[j] = array[j + 1];
12                array[j + 1] = temp;
13                swapped = true;
14            }
15        }
16        
17        // Если не было обменов, массив уже отсортирован
18        if (!swapped) {
19            break;
20        }
21    }
22}
23
24// Пример использования
25int[] array = {64, 34, 25, 12, 22, 11, 90};
26bubbleSort(array);
27// Результат: [11, 12, 22, 25, 34, 64, 90]