Вирішуємо hard-задачу з Leetcode: Regular Expression Matching

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Усім привіт, мене звати Сергій, я більше пʼятнадцяти років працюю розробником ПЗ. Працював з беком і з фронтом, з девопс, зараз працюю бекенд розробником. У цій статті пропоную розглянути вирішення задачі з Leetcode. Щоб було цікавіше, візьмемо задачу з підрозділу hard Regular Expression Matching і вирішимо її на Rust.

Відразу скажу, що перший розгляданий варіант коду не є оптимальним за швидкістю чи за памʼяттю, і ціль статті — показати ітеративно підходи до вирішення складних задач, а не створити найшвидше рішення. Оптимальніше рішення є на моєму гітхабі, і я додумався до того алгоритму вже після написання цієї статті.

Також дисклеймер: я не дивився інші рішення, ні до сабміту свого, ні після. Точно існує щось оптимальніше і простіше, що я пропустив.

Умови задачі і розгляд проблеми

Нам треба реалізувати алгоритм зіставлення рядка зі спрощеним регулярним виразом.

Given an input string s and a pattern p, implement regular expression matching with support for . and * where:

  • . matches any single character.​​​​
  • * matches zero or more of the preceding element.
    The matching should cover the entire input string (not partial).

Маємо такий синтаксис:

  • a зіставляється з одним символом a. Може бути будь-який символ (у цій задачі — будь-яка маленька англійська літера), окрім . та *, які мають спеціальне значення. Зверніть увагу, що екранування підтримувати не потрібно, цього нема в умовах, і рішення проходить тести і без нього.
  • . зіставляється з будь-яким одним символом. Символ обовʼязково має бути присутній, пустий рядок не рахується за збіг.
  • * квантифікатор «нуль або більше». Вказує на те, що попередній символ може зустрічатися від нуля і більше разів.

Також, суттєва умова — вираз має збігатися з рядком повністю, а не з префіксом. Тобто, регулярка a*b не збігається з рядком abc. У цьому є відмінність від звичайних регулярок, які збігаються з підрядком.

Хоча задача може здатися на вигляд дуже простою (як і здалося мені с першого погляду), вона не даремно знаходиться у розділі hard, як ми далі і побачимо.

Цю задачу складно навіть просто вирішити, і ще складніше — вирішити ефективно. Складність її для мене була у тому, що є досить багато випадків, які, природно, не вказані в описі, і до яких я доходив у процесі вирішення. Також ми побачимо, що алгоритм, який може здатися досить простим і прямолінійним, не є таким.

Підготовка до вирішення

Встановлення та налаштування Rust та середовища я не буду тут описувати, все стандартно. Створюємо новий проєкт і редагуємо файл main.rs

pub struct Solution;

#[allow(dead_code)]
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        false
    }
}

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }
}

fn main() {
    println!("Hello, world!");
}

Запускаємо cargo test і бачимо, що наш тест «пройшов». Далі будемо додавати код і більше тест-кейсів.

Перший погляд на алгоритм і перша ітерація

Відразу скажу, що цю задачу можна вирішити за допомогою звичайних регулярних виразів, вбудованих у мову. Спрощений синтаксис є підмножиною синтаксису звичайних регулярних виразів.

Якщо зіставити вираз з рядком за допомогою вбудованих регулярних виразів, і перевірити, що збіг дорівнює вхідному рядку (щоб виконати вимогу на повне зіставлення), то ми вирішимо задачу.

Якщо вам попадеться ця задача на співбесіді — можете на це зауважити. Але вам має бути дуже потрібна саме та робота, щоб вирішувати на співбесіді hard задачі з Leetcode.

Ми реалізуємо власний алгоритм.

Можна побачити, що наш алгоритм рекурсивний. Тобто, ми беремо перший патерн з регулярного виразу, і зіставляємо його з початком рядка. Якщо вдалося зіставити, викликаємо рекурсивно алгоритм для залишку регулярки і залишку вхідної рядка. Синтаксис нашої регулярки досить простий, і ми можемо реалізувати алгоритм без look-back.

Створимо структуру для опису патерну. Тут насправді я трохи забігаю наперед, бо починав я вирішення без цієї структури, але, щоб було коротше, наводжу її одразу:

pub struct Pattern<'a> {
    pub match_char: char,
    pub allow_multiple: bool,
    pub next_regex: &'a str,
}

Структура досить проста: match_char містить символ, з яким іде зіставлення, allow_multiple — якщо після символу була зірочка *, і next_regex — це залишок регулярки.

Також оголошуємо лайфтайм ’a. Його потрібно вказувати, якщо структура містить у собі (нестатичні) посилання (&). Цей лайфтайм підкаже компілятору, що структура не має «пережити» дані, на які є посилання всередині неї (тобто дані, на які ми посилаємося, не можна видалити раніше, ніж структуру).

Також наведу функцію, яка створює цю структуру з рядка:

fn next_pattern<'a>(regex: &'a str) -> Option<Pattern<'a>> {
    let mut next_index = 1;
    let mut chars = regex.chars();

    let next_char = chars.next();
    if next_char.is_none() {
        return None;
    }

    let match_char = next_char.unwrap();

    let allow_multiple = chars.next().unwrap_or_default() == '*';
    if allow_multiple {
        next_index = next_index + 1;
    }

    Some(Pattern {
        match_char,
        allow_multiple,
        next_regex: &regex[next_index..],
    })
}

Вона має бути всередині impl Solution. Ми не будемо розглядати у деталях, як вона працює, тому що вона досить проста і не має безпосереднього стосунку до задачі.

На що тут варто звернути увагу?

По-перше, функція приймає &str. Це слайс — вказівник на діапазон значень всередині рядка або масиву. Це невеличка оптимізація, яка дозволяє мати у памʼяті один екземпляр рядка з регуляркою і не створювати нових строк для кожного залишку патерну (і не копіювати зайвий раз).

По-друге, функція має лайфтайм, який використовується як у параметрі, так і у типі результату. Це означає, що структура, яку поверне функція, буде мати всередині посилання на слайс, переданий у функцію. Слайс, у свою чергу, це посилання на строку + пара індексів (початок і кінець), тобто ми маємо на усю програму два масиви байтів (на інпут і патерн), які не копіюємо.

По-третє, функція повертає Option. Це алгебраїчний тип для (можливо) відсутнього значення. Ми повернемо None, коли дійдемо до кінця регулярки.

Тепер, напишемо сігнатуру-заготовку для нашого рекурсивного алгоритму.

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    false
}

і викличемо її:

pub struct Solution;

#[allow(dead_code)]
impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        return Self::match_recursive(s.as_str(), None);
    }

    fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
        false
    }

    fn next_pattern<'a>(regex: &'a str) -> Option<Pattern<'a>> {
        let mut next_index = 1;
        let mut chars = regex.chars();

        let next_char = chars.next();
        if next_char.is_none() {
            return None;
        }

        let match_char = next_char.unwrap();

        let allow_multiple = chars.next().unwrap_or_default() == '*';
        if allow_multiple {
            next_index = next_index + 1;
        }

        Some(Pattern {
            match_char,
            allow_multiple,
            next_regex: &regex[next_index..],
        })
    }
}

