Программирование[10]

DeadMage said 8 minutes ago:

Вот кому надо на жсе решение (с поддержкой замен букв, пропуски не стал делать) https://codepen.io/jfhs/pen/LYxygEa?editors=0012

Лучше обьясни где это юзается на фронте, если ты вкурсе

Спасибо за стрим @Vova @DDamager

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

Вторую в голове решить не удалось

Zellar написал 5 минут назад:

Лучше обьясни где это юзается на фронте, если ты вкурсе

Жс сейчас не только в фронте 

Запись будет? А то успел только минут 5 глянуть второй задачи =/

Вова неплохо в принципе выступил, учитывая что ему пришлось компилировать решение и местами объяснять мне синтаксис плюсов
Это точно можно расценивать как некий пруф по постам о его собеседованиях

Из минусов что не объяснил идею перед тем как начать кодить усложненный вариант. Возможно он и хотел сразу собирать ноды из которых будут строиться слова, но выглядело так будто он кодил что-то другое, а в итоге получилось что собрал ноды, при этом не разобрался что в этот набор не может попасть нода, которая является суффиксом для другой ноды.
(Это мои впечатления как интервьювера, тут всё супер субъективно)

Короче в целом неплохо, но скорее всего недостаточно для гугла. Наверняка достаточно для амазона.

Вод тут https://www.twitch.tv/svideteli_gusya/videos

запись

FeelYourDestiny написал 13 минут назад:

Дедмейдж, я помню, что ты какой-то крутой чел, но не помню где ты работаешь. 

Есть возможность зарефералить куда нибудь с релокейтом?

Я уже ушел из МСа, так что сам не могу зареферить, да и предыдущий опыт говорит что это не помогает толком. Но есть знакомые в мс/гугле/амазоне, напиши в пм, попытка не пытка :)

Zellar написал 12 минут назад:

DeadMage написал 22 минуты назад:

Вот кому надо на жсе решение (с поддержкой замен букв, пропуски не стал делать) https://codepen.io/jfhs/pen/LYxygEa?editors=0012

Лучше обьясни где это юзается на фронте, если ты вкурсе

Не знаю где конкретно, но наверное где нужен автокомплит, например поисковая строка, ну или там какой-нибудь typescript playground.
 

Я конечно не понимаю как Вова с такими вздохами и тупняками в речи ещё умудряется на английском языке собеседоваться

scarppy написал 11 минут назад:

Я конечно не понимаю как Вова с такими вздохами и тупняками в речи ещё умудряется на английском языке собеседоваться

scarppy написал 16 минут назад:

Я конечно не понимаю как Вова с такими вздохами и тупняками в речи ещё умудряется на английском языке собеседоваться

Ээээ может как раз потому что на русском я сто лет не собеседовался

))))))))))))

да братух, на английском была бы разъебка

Ладно я посмотрел закодил я автодополнение с 20 минуты по 40 паралельно отвечая на то почему мне не нужен bool в трае и тд ненужные вопросы

что вообще то быстро и хорошо и без ошибок в логике кода (синтаксис не в счет его никто не дрочит)

Дрочить формулировку задачи и обсуждать кучу примеров и как работает - обычно это как раз делает интервьюер а не я

Вторую часть я узнал на 60 минуте и закондил решение к 85 минуте при том что условия задачи изменились (Дамагер сказал что ему изначали более простой вариант задал Гугл)

Что опять таки не сверх быстро но и не то чтобы прям плохо

Конечно 20 + 25 не очень то укладывает в 45 все равно учитывая что надо еще попиздеть за жизнь

Кстати зачем мне нужна была мапа words конечно понятно хотя я чет тупил чтобы ответить - без нее я хуй вернул бы массив слов потому что обратных пойнтеров в трае у меня нет чтобы уметь восстанавливать слово имея пойнтер на его конец в трае

К вопросу почему если разрешать ошибку как лишнюю буквы есть проблемы -

Слово "aaa" можно удалить первую букву (а можно вторую а можно третью) и будет префикс "aa" а можно не удалять и будет префикс "aaa" 

В итоге один префикс становится саб-префиксом другого И это как раз приведет к повторным проходам трая которые можно было бы оптимизировать

Все таки моя интуиция была права

Короче сложность моего алгоритма будет количество подходящих слов из словаря * на длину слова из запроса 

А это не то что мы хотим для такой ошибки очевидно - мы хотим просто количество подходящих слов из словаря

Фух моя душа теперь спокойна

Так, господа JSeры, вы же наверное по сто раз за день юзаете либы и шарите за их сбор, нид ваш хелп

Есть короче либа npm html-to-docx-js 
https://github.com/evidenceprime/html-docx-js

Она охуенно работает, но она старая и там есть баги.

Когда я с npm себе ебашу эту штуку то получаю обфусцированный js файл на 13к строчек (Без import/require), мне нравится, заебись работает

============================================================================================================================

Решил взять более свежую либу, html-to-docx
https://github.com/privateOmega/html-to-docx

С npm устанавливается какая-то ебанина на дохуя модулей с папкой node_modules и кучей дополнительных либ, сам же html-to-docx.js содержит в себе REQUIRE или IMPORT других модулей (там две версии cjs, esm).

Но мне нужен лишь ОДИН .js файл причем специфика моей системы запрещает юзать IMPORT или REQUIRE внутри этого файла

Как мне этого добиться в вашем прекрасном мире JavaScript ?

