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 :)
Цикл должен быть до 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 что-то вроде этого тоже должно быть
Хм, хорошее решение! Я думал по другому, переворачивать строку string.split('').reverse().join('') делаем из строки массив символов, переворачиваем массив и объединяем снова в строку, ну и потом в условии сравниваем
Поставил на паузу, пока ты не написал, сделал сам вот так, в целом задача очень простая, вероятно она действительно просто для того чтобы посмотреть как человек размышляет. 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; }
Я раньше решал эту задачу полностью разворачивая число и сравнивая с исходным, но этот способ показался мне более эффективным и простым. Я переписал на ваше решение на 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.
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
С точки зрения "красоты" кода, я согласен. 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-ник, но красоты не вижу. Какой-то сплит, джойн. Ясно, что это костыли, но зачем сплитить строку, если нам надо ее перевернуть?
Первым на ум пришло развернуть строку и сравнить, но по индексам тоже вариант, имеет смысл, если длинная строка а у тебя последний индекс даст false и не придется крутить строки
Вы самый лучший, просто слушать вас так приятно, а еще и очень полезно, было бы здорово увидеть работу над реальным проектом на js от вас, удачи с развитием канала!!!!
Сколько будет занимать памяти такое решение ? В js тоже можно написать в одну строку return str === str.split('').reverse().join('') она будет занимать n*3 вроде как а в питоне сколько?
@@trypophobia7497 изучите временную сложность алгоритмов. Цикл всегда дольше выполняется чем проверка равенства. Да и слайс всё-таки должен быть быстрее чем сплит, реверс, джоин)
@@47clere я тут не писал про временную сложность я тут спросил сколько будет занимать ПАМЯТИ ????? вы прочитай комментарий внимательно! если в цикле будет константное значение то BIG O будет равно O(1) так же как и в сравнении на равенство О(1) а если нет то в цикле O(n) (сейчас я не говорю про то что в цикле будет быстрее или равно я говорю про BIG O) я спрашивал про память копируется ли этот слайс в снова в новую память или нет? в js будет создаваться новые массивы
9:15 можно поставить условие если index >= Math.floor(characters.length / 2), то выйти из цикла, чтобы не проходить лишние итерации. Переменная isPalindrome здесь не нужна, можно просто return true или return false
Добрый день,очень интересно смотреть. Взялся учить яву и уже решал подобную задачу. 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
Перед просмотром постаил на паузу и попробовал решить задачу. Вот что получилось :) const isPalindrome = str => str === str.split('').reverse().join('')
то, что я придумал перед просмотром решения на жабе: 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; }
Можно перевернуть это число и сравнить с исходным. Равны, значит это число есть полиндром, нет-нет. UPD: В кооментах увидел, что этот способ памятезатратный
Здравствуйте, многие почему-то сразу пишут именно о таком кейсе, я в комментах писал почему считаю что такое решение не лучший вариант показывать его на интервью, если интересно, можете заглянуть в комменты :)
Не все языки предоставляют возможность реверса + это может быть не строка, а число или массив. Способ в видео самый универсальный, который можно провернуть в многих языках. Я так же делал на питоне.
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
Очень интересное видео, но я хотел поинтересоваться одним вопросом. Я написал реализацию этой программы с помощью StringBuilder в Java(инициализировал стирнгбилдер с нашей строкой содержащейся внутри, потом сделал reverse и toString, после чего просто приравнял обычную строку с перевернутой и если они равны вернул true). Так вот, всё работает, всё прекрасно, но какая из вариаций будет более предпочтительна для собеседования, с простым циклом или моим способом?
Привет, наверное, немного опоздал, но все же спрошу. Хотел узнать, как вы так быстро перемещаетесь по коду между словами и строками? Это очень много экономит времени. Все, наверное, расписывать долго, может где-то есть видео или удобный лист шорткатов в вс коде? Заранее спасибо)
Я использую alt + стрелка влево/вправо (так на маке). Я когда-то очень давно делал видео по hotkeys, может будет полезно : ruclips.net/video/hKrYyWXNMdc/видео.html
По поводу задачи на парность/непарность, оцените решение: 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)_
Спасибо за видео! Продолжай в том же духе! 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 , то можете попробовать эту задачу решить с помощью лямбда выражений :)
Почему нельзя создать новую строку, развернуть и сравнить их? Видел такую задачу, только доп.условие там было - является ли строка палиндромом с учетом перестановки символов.
В комментариях уже задавали такой вопрос, можете почитать я описывал подробно. Если кратко: Потому что строка может быть очень большая и такая операция будет очень медленной
@@clauseclause6640 Потому что идти во 1 можно только до половины, во вторых вы мало того что ее разворачиваете, так еще и потом делаете операцию сравнения, для того чтобы сравнить две строки инструменты языка программирования сравнивают две строки посимвольно, хоть нам как пользователям языка это и не видно. А также колоссальные затраты по памяти по сравнению с решением с циклом.
Я аналитик, но на некоторых собеседованиях программерские навыки тоже спрашивают. Недавно на питоне предлагали написать throttler: есть лимит в 100 неких входящих на функцию сообщений в секунду. И когда он превышен - новому сообщению отказывать в отправке. Задача была на разработку алгоритма с эффективностью O(N). Вроде просто, кажется что джуниорский вопрос. Плюс очень часто спрашивают про результаты вычислений разных выражений, где надо внимательно следить за трюками индексации и понимать отличие типов данных.
На вскидку, связный список (годится даже односвязный) в который пишем время входящего сообщения, оперируем ссылками на первый и последний элемент и количеством элементов в списке, если количество меньше ста добавляем время сообщений в конец списка, если количество элементов 100 и время между первым элементом и входящим сообщением меньше секунды, то игнорируем сообщение, если больше, добавляем в список, идем по списку с первого элемента удаляя элементы, время которых отстоит от последнего добавленного более чем на секунду. В общем то задача на выбор правильной структуры для хранения списка, при условии, что необходимо удалять элементы из начала списка, проход по списку требуется с первого элемента и в одном направлении, все остальное псевдоматематический антураж.
@@denisn6408 в целом согласен, но! Удаление элемента из начала списка под капотом вызывает перезапись индексов всех остальных элементов. А это совсем контр-производительно. Попробуйте придумать, как обойти это ограничение)
@@Voronza Питонщики не знают что такое связный список? А какой структурой пользовались вы для решения этой задачи? В связном списке нет доступа по индексу, потому что в нем нет индекса)), в этом весь смысл связного списка, в односвязном списке у каждого элемента есть ссылка на следующий, т.е. обойти его можно только с первого элемента, обратно не получится, в двусвязном каждый элемент имеет ссылку на предыдущий и на следующий элемент. Поэтому процедура удаления первого элемента очень простая, он просто удаляется и если список двусвязный, то в элементе который идет следующим удаляется ссылка на удаляемый элемент.
@@denisn6408 простите, узколобо прочитал ваш предыдущий ответ. Пойду RTFM. Не питонячий, потому что гугление в рамках питона мне даёт это: "Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList".
Можно пробегать циклом не по всему стрингу, а только по половине слова т.к. вторую половину мы сразу же проверяем. Разделить длину массива на 2, отбрасывая остаток от деления если длина массива нечетная(т.к. это будет общее число). На четность можно проверить остатком от деления если он не равен нулю то нечётное.
@@itwithvitaly ха, какой занятный момент. Только после этого коммента задумался, что это таки может быть "украинский слэнг", понятный не всем)) До этого и мысли не возникало, что нет такого термина и могут быть сложности с его пониманием (парное/не парное) :)
Спасибо большое, что доходчиво прояснили, зачем нужен index и -1 в итерации - для движения с конца. Как ни странно, до этого в сортировках были проблемы с понимаем этого.
@@tripinprogress2225 в массивах ответ ведётся с нуля. Типа первый элемент имеет индекс 0. А, допустим, если массив состоит из 5 элементов, то индекс 5 элемента будет 4.
@@itwithvitaly Только я не понимаю как это улучшит алгоритм, если и там и там можно просто сравнивать символы по индексу. Это просто лишнее действие на мой взгляд. Только если проверяем не просто число в виде строки а именно строку текста, например "А роза упала на лапу Азора", там и в нижний регистр это перевести и от пробелов избавиться, возможно потребуется массив. В JS не знаю, но в python массив не потребуется даже в этом случае.
@@СергейПресняков-о4р Улучшение в том, что не будет создаваться лишний массив, который будет занимать память. Можно делать решать без массива, не принципиально
@@itwithvitaly Я не так понял комментарий. Подумал что имеется ввиду будто преобразование строки в список как-то улучшит алгоритм, а не работа сразу со строкой. Спасибо.
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
@@clauseclause6640 Не, у вас строка может быть миллион символов, вам надо сначала эту строку развернуть, потом сохранить в память, а потом еще и сравнить, а операция сравнения кстати делается посимвольно самими инструментами языков програмирования. Это очень долго и не эффективно, гораздо быстрее просто пройти строку до половины. Эффективность алгоритма и подхода определяется только на больших данных, где может быть большой затрат памяти и большие задержки
@@itwithvitaly не могу согласиться. Во-первых, в вашем решении вы так же дублируете данные и используете лишнюю память, причем, без причины, ведь у строк можно точно так взять элемент по индексу и узнать длину через length. Встроенные методы в js и операция сравнения строк хорошо оптимизированны, и посимвольное сравнение здесь выполняться не будет в большинстве случаев. Опять же, даже посимвольное сравнение внутри движка js и тем более питона будет дешевле, чем создание цикла, итерация по нему, обращения к элементу по индексу и проверки условия на каждом шаге.
@@itwithvitaly и самое смешное, что ваше решение точно так же посимвольно проверяет строки, ведь вы в цикле проходите i от 0 до length, а не length // 2
Привет. Как я понял твой алгоритм ломается если чисел количество элементов нечётное. В твоём примере так совпало что 12345 и не четное и не палиндром. А если бы было 12321? И пока ты решал подумал про такой метод - ты получил массив Char, можно сделать временный массив.reverse () ( в свифте) и сравнить эти два массива на идентичность
Это не эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Здравствуйте, решение работать будет, но я писал уже в комментах много раз почему не стоит показывать решение с риверсией строки на собесе. Если интересно можете заглянуть :) Еще предложу пару моментов к улучшению кода: 1. Если имя функции начинается на "is", "has", "should" то обычно в этом случае ожидают что из функции будет возвращен boolean. 2. У функции должно быть single responsibility (en.wikipedia.org/wiki/Single-responsibility_principle) , по-этому лучше 1 функция - 1 действие (решение)
@@itwithvitaly просто изначально єта функция просто отвечала на вопрос, полиндром ли это, поэтому такое название (просто не стал изменять название функции, а добавил решение в соответствии с домашним заданием). По этому же и добавлен второй функционал. А по поводу решения без реверса строк к сожелению не нашел(((( Очень хотелось бы порешать типичные задания, которые даются при техническом собеседовании на джуниора JS. Как это можно сделать? Очень буду благодарен, если отправите таковые на мыло matador.ivan.ym15@gmail.com
Мне больше всего нравится такой вариант: 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?
драсьте, я остановил на 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; }
Твой комментарий прочел как записки сумасшедшего гения, в хорошем смысле. Но интересно было наблюдать за ходом ваших мыслей, жаль нет подписки, я бы еще почитал ваши комментарии в таком стиле :)
Вот так ещё на 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
@@itwithvitaly спасибо за ответ. Виталий, а не мог бы ты поднять тему в своих роликах про стандартизации в JS, что такое ECMAScript 6, es6, es2015. Почему в разных стандартах разные синтаксисы, например експорта/импорта функций. Где и какие стандарты требуются. JS, вроде как, по своей сути должен запускаться везде и на всем, а получается что даже маленький тестовый код нигде не запустишь, ни из консоли на NodeJs(установкой бабеля проблема не решается, ему надо еще скормить определенные пресеты), ни в браузере не запустить(помимо требуемого вебсервера, там тоже есть свой стандарт JS - CommonJS). Изучаю потихоньку фронт, и сам язык js не сложный, но вот эта вся обвязка вокруг него - ад.
Из 30+ собесов на которых я был и 25+ где проводил сам с другими собеседующими, только однажды была задача на рекурсивных обход дерева (нужно было папки обойти). В основном дают что-то попроще особенно на Джуниор вроде Палиндрома, работа со строками или оптимизация работы с массивом. Но обычно 60-90% собеседования это теория и задачи на "подумать"
Ахахах, буквально недавно решал эту задачу с сайта проекта Эйлера, но делал это немного другим методом. Рад, что такие простые задачки бывают на собеседованиях, аж гора с плеч
Честно сначала решения задачи первое о чем подумал так это инициализировать массив типа char с длиной равной длине строки, которую подаем на вход методу, а потом в цикле пройтись и в каждую ячейку с помощью метода charAt() подоставать символы из строки и таким образом сформировать массив из символов. но стоило ли так напрягаться когда есть готовый метод который делает все выше написанное в одну строку. Теперь я понял почему однажды провалил интервью. Автор верно сказал о том что должно быть как можно меньше манипуляций. Абракадабра в коде никому не нужна.
Агонь, но более искушенные и иногда (****) итервьюверы, ждут чего-то наподобие: 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)
У меня бы такой код не прошёл ревью :) Надо добавить break в цикл, плюс по всему массиву идти не надо, только до середины, иначе получается двойная работа.
@@ЕвгенийАлексеев-о9э для того, чтобы если например в начале цифры не совпали то прерывать цикл так как без брейк он проверит все равно его до конца, а это не имеет смысла- пустая трата ресурсов и времени
Чувак, а мы не проходимся 2 раза по одним и тем же элементам разве?(после того, как доходим до середины массива) Почему нельзя до середины массива проверять? index
Блин, я бы не додумался до такого) Я бы создал внутри метода новую переменную, которой присвоил бы ревеснутое значение аргумента метода, а потом просто сравнил его с аргументом)
Виталий, 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.
А никакой проблемы и нет, можно показать, но обычно в таких задач в основном оценивается алгоритмическая подготовка, чем знания конкретных инструментов языка. Т.е. если вас попросят перевернуть связный список, это не значит что надо сделать Collection.reverse(myList) и на этом закончить. Тут интересует скорее как вы это с нуля напишите без утилитных методов самого языка.
это наверно в 2008 давали на интервью, почитайте более современные статьи, а вообще обычно на интервью дают задачи с таких площадок как литкод или кодварс, ну и раз уж тут js, то также тестят стэк библиотечный заданиями а-ля создай список чекбоксов на реакте\вью\ангуляре
Я как то делал такое тестовое задание, правда в описании тз палиндром был словом а не цифрой. Но не в этом суть. Хочу дополнить что не обязательно проходить индексом весь массив целиком, достаточно пройти половину округленную в большую сторону.
вообще-то в меньшую, поскольку для массива нечетной длины округление половины длины в большую сторону, заставит вас сравнить элемент сам с собой, так как последний будет центром и встретится лишь в единичном экземпляре, а для четной длины число всегда будет целым и округление ничего не даст.
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 посмотрел в комментах, даже не подумал об этом)
Я бы предпочёл сделать новую функцию, которая была бы рекурсивной, сравнивала елементы и если они равны - вызывалась со следующлими, а если же нет, то возвращала false
Что будет если сказать "а можно загуглить"? Ведь все знают, что забери в разработчиков гугл, и стековерфлов в частности, они почти ничего сами не могут сделать.
А я бы строку спарсил бы в int, далее создал бы новую переменную и присвоил бы ей значение спарсенной строки. Далее методом reverse я бы вторую переменную бы изменил. И далее сравнил бы два числа, если они идентичны, то это палиндром.
Неожиданным для меня оказался такой if, он сделал код более компактным, просто я решил эту задачу используя nested for ну и разумеется, не помешало бы в код добавить break после присвоения булевому значению false в случае, если значения чисел не совпали, чтобы оптимизировать код и не делать лишних проверок, но такое решение поставленной задачи мне понравилось, благодарю!
Я только начал изучать JS (прошел основы), можете, пожалуйста сказать, это видео примерно для какого уровня? То есть эту задачу могут спросить на собеседовании на джуна, спасибо за видео.
Здравствуйте, это видео в целом для всех уровней, потому что такого рода задачи задают как и начинающим на собеседованиях, так и Senior-ам с несколькими годами опыта.
function isSumEven (numAsString) { const arrOfChars = numAsString.split(''); const sum = arrOfChars.reduce((a, b) => a + +b, 0); return sum % 2 == 0; }
а я бы сделал бы как то так (C#) var charNumbers = numbers.ToCharArray(); return charNumbers.Reverse().ToString() == numbers ? true : false; Можете оценить что вы думаете по поводу данного решения?
Внесу свои пять копеек. Не заметил в комментах такого решения: const isPalindrome = str => str.split('').every((element, index, array) => element === array[array.length - 1 - index]);
Привет, да, такого не было еще :) Единственное что, every() обычно пойдет до конца массива, чтобы проверить предикат, и даже если сделаешь return это особо не поможет, т.к. у нас просто функция и return по сути остановит только ее выполнение, а не все выражение every. В этом минус, конечно, с обычным циклом можно сразу все выполнение оборвать, если вдруг число не Палиндром.
@@itwithvitaly Почему же? Выполнение функции every() будет остановлено, если callback функция вернет false. Оставшиеся элементы массива обработаны не будут.
Недавно занялся js, в этом задании просто развернул число в строке и сравнил, и все. А так, конечно split делает массив из строки, reverse переворачивает массив и join собирает обратно в строку, осталось сравнить и всё
Был похожий вопрос дальше. Реверсия строки - плохо. Нужно полностью перебрать строку, сохранить риверсивную копию в память и затем еще и сравнение сделать - очень затратно и очень не оптимально. Гораздо проще 1 циклом перебрать
Здравствуйте Виталий, спасибо за ваши видео на Python придумал такие решения, синтаксис и логика будут отличаться, от С- подобных языков, о которых вы упомянули в начале видео. def isPalindrome(string): return string == string[::-1] def isaSumEven(string): templist = map(int, list(string)) return sum(templist) % 2 == 0
Здравствуйте, ваше решение работать будет но это не совсем эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Логика не особо отличается по логике так же можно написать на любом языке взять слайс строк и развернуть потом сравнить по синтаксису такой же синтаксис может быть в любом языке где поддерживается такой же сахар над слайсами)) Ну я не знаю, если честно стоит ли писать в таком стиле на интервью потому что у интервьюера могут появиться к Вам лишнее вопросы например сколько берет памяти такой алгоритм или алацируется ли новая память под этот слайс или это происходит инплейс и тд но если вы хорошо знаете все эти нюансы в языке то конечно и так можно писать
Я подумал привести к массиву, развернуть, привести обратно к строке, проверить. А в твоем варианте можно в условие добавить, что бы индекс был не больше половины от длинны массива. Эта задача не выглядит сложной. Я думал на собеседовании что-то жутко страшное
С реверсией это простой вариант, не очень подходит для собесов, в комментах много раз писал почему, можете заглянуть, если хотите :) Не, страшного ничего не спрашивают, по алгоритмам сильные собесы обычно в Западные компании, в СНГ по алгоритмам обычно не сильно гоняют:)
Здравствуйте, как я уже многим и писал такое решение работать будет, но проблема в том что когда мы пытаемся решить какую-то задачу, нам нужно найти максимально быстрый и эффективный по памяти алгоритм. В данном случае все ок будет работать если строка будет маленькая, а представьте если строка будет миллион символов. Нам прийдется развернуть всю строку, сделать новую на такой же миллион символов, выделить на нее такое же кол-во памяти , т.е. 2 строки по миллиону, а потом еще и сделать сравнение, которое кстати языком программирования проводится посимвольно, поэтому я рекомендую использовать цикл, там будет всего 1 проход и всего до половины строки. Эффективность алгоритма определяется на больших данных.
@@itwithvitaly да, вы правы, в случае строки с миллионом символов, пожалуй, стандартный js-алгоритм реверса будет отрабатывать заметно медленнее, но я написал именно такое решение, потому что речь шла о числах - ну пусть 20-значное число будет обрабатываться, к примеру. В таком случае потери времени будут минимальными. Просто смотря для чего данную функцию применять.
Цикл в пол длины текста, сравниваем синхронно с начала и с конца, если не совпадает выводим "false" и используем "break" что бы завершить бессмысленное продолжение перебора, иначе перебераем до конца и выводим "true"
Отлично. Единственное что, я бы не делал вот этого numberAsString = numberAsString.toString(); Точнее если бы и делал, то в другую переменную. С точки зрения работоспособности кода с ним ничего не произойдет если сделать как вы написали, но с точки зрения стиля кода обычно не меняют входные параметры.
@@itwithvitaly знаю, убрал до вашего комментария. Надеюсь браузеры начнут таки поголовно использовать typescript чтобы необходимость в перестраховках отпала.
Не, строка может быть очень большой, на такое решение расходуется очень много памяти и времени. Если интересно можете в комментах посмотреть, я там развернуто отвечал как раз на этот вопрос :)
А задача ведь элементарная. Разве у интервьюера не может появиться ощущение, что ты немного недалёкий, раз так долго решаешь и подробно объясняешь такие простые вещи? Одно дело, когда кандидат решил задачу за две минуты, и совсем другое, когда ты выслушиваешь его нудные объяснения уже десяток минут. Мне бы второй показался, ну, немного дурачком... Это ведь не какой-то тяжёлый для восприятия алгоритм.. Или я в своих размышлениях ошибаюсь?
Здравствуйте, если решите быстро это только вам +. Но делайте это вслух, объясняйте свое решение и проговаривайте свои мысли. Также не забывайте что это скорее всего будет незнакомая вам задача, а на интервью может быть несколько человек которые будут следить за каждым шагом и действовать не нервы. Гарантирую вам это совершенно по-другому)
@@itwithvitaly звучит тоже разумно. Дело в том, что на таких задачах вроде и надо что-то объяснять, а объяснять и нечего: в голове абсолютно пусто и ты просто пишешь код. По поводу стрессоустойчивости, я участвовал некоторое время в олимпиадах по программированию. Очень надеюсь, что это поможет. ) Хотя там никто прямо за тобой непосредственно не наблюдает. И мне бы хотелось задать ещё пару вопросов. Будет ли хорошей идеей спросить у интервьюера сразу, интересует его лёгкое и красивое решение, либо быстрое? И будет ли хорошей идеей сначала написать код, а потом его объяснять, либо, всё-таки, лучше не рисковать и проговаривать по ходу решения?
А в питоне: 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' Какой всё-таки питон лаконичный))
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
![[Ответы] Java Junior реальное собеседование | Collection API | Часть 3](/img/1.gif)
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 ???
Цикл должен быть до 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 добавить, при первом не совпадении. А я удивляюсь почему приложения зависают.
Я очень сильно ждал новые видео!! Ура)
спасибо)
Хм, хорошее решение! Я думал по другому, переворачивать строку
string.split('').reverse().join('')
делаем из строки массив символов, переворачиваем массив и объединяем снова в строку, ну и потом в условии сравниваем
кстати на Питоне ещё легче)
string[::-1]
12345 - 54321
А на пыхе можно через array_reverse )
Домашнее задание про Палиндром и сумму цифр:
docs.google.com/document/d/1dLAg-k4XrHrLeLfK-xSLBl_RghzdVjkpUNK4dq2G6lk/edit
а что значит парная или не парная? 10:28
Парная - при делении на 2 мы получаем остаток от деления 0
Не парная - противоположность парному :)
@@someone-special-xc Это у него украинизм: на украинском языке "парнi" и "непарнi", а по-русски "чётные" и "нечётные".
Поставил на паузу, пока ты не написал, сделал сам вот так, в целом задача очень простая, вероятно она действительно просто для того чтобы посмотреть как человек размышляет.
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;
}
Я раньше решал эту задачу полностью разворачивая число и сравнивая с исходным, но этот способ показался мне более эффективным и простым. Я переписал на ваше решение на 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 хорошо, спасибо за обратную связь
Используя возможности 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-ник, но красоты не вижу. Какой-то сплит, джойн. Ясно, что это костыли, но зачем сплитить строку, если нам надо ее перевернуть?
Первым на ум пришло развернуть строку и сравнить, но по индексам тоже вариант, имеет смысл, если длинная строка а у тебя последний индекс даст false и не придется крутить строки
Мне тоже это первое а голову пришло
Вы самый лучший, просто слушать вас так приятно, а еще и очень полезно, было бы здорово увидеть работу над реальным проектом на js от вас, удачи с развитием канала!!!!
Большое спасибо! :)
Буду благодарен , если в одном из следующих видео расскажешь про open source( как там взять проект для новичка).
Юрій Бережний Хорошо, запишу себе эту тему
Функция проверки палиндрома строки для 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 будет создаваться новые массивы
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й версии.
Добрый день,очень интересно смотреть. Взялся учить яву и уже решал подобную задачу.
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 , спасибо.
Перед просмотром постаил на паузу и попробовал решить задачу. Вот что получилось :)
const isPalindrome = str => str === str.split('').reverse().join('')
то, что я придумал перед просмотром решения на жабе:
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;
}
А если еще сделать принудительную остановку цикла, как только найдена неравная пара, чтобы остальное не проверять?
Так и нужно :)
Можно перевернуть это число и сравнить с исходным. Равны, значит это число есть полиндром, нет-нет.
UPD: В кооментах увидел, что этот способ памятезатратный
А ещё лучше перевернуть половину и сравнить с другой половинной
Здравствуйте, многие почему-то сразу пишут именно о таком кейсе, я в комментах писал почему считаю что такое решение не лучший вариант показывать его на интервью, если интересно, можете заглянуть в комменты :)
Не все языки предоставляют возможность реверса + это может быть не строка, а число или массив. Способ в видео самый универсальный, который можно провернуть в многих языках. Я так же делал на питоне.
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
При проверке на палиндром можно сделать так:
...
for (let index = 0; index
На счет сложности вы правы, итак итак будет в конечном счете O(n), но если будет собес, скорее всего захотят увидеть вариант именно с O(n/2)
Нет, О(n) != O(n // 2), асимптотика вычисляется по худшему сценарию, но для практических задач корректнее использовать среднюю сложность
@@achillescres9270 O(n) == O(n/2), потому что при оценке сложности алгоритма не учитываются константные значения. Это сокращение валидное.
Мне кажется, что лучше целочисленно делить:
characters.length%2
Ибо зачем сравнивать центр с самим собой у строк с нечетной длиной?
Очень интересное видео, но я хотел поинтересоваться одним вопросом. Я написал реализацию этой программы с помощью StringBuilder в Java(инициализировал стирнгбилдер с нашей строкой содержащейся внутри, потом сделал reverse и toString, после чего просто приравнял обычную строку с перевернутой и если они равны вернул true). Так вот, всё работает, всё прекрасно, но какая из вариаций будет более предпочтительна для собеседования, с простым циклом или моим способом?
В комментариях сам нашел ответ. Спасибо за видео
Спасибо !:)
@@maksymholovenko2795 Так,как предпочтительней?)
Привет, наверное, немного опоздал, но все же спрошу. Хотел узнать, как вы так быстро перемещаетесь по коду между словами и строками? Это очень много экономит времени. Все, наверное, расписывать долго, может где-то есть видео или удобный лист шорткатов в вс коде? Заранее спасибо)
Я использую alt + стрелка влево/вправо (так на маке). Я когда-то очень давно делал видео по hotkeys, может будет полезно : ruclips.net/video/hKrYyWXNMdc/видео.html
@@itwithvitaly спасибо большое! :)
По поводу задачи на парность/непарность, оцените решение:
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)_
Какую книгу по алгоритмам вы упоминали? И какие посоветуете?
Упоминал книгу "Cracking the coding interview". Посоветовать смогу, но нужно знать что именно вы хотите почитать и на какую тему :)
Спасибо за видео! Продолжай в том же духе!
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 , то можете попробовать эту задачу решить с помощью лямбда выражений :)
Почему нельзя создать новую строку, развернуть и сравнить их? Видел такую задачу, только доп.условие там было - является ли строка палиндромом с учетом перестановки символов.
В комментариях уже задавали такой вопрос, можете почитать я описывал подробно. Если кратко: Потому что строка может быть очень большая и такая операция будет очень медленной
@@clauseclause6640 Потому что идти во 1 можно только до половины, во вторых вы мало того что ее разворачиваете, так еще и потом делаете операцию сравнения, для того чтобы сравнить две строки инструменты языка программирования сравнивают две строки посимвольно, хоть нам как пользователям языка это и не видно. А также колоссальные затраты по памяти по сравнению с решением с циклом.
Я аналитик, но на некоторых собеседованиях программерские навыки тоже спрашивают. Недавно на питоне предлагали написать throttler: есть лимит в 100 неких входящих на функцию сообщений в секунду. И когда он превышен - новому сообщению отказывать в отправке. Задача была на разработку алгоритма с эффективностью O(N). Вроде просто, кажется что джуниорский вопрос. Плюс очень часто спрашивают про результаты вычислений разных выражений, где надо внимательно следить за трюками индексации и понимать отличие типов данных.
Круто, хорошая задача. Мне ее где-то тоже задавали.
На вскидку, связный список (годится даже односвязный) в который пишем время входящего сообщения, оперируем ссылками на первый и последний элемент и количеством элементов в списке, если количество меньше ста добавляем время сообщений в конец списка, если количество элементов 100 и время между первым элементом и входящим сообщением меньше секунды, то игнорируем сообщение, если больше, добавляем в список, идем по списку с первого элемента удаляя элементы, время которых отстоит от последнего добавленного более чем на секунду. В общем то задача на выбор правильной структуры для хранения списка, при условии, что необходимо удалять элементы из начала списка, проход по списку требуется с первого элемента и в одном направлении, все остальное псевдоматематический антураж.
@@denisn6408 в целом согласен, но! Удаление элемента из начала списка под капотом вызывает перезапись индексов всех остальных элементов. А это совсем контр-производительно. Попробуйте придумать, как обойти это ограничение)
@@Voronza Питонщики не знают что такое связный список? А какой структурой пользовались вы для решения этой задачи? В связном списке нет доступа по индексу, потому что в нем нет индекса)), в этом весь смысл связного списка, в односвязном списке у каждого элемента есть ссылка на следующий, т.е. обойти его можно только с первого элемента, обратно не получится, в двусвязном каждый элемент имеет ссылку на предыдущий и на следующий элемент. Поэтому процедура удаления первого элемента очень простая, он просто удаляется и если список двусвязный, то в элементе который идет следующим удаляется ссылка на удаляемый элемент.
@@denisn6408 простите, узколобо прочитал ваш предыдущий ответ. Пойду RTFM. Не питонячий, потому что гугление в рамках питона мне даёт это: "Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList".
const palindrome = a => a.substr(-a.length / 2).split('').reverse().join('') === a.substr(0, a.length / 2) :)
Можно пробегать циклом не по всему стрингу, а только по половине слова т.к. вторую половину мы сразу же проверяем. Разделить длину массива на 2, отбрасывая остаток от деления если длина массива нечетная(т.к. это будет общее число). На четность можно проверить остатком от деления если он не равен нулю то нечётное.
Алексей Чумаков Все правильно)
Идея супер
Спасибо за объяснения, но лучше в будущем не оставлять половину рабочего стола белым окном, очень не комфортно смотреть с телефона!) а так все супер!
хорошее видео, прошу побольше таких с js и чтоб было объяснение задач, влюбился в канал
Спасибо! Будут!
А что значит: парное или не парное???
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 ха, какой занятный момент. Только после этого коммента задумался, что это таки может быть "украинский слэнг", понятный не всем)) До этого и мысли не возникало, что нет такого термина и могут быть сложности с его пониманием (парное/не парное) :)
Спасибо большое, что доходчиво прояснили, зачем нужен index и -1 в итерации - для движения с конца. Как ни странно, до этого в сортировках были проблемы с понимаем этого.
Спасибо! :)
а я не понял почему после -1 еще и -index. можно объяснить гуманитарию?
@@tripinprogress2225 в массивах ответ ведётся с нуля. Типа первый элемент имеет индекс 0. А, допустим, если массив состоит из 5 элементов, то индекс 5 элемента будет 4.
Здравствуйте, можете ли разобрать данный фрагмент кода?
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 нельзя обращаться к символам строки по индексам? Почему мы преобразуем её в массив?
Можно, это как одно из улучшений алгоритма можно рассмотреть, но на самом деле для скорости и работоспособности алгоритма это не будет существенным
@@itwithvitaly Только я не понимаю как это улучшит алгоритм, если и там и там можно просто сравнивать символы по индексу. Это просто лишнее действие на мой взгляд. Только если проверяем не просто число в виде строки а именно строку текста, например "А роза упала на лапу Азора", там и в нижний регистр это перевести и от пробелов избавиться, возможно потребуется массив. В JS не знаю, но в python массив не потребуется даже в этом случае.
@@СергейПресняков-о4р Улучшение в том, что не будет создаваться лишний массив, который будет занимать память. Можно делать решать без массива, не принципиально
@@itwithvitaly Я не так понял комментарий. Подумал что имеется ввиду будто преобразование строки в список как-то улучшит алгоритм, а не работа сразу со строкой. Спасибо.
const isPalindrome = str => str === str.split('').reverse().join('')
Здравствуйте, ваше решение будет работать правильно:) Но на тех интервью скорее хотят увидеть алгоритм, чем использование инструментов языка. Кстати на счет риверсии строки я уже писал много раз и объяснял почему можно сделать лучше, можете заглянуть в комменты, если интересно:)
И что? Алгоритм с инверсией строки, то же алгоритм.
@@itwithvitaly это ведь по факту тоже алгоритм, но с использованием функционального подхода
def is_palindrom(string):
return string == string[::-1]
Пайтон. По скорости и памяти не очень, но как вариант)
Удобное решение конечно :) Но на собесах обычно просят именно алгоритм) Но ваш вариант работать будет тоже конечно)
@@clauseclause6640 Не, у вас строка может быть миллион символов, вам надо сначала эту строку развернуть, потом сохранить в память, а потом еще и сравнить, а операция сравнения кстати делается посимвольно самими инструментами языков програмирования. Это очень долго и не эффективно, гораздо быстрее просто пройти строку до половины. Эффективность алгоритма и подхода определяется только на больших данных, где может быть большой затрат памяти и большие задержки
@@clauseclause6640 4 секунды? Ответ с комплексной логикой в большом приложении может меньше секунды занять, что-то здесь не так.
@@itwithvitaly не могу согласиться. Во-первых, в вашем решении вы так же дублируете данные и используете лишнюю память, причем, без причины, ведь у строк можно точно так взять элемент по индексу и узнать длину через length. Встроенные методы в js и операция сравнения строк хорошо оптимизированны, и посимвольное сравнение здесь выполняться не будет в большинстве случаев. Опять же, даже посимвольное сравнение внутри движка js и тем более питона будет дешевле, чем создание цикла, итерация по нему, обращения к элементу по индексу и проверки условия на каждом шаге.
@@itwithvitaly и самое смешное, что ваше решение точно так же посимвольно проверяет строки, ведь вы в цикле проходите i от 0 до length, а не length // 2
Привет. Как я понял твой алгоритм ломается если чисел количество элементов нечётное. В твоём примере так совпало что 12345 и не четное и не палиндром. А если бы было 12321?
И пока ты решал подумал про такой метод - ты получил массив Char, можно сделать временный массив.reverse () ( в свифте) и сравнить эти два массива на идентичность
Это не эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
С домашним заданием как то так:
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
А время на решение задачи ограничено?
Да, ограничено конечно
@@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 задачки
Мне больше всего нравится такой вариант:
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?
по старинке! )
С возвращением!)
Юрій Бережний Спасибо)
драсьте, я остановил на 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) чучуть ухудшает читаемость кода
Твой комментарий прочел как записки сумасшедшего гения, в хорошем смысле. Но интересно было наблюдать за ходом ваших мыслей, жаль нет подписки, я бы еще почитал ваши комментарии в таком стиле :)
Я смотрю вы отвечаете на все комментарии. Не много времени это отнимает?
Привет, много, но вы же потратили время чтобы написать свой комментарий и поднять мое видео, я поступаю также :)
Добрый день. Скажите, насколько отвечает требованиям данной задачи вот такое решение на 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.");
}
}
Вот так ещё на 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
Я бы без массива делал, работал со строкой, а в цикл for поставил условие i
Отлично! Можно и так как альтернатива, так тоже будет быстро работать
@@itwithvitaly спасибо за ответ. Виталий, а не мог бы ты поднять тему в своих роликах про стандартизации в JS, что такое ECMAScript 6, es6, es2015. Почему в разных стандартах разные синтаксисы, например експорта/импорта функций. Где и какие стандарты требуются. JS, вроде как, по своей сути должен запускаться везде и на всем, а получается что даже маленький тестовый код нигде не запустишь, ни из консоли на NodeJs(установкой бабеля проблема не решается, ему надо еще скормить определенные пресеты), ни в браузере не запустить(помимо требуемого вебсервера, там тоже есть свой стандарт JS - CommonJS).
Изучаю потихоньку фронт, и сам язык js не сложный, но вот эта вся обвязка вокруг него - ад.
Просто переводим в строку.
Создаем другую строку, в которую копируем реверсивную первую.
Сравниваем. Если она равны , то это палиндром
А есть объяснение решения палиндрома числа без превращения в строку?
Почему сравнением срезов строки это плохое решение?
Потому что с точки зрения алгоритмической сложности это делать дольше
Можно рассмотреть более интересные задачи которые могут дать на собесе, задач по обходам деревьев, графов.
Из 30+ собесов на которых я был и 25+ где проводил сам с другими собеседующими, только однажды была задача на рекурсивных обход дерева (нужно было папки обойти). В основном дают что-то попроще особенно на Джуниор вроде Палиндрома, работа со строками или оптимизация работы с массивом. Но обычно 60-90% собеседования это теория и задачи на "подумать"
@@itwithvitaly Понял, спасибо
Ахахах, буквально недавно решал эту задачу с сайта проекта Эйлера, но делал это немного другим методом. Рад, что такие простые задачки бывают на собеседованиях, аж гора с плеч
😃👌
А что в Яве нет цикла while?
Честно сначала решения задачи первое о чем подумал так это инициализировать массив типа char с длиной равной длине строки, которую подаем на вход методу, а потом в цикле пройтись и в каждую ячейку с помощью метода charAt() подоставать символы из строки и таким образом сформировать массив из символов. но стоило ли так напрягаться когда есть готовый метод который делает все выше написанное в одну строку. Теперь я понял почему однажды провалил интервью. Автор верно сказал о том что должно быть как можно меньше манипуляций. Абракадабра в коде никому не нужна.
print(("No", "Yes") [st == st[::-1]])
На питоне так, если нет отрицательных и чисел с точкой)
Хорошая задачка) Решил без проблем и эту, и ту с парной суммой чисел) Не подскажите хороший сервис с задачками по программированию?
leetcode
Спасибо! :) Подскажу: hackerrank, codewars, leetcode
Агонь, но более искушенные и иногда (****) итервьюверы, ждут чего-то наподобие:
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)
А о какой именно книге про алгоритмы вы упомянули в видео?
Здравствуйте, не помню чтобы упоминал о какой-то, киньте таймкод в видео, пожалуйста.
@@itwithvitaly -> 3:13
Да, что можно почитать по алгоритмам?
У меня бы такой код не прошёл ревью :) Надо добавить break в цикл, плюс по всему массиву идти не надо, только до середины, иначе получается двойная работа.
Ilya A Так и есть, я об этом в гугл доке (ссылка есть в комментах) и намекнул, чтобы те кто будет писать улучшили мой алгоритм и подумали
IT с Виталием Карнаухом тогда 👍
А зачем в цикл добавлять break, если есть return false?
@@ЕвгенийАлексеев-о9э да тут вообще не нужна булевская переменная по факту
@@ЕвгенийАлексеев-о9э для того, чтобы если например в начале цифры не совпали то прерывать цикл так как без брейк он проверит все равно его до конца, а это не имеет смысла- пустая трата ресурсов и времени
В Яндексе на стажировку Джуна такие задачки в основном или по сложнее?
Не в курсе про Яндекс, но предполагаю что сложнее гораздо
Вы упомянули книжку по алгоритмам. Что за книжка?
cracking the coding interview
@@itwithvitaly спасибо
Чувак, а мы не проходимся 2 раза по одним и тем же элементам разве?(после того, как доходим до середины массива)
Почему нельзя до середины массива проверять?
index
Можно, я об этом в доке написал которую прикрепил в комментах что мой алгоритм можно улучшить, я это и имел ввиду
@@itwithvitaly аааа) поняла) тогда извиняюс-сс 😊
Блин, я бы не додумался до такого) Я бы создал внутри метода новую переменную, которой присвоил бы ревеснутое значение аргумента метода, а потом просто сравнил его с аргументом)
Как вариант, но обычно просят именно такое решение как я показал, и на это есть причины :)
Самый простой способ с помощью reverse
Но в этом ролике я получил новую способ
Подскажите пожалуйста, что за IDE? В комментариях ответа не нашел((
Это не IDE, это онлайн Sandbox называется "codesandbox", если понравилась расцветка, то можете ее поставить почти на любую IDE, называется OneDarkPro
Как называется IDE из видео?
Виталий, 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.
В чем проблема на собесе показать решение и через цикл и через реверс строки?
А никакой проблемы и нет, можно показать, но обычно в таких задач в основном оценивается алгоритмическая подготовка, чем знания конкретных инструментов языка. Т.е. если вас попросят перевернуть связный список, это не значит что надо сделать Collection.reverse(myList) и на этом закончить. Тут интересует скорее как вы это с нуля напишите без утилитных методов самого языка.
это наверно в 2008 давали на интервью, почитайте более современные статьи, а вообще обычно на интервью дают задачи с таких площадок как литкод или кодварс, ну и раз уж тут js, то также тестят стэк библиотечный заданиями а-ля создай список чекбоксов на реакте\вью\ангуляре
А как тогда мне эту задачу в 2020 году давали на собесах минимум раза 3?
Я как то делал такое тестовое задание, правда в описании тз палиндром был словом а не цифрой.
Но не в этом суть. Хочу дополнить что не обязательно проходить индексом весь массив целиком, достаточно пройти половину округленную в большую сторону.
Так и есть :) Я об этом намекнул в доке, ссылка на которую есть в комментариях.
вообще-то в меньшую, поскольку для массива нечетной длины округление половины длины в большую сторону, заставит вас сравнить элемент сам с собой, так как последний будет центром и встретится лишь в единичном экземпляре, а для четной длины число всегда будет целым и округление ничего не даст.
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 посмотрел в комментах, даже не подумал об этом)
Скобки фигурные забыл))
Я бы предпочёл сделать новую функцию, которая была бы рекурсивной, сравнивала елементы и если они равны - вызывалась со следующлими, а если же нет, то возвращала false
Буду ждать курса от вас)
Спасибо!
На Java я первое, что пришло на ум, захотел сравнить по equals() исходную строку с реверсивным её вариантом
Так не совсем эффективно, из-за расхода по памяти и скорости на больших объемах, я описывал уже это в комментариях, можете заглянуть если интересно :)
Что будет если сказать "а можно загуглить"? Ведь все знают, что забери в разработчиков гугл, и стековерфлов в частности, они почти ничего сами не могут сделать.
А я бы строку спарсил бы в int, далее создал бы новую переменную и присвоил бы ей значение спарсенной строки. Далее методом reverse я бы вторую переменную бы изменил. И далее сравнил бы два числа, если они идентичны, то это палиндром.
А нигде не указано, что число влезет в int
Очень хорошое видео!
Неожиданным для меня оказался такой if, он сделал код более компактным, просто я решил эту задачу используя nested for ну и разумеется, не помешало бы в код добавить break после присвоения булевому значению false в случае, если значения чисел не совпали, чтобы оптимизировать код и не делать лишних проверок, но такое решение поставленной задачи мне понравилось, благодарю!
Я только начал изучать JS (прошел основы), можете, пожалуйста сказать, это видео примерно для какого уровня? То есть эту задачу могут спросить на собеседовании на джуна, спасибо за видео.
Здравствуйте, это видео в целом для всех уровней, потому что такого рода задачи задают как и начинающим на собеседованиях, так и Senior-ам с несколькими годами опыта.
@@itwithvitaly спасибо за ответ, буду развиваться
George Bush Удачи!
На JAVA:
public static boolean isPalindrom(String number) {
char[] c = number.toCharArray();
ArrayList numbers = new ArrayList();
for (int i = 0; i
function isSumEven (numAsString) {
const arrOfChars = numAsString.split('');
const sum = arrOfChars.reduce((a, b) => a + +b, 0);
return sum % 2 == 0;
}
Почему бы просто не перевернуть строку и сравнить с исходной?
Потому что на собеседовании хотят получить понимание того, можешь ли ты мыслить алгоритмически
а я бы сделал бы как то так
(C#)
var charNumbers = numbers.ToCharArray();
return charNumbers.Reverse().ToString() == numbers ? true : false;
Можете оценить что вы думаете по поводу данного решения?
сразу подумал о таком же решении
Внесу свои пять копеек. Не заметил в комментах такого решения:
const isPalindrome = str => str.split('').every((element, index, array) => element === array[array.length - 1 - index]);
Привет, да, такого не было еще :) Единственное что, every() обычно пойдет до конца массива, чтобы проверить предикат, и даже если сделаешь return это особо не поможет, т.к. у нас просто функция и return по сути остановит только ее выполнение, а не все выражение every. В этом минус, конечно, с обычным циклом можно сразу все выполнение оборвать, если вдруг число не Палиндром.
@@itwithvitaly Почему же? Выполнение функции every() будет остановлено, если callback функция вернет false. Оставшиеся элементы массива обработаны не будут.
Хороший выпуск)
У тебя не было желания стать ментор или сделать не большой курс (до 10 человек)?
Спасибо!) Вообще пока не планировал, возможно в будущем и если этого будет хотеть аудитория :)
Как то так:
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
Привет, гуд!
Недавно занялся js, в этом задании просто развернул число в строке и сравнил, и все. А так, конечно split делает массив из строки, reverse переворачивает массив и join собирает обратно в строку, осталось сравнить и всё
В комментах много раз писал почему такое решение не подходит для собеса, можете заглянуть, если интересно:)
@@itwithvitaly тогда просто перебирать строку с начала до середины и с конца до середины, и сравнивать, так тоже можно
как в случае использования string и реверсивный стринг смотрят на интервью?
Mikhail Tikhonov Не очень понял вопрос , если честно :) Если вы про входной параметр, то вариаций может быть много
Был похожий вопрос дальше. Реверсия строки - плохо. Нужно полностью перебрать строку, сохранить риверсивную копию в память и затем еще и сравнение сделать - очень затратно и очень не оптимально. Гораздо проще 1 циклом перебрать
@@itwithvitaly понял спасиб)
Здравствуйте Виталий, спасибо за ваши видео на Python придумал такие решения, синтаксис и логика будут отличаться, от С- подобных языков, о которых вы упомянули в начале видео.
def isPalindrome(string):
return string == string[::-1]
def isaSumEven(string):
templist = map(int, list(string))
return sum(templist) % 2 == 0
Здравствуйте, ваше решение работать будет но это не совсем эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации, алгоритм не ломается когда число не четное, оно все равно пройдет полный путь сравнения, можете попробовать :)
Логика не особо отличается по логике так же можно написать на любом языке взять слайс строк и развернуть потом сравнить по синтаксису такой же синтаксис может быть в любом языке где поддерживается такой же сахар над слайсами))
Ну я не знаю, если честно стоит ли писать в таком стиле на интервью потому что у интервьюера могут появиться к Вам лишнее вопросы например сколько берет памяти такой алгоритм или алацируется ли новая память под этот слайс или это происходит инплейс и тд но если вы хорошо знаете все эти нюансы в языке то конечно и так можно писать
Я подумал привести к массиву, развернуть, привести обратно к строке, проверить. А в твоем варианте можно в условие добавить, что бы индекс был не больше половины от длинны массива. Эта задача не выглядит сложной. Я думал на собеседовании что-то жутко страшное
С реверсией это простой вариант, не очень подходит для собесов, в комментах много раз писал почему, можете заглянуть, если хотите :) Не, страшного ничего не спрашивают, по алгоритмам сильные собесы обычно в Западные компании, в СНГ по алгоритмам обычно не сильно гоняют:)
function isPalindrome(numberAsString) {
return numberAsString === numberAsString.split('').reverse().join('');
}
Все!
Здравствуйте, как я уже многим и писал такое решение работать будет, но проблема в том что когда мы пытаемся решить какую-то задачу, нам нужно найти максимально быстрый и эффективный по памяти алгоритм. В данном случае все ок будет работать если строка будет маленькая, а представьте если строка будет миллион символов. Нам прийдется развернуть всю строку, сделать новую на такой же миллион символов, выделить на нее такое же кол-во памяти , т.е. 2 строки по миллиону, а потом еще и сделать сравнение, которое кстати языком программирования проводится посимвольно, поэтому я рекомендую использовать цикл, там будет всего 1 проход и всего до половины строки. Эффективность алгоритма определяется на больших данных.
@@itwithvitaly да, вы правы, в случае строки с миллионом символов, пожалуй, стандартный js-алгоритм реверса будет отрабатывать заметно медленнее, но я написал именно такое решение, потому что речь шла о числах - ну пусть 20-значное число будет обрабатываться, к примеру. В таком случае потери времени будут минимальными. Просто смотря для чего данную функцию применять.
Цикл в пол длины текста, сравниваем синхронно с начала и с конца, если не совпадает выводим "false" и используем "break" что бы завершить бессмысленное продолжение перебора, иначе перебераем до конца и выводим "true"
function palindrom(numberAsString) {
const reverseNumber = Array.from(numberAsString).reverse().join("");
return numberAsString === reverseNumber;
}
Здравстуйте, в комментах писал почему решение с риверсией не самое лучшее, что можно показать на собесе, если интересно можете заглянуть :)
IT с Виталием Карнаухом , да, спасибо, увидел )
Вторая задача так выглядет:
int polinom = 12321; // 0, 123, 4321
int sum =0;
do{
sum += polinom % 10;
}while(polinom = polinom /10) ;
Со стрингом можно работать как с массивом, так что:
function isPalindrom(numberAsString) {
for (let i = 0; i
Отлично. Единственное что, я бы не делал вот этого numberAsString = numberAsString.toString();
Точнее если бы и делал, то в другую переменную. С точки зрения работоспособности кода с ним ничего не произойдет если сделать как вы написали, но с точки зрения стиля кода обычно не меняют входные параметры.
@@itwithvitaly знаю, убрал до вашего комментария. Надеюсь браузеры начнут таки поголовно использовать typescript чтобы необходимость в перестраховках отпала.
А не слишком сложно?
Разве не достаточно просто скопировать входящие число развернуть его и сравнить с изначальным входящим числом?
Не, строка может быть очень большой, на такое решение расходуется очень много памяти и времени. Если интересно можете в комментах посмотреть, я там развернуто отвечал как раз на этот вопрос :)
@@itwithvitaly ну тогда и записывать в isPalindrome не надо. просто кидаем return false; экононмим такты процессора)
А задача ведь элементарная. Разве у интервьюера не может появиться ощущение, что ты немного недалёкий, раз так долго решаешь и подробно объясняешь такие простые вещи?
Одно дело, когда кандидат решил задачу за две минуты, и совсем другое, когда ты выслушиваешь его нудные объяснения уже десяток минут. Мне бы второй показался, ну, немного дурачком... Это ведь не какой-то тяжёлый для восприятия алгоритм..
Или я в своих размышлениях ошибаюсь?
Здравствуйте, если решите быстро это только вам +. Но делайте это вслух, объясняйте свое решение и проговаривайте свои мысли. Также не забывайте что это скорее всего будет незнакомая вам задача, а на интервью может быть несколько человек которые будут следить за каждым шагом и действовать не нервы. Гарантирую вам это совершенно по-другому)
@@itwithvitaly звучит тоже разумно. Дело в том, что на таких задачах вроде и надо что-то объяснять, а объяснять и нечего: в голове абсолютно пусто и ты просто пишешь код.
По поводу стрессоустойчивости, я участвовал некоторое время в олимпиадах по программированию. Очень надеюсь, что это поможет. )
Хотя там никто прямо за тобой непосредственно не наблюдает.
И мне бы хотелось задать ещё пару вопросов. Будет ли хорошей идеей спросить у интервьюера сразу, интересует его лёгкое и красивое решение, либо быстрое? И будет ли хорошей идеей сначала написать код, а потом его объяснять, либо, всё-таки, лучше не рисковать и проговаривать по ходу решения?
Чел, зачем такие сложности? Не проще ли просто развернуть число задом на перёд, и сравнить с исходным числом?
если строка на n символов, как будет пройтись быстрее: по n/2 или n элементам?
Это не эффективно, на алгоритм всегда надо смотреть с расчетом на то, что он будет обрабатывать большие объемы информации.
А в питоне:
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'
Какой всё-таки питон лаконичный))
Что за компилятор ?