pub struct Pattern<'a> {
    pub match_char: char,
    pub allow_multiple: bool,
    pub next_regex: &'a str,
}

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }
}

fn main() {
    println!("Hello, world!");
}

Поки що наше рішення нічого не робить, але ми підготували оточення для подальшої реалізації. Це дуже важливо — мати щось, що можна запустити і протестити, навіть якщо воно не працює. Це дозволить швидко перевіряти різні варіанти кода і робити маленькі зміни, які просто оцінити і перевірити.

Початок реалізації

Загалом, як я вже казав, алгоритм буде виглядати майже як посимвольне перевіряння вхідної рядка за допомогою патерну.

Запишемо початок рекурсії:

pub fn is_match(s: String, p: String) -> bool {
    let first_pattern = Self::next_pattern(p.as_str());
    return Self::match_recursive(s.as_str(), first_pattern);
}

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        false
    } else {
        return s.len() == 0;
    }
}

Тут ми заодно реалізували перевірку, чи охопив патерн усю строку. Якщо регулярка скінчилася, а рядок ні, то рядок не збігся з патерном, і ми повернемо false.

Зіставлення одного символу

Наступним кроком реалізуємо зіставлення одного фіксованого символу. Це вже корисний код, який вирішує частину наших вимог:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if let Some(next) = next_char {
            if next == pattern.match_char {
                return Self::match_recursive(&s[1..], Self::next_pattern(pattern.next_regex));
            } else {
                return false;
            }
        } else {
            return false;
        }
    } else {
        return s.len() == 0;
    }
}

Ми отримуємо наступний символ вхідного рядка і порівнюємо його з патерном.

По-перше, наступного символу може і не бути. Це значить, що ми добігли кінця рядка, але в нас ще залишилися патерни для зіставлення. Тоді ми одразу повертаємо false. Це не зовсім вірно у загальному випадку, пустий рядок — це цілком коректний інпут, але для частини, яку ми реалізуємо — зіставлення лише одного символу без квантифікаторів — це буде коректно.

По-друге, якщо символ є, але не сходиться — повертаємо false. Це вже не спрощення, так і має бути.

І, по-третє, якщо символ зійшовся, то викликаємо рекурсивно алгоритм для наступного патерна і залишку рядка.

Також, додамо декілька тест-кейсів:

#[cfg(test)]
mod test {
    use super::Solution;