@Vova@DeadMage
Поразмыслил как поддержать ошибку типа "буква была пропущена" и нашел решение
Если мы всегда будем пытаться скипать, то получим дубликаты
Оказывается, нам всего лишь нужно найти ближайшую к корню ноду, добраться до которой можно за заданное количество ошибок пройдя весь префикс. Для этого мы будем пытаться скипать только тогда, когда не сможем пройти весь префикс без скипов. Это даст нам гарантию того, что нода на которой мы остановимся будет ближайшей к корню из тех, что мы могли найти.

UPD: пофиксил коменты (номера строк поехали) и выпилил сеты
https://www.ideone.com/WLhdmP

Drakonian написал 2 часа назад:

Решил взять более свежую либу, html-to-docx
https://github.com/privateOmega/html-to-docx

С npm устанавливается какая-то ебанина на дохуя модулей с папкой node_modules и кучей дополнительных либ, сам же html-to-docx.js содержит в себе REQUIRE или IMPORT других модулей (там две версии cjs, esm).

Но мне нужен лишь ОДИН .js файл причем специфика моей системы запрещает юзать IMPORT или REQUIRE внутри этого файла

Как мне этого добиться в вашем прекрасном мире JavaScript ?

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

Какие у тебя там ограничения по импорту файлов я не особо шарю. Но даже если тебе доступен только один жс файл, то в теории ты можешь превратить то что я описал выше в веб-сервак, который будет делать конвертацию и посылать результат обратно, а твой жс файл будет посылать данные серваку и асинхронно получать результаты. Для такого точно никакие импорты не нужны, ибо это обычный fetch.

Drakonian said 7 hours ago:

Как мне этого добиться в вашем прекрасном мире JavaScript ?

То, что тебе надо, называется UMD build. Если библиотека его не предоставляет сама, то твой лучший вариант это собрать её в umd из исходников. Для этого тебе надо будет поковыряться в их вебпак файле (ну или rollup или что они там ещё юзают). Но поищи сначала на гитхабе, кто-то уже наврняка им по этой теме тикет создавал, и может там есть какой-то workaround

DDamager написал 10 часов назад:

@Vova@DeadMage
Поразмыслил как поддержать ошибку типа "буква была пропущена" и нашел решение
Если мы всегда будем пытаться скипать, то получим дубликаты
Оказывается, нам всего лишь нужно найти ближайшую к корню ноду, добраться до которой можно за заданное количество ошибок пройдя весь префикс. Для этого мы будем пытаться скипать только тогда, когда не сможем пройти весь префикс без скипов. Это даст нам гарантию того, что нода на которой мы остановимся будет ближайшей к корню из тех, что мы могли найти.

UPD: пофиксил коменты (номера строк поехали) и выпилил сеты
https://www.ideone.com/WLhdmP

 

Не работает, если есть в словаре совпадающие с префиксом и с ошибками: https://www.ideone.com/iI9uak

DeadMage написал 23 минуты назад:

DDamager написал 10 часов назад:

@Vova@DeadMage
Поразмыслил как поддержать ошибку типа "буква была пропущена" и нашел решение
Если мы всегда будем пытаться скипать, то получим дубликаты
Оказывается, нам всего лишь нужно найти ближайшую к корню ноду, добраться до которой можно за заданное количество ошибок пройдя весь префикс. Для этого мы будем пытаться скипать только тогда, когда не сможем пройти весь префикс без скипов. Это даст нам гарантию того, что нода на которой мы остановимся будет ближайшей к корню из тех, что мы могли найти.

UPD: пофиксил коменты (номера строк поехали) и выпилил сеты
https://www.ideone.com/WLhdmP

 

Показать больше  

Не работает, если есть в словаре совпадающие с префиксом и с ошибками: https://www.ideone.com/iI9uak

 

 

Да, ошибка
Тогда придется каждый раз когда находим ноду с которой будем стартовать, нужно пометить всё поддерево начиная с этой ноды. И дальше проверять, если нода помечена, значит возвращаем пустой результат

https://www.ideone.com/ZrQWPn

DDamager написал 11 часов назад:

@Vova@DeadMage
Поразмыслил как поддержать ошибку типа "буква была пропущена" и нашел решение
Если мы всегда будем пытаться скипать, то получим дубликаты
Оказывается, нам всего лишь нужно найти ближайшую к корню ноду, добраться до которой можно за заданное количество ошибок пройдя весь префикс. Для этого мы будем пытаться скипать только тогда, когда не сможем пройти весь префикс без скипов. Это даст нам гарантию того, что нода на которой мы остановимся будет ближайшей к корню из тех, что мы могли найти.

UPD: пофиксил коменты (номера строк поехали) и выпилил сеты
https://www.ideone.com/WLhdmP

 

Я не очень понимаю комплексити твоего решения - кажется что комплексити плохая но судить не буду не разбирался

Есть прямолинейное оптимальное решение:

1) Замечаем что ошибка со скипом дает префикс на 1 символ меньше а значит соответствует ноде на 1 уровень выше (ближе к корню)

2) Проходим по траю делая ровно 1 скип и заносим полученные ноды в unordered_set<Trie*> prefixes_with_one_skip

3) Далее решаем задачу для ошибок замены и без ошибок как решали раньше проходя по траю и если мы дошли до ноды из prefixes_with_one_skip то ниче не делаем и дальше не идем потому что все слова из этого поддерева уже собраны