Цикл должен быть до length/2. У вас в 2 раза больше работы выполняется. Upd: и если на i-том индексе условие не совпало, нужно сразу возвращать фолс, а не идти до конца цикла.
Так и есть, я написал об этом в доке, ссылка на которую есть в комментах. Там сказано что мой алгоритм не оптимальный и его можно улучшить, что вы, собственно и сделали.
@@itwithvitaly Ну я про 2 строчи говорил не про решение с реверсом, а, условно: for (size_t index = 0; index < collection.size() / 2; index++) if (collection[index] != collection[collection.size() - index - 1]) return false; return true; На js что-то вроде этого тоже должно быть
Your for loop is not optimal :) You don't need to loop through all the characters (index < characters.length), you only need to loop through half of them (index < characters.length/2). If you have a very long string which IS a palindrome, you're just looping through the second half of it unnecessarily.
Exactly, I’ve left the link to the google document in the comments where I described that my algorithm is not optimal with the suggestion that people who are watching this video would have the space to think and can make it more effective :)
Хм, хорошее решение! Я думал по другому, переворачивать строку string.split('').reverse().join('') делаем из строки массив символов, переворачиваем массив и объединяем снова в строку, ну и потом в условии сравниваем
Я раньше решал эту задачу полностью разворачивая число и сравнивая с исходным, но этот способ показался мне более эффективным и простым. Я переписал на ваше решение на JAVA вот метод: public static void palindrome(String str) { String[] string = str.split(""); boolean palindrome = true; for(int i = 0;i < string.length / 2;i++) { if(Integer.parseInt(string[i]) != Integer.parseInt(string[string.length - 1 - i])) { palindrome = false; break; } } System.out.println(palindrome); } Я не знаю как в происходит в JS, но в JAVA при сравнении ссылочных типов данных сравниваются именно ссылки, а не содержание строки, поэтому я использовал классы обертки, чтобы перевести строку в интеджер. Жду критики, т.к я новичок и многого ещё недопонимаю
Все гуд, алгоритм хороший, пару моментов к улучшению: 1. Лучше назвать метод isPalindrome, "is" здесь означает что метод будет возвращать boolean (naming convention) 2. Из метода лучше возвращать boolean вместо вывода строки, потому что этим методом можно пользоваться как утилитным в разных местах. 3. Если соблюдать пункт 1 и пункт 2 то там где у вас стоит break, можно будет сразу делать return.
9:15 можно поставить условие если index >= Math.floor(characters.length / 2), то выйти из цикла, чтобы не проходить лишние итерации. Переменная isPalindrome здесь не нужна, можно просто return true или return false
Сколько будет занимать памяти такое решение ? В js тоже можно написать в одну строку return str === str.split('').reverse().join('') она будет занимать n*3 вроде как а в питоне сколько?
@@trypophobia7497 изучите временную сложность алгоритмов. Цикл всегда дольше выполняется чем проверка равенства. Да и слайс всё-таки должен быть быстрее чем сплит, реверс, джоин)
@@47clere я тут не писал про временную сложность я тут спросил сколько будет занимать ПАМЯТИ ????? вы прочитай комментарий внимательно! если в цикле будет константное значение то BIG O будет равно O(1) так же как и в сравнении на равенство О(1) а если нет то в цикле O(n) (сейчас я не говорю про то что в цикле будет быстрее или равно я говорю про BIG O) я спрашивал про память копируется ли этот слайс в снова в новую память или нет? в js будет создаваться новые массивы
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
С точки зрения "красоты" кода, я согласен. return str.split('').reverse().join('') === str очень компактная запись. С точки зрения производительности... Ну, такое себе. Если я правильно понимаю, создается промежуточный массив, который потом собирается обратно. Сложность алгоритма О(3n) = n + n + n, соответственно n на разделение, на разворот и на джойн. Алгоритм который имеет сложность O(n/2) function isPalindrome(str) { for (let i = 0; i < Number(str.length / 2); i++) { if (str.charAt(i) !== str.charAt(str.length - 1 - i)) { return false; } } return true; }
@@НикитаНигматуллин-т1ы javascript не тот язык, где имеет смысл сравнивать O(n/2) и O(3n), для js, с учетом браузерных оптимизаций это капля в море. Куда большее значение имеет читабельность, так вот в случае с reverse() читабельность кода в разы лучше, код яснее. А тут, что вы пытались запихнуть в цикл for далеко не очевидно. Именно поэтому говорят, что бэкендерам лучше не давать писать фронт
@@НикитаНигматуллин-т1ы я не js-ник, но красоты не вижу. Какой-то сплит, джойн. Ясно, что это костыли, но зачем сплитить строку, если нам надо ее перевернуть?
Перед просмотром постаил на паузу и попробовал решить задачу. Вот что получилось :) const isPalindrome = str => str === str.split('').reverse().join('')
Первым на ум пришло развернуть строку и сравнить, но по индексам тоже вариант, имеет смысл, если длинная строка а у тебя последний индекс даст false и не придется крутить строки
Поставил на паузу, пока ты не написал, сделал сам вот так, в целом задача очень простая, вероятно она действительно просто для того чтобы посмотреть как человек размышляет. static boolean isPalindrome(String string){ boolean value = false; boolean result = true; if (string.length()%2!=0) value = true; String s1; String s2; if (value){ s1 = string.substring(0,string.length()/2+1); s2 = string.substring(string.length()/2-1); } else { s1 = string.substring(0,string.length()/2); s2 = string.substring(string.length()/2); } String s3 =""; for (int i = 0; i < s2.length(); i++) { s3+=s2.charAt(s2.length()-1-i); } s2 = s3; for (int i = 0; i < s1.length(); i++) { if(s1.charAt(i)!=s2.charAt(i)) { result = false; break; } } return result; }
Можно перевернуть это число и сравнить с исходным. Равны, значит это число есть полиндром, нет-нет. UPD: В кооментах увидел, что этот способ памятезатратный
Здравствуйте, многие почему-то сразу пишут именно о таком кейсе, я в комментах писал почему считаю что такое решение не лучший вариант показывать его на интервью, если интересно, можете заглянуть в комменты :)
Не все языки предоставляют возможность реверса + это может быть не строка, а число или массив. Способ в видео самый универсальный, который можно провернуть в многих языках. Я так же делал на питоне.
драсьте, я остановил на 2:53, прошел по ссылке гугл докс и пошёл пробовать сам. Буду сюда писать свои мысли Первое, что я заметил, это то, что параметр, который принимает функция isPalindrome это number. Но далее в console.log'ах можно увидеть, что ему передают не число, а строку с числом. Т.е. "контракт" использования этой функции - передача строки с числом. И там же функция isSumEven (другая задача), где также передаются строки с числами, но параметр называется string. Решив, что будь это TypeScript (с которым я не очень знаком), было бы странно увидеть "function isPalindrome (number: string): boolean {}", я поменял название параметра на string. Дальше, я сразу записал такое решение: function isPalindrome(string) { return string === string.split('').reverse().join(''); }; Вернулся сюда, почитал комменты, понял, что такой вариант не устраивает. LUL Дальше я написал такое решение: function isPalindrome(string) { // defining the middle index to know when to stop const middleIndex = Math.floor(string.length / 2); // comparing numbers. It will return false if the numbers are not the same. for (let i = 0; i < middleIndex; i++) { if (string[i] !== string[string.length - (i + 1)]) { return false; } } return true; }; Я прохожу по строке один раз, разузнав перед этим где середина и когда остановиться. Проверяю число string[i] с тем же по счёту числом с другой стороны string[string.length - (i + 1)]. Если они не совпадают, то число уже не палиндром, и я выхожу из функции с false. А теперь иду смотреть видео.
9:35 я правильно понял, что Вы не остановились в середине массива, а прошли его полностью, и это и является местом, где можно улучшить алгоритм? UPD: почитал комментарии, всё верно
Что насчёт такого isSumEven ? function isSumEven(numberAsString) { // transforming it to an array to use reduce() const characters = numberAsString.split(''); const sum = characters.reduce((prev, curr) => { return prev + (+curr); // Tried to use parseInt (looks better), but codesandbox requires radix argument for some reason, which is actually optional }, 0); return sum % 2 === 0; }
Твой комментарий прочел как записки сумасшедшего гения, в хорошем смысле. Но интересно было наблюдать за ходом ваших мыслей, жаль нет подписки, я бы еще почитал ваши комментарии в таком стиле :)
По поводу задачи на парность/непарность, оцените решение: function isSumEven(string) { return string.split('').reduce((acc, cur) => acc + +cur, 0) % 2 === 0; }
Пытаюсь разобраться и не могу въехать в запись "acc + +cur" . Зачем плюс перед cur? Т.е. оно работает, но я не могу понять почему. Разбирался полтора часа, по-честному. Пробовал ставить и убирать {} и всё равно до конца не понял. Документацию по reduce читал, другие ролики смотрел. Вот теперь решил спросить.
@@lastfornit Если мне не изменяет память, _+cur_ превратит *cur* в тип *number* . Тут, судя по всему, происходит дополнительная проверка/обработка, что бы JS не конкатенировал *acc* и *cur* как строки. _+сur_ это краткий эквивалент _Number(cur)_
Добрый день,очень интересно смотреть. Взялся учить яву и уже решал подобную задачу. class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next();// считали строку ArrayList alist = new ArrayList();// создали динамически массив alist alist.addAll(Arrays.asList(str.split(""))); // заполнили список символами // System.out.println(alist); ArrayList alist2 = new ArrayList(alist);// создали копию списка Collections.reverse(alist2);// перевернули // alist.addAll(alist2); // сложили массив //System.out.println(alist); // надо нормально вывести for (int i = 0; i
class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next();// лучше дать более точное имя -> stringWithPalindromeNumber/palindromAsString ArrayList alist = new ArrayList(); // лучше List alist = (опираемся на интерфейс, а на реализацию), и лучше дать meaninful имя, например symbols/listWithSymbols/symbolsList alist.addAll(Arrays.asList(str.split(""))); // лист выше можно вообще не создавать а сразу получать то что возвращает Arrays.asList в переменную List alist ArrayList alist2 = new ArrayList(alist);// можно обойтись без этого массива Collections.reverse(alist2);// В комментариях уже спрашивали почему я считаю что реверснуть строку это плохой вариант, можно почитать :) alist.addAll(alist2); // можно обойтись без этого массива, каждый новый массив - трата памяти, которая ограничена к сожалению // у листа есть перегруженный метод toString -> можно просто System.out.print(alist); for (int i = 0; i
Можно пробегать циклом не по всему стрингу, а только по половине слова т.к. вторую половину мы сразу же проверяем. Разделить длину массива на 2, отбрасывая остаток от деления если длина массива нечетная(т.к. это будет общее число). На четность можно проверить остатком от деления если он не равен нулю то нечётное.
то, что я придумал перед просмотром решения на жабе: boolean isPalindrom(int num){ if(num < 0) return false; String[] chars = new String(num).split(""); for(int i=0; i < chars.length/2; i++) if(!chars[i].equals(chars[chars.length-1-i)) return false; return true; }
Вы самый лучший, просто слушать вас так приятно, а еще и очень полезно, было бы здорово увидеть работу над реальным проектом на js от вас, удачи с развитием канала!!!!
Я аналитик, но на некоторых собеседованиях программерские навыки тоже спрашивают. Недавно на питоне предлагали написать throttler: есть лимит в 100 неких входящих на функцию сообщений в секунду. И когда он превышен - новому сообщению отказывать в отправке. Задача была на разработку алгоритма с эффективностью O(N). Вроде просто, кажется что джуниорский вопрос. Плюс очень часто спрашивают про результаты вычислений разных выражений, где надо внимательно следить за трюками индексации и понимать отличие типов данных.
На вскидку, связный список (годится даже односвязный) в который пишем время входящего сообщения, оперируем ссылками на первый и последний элемент и количеством элементов в списке, если количество меньше ста добавляем время сообщений в конец списка, если количество элементов 100 и время между первым элементом и входящим сообщением меньше секунды, то игнорируем сообщение, если больше, добавляем в список, идем по списку с первого элемента удаляя элементы, время которых отстоит от последнего добавленного более чем на секунду. В общем то задача на выбор правильной структуры для хранения списка, при условии, что необходимо удалять элементы из начала списка, проход по списку требуется с первого элемента и в одном направлении, все остальное псевдоматематический антураж.
@@denisn6408 в целом согласен, но! Удаление элемента из начала списка под капотом вызывает перезапись индексов всех остальных элементов. А это совсем контр-производительно. Попробуйте придумать, как обойти это ограничение)
@@Voronza Питонщики не знают что такое связный список? А какой структурой пользовались вы для решения этой задачи? В связном списке нет доступа по индексу, потому что в нем нет индекса)), в этом весь смысл связного списка, в односвязном списке у каждого элемента есть ссылка на следующий, т.е. обойти его можно только с первого элемента, обратно не получится, в двусвязном каждый элемент имеет ссылку на предыдущий и на следующий элемент. Поэтому процедура удаления первого элемента очень простая, он просто удаляется и если список двусвязный, то в элементе который идет следующим удаляется ссылка на удаляемый элемент.
@@denisn6408 простите, узколобо прочитал ваш предыдущий ответ. Пойду RTFM. Не питонячий, потому что гугление в рамках питона мне даёт это: "Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList".
@@clauseclause6640 Не, у вас строка может быть миллион символов, вам надо сначала эту строку развернуть, потом сохранить в память, а потом еще и сравнить, а операция сравнения кстати делается посимвольно самими инструментами языков програмирования. Это очень долго и не эффективно, гораздо быстрее просто пройти строку до половины. Эффективность алгоритма и подхода определяется только на больших данных, где может быть большой затрат памяти и большие задержки
@@itwithvitaly не могу согласиться. Во-первых, в вашем решении вы так же дублируете данные и используете лишнюю память, причем, без причины, ведь у строк можно точно так взять элемент по индексу и узнать длину через length. Встроенные методы в js и операция сравнения строк хорошо оптимизированны, и посимвольное сравнение здесь выполняться не будет в большинстве случаев. Опять же, даже посимвольное сравнение внутри движка js и тем более питона будет дешевле, чем создание цикла, итерация по нему, обращения к элементу по индексу и проверки условия на каждом шаге.
@@itwithvitaly и самое смешное, что ваше решение точно так же посимвольно проверяет строки, ведь вы в цикле проходите i от 0 до length, а не length // 2
@@itwithvitaly спасибо за ответ. Виталий, а не мог бы ты поднять тему в своих роликах про стандартизации в JS, что такое ECMAScript 6, es6, es2015. Почему в разных стандартах разные синтаксисы, например експорта/импорта функций. Где и какие стандарты требуются. JS, вроде как, по своей сути должен запускаться везде и на всем, а получается что даже маленький тестовый код нигде не запустишь, ни из консоли на NodeJs(установкой бабеля проблема не решается, ему надо еще скормить определенные пресеты), ни в браузере не запустить(помимо требуемого вебсервера, там тоже есть свой стандарт JS - CommonJS). Изучаю потихоньку фронт, и сам язык js не сложный, но вот эта вся обвязка вокруг него - ад.
Привет, наверное, немного опоздал, но все же спрошу. Хотел узнать, как вы так быстро перемещаетесь по коду между словами и строками? Это очень много экономит времени. Все, наверное, расписывать долго, может где-то есть видео или удобный лист шорткатов в вс коде? Заранее спасибо)
Я использую alt + стрелка влево/вправо (так на маке). Я когда-то очень давно делал видео по hotkeys, может будет полезно : ua-cam.com/video/hKrYyWXNMdc/v-deo.html
Очень интересное видео, но я хотел поинтересоваться одним вопросом. Я написал реализацию этой программы с помощью StringBuilder в Java(инициализировал стирнгбилдер с нашей строкой содержащейся внутри, потом сделал reverse и toString, после чего просто приравнял обычную строку с перевернутой и если они равны вернул true). Так вот, всё работает, всё прекрасно, но какая из вариаций будет более предпочтительна для собеседования, с простым циклом или моим способом?
@@itwithvitaly Только я не понимаю как это улучшит алгоритм, если и там и там можно просто сравнивать символы по индексу. Это просто лишнее действие на мой взгляд. Только если проверяем не просто число в виде строки а именно строку текста, например "А роза упала на лапу Азора", там и в нижний регистр это перевести и от пробелов избавиться, возможно потребуется массив. В JS не знаю, но в python массив не потребуется даже в этом случае.
@@СергейПресняков-о4р Улучшение в том, что не будет создаваться лишний массив, который будет занимать память. Можно делать решать без массива, не принципиально
@@itwithvitaly Я не так понял комментарий. Подумал что имеется ввиду будто преобразование строки в список как-то улучшит алгоритм, а не работа сразу со строкой. Спасибо.
I haven’t watched this cideo yet, but what about using stack, like in the parentheses problem? I think, that would be the same, except palindrome problem will be little bit harder
Спасибо большое, что доходчиво прояснили, зачем нужен index и -1 в итерации - для движения с конца. Как ни странно, до этого в сортировках были проблемы с понимаем этого.
@@tripinprogress2225 в массивах ответ ведётся с нуля. Типа первый элемент имеет индекс 0. А, допустим, если массив состоит из 5 элементов, то индекс 5 элемента будет 4.
Здравствуйте, решение работать будет, но я писал уже в комментах много раз почему не стоит показывать решение с риверсией строки на собесе. Если интересно можете заглянуть :) Еще предложу пару моментов к улучшению кода: 1. Если имя функции начинается на "is", "has", "should" то обычно в этом случае ожидают что из функции будет возвращен boolean. 2. У функции должно быть single responsibility (en.wikipedia.org/wiki/Single-responsibility_principle) , по-этому лучше 1 функция - 1 действие (решение)
@@itwithvitaly просто изначально єта функция просто отвечала на вопрос, полиндром ли это, поэтому такое название (просто не стал изменять название функции, а добавил решение в соответствии с домашним заданием). По этому же и добавлен второй функционал. А по поводу решения без реверса строк к сожелению не нашел(((( Очень хотелось бы порешать типичные задания, которые даются при техническом собеседовании на джуниора JS. Как это можно сделать? Очень буду благодарен, если отправите таковые на мыло matador.ivan.ym15@gmail.com
Спасибо за видео! Продолжай в том же духе! Java: private static String isSumEven(String numberAsString) { //write you code here String[] symbols = numberAsString.split(""); int sum = 0; for (int i = 0; i < numberAsString.length(); i++) { sum = sum + Integer.parseInt(symbols[i]); } return "The amount equals " + sum + " - " + ((sum % 2 == 0) ? "even" : "odd"); }
Спасибо! Пару замечаний для улучшения: 1) Если название метода начинается с "has", "is", "should" то ожидается, что он будет возвращать булеан, как и в нашем случаи :) 2) Алгоритм хороший, работать будет быстро, но если например работали уже с Java 8 Stream API , то можете попробовать эту задачу решить с помощью лямбда выражений :)
Вот так ещё на python def is_palindrome(string): # индексы начала и конца строки i = 0 j = len(string) - 1 # i и j встречаются на середине строки while i < j: if string[i] != string[j]: return False i += 1 j -= 1 return True
Привет. Как я понял твой алгоритм ломается если чисел количество элементов нечётное. В твоём примере так совпало что 12345 и не четное и не палиндром. А если бы было 12321? И пока ты решал подумал про такой метод - ты получил массив Char, можно сделать временный массив.reverse () ( в свифте) и сравнить эти два массива на идентичность
Это не эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Агонь, но более искушенные и иногда (****) итервьюверы, ждут чего-то наподобие: function isPolindrome(numberAsString) { let characters = numberAsString.split(''); for (let index = 0; index < characters.length / 2; index++ ) { // тут важно показать, что для полиндрома достаточно сложность O(N/2) if (characters[index] !== characters[characters.length-1-index]) { return false; } } return true; } isPolindrome('123321');
Хороший пример, но, 2 момента для улучшения в вашем алгоритме: 1. Проверка на парность числа, а что если число будет 12521? Кол-во символов ведь не парное, но число палиндром. 2. Круто что вы еще написали сложность O (n/2), но не забывайте что при расчете сложности алгоритма константные числа не учитываются, т.е. O(n/3), O(n*15), O(n/2) это все равно в конечном счете дает нам O(n)
@@itwithvitaly 1. ++, условие лишнее 2. она конечно формально O(N), но это как раз и есть уточнение в рамках обработки(performance) - когда делают оптимизации, это учитывают с сумме с таймингами выполнения (если массив делить пополам, то реально на триллионе будет разница в таймингах отработки между - N и N/2)
Почему нельзя создать новую строку, развернуть и сравнить их? Видел такую задачу, только доп.условие там было - является ли строка палиндромом с учетом перестановки символов.
В комментариях уже задавали такой вопрос, можете почитать я описывал подробно. Если кратко: Потому что строка может быть очень большая и такая операция будет очень медленной
@@clauseclause6640 Потому что идти во 1 можно только до половины, во вторых вы мало того что ее разворачиваете, так еще и потом делаете операцию сравнения, для того чтобы сравнить две строки инструменты языка программирования сравнивают две строки посимвольно, хоть нам как пользователям языка это и не видно. А также колоссальные затраты по памяти по сравнению с решением с циклом.
Из 30+ собесов на которых я был и 25+ где проводил сам с другими собеседующими, только однажды была задача на рекурсивных обход дерева (нужно было папки обойти). В основном дают что-то попроще особенно на Джуниор вроде Палиндрома, работа со строками или оптимизация работы с массивом. Но обычно 60-90% собеседования это теория и задачи на "подумать"
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
Внесу свои пять копеек. Не заметил в комментах такого решения: const isPalindrome = str => str.split('').every((element, index, array) => element === array[array.length - 1 - index]);
Привет, да, такого не было еще :) Единственное что, every() обычно пойдет до конца массива, чтобы проверить предикат, и даже если сделаешь return это особо не поможет, т.к. у нас просто функция и return по сути остановит только ее выполнение, а не все выражение every. В этом минус, конечно, с обычным циклом можно сразу все выполнение оборвать, если вдруг число не Палиндром.
@@itwithvitaly Почему же? Выполнение функции every() будет остановлено, если callback функция вернет false. Оставшиеся элементы массива обработаны не будут.
@@itwithvitaly ха, какой занятный момент. Только после этого коммента задумался, что это таки может быть "украинский слэнг", понятный не всем)) До этого и мысли не возникало, что нет такого термина и могут быть сложности с его пониманием (парное/не парное) :)
Недавно занялся js, в этом задании просто развернул число в строке и сравнил, и все. А так, конечно split делает массив из строки, reverse переворачивает массив и join собирает обратно в строку, осталось сравнить и всё
Ахахах, буквально недавно решал эту задачу с сайта проекта Эйлера, но делал это немного другим методом. Рад, что такие простые задачки бывают на собеседованиях, аж гора с плеч
Честно сначала решения задачи первое о чем подумал так это инициализировать массив типа char с длиной равной длине строки, которую подаем на вход методу, а потом в цикле пройтись и в каждую ячейку с помощью метода charAt() подоставать символы из строки и таким образом сформировать массив из символов. но стоило ли так напрягаться когда есть готовый метод который делает все выше написанное в одну строку. Теперь я понял почему однажды провалил интервью. Автор верно сказал о том что должно быть как можно меньше манипуляций. Абракадабра в коде никому не нужна.
Неожиданным для меня оказался такой if, он сделал код более компактным, просто я решил эту задачу используя nested for ну и разумеется, не помешало бы в код добавить break после присвоения булевому значению false в случае, если значения чисел не совпали, чтобы оптимизировать код и не делать лишних проверок, но такое решение поставленной задачи мне понравилось, благодарю!
а я бы сделал бы как то так (C#) var charNumbers = numbers.ToCharArray(); return charNumbers.Reverse().ToString() == numbers ? true : false; Можете оценить что вы думаете по поводу данного решения?
Блин, я бы не додумался до такого) Я бы создал внутри метода новую переменную, которой присвоил бы ревеснутое значение аргумента метода, а потом просто сравнил его с аргументом)
Я только начал изучать JS (прошел основы), можете, пожалуйста сказать, это видео примерно для какого уровня? То есть эту задачу могут спросить на собеседовании на джуна, спасибо за видео.
Здравствуйте, это видео в целом для всех уровней, потому что такого рода задачи задают как и начинающим на собеседованиях, так и Senior-ам с несколькими годами опыта.
Мне больше всего нравится такой вариант: function isPalindrome(str) { for (let i = 0, let j = str.length-1; i < str.length / 2; i++, j--) { if (str[i] !== str[j]) { return false } } return true }
In my opinion you may loop one too many times if a number of chars in an input string is odd. let k; if (str.length % 2 !== 0) { k = str.length/2 - 1 } for (let i = 0, let j = str.length-1; i < k; i++, j--) { ... } Example: The input string contains an odd number of chars (lets say 5) than you need to loop 2 times, not 3. Am I right?
Был похожий вопрос дальше. Реверсия строки - плохо. Нужно полностью перебрать строку, сохранить риверсивную копию в память и затем еще и сравнение сделать - очень затратно и очень не оптимально. Гораздо проще 1 циклом перебрать
Чувак, а мы не проходимся 2 раза по одним и тем же элементам разве?(после того, как доходим до середины массива) Почему нельзя до середины массива проверять? index
c++: bool isPalindrom(string str) { for (size_t i = 0; i < str.size() / 2; i++) if (str[i] != str[str.size() - 1 - i]) return false; return true; } про деление на 2 посмотрел в комментах, даже не подумал об этом)
А в питоне: 1) def func(numb: str): return number == number[ : :-1] 2) return 'Pair' if len(str(sum([int(x) for x in numb]))) % 2 == 0 else 'notPair' Какой всё-таки питон лаконичный))
А я бы строку спарсил бы в int, далее создал бы новую переменную и присвоил бы ей значение спарсенной строки. Далее методом reverse я бы вторую переменную бы изменил. И далее сравнил бы два числа, если они идентичны, то это палиндром.
Отлично. Единственное что, я бы не делал вот этого numberAsString = numberAsString.toString(); Точнее если бы и делал, то в другую переменную. С точки зрения работоспособности кода с ним ничего не произойдет если сделать как вы написали, но с точки зрения стиля кода обычно не меняют входные параметры.
@@itwithvitaly знаю, убрал до вашего комментария. Надеюсь браузеры начнут таки поголовно использовать typescript чтобы необходимость в перестраховках отпала.
Я как то делал такое тестовое задание, правда в описании тз палиндром был словом а не цифрой. Но не в этом суть. Хочу дополнить что не обязательно проходить индексом весь массив целиком, достаточно пройти половину округленную в большую сторону.
вообще-то в меньшую, поскольку для массива нечетной длины округление половины длины в большую сторону, заставит вас сравнить элемент сам с собой, так как последний будет центром и встретится лишь в единичном экземпляре, а для четной длины число всегда будет целым и округление ничего не даст.
Здравствуйте Виталий, спасибо за ваши видео на Python придумал такие решения, синтаксис и логика будут отличаться, от С- подобных языков, о которых вы упомянули в начале видео. def isPalindrome(string): return string == string[::-1] def isaSumEven(string): templist = map(int, list(string)) return sum(templist) % 2 == 0
Здравствуйте, ваше решение работать будет но это не совсем эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Логика не особо отличается по логике так же можно написать на любом языке взять слайс строк и развернуть потом сравнить по синтаксису такой же синтаксис может быть в любом языке где поддерживается такой же сахар над слайсами)) Ну я не знаю, если честно стоит ли писать в таком стиле на интервью потому что у интервьюера могут появиться к Вам лишнее вопросы например сколько берет памяти такой алгоритм или алацируется ли новая память под этот слайс или это происходит инплейс и тд но если вы хорошо знаете все эти нюансы в языке то конечно и так можно писать
Я подумал привести к массиву, развернуть, привести обратно к строке, проверить. А в твоем варианте можно в условие добавить, что бы индекс был не больше половины от длинны массива. Эта задача не выглядит сложной. Я думал на собеседовании что-то жутко страшное
С реверсией это простой вариант, не очень подходит для собесов, в комментах много раз писал почему, можете заглянуть, если хотите :) Не, страшного ничего не спрашивают, по алгоритмам сильные собесы обычно в Западные компании, в СНГ по алгоритмам обычно не сильно гоняют:)
Я бы предпочёл сделать новую функцию, которая была бы рекурсивной, сравнивала елементы и если они равны - вызывалась со следующлими, а если же нет, то возвращала false
А никакой проблемы и нет, можно показать, но обычно в таких задач в основном оценивается алгоритмическая подготовка, чем знания конкретных инструментов языка. Т.е. если вас попросят перевернуть связный список, это не значит что надо сделать Collection.reverse(myList) и на этом закончить. Тут интересует скорее как вы это с нуля напишите без утилитных методов самого языка.
Виталий, at the best of my knowledge, strings are arrays in all the languages (well, at least in those that I know). That means you don't need to use a split() function. You can access a character in a string right away like this : let mySting = 'aaaaa'; let index = i; i = 2; let char = mySting[i];
Hi, it can be the solution as well, yes. But to be more precise in most of the popular languages the strings are not arrays itself. It's better to say that the API of the languages gives us the possibility to treat and work the strings in some cases as arrays. For example, get the actual string length or get the character by index :)
@@itwithvitaly Well, strings are datatypes and for any datatype we need to know how memory for it gets allocated. In majority of languages memory allocated for a fixed/immutable array (I agree, maybe this is not always a case). You don't need to reply, but if you would like to than use Russian.
это наверно в 2008 давали на интервью, почитайте более современные статьи, а вообще обычно на интервью дают задачи с таких площадок как литкод или кодварс, ну и раз уж тут js, то также тестят стэк библиотечный заданиями а-ля создай список чекбоксов на реакте\вью\ангуляре
Если бы мне задали подобную задачу, то я бы задумался стоит ли тратить время на данную компанию, т.к. на собеседовании должны задаваться реально толковые вопросы, а не какая-то ерундистика которую на практике никто применять не будет, я не разу не сталкивался с задачами по палиндрому, по крайней мере строк, с объектами ещё можно что-то придумать. Как по мне вопросы должны быть максимально приближёнными к практике, без этого не смысла в собеседовании. Человек может знать теорию, проштудировать кучу заданий для собеседования, но когда ему дадут к примеру простую задачу (для фронта) сделать так чтоб элемент отображался только если он на экране более 1 секунды, а затем убирался из отслеживания видимости. Тут скорее всего собеседуемый сядет в лужу, т.к. с этим сталкиваются на практике постоянно, но в уроках по супер-пупер изи прохождению собеседований подобного не встречал.
У меня бы такой код не прошёл ревью :) Надо добавить break в цикл, плюс по всему массиву идти не надо, только до середины, иначе получается двойная работа.
@@ЕвгенийАлексеев-о9э для того, чтобы если например в начале цифры не совпали то прерывать цикл так как без брейк он проверит все равно его до конца, а это не имеет смысла- пустая трата ресурсов и времени
Цикл в пол длины текста, сравниваем синхронно с начала и с конца, если не совпадает выводим "false" и используем "break" что бы завершить бессмысленное продолжение перебора, иначе перебераем до конца и выводим "true"
По сути и тернарник то не нужен, сравнение вернет true / false. А так автор видео писал что: "Не, строка может быть очень большой, на такое решение расходуется очень много памяти и времени. Если интересно можете в комментах посмотреть, я там развернуто отвечал как раз на этот вопрос :)" и " Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка."
Здравствуйте, как я уже многим и писал такое решение работать будет, но проблема в том что когда мы пытаемся решить какую-то задачу, нам нужно найти максимально быстрый и эффективный по памяти алгоритм. В данном случае все ок будет работать если строка будет маленькая, а представьте если строка будет миллион символов. Нам прийдется развернуть всю строку, сделать новую на такой же миллион символов, выделить на нее такое же кол-во памяти , т.е. 2 строки по миллиону, а потом еще и сделать сравнение, которое кстати языком программирования проводится посимвольно, поэтому я рекомендую использовать цикл, там будет всего 1 проход и всего до половины строки. Эффективность алгоритма определяется на больших данных.
@@itwithvitaly да, вы правы, в случае строки с миллионом символов, пожалуй, стандартный js-алгоритм реверса будет отрабатывать заметно медленнее, но я написал именно такое решение, потому что речь шла о числах - ну пусть 20-значное число будет обрабатываться, к примеру. В таком случае потери времени будут минимальными. Просто смотря для чего данную функцию применять.
я решал, как раз на онлайн собесе задачку на полиндром... но я просто разрезал и через reverse разворачивал, сравнивал и всё :) к тому же это можно в одну строку сделать
@@SVP-d1d да, есть такой способ. Он мне тоже сразу на ум пришёл. Но при больших строках это займет много времени потому что строка будет проходиться минимум три раза (полностью) . И как собес прошёл? Тебя взяли на работу? Какие ещё задачи там были?
@@ReAgent003 дальше завалили, на прототипах и асинхронщине :) а дальшееее.... только "извините, без коммерческого опыта 1-2+ года нам неочем с вами разговаривать" :)
@@ReAgent003 та то просто один собес вспомнил на котором была задачка с полиндромом :) на нём просто завалили... позиция react . А так то уже давненько, как-то поработал на вордпресс но плюнул и последние пол года ковырял react. Но тут беда, или ты с опытом или ты без работы
Хотелось бы еще, чтоб испытуемый спросил, что делать если строка null или nan. Пустая строка, понятно, является палиндромом, но об этом все равно лучше подумать :)
![[Ответы] Java Junior реальное собеседование | ООП, Java Core | Часть1](/img/n.gif)
Цикл должен быть до length/2. У вас в 2 раза больше работы выполняется.
Upd: и если на i-том индексе условие не совпало, нужно сразу возвращать фолс, а не идти до конца цикла.
На самом деле, в 4, так как нет return
Господи, то, что надо писать за 2 строчки, растягивается на хрен знает сколько..
Так и есть, я написал об этом в доке, ссылка на которую есть в комментах. Там сказано что мой алгоритм не оптимальный и его можно улучшить, что вы, собственно и сделали.
Я уже писал почему решение с риверсией не подходит для тех интрвью, если интересно - можете заглянуть :)
@@itwithvitaly Ну я про 2 строчи говорил не про решение с реверсом, а, условно:
for (size_t index = 0; index < collection.size() / 2; index++) if (collection[index] != collection[collection.size() - index - 1]) return false;
return true;
На js что-то вроде этого тоже должно быть
И break добавить, при первом не совпадении. А я удивляюсь почему приложения зависают.
Your for loop is not optimal :) You don't need to loop through all the characters (index < characters.length), you only need to loop through half of them (index < characters.length/2). If you have a very long string which IS a palindrome, you're just looping through the second half of it unnecessarily.
Exactly, I’ve left the link to the google document in the comments where I described that my algorithm is not optimal with the suggestion that people who are watching this video would have the space to think and can make it more effective :)
and you should use break if element from begin is not equal element from the end to stop the circle ;)
@@torburgmax yup, 'isPalindrome = false' is OK, but I guess just a plain old 'return false' would be better? :)
@@whythisisntchanging more than one return from the function isn't in best code practices I think.
@@torburgmax ???
Хм, хорошее решение! Я думал по другому, переворачивать строку
string.split('').reverse().join('')
делаем из строки массив символов, переворачиваем массив и объединяем снова в строку, ну и потом в условии сравниваем
кстати на Питоне ещё легче)
string[::-1]
12345 - 54321
А на пыхе можно через array_reverse )
Я раньше решал эту задачу полностью разворачивая число и сравнивая с исходным, но этот способ показался мне более эффективным и простым. Я переписал на ваше решение на JAVA вот метод:
public static void palindrome(String str) {
String[] string = str.split("");
boolean palindrome = true;
for(int i = 0;i < string.length / 2;i++) {
if(Integer.parseInt(string[i]) != Integer.parseInt(string[string.length - 1 - i])) {
palindrome = false;
break;
}
}
System.out.println(palindrome);
}
Я не знаю как в происходит в JS, но в JAVA при сравнении ссылочных типов данных сравниваются именно ссылки, а не содержание строки, поэтому я использовал классы обертки, чтобы перевести строку в интеджер. Жду критики, т.к я новичок и многого ещё недопонимаю
Все гуд, алгоритм хороший, пару моментов к улучшению:
1. Лучше назвать метод isPalindrome, "is" здесь означает что метод будет возвращать boolean (naming convention)
2. Из метода лучше возвращать boolean вместо вывода строки, потому что этим методом можно пользоваться как утилитным в разных местах.
3. Если соблюдать пункт 1 и пункт 2 то там где у вас стоит break, можно будет сразу делать return.
@@itwithvitaly хорошо, спасибо за обратную связь
9:15 можно поставить условие если index >= Math.floor(characters.length / 2), то выйти из цикла, чтобы не проходить лишние итерации. Переменная isPalindrome здесь не нужна, можно просто return true или return false
Math.floor не нужен, так как целое/целое = целое.
@@mormeoi 7 / 2 = 3.5
@@piggy7461 Нет. Читайте Java Language Specification пункт 15.17.2. Division Operator /
@@mormeoi Ну в джаве мб так и есть, я не знал :)
@@piggy7461 Так скорее всего во всех языках, которые наследуют синтаксис от Си. В питоне тоже так было до 3й версии.
Функция проверки палиндрома строки для python:
def figure(number):
return number == number[::-1]
Сколько будет занимать памяти такое решение ?
В js тоже можно написать в одну строку
return str === str.split('').reverse().join('')
она будет занимать n*3 вроде как а в питоне сколько?
@@trypophobia7497 изучите временную сложность алгоритмов. Цикл всегда дольше выполняется чем проверка равенства.
Да и слайс всё-таки должен быть быстрее чем сплит, реверс, джоин)
@@47clere я тут не писал про временную сложность я тут спросил сколько будет занимать ПАМЯТИ ????? вы прочитай комментарий внимательно! если в цикле будет константное значение то BIG O будет равно O(1) так же как и в сравнении на равенство О(1) а если нет то в цикле O(n) (сейчас я не говорю про то что в цикле будет быстрее или равно я говорю про BIG O) я спрашивал про память копируется ли этот слайс в снова в новую память или нет? в js будет создаваться новые массивы
Используя возможности JS, я бы записал так:
Function isPalindrome(str) {
return (str.split('')
.reverse()
.join('') === str) ? true : false
}
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
Тирнарный оператор тут лишний, выражение и так булево
С точки зрения "красоты" кода, я согласен.
return str.split('').reverse().join('') === str очень компактная запись.
С точки зрения производительности... Ну, такое себе. Если я правильно понимаю, создается промежуточный массив, который потом собирается обратно. Сложность алгоритма О(3n) = n + n + n, соответственно n на разделение, на разворот и на джойн.
Алгоритм который имеет сложность O(n/2)
function isPalindrome(str) {
for (let i = 0; i < Number(str.length / 2); i++) {
if (str.charAt(i) !== str.charAt(str.length - 1 - i)) {
return false;
}
}
return true;
}
@@НикитаНигматуллин-т1ы javascript не тот язык, где имеет смысл сравнивать O(n/2) и O(3n), для js, с учетом браузерных оптимизаций это капля в море. Куда большее значение имеет читабельность, так вот в случае с reverse() читабельность кода в разы лучше, код яснее. А тут, что вы пытались запихнуть в цикл for далеко не очевидно. Именно поэтому говорят, что бэкендерам лучше не давать писать фронт
@@НикитаНигматуллин-т1ы я не js-ник, но красоты не вижу. Какой-то сплит, джойн. Ясно, что это костыли, но зачем сплитить строку, если нам надо ее перевернуть?
Я очень сильно ждал новые видео!! Ура)
спасибо)
Перед просмотром постаил на паузу и попробовал решить задачу. Вот что получилось :)
const isPalindrome = str => str === str.split('').reverse().join('')
Первым на ум пришло развернуть строку и сравнить, но по индексам тоже вариант, имеет смысл, если длинная строка а у тебя последний индекс даст false и не придется крутить строки
Мне тоже это первое а голову пришло
Поставил на паузу, пока ты не написал, сделал сам вот так, в целом задача очень простая, вероятно она действительно просто для того чтобы посмотреть как человек размышляет.
static boolean isPalindrome(String string){
boolean value = false;
boolean result = true;
if (string.length()%2!=0) value = true;
String s1;
String s2;
if (value){
s1 = string.substring(0,string.length()/2+1);
s2 = string.substring(string.length()/2-1);
} else {
s1 = string.substring(0,string.length()/2);
s2 = string.substring(string.length()/2);
}
String s3 ="";
for (int i = 0; i < s2.length(); i++) {
s3+=s2.charAt(s2.length()-1-i);
}
s2 = s3;
for (int i = 0; i < s1.length(); i++) {
if(s1.charAt(i)!=s2.charAt(i)) {
result = false;
break;
}
}
return result;
}
Можно перевернуть это число и сравнить с исходным. Равны, значит это число есть полиндром, нет-нет.
UPD: В кооментах увидел, что этот способ памятезатратный
А ещё лучше перевернуть половину и сравнить с другой половинной
Здравствуйте, многие почему-то сразу пишут именно о таком кейсе, я в комментах писал почему считаю что такое решение не лучший вариант показывать его на интервью, если интересно, можете заглянуть в комменты :)
Не все языки предоставляют возможность реверса + это может быть не строка, а число или массив. Способ в видео самый универсальный, который можно провернуть в многих языках. Я так же делал на питоне.
драсьте, я остановил на 2:53, прошел по ссылке гугл докс и пошёл пробовать сам.
Буду сюда писать свои мысли
Первое, что я заметил, это то, что параметр, который принимает функция isPalindrome это number.
Но далее в console.log'ах можно увидеть, что ему передают не число, а строку с числом.
Т.е. "контракт" использования этой функции - передача строки с числом.
И там же функция isSumEven (другая задача), где также передаются строки с числами, но параметр называется string.
Решив, что будь это TypeScript (с которым я не очень знаком), было бы странно увидеть "function isPalindrome (number: string): boolean {}", я поменял название параметра на string.
Дальше, я сразу записал такое решение:
function isPalindrome(string) {
return string === string.split('').reverse().join('');
};
Вернулся сюда, почитал комменты, понял, что такой вариант не устраивает. LUL
Дальше я написал такое решение:
function isPalindrome(string) {
// defining the middle index to know when to stop
const middleIndex = Math.floor(string.length / 2);
// comparing numbers. It will return false if the numbers are not the same.
for (let i = 0; i < middleIndex; i++) {
if (string[i] !== string[string.length - (i + 1)]) {
return false;
}
}
return true;
};
Я прохожу по строке один раз, разузнав перед этим где середина и когда остановиться.
Проверяю число string[i] с тем же по счёту числом с другой стороны string[string.length - (i + 1)].
Если они не совпадают, то число уже не палиндром, и я выхожу из функции с false.
А теперь иду смотреть видео.
ахахаха, я остановил прямо перед переименованием в numberAsString))))
9:35
я правильно понял, что Вы не остановились в середине массива, а прошли его полностью, и это и является местом, где можно улучшить алгоритм?
UPD: почитал комментарии, всё верно
Что насчёт такого isSumEven ?
function isSumEven(numberAsString) {
// transforming it to an array to use reduce()
const characters = numberAsString.split('');
const sum = characters.reduce((prev, curr) => {
return prev + (+curr); // Tried to use parseInt (looks better), but codesandbox requires radix argument for some reason, which is actually optional
}, 0);
return sum % 2 === 0;
}
Хорошее решение isSumEven! Единственное я бы лучше сделал либо как вы сказали через parseInt, потому что +(+cur) чучуть ухудшает читаемость кода
Твой комментарий прочел как записки сумасшедшего гения, в хорошем смысле. Но интересно было наблюдать за ходом ваших мыслей, жаль нет подписки, я бы еще почитал ваши комментарии в таком стиле :)
По поводу задачи на парность/непарность, оцените решение:
function isSumEven(string) {
return string.split('').reduce((acc, cur) => acc + +cur, 0) % 2 === 0;
}
Да, супер! Я точно также ее решил.
Пытаюсь разобраться и не могу въехать в запись "acc + +cur" . Зачем плюс перед cur? Т.е. оно работает, но я не могу понять почему. Разбирался полтора часа, по-честному. Пробовал ставить и убирать {} и всё равно до конца не понял. Документацию по reduce читал, другие ролики смотрел. Вот теперь решил спросить.
@@lastfornit Если мне не изменяет память, _+cur_ превратит *cur* в тип *number* . Тут, судя по всему, происходит дополнительная проверка/обработка, что бы JS не конкатенировал *acc* и *cur* как строки. _+сur_ это краткий эквивалент _Number(cur)_
Добрый день,очень интересно смотреть. Взялся учить яву и уже решал подобную задачу.
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.next();// считали строку
ArrayList alist = new ArrayList();// создали динамически массив alist
alist.addAll(Arrays.asList(str.split(""))); // заполнили список символами
// System.out.println(alist);
ArrayList alist2 = new ArrayList(alist);// создали копию списка
Collections.reverse(alist2);// перевернули
//
alist.addAll(alist2); // сложили массив
//System.out.println(alist);
// надо нормально вывести
for (int i = 0; i
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.next();// лучше дать более точное имя -> stringWithPalindromeNumber/palindromAsString
ArrayList alist = new ArrayList(); // лучше List alist = (опираемся на интерфейс, а на реализацию), и лучше дать meaninful имя, например symbols/listWithSymbols/symbolsList
alist.addAll(Arrays.asList(str.split(""))); // лист выше можно вообще не создавать а сразу получать то что возвращает Arrays.asList в переменную List alist
ArrayList alist2 = new ArrayList(alist);// можно обойтись без этого массива
Collections.reverse(alist2);// В комментариях уже спрашивали почему я считаю что реверснуть строку это плохой вариант, можно почитать :)
alist.addAll(alist2); // можно обойтись без этого массива, каждый новый массив - трата памяти, которая ограничена к сожалению
// у листа есть перегруженный метод toString -> можно просто System.out.print(alist);
for (int i = 0; i
@@itwithvitaly , спасибо.
Можно пробегать циклом не по всему стрингу, а только по половине слова т.к. вторую половину мы сразу же проверяем. Разделить длину массива на 2, отбрасывая остаток от деления если длина массива нечетная(т.к. это будет общее число). На четность можно проверить остатком от деления если он не равен нулю то нечётное.
Алексей Чумаков Все правильно)
Идея супер
то, что я придумал перед просмотром решения на жабе:
boolean isPalindrom(int num){
if(num < 0)
return false;
String[] chars = new String(num).split("");
for(int i=0; i < chars.length/2; i++)
if(!chars[i].equals(chars[chars.length-1-i))
return false;
return true;
}
Буду благодарен , если в одном из следующих видео расскажешь про open source( как там взять проект для новичка).
Юрій Бережний Хорошо, запишу себе эту тему
Вы самый лучший, просто слушать вас так приятно, а еще и очень полезно, было бы здорово увидеть работу над реальным проектом на js от вас, удачи с развитием канала!!!!
Большое спасибо! :)
Какую книгу по алгоритмам вы упоминали? И какие посоветуете?
Упоминал книгу "Cracking the coding interview". Посоветовать смогу, но нужно знать что именно вы хотите почитать и на какую тему :)
При проверке на палиндром можно сделать так:
...
for (let index = 0; index
На счет сложности вы правы, итак итак будет в конечном счете O(n), но если будет собес, скорее всего захотят увидеть вариант именно с O(n/2)
Нет, О(n) != O(n // 2), асимптотика вычисляется по худшему сценарию, но для практических задач корректнее использовать среднюю сложность
@@achillescres9270 O(n) == O(n/2), потому что при оценке сложности алгоритма не учитываются константные значения. Это сокращение валидное.
Мне кажется, что лучше целочисленно делить:
characters.length%2
Ибо зачем сравнивать центр с самим собой у строк с нечетной длиной?
Я аналитик, но на некоторых собеседованиях программерские навыки тоже спрашивают. Недавно на питоне предлагали написать throttler: есть лимит в 100 неких входящих на функцию сообщений в секунду. И когда он превышен - новому сообщению отказывать в отправке. Задача была на разработку алгоритма с эффективностью O(N). Вроде просто, кажется что джуниорский вопрос. Плюс очень часто спрашивают про результаты вычислений разных выражений, где надо внимательно следить за трюками индексации и понимать отличие типов данных.
Круто, хорошая задача. Мне ее где-то тоже задавали.
На вскидку, связный список (годится даже односвязный) в который пишем время входящего сообщения, оперируем ссылками на первый и последний элемент и количеством элементов в списке, если количество меньше ста добавляем время сообщений в конец списка, если количество элементов 100 и время между первым элементом и входящим сообщением меньше секунды, то игнорируем сообщение, если больше, добавляем в список, идем по списку с первого элемента удаляя элементы, время которых отстоит от последнего добавленного более чем на секунду. В общем то задача на выбор правильной структуры для хранения списка, при условии, что необходимо удалять элементы из начала списка, проход по списку требуется с первого элемента и в одном направлении, все остальное псевдоматематический антураж.
@@denisn6408 в целом согласен, но! Удаление элемента из начала списка под капотом вызывает перезапись индексов всех остальных элементов. А это совсем контр-производительно. Попробуйте придумать, как обойти это ограничение)
@@Voronza Питонщики не знают что такое связный список? А какой структурой пользовались вы для решения этой задачи? В связном списке нет доступа по индексу, потому что в нем нет индекса)), в этом весь смысл связного списка, в односвязном списке у каждого элемента есть ссылка на следующий, т.е. обойти его можно только с первого элемента, обратно не получится, в двусвязном каждый элемент имеет ссылку на предыдущий и на следующий элемент. Поэтому процедура удаления первого элемента очень простая, он просто удаляется и если список двусвязный, то в элементе который идет следующим удаляется ссылка на удаляемый элемент.
@@denisn6408 простите, узколобо прочитал ваш предыдущий ответ. Пойду RTFM. Не питонячий, потому что гугление в рамках питона мне даёт это: "Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList".
def is_palindrom(string):
return string == string[::-1]
Пайтон. По скорости и памяти не очень, но как вариант)
Удобное решение конечно :) Но на собесах обычно просят именно алгоритм) Но ваш вариант работать будет тоже конечно)
@@clauseclause6640 Не, у вас строка может быть миллион символов, вам надо сначала эту строку развернуть, потом сохранить в память, а потом еще и сравнить, а операция сравнения кстати делается посимвольно самими инструментами языков програмирования. Это очень долго и не эффективно, гораздо быстрее просто пройти строку до половины. Эффективность алгоритма и подхода определяется только на больших данных, где может быть большой затрат памяти и большие задержки
@@clauseclause6640 4 секунды? Ответ с комплексной логикой в большом приложении может меньше секунды занять, что-то здесь не так.
@@itwithvitaly не могу согласиться. Во-первых, в вашем решении вы так же дублируете данные и используете лишнюю память, причем, без причины, ведь у строк можно точно так взять элемент по индексу и узнать длину через length. Встроенные методы в js и операция сравнения строк хорошо оптимизированны, и посимвольное сравнение здесь выполняться не будет в большинстве случаев. Опять же, даже посимвольное сравнение внутри движка js и тем более питона будет дешевле, чем создание цикла, итерация по нему, обращения к элементу по индексу и проверки условия на каждом шаге.
@@itwithvitaly и самое смешное, что ваше решение точно так же посимвольно проверяет строки, ведь вы в цикле проходите i от 0 до length, а не length // 2
Буду ждать курса от вас)
Спасибо!
Я бы без массива делал, работал со строкой, а в цикл for поставил условие i
Отлично! Можно и так как альтернатива, так тоже будет быстро работать
@@itwithvitaly спасибо за ответ. Виталий, а не мог бы ты поднять тему в своих роликах про стандартизации в JS, что такое ECMAScript 6, es6, es2015. Почему в разных стандартах разные синтаксисы, например експорта/импорта функций. Где и какие стандарты требуются. JS, вроде как, по своей сути должен запускаться везде и на всем, а получается что даже маленький тестовый код нигде не запустишь, ни из консоли на NodeJs(установкой бабеля проблема не решается, ему надо еще скормить определенные пресеты), ни в браузере не запустить(помимо требуемого вебсервера, там тоже есть свой стандарт JS - CommonJS).
Изучаю потихоньку фронт, и сам язык js не сложный, но вот эта вся обвязка вокруг него - ад.
А если еще сделать принудительную остановку цикла, как только найдена неравная пара, чтобы остальное не проверять?
Так и нужно :)
Привет, наверное, немного опоздал, но все же спрошу. Хотел узнать, как вы так быстро перемещаетесь по коду между словами и строками? Это очень много экономит времени. Все, наверное, расписывать долго, может где-то есть видео или удобный лист шорткатов в вс коде? Заранее спасибо)
Я использую alt + стрелка влево/вправо (так на маке). Я когда-то очень давно делал видео по hotkeys, может будет полезно : ua-cam.com/video/hKrYyWXNMdc/v-deo.html
@@itwithvitaly спасибо большое! :)
Очень интересное видео, но я хотел поинтересоваться одним вопросом. Я написал реализацию этой программы с помощью StringBuilder в Java(инициализировал стирнгбилдер с нашей строкой содержащейся внутри, потом сделал reverse и toString, после чего просто приравнял обычную строку с перевернутой и если они равны вернул true). Так вот, всё работает, всё прекрасно, но какая из вариаций будет более предпочтительна для собеседования, с простым циклом или моим способом?
В комментариях сам нашел ответ. Спасибо за видео
Спасибо !:)
@@maksymholovenko2795 Так,как предпочтительней?)
А в JS нельзя обращаться к символам строки по индексам? Почему мы преобразуем её в массив?
Можно, это как одно из улучшений алгоритма можно рассмотреть, но на самом деле для скорости и работоспособности алгоритма это не будет существенным
@@itwithvitaly Только я не понимаю как это улучшит алгоритм, если и там и там можно просто сравнивать символы по индексу. Это просто лишнее действие на мой взгляд. Только если проверяем не просто число в виде строки а именно строку текста, например "А роза упала на лапу Азора", там и в нижний регистр это перевести и от пробелов избавиться, возможно потребуется массив. В JS не знаю, но в python массив не потребуется даже в этом случае.
@@СергейПресняков-о4р Улучшение в том, что не будет создаваться лишний массив, который будет занимать память. Можно делать решать без массива, не принципиально
@@itwithvitaly Я не так понял комментарий. Подумал что имеется ввиду будто преобразование строки в список как-то улучшит алгоритм, а не работа сразу со строкой. Спасибо.
Очень хорошое видео!
I haven’t watched this cideo yet, but what about using stack, like in the parentheses problem? I think, that would be the same, except palindrome problem will be little bit harder
А время на решение задачи ограничено?
Да, ограничено конечно
@@itwithvitaly public static void addAllCharacters(String value) {
char [] num = value.toCharArray();
int temp = 0;
boolean isEven = false;
for (int i = 0; i < num.length; i++) {
if (num[i] > 47 && num[i] < 58) {
temp += num[i] - '0';
} if (temp % 2 != 0) {
isEven = true;
}
}
System.out.println(temp);
System.out.println(isEven);
} Такое засчитывается ? для 2 задачки
Спасибо большое, что доходчиво прояснили, зачем нужен index и -1 в итерации - для движения с конца. Как ни странно, до этого в сортировках были проблемы с понимаем этого.
Спасибо! :)
а я не понял почему после -1 еще и -index. можно объяснить гуманитарию?
@@tripinprogress2225 в массивах ответ ведётся с нуля. Типа первый элемент имеет индекс 0. А, допустим, если массив состоит из 5 элементов, то индекс 5 элемента будет 4.
В Яндексе на стажировку Джуна такие задачки в основном или по сложнее?
Не в курсе про Яндекс, но предполагаю что сложнее гораздо
хорошее видео, прошу побольше таких с js и чтоб было объяснение задач, влюбился в канал
Спасибо! Будут!
С домашним заданием как то так:
const str1 = '123';
const str2 = '111';
const isPolyndrome = string => {
let isEven = '';
let polyndrome = '';
const stringToArray = string.split('');
let sum = 0;
stringToArray.map(num => sum += Number(num));
if(sum%2 === 0){
isEven = 'even';
} else {
isEven = 'odd';
};
const reversedString = string.split('').reverse().join('');
if(string === reversedString){
polyndrome = 'polyndrome';
} else {
polyndrome = 'not polyndrome';
};
return `This string is ${isEven} and ${polyndrome}!`;
};
console.log(isPolyndrome(str1));
console.log(isPolyndrome(str2));
console.log(isPolyndrome('12345678987654321'));
console.log(isPolyndrome('12345678877654321'));
Здравствуйте, решение работать будет, но я писал уже в комментах много раз почему не стоит показывать решение с риверсией строки на собесе. Если интересно можете заглянуть :)
Еще предложу пару моментов к улучшению кода:
1. Если имя функции начинается на "is", "has", "should" то обычно в этом случае ожидают что из функции будет возвращен boolean.
2. У функции должно быть single responsibility (en.wikipedia.org/wiki/Single-responsibility_principle) , по-этому лучше 1 функция - 1 действие (решение)
@@itwithvitaly просто изначально єта функция просто отвечала на вопрос, полиндром ли это, поэтому такое название (просто не стал изменять название функции, а добавил решение в соответствии с домашним заданием). По этому же и добавлен второй функционал. А по поводу решения без реверса строк к сожелению не нашел((((
Очень хотелось бы порешать типичные задания, которые даются при техническом собеседовании на джуниора JS. Как это можно сделать? Очень буду благодарен, если отправите таковые на мыло matador.ivan.ym15@gmail.com
Спасибо за видео! Продолжай в том же духе!
Java:
private static String isSumEven(String numberAsString) {
//write you code here
String[] symbols = numberAsString.split("");
int sum = 0;
for (int i = 0; i < numberAsString.length(); i++) {
sum = sum + Integer.parseInt(symbols[i]);
}
return "The amount equals " + sum + " - " + ((sum % 2 == 0) ? "even" : "odd");
}
Спасибо! Пару замечаний для улучшения:
1) Если название метода начинается с "has", "is", "should" то ожидается, что он будет возвращать булеан, как и в нашем случаи :)
2) Алгоритм хороший, работать будет быстро, но если например работали уже с Java 8 Stream API , то можете попробовать эту задачу решить с помощью лямбда выражений :)
Вот так ещё на python
def is_palindrome(string):
# индексы начала и конца строки
i = 0
j = len(string) - 1
# i и j встречаются на середине строки
while i < j:
if string[i] != string[j]:
return False
i += 1
j -= 1
return True
Здравствуйте, так тоже хорошо, единственное что цикл for обычно легче читать, чем while
const palindrome = a => a.substr(-a.length / 2).split('').reverse().join('') === a.substr(0, a.length / 2) :)
Почему сравнением срезов строки это плохое решение?
Потому что с точки зрения алгоритмической сложности это делать дольше
Подскажите пожалуйста, что за IDE? В комментариях ответа не нашел((
Это не IDE, это онлайн Sandbox называется "codesandbox", если понравилась расцветка, то можете ее поставить почти на любую IDE, называется OneDarkPro
С возвращением!)
Юрій Бережний Спасибо)
Привет. Как я понял твой алгоритм ломается если чисел количество элементов нечётное. В твоём примере так совпало что 12345 и не четное и не палиндром. А если бы было 12321?
И пока ты решал подумал про такой метод - ты получил массив Char, можно сделать временный массив.reverse () ( в свифте) и сравнить эти два массива на идентичность
Это не эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
А о какой именно книге про алгоритмы вы упомянули в видео?
Здравствуйте, не помню чтобы упоминал о какой-то, киньте таймкод в видео, пожалуйста.
@@itwithvitaly -> 3:13
Да, что можно почитать по алгоритмам?
Агонь, но более искушенные и иногда (****) итервьюверы, ждут чего-то наподобие:
function isPolindrome(numberAsString) {
let characters = numberAsString.split('');
for (let index = 0; index < characters.length / 2; index++ ) { // тут важно показать, что для полиндрома достаточно сложность O(N/2)
if (characters[index] !== characters[characters.length-1-index]) {
return false;
}
}
return true;
}
isPolindrome('123321');
Но в целом видос норм;)
Хороший пример, но, 2 момента для улучшения в вашем алгоритме:
1. Проверка на парность числа, а что если число будет 12521? Кол-во символов ведь не парное, но число палиндром.
2. Круто что вы еще написали сложность O (n/2), но не забывайте что при расчете сложности алгоритма константные числа не учитываются, т.е. O(n/3), O(n*15), O(n/2) это все равно в конечном счете дает нам O(n)
@@itwithvitaly
1. ++, условие лишнее
2. она конечно формально O(N), но это как раз и есть уточнение в рамках обработки(performance) - когда делают оптимизации, это учитывают с сумме с таймингами выполнения (если массив делить пополам, то реально на триллионе будет разница в таймингах отработки между - N и N/2)
сам хотел примерно такой же комментарий написать :) но я бы делал не characters.length / 2 а Math.floor(characters.length / 2)
Почему нельзя создать новую строку, развернуть и сравнить их? Видел такую задачу, только доп.условие там было - является ли строка палиндромом с учетом перестановки символов.
В комментариях уже задавали такой вопрос, можете почитать я описывал подробно. Если кратко: Потому что строка может быть очень большая и такая операция будет очень медленной
@@clauseclause6640 Потому что идти во 1 можно только до половины, во вторых вы мало того что ее разворачиваете, так еще и потом делаете операцию сравнения, для того чтобы сравнить две строки инструменты языка программирования сравнивают две строки посимвольно, хоть нам как пользователям языка это и не видно. А также колоссальные затраты по памяти по сравнению с решением с циклом.
Добрый день. Скажите, насколько отвечает требованиям данной задачи вот такое решение на Java:
public static void main(String [] args) {
try (Scanner scan = new Scanner (System.in)) {
System.out.println("Enter your string, please");
String str = scan.nextLine();
int sLength = str.length();
String invert = "" ;
for (int i = 0; i < sLength; i++) {
invert= str.charAt(i) + invert;
}
boolean isPalindrom = str.equals(invert);
if (isPalindrom == true ){
System.out.println (str + " is palindrom.");
} else System.out.println(str + " is not palindrom.");
}
}
Вы упомянули книжку по алгоритмам. Что за книжка?
cracking the coding interview
@@itwithvitaly спасибо
Просто переводим в строку.
Создаем другую строку, в которую копируем реверсивную первую.
Сравниваем. Если она равны , то это палиндром
Я смотрю вы отвечаете на все комментарии. Не много времени это отнимает?
Привет, много, но вы же потратили время чтобы написать свой комментарий и поднять мое видео, я поступаю также :)
Можно рассмотреть более интересные задачи которые могут дать на собесе, задач по обходам деревьев, графов.
Из 30+ собесов на которых я был и 25+ где проводил сам с другими собеседующими, только однажды была задача на рекурсивных обход дерева (нужно было папки обойти). В основном дают что-то попроще особенно на Джуниор вроде Палиндрома, работа со строками или оптимизация работы с массивом. Но обычно 60-90% собеседования это теория и задачи на "подумать"
@@itwithvitaly Понял, спасибо
const isPalindrome = str => str === str.split('').reverse().join('')
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
И что? Алгоритм с инверсией строки, то же алгоритм.
@@itwithvitaly это ведь по факту тоже алгоритм, но с использованием функционального подхода
Хорошая задачка) Решил без проблем и эту, и ту с парной суммой чисел) Не подскажите хороший сервис с задачками по программированию?
leetcode
Спасибо! :) Подскажу: hackerrank, codewars, leetcode
А что в Яве нет цикла while?
Спасибо за объяснения, но лучше в будущем не оставлять половину рабочего стола белым окном, очень не комфортно смотреть с телефона!) а так все супер!
Внесу свои пять копеек. Не заметил в комментах такого решения:
const isPalindrome = str => str.split('').every((element, index, array) => element === array[array.length - 1 - index]);
Привет, да, такого не было еще :) Единственное что, every() обычно пойдет до конца массива, чтобы проверить предикат, и даже если сделаешь return это особо не поможет, т.к. у нас просто функция и return по сути остановит только ее выполнение, а не все выражение every. В этом минус, конечно, с обычным циклом можно сразу все выполнение оборвать, если вдруг число не Палиндром.
@@itwithvitaly Почему же? Выполнение функции every() будет остановлено, если callback функция вернет false. Оставшиеся элементы массива обработаны не будут.
А что значит: парное или не парное???
even/odd; четное/нечетное; парное/не парное; Я так полагаю вы не из Украины, это видимо укранский слэнг у меня (неожиданно для себя самого)
@@itwithvitaly я из России. Никогда не слышал такого термина как парное/не парное)) четное/нечётное..
Спасибо
парное заварное
@@itwithvitaly Ясно, а то я уже попарное сложение написал:
Рассмотрим ряд чисел, которые нужно сложить:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
Для удобного подсчета попарно сложим крайние члены ряда:
(1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5 = 10 + 10 + 10 + 10 + 5 = 45
, хорошо полез в комменты).
@@itwithvitaly ха, какой занятный момент. Только после этого коммента задумался, что это таки может быть "украинский слэнг", понятный не всем)) До этого и мысли не возникало, что нет такого термина и могут быть сложности с его пониманием (парное/не парное) :)
Здравствуйте, можете ли разобрать данный фрагмент кода?
public static boolean isPalindrome(int number) {
char[] elementsOfNumber = String.valueOf(number).toCharArray();
boolean isPalindrome = false;
for (int i = 0, j = elementsOfNumber.length - 1; i < j; i++, j--) {
if (elementsOfNumber[i] == elementsOfNumber[j]) isPalindrome = true;
else{
isPalindrome = false;
break;
}
}
return isPalindrome;
}
А со 2 заданием немного странно получается
//111
public static boolean isSumOfNumberEven(int number) {
String[] numberAsString = String.valueOf(number).split(""); // "111"
int[] elementsOfNumbers = new int[numberAsString.length];
int sum = 0;
for (int i = 0; i < elementsOfNumbers.length; i++) {
elementsOfNumbers[i] = Integer.parseInt(numberAsString[i]);
sum += elementsOfNumbers[i];
}
return sum % 2 == 0;
}
Недавно занялся js, в этом задании просто развернул число в строке и сравнил, и все. А так, конечно split делает массив из строки, reverse переворачивает массив и join собирает обратно в строку, осталось сравнить и всё
В комментах много раз писал почему такое решение не подходит для собеса, можете заглянуть, если интересно:)
@@itwithvitaly тогда просто перебирать строку с начала до середины и с конца до середины, и сравнивать, так тоже можно
Ахахах, буквально недавно решал эту задачу с сайта проекта Эйлера, но делал это немного другим методом. Рад, что такие простые задачки бывают на собеседованиях, аж гора с плеч
😃👌
Честно сначала решения задачи первое о чем подумал так это инициализировать массив типа char с длиной равной длине строки, которую подаем на вход методу, а потом в цикле пройтись и в каждую ячейку с помощью метода charAt() подоставать символы из строки и таким образом сформировать массив из символов. но стоило ли так напрягаться когда есть готовый метод который делает все выше написанное в одну строку. Теперь я понял почему однажды провалил интервью. Автор верно сказал о том что должно быть как можно меньше манипуляций. Абракадабра в коде никому не нужна.
Неожиданным для меня оказался такой if, он сделал код более компактным, просто я решил эту задачу используя nested for ну и разумеется, не помешало бы в код добавить break после присвоения булевому значению false в случае, если значения чисел не совпали, чтобы оптимизировать код и не делать лишних проверок, но такое решение поставленной задачи мне понравилось, благодарю!
а я бы сделал бы как то так
(C#)
var charNumbers = numbers.ToCharArray();
return charNumbers.Reverse().ToString() == numbers ? true : false;
Можете оценить что вы думаете по поводу данного решения?
сразу подумал о таком же решении
Как то так:
let sum = numberString.split('').map(el => parseInt(el, 10)).reduce((sum, el) => sum + el, 0)
let sumEven = (sum % 2 == 0) ? true : false
лучше так:
const sum = [...numberString].reduce((sum, el) => sum + parseInt(el,10), 0)
const sumEven = sum % 2 === 0
Привет, гуд!
Блин, я бы не додумался до такого) Я бы создал внутри метода новую переменную, которой присвоил бы ревеснутое значение аргумента метода, а потом просто сравнил его с аргументом)
Как вариант, но обычно просят именно такое решение как я показал, и на это есть причины :)
На Java я первое, что пришло на ум, захотел сравнить по equals() исходную строку с реверсивным её вариантом
Так не совсем эффективно, из-за расхода по памяти и скорости на больших объемах, я описывал уже это в комментариях, можете заглянуть если интересно :)
Я только начал изучать JS (прошел основы), можете, пожалуйста сказать, это видео примерно для какого уровня? То есть эту задачу могут спросить на собеседовании на джуна, спасибо за видео.
Здравствуйте, это видео в целом для всех уровней, потому что такого рода задачи задают как и начинающим на собеседованиях, так и Senior-ам с несколькими годами опыта.
@@itwithvitaly спасибо за ответ, буду развиваться
George Bush Удачи!
Домашнее задание про Палиндром и сумму цифр:
docs.google.com/document/d/1dLAg-k4XrHrLeLfK-xSLBl_RghzdVjkpUNK4dq2G6lk/edit
а что значит парная или не парная? 10:28
Парная - при делении на 2 мы получаем остаток от деления 0
Не парная - противоположность парному :)
@@someone-special-xc Это у него украинизм: на украинском языке "парнi" и "непарнi", а по-русски "чётные" и "нечётные".
Мне больше всего нравится такой вариант:
function isPalindrome(str) {
for (let i = 0, let j = str.length-1; i < str.length / 2; i++, j--) {
if (str[i] !== str[j]) {
return false
}
}
return true
}
Гуд, хорошее решение!
In my opinion you may loop one too many times if a number of chars in an input string is odd.
let k;
if (str.length % 2 !== 0) { k = str.length/2 - 1 }
for (let i = 0, let j = str.length-1; i < k; i++, j--) { ... }
Example:
The input string contains an odd number of chars (lets say 5) than you need to loop 2 times, not 3. Am I right?
по старинке! )
print(("No", "Yes") [st == st[::-1]])
На питоне так, если нет отрицательных и чисел с точкой)
как в случае использования string и реверсивный стринг смотрят на интервью?
Mikhail Tikhonov Не очень понял вопрос , если честно :) Если вы про входной параметр, то вариаций может быть много
Был похожий вопрос дальше. Реверсия строки - плохо. Нужно полностью перебрать строку, сохранить риверсивную копию в память и затем еще и сравнение сделать - очень затратно и очень не оптимально. Гораздо проще 1 циклом перебрать
@@itwithvitaly понял спасиб)
Чувак, а мы не проходимся 2 раза по одним и тем же элементам разве?(после того, как доходим до середины массива)
Почему нельзя до середины массива проверять?
index
Можно, я об этом в доке написал которую прикрепил в комментах что мой алгоритм можно улучшить, я это и имел ввиду
@@itwithvitaly аааа) поняла) тогда извиняюс-сс 😊
c++:
bool isPalindrom(string str) {
for (size_t i = 0; i < str.size() / 2; i++)
if (str[i] != str[str.size() - 1 - i]) return false;
return true;
}
про деление на 2 посмотрел в комментах, даже не подумал об этом)
Скобки фигурные забыл))
А в питоне:
1) def func(numb: str):
return number == number[ : :-1]
2) return 'Pair' if len(str(sum([int(x) for x in numb]))) % 2 == 0 else 'notPair'
Какой всё-таки питон лаконичный))
Какое отношение эта задача имеет к предполагаемой работе?))
Особого не имеет, это задача с собеседования.
На JAVA:
public static boolean isPalindrom(String number) {
char[] c = number.toCharArray();
ArrayList numbers = new ArrayList();
for (int i = 0; i
А я бы строку спарсил бы в int, далее создал бы новую переменную и присвоил бы ей значение спарсенной строки. Далее методом reverse я бы вторую переменную бы изменил. И далее сравнил бы два числа, если они идентичны, то это палиндром.
А нигде не указано, что число влезет в int
Как называется IDE из видео?
А есть объяснение решения палиндрома числа без превращения в строку?
Со стрингом можно работать как с массивом, так что:
function isPalindrom(numberAsString) {
for (let i = 0; i
Отлично. Единственное что, я бы не делал вот этого numberAsString = numberAsString.toString();
Точнее если бы и делал, то в другую переменную. С точки зрения работоспособности кода с ним ничего не произойдет если сделать как вы написали, но с точки зрения стиля кода обычно не меняют входные параметры.
@@itwithvitaly знаю, убрал до вашего комментария. Надеюсь браузеры начнут таки поголовно использовать typescript чтобы необходимость в перестраховках отпала.
Я как то делал такое тестовое задание, правда в описании тз палиндром был словом а не цифрой.
Но не в этом суть. Хочу дополнить что не обязательно проходить индексом весь массив целиком, достаточно пройти половину округленную в большую сторону.
Так и есть :) Я об этом намекнул в доке, ссылка на которую есть в комментариях.
вообще-то в меньшую, поскольку для массива нечетной длины округление половины длины в большую сторону, заставит вас сравнить элемент сам с собой, так как последний будет центром и встретится лишь в единичном экземпляре, а для четной длины число всегда будет целым и округление ничего не даст.
Здравствуйте Виталий, спасибо за ваши видео на Python придумал такие решения, синтаксис и логика будут отличаться, от С- подобных языков, о которых вы упомянули в начале видео.
def isPalindrome(string):
return string == string[::-1]
def isaSumEven(string):
templist = map(int, list(string))
return sum(templist) % 2 == 0
Здравствуйте, ваше решение работать будет но это не совсем эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Логика не особо отличается по логике так же можно написать на любом языке взять слайс строк и развернуть потом сравнить по синтаксису такой же синтаксис может быть в любом языке где поддерживается такой же сахар над слайсами))
Ну я не знаю, если честно стоит ли писать в таком стиле на интервью потому что у интервьюера могут появиться к Вам лишнее вопросы например сколько берет памяти такой алгоритм или алацируется ли новая память под этот слайс или это происходит инплейс и тд но если вы хорошо знаете все эти нюансы в языке то конечно и так можно писать
Я подумал привести к массиву, развернуть, привести обратно к строке, проверить. А в твоем варианте можно в условие добавить, что бы индекс был не больше половины от длинны массива. Эта задача не выглядит сложной. Я думал на собеседовании что-то жутко страшное
С реверсией это простой вариант, не очень подходит для собесов, в комментах много раз писал почему, можете заглянуть, если хотите :) Не, страшного ничего не спрашивают, по алгоритмам сильные собесы обычно в Западные компании, в СНГ по алгоритмам обычно не сильно гоняют:)
Я бы предпочёл сделать новую функцию, которая была бы рекурсивной, сравнивала елементы и если они равны - вызывалась со следующлими, а если же нет, то возвращала false
function palindrom(numberAsString) {
const reverseNumber = Array.from(numberAsString).reverse().join("");
return numberAsString === reverseNumber;
}
Здравстуйте, в комментах писал почему решение с риверсией не самое лучшее, что можно показать на собесе, если интересно можете заглянуть :)
IT с Виталием Карнаухом , да, спасибо, увидел )
В чем проблема на собесе показать решение и через цикл и через реверс строки?
А никакой проблемы и нет, можно показать, но обычно в таких задач в основном оценивается алгоритмическая подготовка, чем знания конкретных инструментов языка. Т.е. если вас попросят перевернуть связный список, это не значит что надо сделать Collection.reverse(myList) и на этом закончить. Тут интересует скорее как вы это с нуля напишите без утилитных методов самого языка.
Виталий, at the best of my knowledge, strings are arrays in all the languages (well, at least in those that I know). That means you don't need to use a split() function. You can access a character in a string right away like this
:
let mySting = 'aaaaa';
let index = i;
i = 2;
let char = mySting[i];
Hi, it can be the solution as well, yes. But to be more precise in most of the popular languages the strings are not arrays itself. It's better to say that the API of the languages gives us the possibility to treat and work the strings in some cases as arrays. For example, get the actual string length or get the character by index :)
@@itwithvitaly Well, strings are datatypes and for any datatype we need to know how memory for it gets allocated. In majority of languages memory allocated for a fixed/immutable array (I agree, maybe this is not always a case). You don't need to reply, but if you would like to than use Russian.
это наверно в 2008 давали на интервью, почитайте более современные статьи, а вообще обычно на интервью дают задачи с таких площадок как литкод или кодварс, ну и раз уж тут js, то также тестят стэк библиотечный заданиями а-ля создай список чекбоксов на реакте\вью\ангуляре
А как тогда мне эту задачу в 2020 году давали на собесах минимум раза 3?
Если бы мне задали подобную задачу, то я бы задумался стоит ли тратить время на данную компанию, т.к. на собеседовании должны задаваться реально толковые вопросы, а не какая-то ерундистика которую на практике никто применять не будет, я не разу не сталкивался с задачами по палиндрому, по крайней мере строк, с объектами ещё можно что-то придумать. Как по мне вопросы должны быть максимально приближёнными к практике, без этого не смысла в собеседовании. Человек может знать теорию, проштудировать кучу заданий для собеседования, но когда ему дадут к примеру простую задачу (для фронта) сделать так чтоб элемент отображался только если он на экране более 1 секунды, а затем убирался из отслеживания видимости. Тут скорее всего собеседуемый сядет в лужу, т.к. с этим сталкиваются на практике постоянно, но в уроках по супер-пупер изи прохождению собеседований подобного не встречал.
У меня бы такой код не прошёл ревью :) Надо добавить break в цикл, плюс по всему массиву идти не надо, только до середины, иначе получается двойная работа.
Ilya A Так и есть, я об этом в гугл доке (ссылка есть в комментах) и намекнул, чтобы те кто будет писать улучшили мой алгоритм и подумали
IT с Виталием Карнаухом тогда 👍
А зачем в цикл добавлять break, если есть return false?
@@ЕвгенийАлексеев-о9э да тут вообще не нужна булевская переменная по факту
@@ЕвгенийАлексеев-о9э для того, чтобы если например в начале цифры не совпали то прерывать цикл так как без брейк он проверит все равно его до конца, а это не имеет смысла- пустая трата ресурсов и времени
Вторая задача так выглядет:
int polinom = 12321; // 0, 123, 4321
int sum =0;
do{
sum += polinom % 10;
}while(polinom = polinom /10) ;
Что за компилятор ?
Цикл в пол длины текста, сравниваем синхронно с начала и с конца, если не совпадает выводим "false" и используем "break" что бы завершить бессмысленное продолжение перебора, иначе перебераем до конца и выводим "true"
Почему бы не (str==str.split().reverse().join()) ? true : false
По сути и тернарник то не нужен, сравнение вернет true / false. А так автор видео писал что: "Не, строка может быть очень большой, на такое решение расходуется очень много памяти и времени. Если интересно можете в комментах посмотреть, я там развернуто отвечал как раз на этот вопрос :)" и " Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка."
Gasu отписал хороший ответ и объяснение :)
function isPalindrome(numberAsString) {
return numberAsString === numberAsString.split('').reverse().join('');
}
Все!
Здравствуйте, как я уже многим и писал такое решение работать будет, но проблема в том что когда мы пытаемся решить какую-то задачу, нам нужно найти максимально быстрый и эффективный по памяти алгоритм. В данном случае все ок будет работать если строка будет маленькая, а представьте если строка будет миллион символов. Нам прийдется развернуть всю строку, сделать новую на такой же миллион символов, выделить на нее такое же кол-во памяти , т.е. 2 строки по миллиону, а потом еще и сделать сравнение, которое кстати языком программирования проводится посимвольно, поэтому я рекомендую использовать цикл, там будет всего 1 проход и всего до половины строки. Эффективность алгоритма определяется на больших данных.
@@itwithvitaly да, вы правы, в случае строки с миллионом символов, пожалуй, стандартный js-алгоритм реверса будет отрабатывать заметно медленнее, но я написал именно такое решение, потому что речь шла о числах - ну пусть 20-значное число будет обрабатываться, к примеру. В таком случае потери времени будут минимальными. Просто смотря для чего данную функцию применять.
Хороший выпуск)
У тебя не было желания стать ментор или сделать не большой курс (до 10 человек)?
Спасибо!) Вообще пока не планировал, возможно в будущем и если этого будет хотеть аудитория :)
Привет!
В данном решении зачем тебе обходить строку полностью? Ведь достаточно дойти до её середины. Или я не прав?
я решал, как раз на онлайн собесе задачку на полиндром... но я просто разрезал и через reverse разворачивал, сравнивал и всё :) к тому же это можно в одну строку сделать
@@SVP-d1d да, есть такой способ. Он мне тоже сразу на ум пришёл. Но при больших строках это займет много времени потому что строка будет проходиться минимум три раза (полностью) .
И как собес прошёл? Тебя взяли на работу? Какие ещё задачи там были?
@@ReAgent003 дальше завалили, на прототипах и асинхронщине :) а дальшееее.... только "извините, без коммерческого опыта 1-2+ года нам неочем с вами разговаривать" :)
@@SVP-d1d так ты не прошел из за прототипов или стажа все таки? Сколько уже изучаешь Программирование? И каким образом?
@@ReAgent003 та то просто один собес вспомнил на котором была задачка с полиндромом :) на нём просто завалили... позиция react . А так то уже давненько, как-то поработал на вордпресс но плюнул и последние пол года ковырял react. Но тут беда, или ты с опытом или ты без работы
У меня как раз завтра собеседование. Будет забавно, если дадут эту задачу :D
Удачи вам !:)
Ну как собес?
Ну как там?
Хотелось бы еще, чтоб испытуемый спросил, что делать если строка null или nan. Пустая строка, понятно, является палиндромом, но об этом все равно лучше подумать :)
Да, согласен, корнер кейсы тоже нужно учитывать!
Привет! О какой книжке идет речь?
Привет, пришлите плз таймкод с видео , не совсем понимаю о чем вопрос.
@@itwithvitaly ua-cam.com/video/nHTgmj32nwE/v-deo.html
Илья Шишлачев А, если я не ошибаюсь это была книга “Cracking the coding interview”