    #[test]
    fn case001() {
        assert_eq!(Solution::is_match("aa".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case002() {
        assert_eq!(Solution::is_match("aa".to_string(), "aa".to_string()), true);
    }

    #[test]
    fn case003() {
        assert_eq!(Solution::is_match("ab".to_string(), "ab".to_string()), true);
    }

    #[test]
    fn case004() {
        assert_eq!(Solution::is_match("".to_string(), "".to_string()), true);
    }

    #[test]
    fn case005() {
        assert_eq!(Solution::is_match("a".to_string(), "".to_string()), false);
    }

    #[test]
    fn case006() {
        assert_eq!(Solution::is_match("".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case007() {
        assert_eq!(Solution::is_match("b".to_string(), "a".to_string()), false);
    }

    #[test]
    fn case008() {
        assert_eq!(
            Solution::is_match("ab".to_string(), "ac".to_string()),
            false
        );
    }
}

Усі тести проходять.

Також тривіально додаємо підтримку для . (будь-який символ):

...

    if pattern.match_char == '.' || next == pattern.match_char {

...

І тест-кейси.

#[test]
fn case009() {
    assert_eq!(Solution::is_match("ab".to_string(), "a.".to_string()), true);
}

#[test]
fn case010() {
    assert_eq!(
        Solution::is_match("abcd".to_string(), "....".to_string()),
        true
    );
}

#[test]
fn case011() {
    assert_eq!(
        Solution::is_match("abcd".to_string(), "...".to_string()),
        false
    );
}

Проста частина позаду. Як бачимо, головне — підготувати код до ітеративних змін, забезпечити просте написання та виклик тестів, писати як позитивні, так і негативні тест-кейси, і не намагатися одразу писати 100% правильний код.

Видалення і виправлення — це нормально, і це суть ітеративної розробки.

Зіставлення з повторюваннями

Нагадаю, якщо після символу (у тому числі і .) іде зірочка *, то це означає, що символ може зустрічатися нуль або більше разів. Саме ця умова є найскладнішою у цьому завданні, і саме з цією умовою повʼязана купа неочевидних тест-кейсів, на які я витратив найбільше часу.

Це завдання на Leetcode має понад 450 тест-кейсів, що може дати вам уяву, скільки там тонкощів і різних граничних умов.

На перший погляд, усе досить просто. Спочатку додамо декілька тест-кейсів:

#[test]
fn case012_match_multiple() {
    assert_eq!(
        Solution::is_match("aaad".to_string(), "a*d".to_string()),
        true
    );
}
#[test]
fn case013_match_multiple_to_one() {
    assert_eq!(
        Solution::is_match("ad".to_string(), "a*d".to_string()),
        true
    );
}
#[test]
fn case014_match_mutiple_to_zero() {
    assert_eq!(Solution::is_match("d".to_string(), "a*d".to_string()), true);
}

Бачимо, що вони валяться, окрім case013_match_multiple_to_one, який, по суті, покривається уже реалізованою логікою, а тому не валиться.

Додамо просту реалізацію:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if pattern.allow_multiple {
            false
        } else {
            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    return Self::match_recursive(
                        &s[1..],
                        Self::next_pattern(pattern.next_regex),
                    );
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    } else {
        return s.len() == 0;
    }
}

Логіку для зіставлення з одним символом ми вже написали і потестили, тому робимо if, і залишаємо попередній код у else.

Поки що відразу повертаємо false, тестимо, тепер усе вірно, і нереалізовані тести валяться.

Пишемо реалізацію:

if let Some(next) = next_char {
    if pattern.match_char == '.' || next == pattern.match_char {
        return Self::match_recursive(&s[1..], Some(pattern));
    } else {
        return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
    }
} else {
    return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
}

По-перше: пустий вхідний рядок — цілком коректний інпут для регекса із зірочкою. Якщо ми не можемо прочитати наступний символ рядка, то викликаємо зіставлення далі.

Цим ми обробимо патерни типу abc* на рядках ab.

Додамо ці тест-кейси:

#[test]
fn case015_match_mutiple_at_the_end_string() {
    assert_eq!(
        Solution::is_match("ab".to_string(), "abc*".to_string()),
        true
    );
}
#[test]
fn case016_match_several_mutiple_at_the_end_string() {
    assert_eq!(
        Solution::is_match("ab".to_string(), "abc*d*e*".to_string()),
        true
    );
}

Все працює.

Здавалося б, готово, але давайте спочатку перевіримо, чи буде працювати такий патерн на початку рядка:

#[test]
fn case017_match_several_at_the_start_of_string() {
    assert_eq!(
        Solution::is_match("bc".to_string(), "a*bc".to_string()),
        true
    );
}
#[test]
fn case018_match_multiple_several_at_the_start_of_string() {
    assert_eq!(
        Solution::is_match("de".to_string(), "a*b*c*de".to_string()),
        true
    );
}

Працює. Спробуємо засабмітити, і тут нас чекає...

Wrong answer

Input: s = «aaa»
Pattern: p = «a*a»
Expected: true
Output: false

У чому ж помилка? Річ у тім, що наш алгоритм «жадібний». Він зіставляє патерн, доки він зіставляється, максимальну кількість разів. У нашому випадку це призводить до того, що перший же a* добігає кінця рядка, і у патерні залишається a, яке зіставляється з порожнім рядком.

Тобто інколи нам треба зупинити «жадібність» алгоритму, навіть якщо є можливість зіставляти далі. Це і є сама складна частина задачі. Я перепробував декілька ідей:

  • перевіряв наступний патерн, і якщо його символ такий самий, як і у попереднього, то пропускав, якщо попередній зіставився хоча б з одним символом. Це валилося на зіставленнях патернів типу a*aa з рядком aaaaa, бо там символів більше, ніж один. Генералізація цього випадку для n символів після патерну із зірочкою теж не допомогла, бо є випадки типу патерн a*b*c*abc і рядка abcabc;
  • думав перевіряти з початку, а потім ще з кінця, але це по суті те саме. Також пізніше знайшов тест-кейси, де це не спрацює, наприклад .*abc.* на рядку aaaaaaaa.

Розвʼязання

Що точно спрацює? І як взагалі цей алгоритм повинен перевіряти, щоб покрити усі випадки?

Спочатку додамо декілька тест-кейсів:

#[test]
fn case019_match_all() {
    assert_eq!(Solution::is_match("ab".to_string(), ".*".to_string()), true);
}
#[test]
fn case020() {
    assert_eq!(
        Solution::is_match("abc1111111d".to_string(), "a.c.*d".to_string()),
        true
    );
}

#[test]
fn case021() {
    assert_eq!(
        Solution::is_match("aa".to_string(), "a.*a".to_string()),
        true
    );
}
#[test]
fn case022_leetcode_test_case() {
    assert_eq!(
        Solution::is_match("mississippi".to_string(), "mis*is*ip*.".to_string()),
        true
    );
}
#[test]
fn case023_non_greedy() {
    let result = Solution::is_match("ab".to_string(), ".*c".to_string());
    assert_eq!(result, false);
}
#[test]
fn case024_regex_longer() {
    let result = Solution::is_match("aaa".to_string(), "aaaa".to_string());
    assert_eq!(result, false);
}
#[test]
fn case025_stop_char_same_as_pattern() {
    let result = Solution::is_match("aaa".to_string(), "a*a".to_string());
    assert_eq!(result, true);
}
#[test]
fn case026_multiple_zero_patterns() {
    let result = Solution::is_match("aaa".to_string(), "ab*a*c*d*e*f*a".to_string());
    assert_eq!(result, true);
}
#[test]
fn case027_simplest_zero_pattern() {
    let result = Solution::is_match("aa".to_string(), "a*a".to_string());
    assert_eq!(result, true);
}
#[test]
fn case028_simplest_zero_pattern_interaction() {
    let result = Solution::is_match("aa".to_string(), "a*b*a".to_string());
    assert_eq!(result, true);
}
#[test]
fn case029_fucked_up_lookup() {
    let result = Solution::is_match("aaacacaab".to_string(), ".*ab".to_string());
    assert_eq!(result, true);
}
#[test]
fn case030_zero_or_more_at_the_end() {
    let result = Solution::is_match("a".to_string(), "ab*".to_string());
    assert_eq!(result, true);
}

Деякі з них вигадані, деякі я додавав з літкодівських тест-кейсів, які у мене валилися. (Зрозуміло, що кожен літкодівський тест-кейс, який у вас не пройшов, треба додавати до своїх тест-кейсів.)

Так який же універсальний код зможе точно зіставити будь-який патерн, най і не з найкращим перформансом? Це, звісно, брутфорс.

Коли у нас у регексі є патерн із зірочкою, то ми не можемо знати точно, коли зупинитися. Ми можемо додати деякі еврістики, але у загальному випадку точно знати ми не можемо.

Тому, у нашому коді, коли ми перевіряємо патерн із зірочкою і він збігається, нам потрібно перевірити насправді два випадки: перший — це залишок рядка з тим же патерном, і другий — це залишок рядка з наступним патерном. Бо навіть збіжний символ може бути насправді кінцем патерну.

Напишемо код:

if pattern.allow_multiple {
    if let Some(next) = next_char {
        if pattern.match_char == '.' || next == pattern.match_char {

            // Here we add
            let is_matching_if_end_of_greed =
                Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));

            if is_matching_if_end_of_greed {
                return true;
            }
            // end of add

            return Self::match_recursive(&s[1..], Some(pattern));
        } else {
            return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
        }
    } else {
        return Self::match_recursive(&s, Self::next_pattern(pattern.next_regex));
    }
}
...
Цей код проходить усі тест-кейси Leetcode, але не є оптимальним. Він бʼє лише 22,96% по швидкості і 8,15% по памʼяті.

Спробуємо трохи оптимізувати.

Перше, що спадає на думку — обробляти ситуацію типу a*b, коли патерн із зірочкою не є . (будь-який символ), і наступний патерн є «один точний символ» (b), і символи у патернах різні. У цьому випадку ми знаємо точно, коли співпадіння повинно зупинитися.

Напишемо код:

fn match_recursive<'a>(s: &str, p: Option<Pattern<'a>>) -> bool {
    if let Some(pattern) = p {
        let next_char = s.chars().next();

        if pattern.allow_multiple {
            let maybe_next_pattern = Self::next_pattern(pattern.next_regex);

            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    if pattern.match_char == '.'
                        || maybe_next_pattern
                            .as_ref()
                            .map(|n| {
                                n.allow_multiple
                                    || n.match_char == '.'
                                    || n.match_char == pattern.match_char
                            })
                            .unwrap_or(false)
                    {
                        let is_matching_if_end_of_greed =
                            Self::match_recursive(&s, maybe_next_pattern);

                        if is_matching_if_end_of_greed {
                            return true;
                        }
                    }

                    return Self::match_recursive(&s[1..], Some(pattern));
                } else {
                    return Self::match_recursive(&s, maybe_next_pattern);
                }
            } else {
                return Self::match_recursive(&s, maybe_next_pattern);
            }
        } else {
            if let Some(next) = next_char {
                if pattern.match_char == '.' || next == pattern.match_char {
                    return Self::match_recursive(
                        &s[1..],
                        Self::next_pattern(pattern.next_regex),
                    );
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    } else {
        return s.len() == 0;
    }
}

Тепер бʼє 16,30% по швидкості, але 96,3% по памʼяті.

Не радіємо завчасно, тому що використання памʼяті дуже різниться від одного запуска до іншого, навіть якщо сабмітити той самий код декілька разів, споживання памʼяті може різнитися від 10% до 90% від інших. Схоже, що Leetcode не робить тести на навантаження, і на таких маленьких обсягах памʼяті похибка більша, ніж саме споживання.

Інша оптимізація — це замість рядка працювати зі слайсом (масивом) байт, за умовами у вхідному рядку і у патерні мають бути лише англійські літери. Рядки у Rust юнікоді, і один символ може складатися з декількох байтів. Ітератор &str::chars() виконує пошук мультибайтових символів і працює повільніше, ніж ітератор по масиву байт, який просто збільшує вказівник.

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let first_pattern = Self::next_pattern(p.as_bytes());
        return Self::match_recursive(s.as_bytes(), first_pattern);
    }

    fn match_recursive<'a>(s: &[u8], p: Option<Pattern<'a>>) -> bool {
        if let Some(pattern) = p {
            let next_char = s.iter().next();

            if pattern.allow_multiple {
                let maybe_next_pattern = Self::next_pattern(pattern.next_regex);

                if let Some(next) = next_char {
                    if pattern.match_char == b'.' || *next == pattern.match_char {
                        if pattern.match_char == b'.'
                            || maybe_next_pattern
                                .as_ref()
                                .map(|n| {
                                    n.allow_multiple
                                        || n.match_char == b'.'
                                        || n.match_char == pattern.match_char
                                })
                                .unwrap_or(false)
                        {
                            let is_matching_if_end_of_greed =
                                Self::match_recursive(&s, maybe_next_pattern);

                            if is_matching_if_end_of_greed {
                                return true;
                            }
                        }

                        return Self::match_recursive(&s[1..], Some(pattern));
                    } else {
                        return Self::match_recursive(&s, maybe_next_pattern);
                    }
                } else {
                    return Self::match_recursive(&s, maybe_next_pattern);
                }
            } else {
                if let Some(next) = next_char {
                    if pattern.match_char == b'.' || *next == pattern.match_char {
                        return Self::match_recursive(
                            &s[1..],
                            Self::next_pattern(pattern.next_regex),
                        );
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        } else {
            return s.len() == 0;
        }
    }

    #[inline]
    fn next_pattern<'a>(regex: &'a [u8]) -> Option<Pattern<'a>> {
        let mut next_index = 1;
        let mut chars = regex.iter();

        let next_char = chars.next();
        if next_char.is_none() {
            return None;
        }

        let match_char = next_char.unwrap();

        let allow_multiple = *(chars.next().unwrap_or(&b' ')) == b'*';
        if allow_multiple {
            next_index = next_index + 1;
        }

        Some(Pattern {
            match_char: *match_char,
            allow_multiple,
            next_regex: &regex[next_index..],
        })
    }
}

#[derive(Debug)]
pub struct Pattern<'a> {
    pub match_char: u8,
    pub allow_multiple: bool,
    pub next_regex: &'a [u8],
}

Тепер по швидкості додалося десь 10%, стало 25,19%. Пропоную забити і зупинитися на цьому.

Я думаю, що навряд чи ми значно пришвидшимося, доки використовуємо рекурсивний алгоритм. Його використання дозволило нам тривіально реалізувати брут-форс зіставлення, з досить зрозумілим кодом. Циклічна версія алгоритму виглядала б досить монструозно, як на мене. Тим більше, що основна причина повільності у перевірянні кожного підрядка. Вочевидь, перевіряти кожен підрядок непотрібно, така реалізація є на моєму гітхабі, але обʼєм та складність коду там на порядок більша.

Також не впевнений, що можна поміняти цей код так, щоб спрацювали tail recursion або tail call оптимізації (та і взагалі далеко не факт, що літкод запускає з потрібними прапорцями).

Тому, скоріш за все, швидші реалізації просто додумалися до кращого алгоритму (як і я, зрештою).

Наш алгоритм проходить тести літкоду лише тому, що там є обмеження по довжині як вхідної рядка (20 символів), так і патерну (30 символів). Використання його на довгих рядках або довгих патернах призведе до «комбінаторного вибуху» рекурсивних перевірок.

Вже після написання статті я додумався до іншого алгоритму, який є кращим внаслідок зменшення кількості непотрібних рекурсивних викликів.

Кращий алгоритм

Патерн ділиться на частини, які складаються з поряд розташованих однотипних патернів (тільки фіксовані або тільки повторювані патерни, які йдуть підряд).

Наприклад, у патерні ab*c*de ми могли б виділити такий набір патернів:

