Здравствуйте, AmSpb, Вы писали:
AS>Можно не знать реализации тех или иных структур и алгоритмов, но знать сложность обязан, а если лень знать, распечатываешь и вешаешь перед собой
Знать за сложность надо, да. Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры.
А то ж порой бывает и так что алгоритм с линейной сложностью работает быстрее чем с логарифмической, просто потому что цена одного "шага" разная.
Комменты вообще огонь я считаю и реально театр абсурда. Каждый второй сводится к тому, что "я хотел бы в Яндекс, но как только захожу на Литкод, корона нестерпимо давить начинает".
Здравствуйте, CreatorCray, Вы писали:
AS>>Можно не знать реализации тех или иных структур и алгоритмов, но знать сложность обязан, а если лень знать, распечатываешь и вешаешь перед собой CC>Знать за сложность надо, да. Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры. CC>А то ж порой бывает и так что алгоритм с линейной сложностью работает быстрее чем с логарифмической, просто потому что цена одного "шага" разная.
Да, понимать тоже стоит, но без деталей, т.к. детали со временем забываются, остается только общее понимание.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, sergey2b, Вы писали:
S>>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке
L>Лучше, в основном. Реверс строки или слов в строке — это уже заезженная пластинка.
Для тебя заезженная. Для многих нет.
S>>и поиск цикла в list
L>А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
Если не знаешь, можно поговорить. Там 3 варианта решения, соответственно, "без использования памяти и модификации"- можно подсказать.
Здравствуйте, sergii.p, Вы писали:
SP>особенно понравилось SP>
SP>Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз.
SP>Реально питон головного мозга. Вроде и программист, но как с другой планеты.
Господа, ну зачем сразу "питон'? Вы вообще в курсе, что на питоне отсчитывают всякие там корелляции и финансы- там сложность — первое требование.
А отквоченный текст- это я считаю, типичный руссо-укро-беларусский программист. Да. 99% таких чуваков можно опознать ещё по упоминаниям мифических индусов, за которыми они разгребают.
Здравствуйте, Тёмчик, Вы писали:
Pzz>>Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
Тё>Наблюдал, как весьма хорошие программисты, успешно и быстро решившие тот же переворот, впадали в ступор при подсказках про поиск цикла.
А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами?
Здравствуйте, Pzz, Вы писали:
Pzz>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>[AAAA][BBBBB] -> [BBBBB][AAAA]
Переворачиваем сначала весь массив, а потом переворачиваем каждую часть.
Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Здравствуйте, Pzz, Вы писали:
Pzz>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами?
Pzz>[AAAA][BBBBB] -> [BBBBB][AAAA]
Можно как разворот строки решить, сходу, за 2с*O(N). Можно заморочиться чтоб за c*O(N-1), то мне лень мозг вывихивать.
Здравствуйте, Буравчик, Вы писали:
Pzz>>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>>[AAAA][BBBBB] -> [BBBBB][AAAA]
Б>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся.
[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA]
Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Здравствуйте, Pzz, Вы писали:
Б>>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Pzz>Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся.
Pzz>[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA]
Pzz>Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Это двойной переворот.
Можно сделать циклический сдвиг, получится O(N):
[0..k), [k..n)
Как-то так, но нужно проверять правильность offset:
function swap_k<T>(a: T[], k: number) {
const n = a.length;
if (k === 0 || k === n - 1) {
return;
}
const acc = a[k];
const offset = n / 2 + n % 2;
for (let i=0; i < offset; ++i) {
a[(k + i) % n] = a[(k + offset + i) % n];
}
a[k + off] = acc;
}
Здравствуйте, Pzz, Вы писали: Pzz>>>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>>>[AAAA][BBBBB] -> [BBBBB][AAAA] Б>>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д. Pzz>Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся. Pzz>[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA] Pzz>Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Двойной разворот -- это из "Потрескивания на интервью по написанию кода". А интересная оказалась задача, вот мой однопроходный вариант:
function swapArrayParts(arr, ind) {
if (!Array.isArray(arr))
return "Incorrect array.";
var len = arr.length;
if (!Number.isInteger(ind) || ind < 1 || ind >= len)
return "Incorrect index.";
var i, curPos = 0, oldPos, newPos, oldBuff = arr[curPos], newBuff;
for (var i = 0; i < len; i++) {
newPos = curPos < ind ? curPos + len - ind : curPos - ind; // New position to drop the previous buffered item.
newBuff = arr[newPos];
arr[newPos] = oldBuff;
if (oldPos === newPos) { // 2 elements have swapped, move to the next item in the 1st subset.
curPos = newPos + 1;
oldBuff = arr[curPos];
}
else { // Leap with the buffered value to the new position.
oldPos = curPos;
curPos = newPos;
oldBuff = newBuff;
}
}
return arr;
}
Тест
<html>
<body>
<form onsubmit="javascript:swapArr(); return false;" >
<p>
Array (chars w/o delimiters): <br/><input type="string" id="arr"> <p>
Pivot (0-based index of the first item in the 2nd subset): <br/><input type="number" id="ind" min="1"> <p>
<input type="submit" value="Swap">
</form>
Result:<p>
<p id="output"/>
<script>
function swapArrayParts(arr, ind) {
if (!Array.isArray(arr))
return "Incorrect array.";
var len = arr.length;
if (!Number.isInteger(ind) || ind < 1 || ind >= len)
return "Incorrect index.";
var i, curPos = 0, oldPos, newPos, oldBuff = arr[curPos], newBuff;
for (var i = 0; i < len; i++) {
newPos = curPos < ind ? curPos + len - ind : curPos - ind; // New position to drop the previous buffered item.
newBuff = arr[newPos];
arr[newPos] = oldBuff;
if (oldPos === newPos) { // 2 elements have swapped, move to the next item in the 1st subset.
curPos = newPos + 1;
oldBuff = arr[curPos];
}
else { // Leap with the buffered value to the new position.
oldPos = curPos;
curPos = newPos;
oldBuff = newBuff;
}
}
return arr;
}
function swapArr() {
var arr = document.getElementById("arr").value;
var ind = document.getElementById("ind").valueAsNumber;
var output = swapArrayParts(arr.split(""), ind);
document.getElementById("output").innerHTML = output;
}
</script>
</body>
</html>
Здравствуйте, sergey2b, Вы писали:
S>Да автору не зачёт S>Большая честь задач не сложные
пост же не про задачи сами по себе, а что одну и ту же пластинку ставят раз за разом. такое ощущение что это какие то hunger games заочные, ищут самого выносливого и/или мотиварованного что ли.
Здравствуйте, sergey2b, Вы писали:
S>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке S>и поиск цикла в list
S>https://habr.com/ru/post/550088/ S>Собеседование в Яндекс: театр абсурда :/
Я как-то собеседовался в Яндекс (в Минске) лет 6 назад. Причём честно предупредил, что у меня нет высшего образования, только среднее специальное, а остальное доучиваю сам по необходимости.
В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами.
Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно.
Оказалось, что от меня хотели, чтобы я просто взял предел.
Я конечно всё понимаю и не утверждаю, что это бесполезные знания, но по-моему это уже какой-то бзик, где такие вот вопросы ставят выше умений проектировать архитектуру и знаний языка.
Здравствуйте, SaZ, Вы писали:
SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? SaZ>Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами. SaZ>Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно. SaZ>Оказалось, что от меня хотели, чтобы я просто взял предел.
А причем тут предел ?
Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n
Здравствуйте, AmSpb, Вы писали:
AS>Здравствуйте, SaZ, Вы писали:
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? SaZ>>Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами. SaZ>>Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно. SaZ>>Оказалось, что от меня хотели, чтобы я просто взял предел.
AS>А причем тут предел ? AS>Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n
Рисовал график. От меня требовали именно теоретическое обоснование.
Здравствуйте, Тёмчик, Вы писали:
Тё>Господа, ну зачем сразу "питон'? Вы вообще в курсе, что на питоне отсчитывают всякие там корелляции и финансы- там сложность — первое требование.
Это всё скорее всего "отсчитывается" библиотеками, которые ты подцепил