  • a (фіксований патерн);
  • b*c* (два повторюваних патерна);
  • de (два фіксованих патерна);

Згрупуємо їх так, щоб у нас утворилися пари «повторюваний патерн + фіксований патерн» (кожен з них може бути відсутній). Візьмемо довший патерн для більшої наочності:

abc*d*efg*h*ijklmn*

  • None + ab
  • c*d* + ef
  • g*h* + ijklm
  • n* + None

Тепер робимо наступне: беремо першу пару патернів і шукаємо у рядку усі входження фіксованого патерну (через аналог метода index of, який вміє шукати по патерну і враховує спеціальне значення крапки .).

Якщо не знайшли, повертаємо false, бо рядок не має входження фіксованого патерну.

Далі для кожного входження беремо підрядок від початку інпуту до позиції фіксованого патерну і перевіряємо його на збіг з повторюваним патерном з пари.

Підрядки, які не зійшлися, ми пропускаємо. Якщо ж рядок зійшовся, то ми беремо частину інпут рядка, яка знаходиться після фіксованого патерну, і викликаємо рекурсивну перевірку з наступним патерном.

Якщо пара не містить повторюваного патерну, перевіряємо на збіг з початком рядка (це може бути перша пара патернів). Якщо пара не містить фіксованого патерну, перевіряємо залишок до кінця рядка (буває наприкінці рядка).

Приклад

Наприклад, хай у нас є патерн .*a та рядок bbbabba. Пара патернів у нас така: повторюваний .* і фіксований a.

  • Шукаємо перше входження фіксованого патерну, це індекс 3:
    • рядок до фіксованого патерну bbb;
    • Залишок рядка bba, залишок патерну "" (порожній рядок);
      • Збігу немає, бо залишок рядка не сходиться з патерном;
  • Наступне входження фіксованого патерну — це індекс 6:
    • рядок до фіксованого патерну bbbabb, сходиться з повторюваним патерном;
    • Залишок рядка і патерну — пусті рядки, тому маємо збіг.

Оцінка складності алгоритмів

У другому алгоритмі все ще є комбінаторна перевірка, але значно ефективніша, яка залежить лише від кількості входжень фіксованого патерну у залишок рядка, а не від довжини рядка, який сходиться з повторюваним патерном.

Реалізація цього алгоритму бʼє 100% за швидкістю і 60% відсотків за памʼяттю, але має на порядок більший обʼєм коду і кончені алгоритми з кучею граничних умов. Ця стаття вийшла і так дуже довгою, якщо буде цікаво, реалізацію можна побачити у репозиторії на гітхабі.

Спробуємо оцінити складність першого алгоритму.

Перевірка фіксованого патерну це О(1).

Якщо у нас є один повторюваний патерн, перевірка рядка з ним буде O(N!), де N — це довжина рядка, яка збігається з повторюваним патерном. Якщо у нас декілька патернів, то перевірка кожного це буде N!, але N це буде не повна довжина рядка, а залишок довжини, який ми перевіряємо. Тобто приблизно O(k*N!).

Не зовсім впевнений, що правильно оцінив складність алгоритму, але видно, що алгоритм потенційно дуже повільний.

Другий алгоритм набагато простіший.

Перевірка рядка на збіг з повторюваним патерном у ньому O(N), де N — це довжина рядка. Пошук фіксованого патерну — це O(N).

По-третє, кількість рекурсивних викликів залежить від кількості входження фіксованого патерну, яке не може бути більше, ніж N (довжина рядка).

Тобто, маємо O(N^2), а насправді скоріш за все O((N/2)^2), навіть у гіршому випадку. У кращому випадку буде майже лінійний алгоритм, у той час, як перший алгоритм буде факторіал при достатньо довгій частині рядка, яка збігається з повторюваними патернами.

Поради для успішного проходження тестів

  • 50% успіху вирішення задачі — це підготовка оточення, у якому можна швидко і зручно писати і запускати тести, а також пробувати різні варіанти і відкочувати зміни (тому хороша ідея створити локальний гіт-репозиторій і комітити туди).
  • Щоб не витрачати час тестування на налаштування оточення, краще це зробити заздалегідь. Сайти з тестами влаштовані досить схоже, тому навіть якщо ви не знаєте, яка буде структура, підготуйте хоча б таку, як у літкоді. Адаптувати буде швидше, ніж зробити з нуля.
    У випадку Rust усе робиться швидко, але для інших мов може зайняти 5-10 хвилин, які можуть виявитися далеко не зайвими у кінці.
  • Пишіть код у IDE, до якої ви звикли, за можливості. Варто поцікавитися у інтервʼюера, чи можна це робити. Деякі компанії (а також деякі сайти з тестами) забороняють перемикати вкладки браузера та перемикатися на інші програми. У цьому випадку можна запропонувати зробити запис свого екрану, як альтернативу. Не всі на це погодяться, тому що хочуть обробляти результати тестування (напів)автоматично, і хочуть одразу відкидати типу «читерів» (тих, хто перемикався).
    Звісно, велике питання, чи варто взагалі витрачати час на тести для компанії, яка вимагає написання такого, досить важкого навіть у звичному оточенні, тесту у браузері.
  • Може, це досить очевидно, але головне — по-перше, зрозуміти умови задачі, а по-друге — створити алгоритм. Написати код по готовому алгоритму значно простіше, ніж зразу писати в надії створити алгоритм на ходу.
  • Також не нехтуйте категорією складності задачі. Якщо на літкоді вона відноситься до складних, то вона, напевно, і є складна, і якщо алгоритм знайшовся легко і просто, то тричі подумайте і перевірте, чи справді алгоритм підходить і вирішує задачу, зекономите час на написання.
  • Одразу можна зробити функції та структури (а також написати до них тести), які точно підійдуть до будь-якого алгоритму. У нашому випадку це структура з патерном та функція парсингу наступного патерну з рядка.
  • Варто запитати у інтервʼюера, що для нього важливіше: перформанс чи чистий код. Також запитайте, якої складності він очікує алгоритм, деякі завдання мають тривіальні розвʼязання зі складністю O(n^2), і набагато складніші з меншою складністю.
  • Тренуйтесь вирішувати алгоритмічні задачі. Це окремий вид програмування, особливо якщо є обмеження по складності/ памʼяті, або обмежений час на вирішення. Не маючи звички, можна завалити такий тест навіть прекрасно вміючи програмувати. Тому підготуйтесь, вирішіть кілька задач, най навіть з категорії легких.
👍ПодобаєтьсяСподобалось4
До обраногоВ обраному5
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Я, звісно, в фаангах не працював й літкод не задрочував, але на мою думку підхід «від простих юзкейсів до складних» не є вірним. Адже весь сенс цієї задачі саме у рішенні для найскладнішого кейса, а саме .* Усе інше — або тривіально, або підмножина цього кейсу. Всі інші комбінації типу a*a, або .*.*. не треба навіть чіпати, оскільки вони прибираються нормалізацією патерну перед перевіркою.
А вирішення простих кейсів не дає абсолютно нічого крім великів шансів обрати взагалі невірний солюшен, який ніколи не дасть розв‘язок для задачі в цілому. Це як в старому анекдоті про масло з гівна — те, що вже намазується на хліб, це не вирішення половини проблеми :)
Нажаль, багато розробників (да і навіть команд/компаній) намагаються піти цим шляхом, відкладаючи складний кейс на потім, та деліверять «майже готовий проект», але який не реалізує (й не може реалізувати) головний функціонал, а отже — немає ніякого велью для клієнта (хоча оплачено 50-90% вартості). Така фігня

для найскладнішого кейса, а саме .*

Самый сложный кейс на самом деле «a*.» и «.*a».

a*. потребує того ж алгоритму, що й .*а, тільки у простішому варіанті — корегувати жадібність треба в першому випадку тільки на один символ й один раз, а у другому — 1+ разів, от і все

П.С. під «.*» я маю на увазі не весь патерн, а входження такої конструкції у патерн, тоб-то і «аа.*а», і «.*.*.» і т.п.

Конечный автомат с магазинной памятью (pushdown automaton).

Магазинная память оверкил, ибо его достаточно для разбора не только регулярных, но и контекстно-свободных грамматик.

Есть такое, да. Но на паре (КА+стек состояний) во-первых искомая задача решается куда проще, чем на одиночном КА, а во-вторых есть потенциал под будущие изменения требований к распознаваемой грамматике.

Ну... взагалі є теорема, що регулярна множина розпізнається фінітним автоматом. Тому оптимальний розв’язок це: побудова автомату, необов’язковий крок оптимізація автомату, його виконання. Тоді складність буде рівно O(m), де m це довжина ланцюга на вході, при цьому кожен крок це одна операція. Розмір автомату так, може бути O(n^2), де n це довжина регулярного виразу, гірший випадок це якщо подати на вхід щось на кшталт a*b*c*d*e*x.*.

Але на Leetcode, судячи з усього, розбір регулярного виразу завжди буде рахуватися з його виконанням.

Мені подобається елегантне рішення цієї задачі від Rob Pike: github.com/...​ike/blob/master/repike.go

Russ Cox також має цікавий погляд на дану проблему: swtch.com/~rsc/regexp

Люди з освітою в комп`ютерних науках не можуть обійти цю тему стороною. Також вона представлена в книзі Algorithms від Robert Sedgewick.

На співбесіді спроба винайти своє рішення говорить про прогалини в фундаментальних знаннях.

Запам`ятатти рандомне рішення з літкоду на мій погляд набагало важче ніж зрозуміти саму проблему з найліпшою реалізацією.

я не дивився інші рішення, ні до сабміту свого, ні після. Точно існує щось оптимальніше і простіше, що я пропустив.

Якщо ви не розiбрали оптимальне рiшення — не зрозумiло яку користь особисто ви для себе винесли пiсля вирiшення цiеi задачi

Ну, друга моя реалізаця бʼє 100% по швидкості, так шо вона не така вже і неоптимальна. Я так розумію, це щось близько до оптимальної реалізації через динамічне програмування.

Тим не менше — лiткод це не зовсiм про дрочку на графiки)
Яка у вашому випадку проблема вирiшуеться шляхом вирiшення задач на лiткод?

Я тренуюся вирішувати алгоритмічні задачі. В цілому з вами згоден, треба б розбирати класичні рішення. Не підкажете, де їх дивитися саме для задач літкода?

На літкоді є вирішення задач рекомендоване літкодом.

Ні, не преміум. Вже знайшов де, як і те, що без преміума не показує.
Скажіть, там тільки код або ще і пояснення (хоча б на рівні назву алгоритму)

Дуже залежить)
тут нещодавно була стаття про контрибуцію у літкод. З якої відомо що над рішеннями працюють різні люди, тому і якість пояснення може відрізнятись.

Повертаючись до цілі — якщо немає конкретної, то не варто витрачати гроші на преміум, на мою думку)

У каждой задачи есть раздел, где люди публикуют свои решения. Доступен без премиума.

Скажiмо так — цей роздiл не завжди адекватний)

Вполне адекватный. Для популярных задач там будут годные решения с подробным описанием

Так, але значна частина людей там більше старається народити Python one-liner, ніж оптимальне рішення.

В интернете вообще много бесполезного шлака. Вы в интернет из-за этого не ходите?

Те що ви тренуєтеся вирішувати алгоритмічні задачі я розумію.
А для чого ви тренуєтесь?
Яка кінцева мета?

Щоб було легше проходити співбесіди, якщо там буде алгоритмічні задачі

Якщо ви вирішуєте хард то дефолтні голерні співбесіди вас наврядче злякають)
Плануєте у Фаанг?

Зараз не те, що щось планую взагалі. Але в цілому так, мабуть за декілька років можливо спробую.

Зі свого досвіду можу сказати що для результату краще мати чітку ціль. Тоді виходить продуктивніше працювати на шляху до мети, тоді є зрозумілий вимір результату і таке інше)
Можливо у ва по іншому.
Але я все таки схиляюсь до того що не маючи конкретної цілі і контрольних точок це менш продуктивний підхід до будь-якої задачі.

fn next_pattern<'a>(regex: &'a str) -> Option<Pattern<'a>> {
    let mut next_index = 1;
    let mut chars = regex.chars();

    let next_char = chars.next();
    if next_char.is_none() {
        return None;
    }

    let match_char = next_char.unwrap();

    let allow_multiple = chars.next().unwrap_or_default() == '*';
    if allow_multiple {
        next_index = next_index + 1;
    }

    Some(Pattern {
        match_char,
        allow_multiple,
        next_regex: &regex[next_index..],
    })
}

1) Вместо кучи проверок + unwrap

    let next_char = chars.next()?;
    if next_char.is_none() {
        return None;
    }

    let match_char = next_char.unwrap();

делаем проще:

    let match_char = chars.next()?;

Если ? сильно смущает, то

    let Some(match_char) = chars.next() else { return None; };

2)

    let allow_multiple = chars.next().unwrap_or_default() == '*';

Заменяем на

    let allow_multiple = chars.next() == Some('*');

3)

    Some(Pattern {
        match_char,
        allow_multiple,
        next_regex: &regex[next_index..],
    })

Вот тут начинается интересное. Делать так нельзя.
1) В Rust str — это корректная UTF8 строка.
2) В UTF8 символы могут иметь разную длину
3) В Rust индексация внутри str работает не по символам а по байтам.

Учитывая это, считывание из строки через [...] может привести к тому, что вы «разрежете» строку внутри многобайтного UTF8 символа и произойдет ошибка, так как Rust не позволяет иметь невалидную UTF8 строку в str

Чтоб убедиться, можете запустить

    println!("{}", &"Привет"[1..]);

Самое простое решение — отказаться от использования строк и перейти к [char]

Другое — вместо хранение «хвоста» в str, хранить его в итераторе Peekable<Chars>

pub struct Pattern<'a> {
    pub match_char: char,
    pub allow_multiple: bool,
    pub remaining: Peekable<Chars<'a>>,
}

fn next_pattern<'a>(mut remaining_regex: Peekable<Chars<'a>>) -> Option<Pattern<'a>> {
    let match_char = remaining_regex.next()?;

    let allow_multiple = if remaining_regex.peek() == Some(&'*') {
        // Consume '*' from iterator
        remaining_regex.next();
        true
    } else {
        false
    };

    Some(Pattern {
        match_char,
        allow_multiple,
        remaining: remaining_regex,
    })
}

Дякую за корисний коментар.

Вот тут начинается интересное. Делать так нельзя.
1) В Rust str — это корректная UTF8 строка.

В умові задачі є те, що вхідна строка — це лише маленькі латинські літери. Але ви праві, і в загальному випадку так робити не варто

Ну это не значит, что надо говнокодить ради того, чтоб рассказать как вы получили top 100% time на сабмите. Ваш код неокрепшие умы читают и потянут идеи туда, где есть реальный мир, в котором больше не используют KOI8

BTW

маємо O(N^2), а насправді скоріш за все O((N/2)^2),

треба забути, бо це константа і така фраза індикатор швидше, що кандидат не дуже розуміє нащо осьце O взагалі потрібно

darkcoding.net/...​sional-software-engineer

That reminded me that I hadn’t finished my Big O calculations for the design review later this week, so that was my first task after lunch. Junior engineers only do the ‘n’ part, but as a senior I do the constant as well. I have three more functions to calculate.

не зовсім розумію на кого розрахована ось ця стаття. Якщо на підготовку до інтервʼю, то половина висновків просто-напросто невірна — не треба юзати IDE, не треба готувати енвайрмент для парсингу, не треба вбивати купу часу на прописування тестів (прошу не плутати з продумуванням тест-кейсів), не треба херачити купу структур даних.
Якщо розібрати цю задачу конкретно, то

Також дисклеймер: я не дивився інші рішення, ні до сабміту свого, ні після. Точно існує щось оптимальніше і простіше, що я пропустив.

це робить статтю абсолютно марною, бо оптимальне рішення тут не розбирається.

Якщо на літкоді вона відноситься до складних, то вона, напевно, і є складна, і якщо алгоритм знайшовся легко і просто

Не обовʼязково. Наприклад ця задача вирішується елементарно через ДП і якщо розуміти ДП, то це ізі-медіум, не більше. Вона в харді просто тому що для багатьох ДП це жах

Також запитайте, якої складності він очікує алгоритм

Е ні, так не прокатує. Кандидат повинен розуміти, чому це оптимальний або не оптимальний варіант. За таке питання можна швидше мінус вихопити.

Варто запитати у інтервʼюера, що для нього важливіше: перформанс чи чистий код

не варто. Це питання має сенс тільки якщо ви приходите до конкретного випадку, де можна впровадити barely-readable рішення, але яке буде краще по O. Тоді треба сказати про ці дві альтернативи, проаналізувати плюси та мінуси і приймати тоді рішення. Але ну серйозно, такого майже ніколи не буває. Код повинен бути і оптимальний, і чистий. Швидше за все після вищезгаданого аналізу та дискусії з інтервʼюєром знайдеться підхід.

Якщо на підготовку до інтервʼю, то половина висновків просто-напросто невірна — не треба юзати IDE, не треба готувати енвайрмент для парсингу, не треба вбивати купу часу на прописування тестів (прошу не плутати з продумуванням тест-кейсів), не треба херачити купу структур даних.

Чому? Ви маєте на увазі, що на інтервʼю не дадуть користуватися IDE? Тести зручніше запускати локально, бо їх може бути треба запускати часто, а у літкоді це до хвилини часу займає.

це робить статтю абсолютно марною, бо оптимальне рішення тут не розбирається.

Чому? На співбесіді не завжди треба видати оптимальне рішення, більш того, якщо ти швидко написав оптимальне рішення, то сенс і цінність саме цього тестового завдання дорівнює нулю. Це як поставити задачу на логіку, на яку кандидат вже знає відповідь.

Наприклад ця задача вирішується елементарно через ДП

Що таке ДП?

Е ні, так не прокатує. Кандидат повинен розуміти, чому це оптимальний або не оптимальний варіант. За таке питання можна швидше мінус вихопити.

Чому, знову ж? Для багатьох задач є менш оптимальне, але значно коротше і виразніше рішення. Якщо ви можете написати обидва, чому не запитати, що важливіше для інтервʼюера: перформанс чи чистий код.

Це питання має сенс тільки якщо ви приходите до конкретного випадку, де можна впровадити barely-readable рішення, але яке буде краще по O

Навіть у задачі, яку я розбирав у статті є декілька рішень: коротке і більш виразне, але повільне, довге, не дуже виразне, але швидке (є на гітхабі, посилання у статті), ну і академічно правильне на кінцевих автоматах.

Чому? Ви маєте на увазі, що на інтервʼю не дадуть користуватися IDE? Тести зручніше запускати локально, бо їх може бути треба запускати часто, а у літкоді це до хвилини часу займає.

Ну в общем, когда ты пишешь задачу интервьюверу, тебе нужно написать код, который so simple that it obviously does not have errors. Код должен быть простым, чтоб ты мог двумя словами убедить интервьювера в том, что он решает задачу, типа ну смотри, очевидно же. Если тебе нужно писать тесты в поддержку кода, то ты уже делаешь что-то не то.

«золотой стандарт» на литкоде — когда ты пишешь код прямо в веб браузере, сабмитишь его и он проходит все тесты. Когда ты засабмитил код, тебе что-то упало, и ты так «опа, тут еще стопитсот корневых случаев, давайте еще погриндим юнит тестов пока не пройдет» — это немного не то, к чему нужно стремится.

Що таке ДП?

Динамическое программирование. Штука, которая при правильном использовании на некоторы задачах позволяет перейти от O(2^N) до O(N). Советую пойти, разобраться и начать практиковать, потому что без нее решать подобные задачи на литкоде рекурсией — трата времени, как носить кирпичи с места на места — зае*шься, но дом не построишь.

Чому? На співбесіді не завжди треба видати оптимальне рішення, більш того, якщо ти швидко написав оптимальне рішення, то сенс і цінність саме цього тестового завдання дорівнює нулю. Це як поставити задачу на логіку, на яку кандидат вже знає відповідь.

На собеседование будут приходить кандидаты, которые
1) эту задачу уже видели, и знают ее решение наперед
2) которые решили столько задач, что подобная задача для них очевидна и решается «спинным мозгом».

Ты не можешь под каждого кандидата подбирать какоую-то заковыристую задачу, чтоб он на ней «завалился» и начать на самом деле думать головой.

Чому? Ви маєте на увазі, що на інтервʼю не дадуть користуватися IDE? Тести зручніше запускати локально, бо їх може бути треба запускати часто, а у літкоді це до хвилини часу займає.

Так, швидше за все не дадуть. Якщо вам доводиться запускати тести настільки часто, що вам важливо, що літкодівські бігають хвилину, то ви щось не так робите. Ці задачі на співбесіді ніхто не дасть додебажити за допомогою молотка, навіть якщо дадуть ІДЄ, бо якщо вам доводиться так робити, то швидше за все, ви не дуже розумієте своє рішення

Чому? На співбесіді не завжди треба видати оптимальне рішення, більш того, якщо ти швидко написав оптимальне рішення, то сенс і цінність саме цього тестового завдання дорівнює нулю.

Не треба видати оптимальне рішення, якщо це задача рівня всесвітньої олімпіади. Деякі інтерв"юєри ставлять такі задачі, щоб перевірити, як кандидат буде реагувати на задачу, яку не може вирішити. В решті випадків неоптимальне рішення буде мінусом. Якщо мені кандидат напише рішення з пам"яті, я поставлю йому фоллоу-апи, або поговорю про параллелізацію, або дам інше завдання. Мені за сотню співбесід жодного разу не написали ідеально з голови рішення. Але якщо що, я готовий))

Що таке ДП?

Ваш підхід до рішення задач ІМО дуже неструктурований, якщо ви все ще не знаєте, що таке динамічне програмування. Раджу трохи більше пройтись по теорії

Для багатьох задач є менш оптимальне, але значно коротше і виразніше рішення.

Можна приклад? Серед реальних задач, які реально ставлять на інтерв"ю, таких мінімум. Бо зазвичай інтерв«юєр має вже в голові «ідеальне» рішення і воно буде і оптимальне і зрозуміле і лаконічне

більш виразне, але повільне, довге, не дуже виразне, але швидке

секція діскас на літкоді дасть оптимальне і коротке.

Так, швидше за все не дадуть. Якщо вам доводиться запускати тести настільки часто, що вам важливо, що літкодівські бігають хвилину, то ви щось не так робите. Ці задачі на співбесіді ніхто не дасть додебажити за допомогою молотка, навіть якщо дадуть ІДЄ, бо якщо вам доводиться так робити, то швидше за все, ви не дуже розумієте своє рішення

Я правильно розумію, що по суті на гугловскій співбесіді такі задачі треба писати по суті на памʼять? Тобто, швидко зрозуміти, який алгоритм там має бути, і з голови його записати у вигляді рішення?

В решті випадків неоптимальне рішення буде мінусом.

Тобто ціль таких завдань — це перевірка, що кандидат вивчив розповсюджені алгоритми? Не перевірка, що ти здатен придумати алгоритм для незнайомої задачі? (Якщо що, я не сперечаюся, мені справді цікаво).

Ваш підхід до рішення задач ІМО дуже неструктурований, якщо ви все ще не знаєте, що таке динамічне програмування. Раджу трохи більше пройтись по теорії

Дякую, не одразу розшифрував абревіатуру, щось некомпʼютерне більше в голову лізло

Можна приклад? Серед реальних задач, які реально ставлять на інтерв"ю, таких мінімум. Бо зазвичай інтерв«юєр має вже в голові «ідеальне» рішення і воно буде і оптимальне і зрозуміле і лаконічне

Ну, як грубий приклад, вирішити задачу брутфорсом. Я розумію, що брутфорс не зарахується за рішення, але можна вирішити задачу за O(N*log(N)) замість O(N).

швидко зрозуміти, який алгоритм там має бути, і з голови його записати у вигляді рішення

З того, що я читав, так, інакще не вистане часу на 2 медіум задачки за 50 хвилин з фоллоу-апами. Індуси з ютубу дають приблизний таймінг у
2 хв — зрозуміти клас задачі, проговорити з інтервьюером, «буду вирішувати через дфс»
7 хв — закодити базові кейси, проговорити
5 хв — драй рани
7 хв — фоллоу-ап питання.
Гуглити і думати часу нема. Просто робиш креш курс на місяць — два (залежить від базового знання алгоритмів) по 6-8 задач на день, поки воно не потрапить до безумовних рефлексів.
Наприклад, ось leetcode.com/...​nterview-preparation-plan

Гуглити

не часу немає, а просто не можна. Так-то усі ці алгоритми є на умовному стековерфлоу, або від ChatGPT)))

Наприклад, ось leetcode.com/...​nterview-preparation-plan

Це булшіт. По-перше по темах оверкіл, по-друге це нереальне навантаження — кожного дня розбирати по 5-7 задач. І навіть якщо пропрацювати цей план, на 31 день виявиться, що вже ніфіга не пам’ятаєш, що було в перший день.

2 медіум задачки за 50 хвилин з фоллоу-апами

Медіуми бувають різні. 2 бойових медіуми з фолоу-апами я хз хто вимагає, можливо Jane Street +. Автоматичне відтворення задачі — це хрінь. І якщо мені кандидат просто одразу фігачить задачу начисто, бо пам’ятає її, цінність такого нуль. І до того ж оцінюється і те, як кодиш, як розмовляєш.

2 бойових медіуми з фолоу-апами я хз хто вимагає

Тобто два медіума це доволі велика рідкість в фаангів? Читав декілька статей про хайрінг в фаангах, посил був готовим до хард задач. Імхо, але один хард складніше за два медіума, суб’єктивно, так.

проблема в 2 медіумах з фоллоу-апами не в складності per se, а в тому, що тупо часу не вистачить на те, щоб нормально проговорити та написати задачу.

Хард так — я вихопив хард на DP ще на першому інтервʼю і потім ще півтора в процесі наступних. Особисто я не прихильник питати хард через декілька причин, але багато хто питає.

Мені комфортніше на інтервʼю вирішити один хард, ніж 2 медіума.

по суті на гугловскій співбесіді такі задачі треба писати по суті на памʼять? Тобто, швидко зрозуміти, який алгоритм там має бути, і з голови його записати у вигляді рішення?
Тобто ціль таких завдань — це перевірка, що кандидат вивчив розповсюджені алгоритми? Не перевірка, що ти здатен придумати алгоритм для незнайомої задачі?

ну я б не назвав це «на памʼять». Треба пам’ятати і розуміти швидше підходи, а не конкретні алгоритми. І тоді алгоритм можна згенерувати самостійно. До того ж задача не буде звучати, як «повернути червоне-чорне дерево». Ні, це буде якась адаптація або зміна відомих алгоритмів. Напевно гарний приклад — відстань Левенштейна. Можна завчити цей алгоритм, а можна зрозуміти ДП підхід і на співбесіді просто заново згенерувати цей алгоритм. Для розуміння того, які бувають підходи, є наприклад файний курс grokking the coding interview, там задачі ділились на 14 підходів. Погодьтеся, 14 підходів простіше запам’ятати, ніж сотні алгоритмів.

Коли я готувався, я навіть мав бекап план — якщо задачу вирішити не можу, то я проходжусь по цих 14 підходах в голові швиденько та по 5-6 структурах даних і думаю, чи можуть вони мені якось допомогти. Але зазвичай цей зв’язок формується автоматично. Бачиш longest substring — DP або sliding window. Бачиш «оптимальний шлях» — напевно бектрекінг. Є в задачі лист слів і щось з ним треба зробити — швидше за все Trie може допомогти. І так далі.

Ну, як грубий приклад, вирішити задачу брутфорсом

Ні, я маю на увазі приклад конкретної задачі, де оптимальне рішення буде задовге/нечитабельне і реально потрібно буде обирати між оптимальним та readable.

Порадьте книжку чи курс по алгоритмам, щоб справді був корисний на співбесідах у МААНГ

я починав з цього курсу www.coursera.org/...​learn/algorithmic-toolbox — він мені непогано закрив пробіли в підготовці базовій. Далі пішов вже закривати теми на літкоді — якщо тему не розумію — зовсім — читаю теорію, пробую вирішувати ізі. Якщо ізі виходять — медіум, на ізі не засиджуюсь.

Якщо все ще не розумію, як воно працює — www.youtube.com/...​/UCmJz2DV1a3yfgrR7GqRtUUA цей канал мені заходив на пояснення.

По задачах — навіть якщо моє рішення показує 100% — йду до секції діскас і читаю найзалайканіші рішення, бо вони можуть бути лаконічнішими або більш зручними до імплементації.

Обовʼязково забував про ІДЄ за виключенням ситуації, коли вже цікаво добити якісь кейси в задачі, але загалом треба відмовлятись і вирішувати прям в едіторі літкоду. Також приймав участь в контестах (тут вже використовував ІДЄ). Контести допомагають привчитися вирішувати задачі в стресовій ситуації і з обмеженим часом. Також гарна річ мок — інтервʼю, але я тоді обійшовся без них.

Щоб переконатись, що я закрив теми, використовував літкод класифікатор, та стару версію цього курсу www.educative.io/...​king-the-coding-interview

При виборі яку задачу вирішувати, фільтрував по тегах і далі обирав задачі, в яких кількість лайків перевищує кількість дизлайків, бо інакше це може бути задача, де просто купа едж кейсів і рішення на три екрани — такого на співбесіді не буде.

Эээ. Я вообще-то ожидал преобразование регулярки в Недетерминированный Конечный Автомат, потом преобразование НКА->ДКА, и потом прогон автомата по строке. Какая рекурсия, вы о чем?

Навіть з автоматом будет потрібний рекурсивний виклик, чи ні? Якщо у нас є символ, який підходить і під патерн з повторюванням, і під наступний фіксований патерн. Ми не можемо знати без перевірки обох варіантів, який з них вірний.

Мабуть, технічно можливо це реалізувати і без рекурсії, але по суті у нас буде рекурсивний виклик.

Регулярка не использует скобочки, поэтому рекурсивный вызов не нужен.
Сначала читаем матчасть:
en.wikipedia.org/...​ministic_finite_automaton
en.wikipedia.org/...​ministic_finite_automaton
Там есть еще и описание эквивалентности этих двух штук

Состояния — это промежутки между буквами.
— Если мы видим обычный символ («терминал»), то создаем новое состояние и просто от предыдущего состояния к следующему рисуем переход по этому символу
— Если мы видим точку, то от предыдущего состояния к следующему рисуем переходы по всем символам
— Если мы видим звездочку, то не создаем нового состояния, а просто у текущего и предыдущего рисуем эпсилон-переходы в обе стороны

В итоге получили ε-НКА, который потом преобразуем в ДКА, потом за линейное время проходим по строке.

Возможно, основные оптимизации тут будут в виде построения ДКА напрямую, без НКА, надо подумоть.

Мне было лом читать теорию (да и не математик), задача — регулярка для телефонных номеров (ограниченной длины). Запилил через динамическое программирование — каждый терм запоминает в битмап на каких позициях в строке он может начинаться и на каких — заканчиваться. Даже скобочки поддерживались.

А потом пришел ПО, сказал, что круто, и надо допилить замену кусков номера регекспом. В общем, еще 3-4 недели работы, и абсолютно нечитаемый код. А соседняя команда сделала без скобочек за 3 дня через scanf().

Підписатись на коментарі