« first day (1953 days earlier)      last day (1078 days later) » 

A K
6:56 PM
@tym32167 Оно не то, чтобы прям "сложно".... я вообще не в ту сторону думаю. Вот подходящий случай:
void Main()
{
	var workDir = Path.Combine(Util.MyQueriesFolder, "nunit-work");

	var args = new string[]
	{
		 "-noheader",
		 $"--work={workDir}",
	};

	RunUnitTests(args);
}

// Define other methods and classes here

[Test]
[TestCase(new int[] { 0,0,0,0,0 }, 0, new int[] { 1,2,3,4,5 }, 5, new int[] { 1,2,3,4,5 })] // A6
[TestCase(new int[] { 0 }, 0, new int[] {1 }, 1, new int[] { 1 })] // A5
[TestCase(new int[] { 1, 101,0 }, 2, new int[] { }, 0, new int[] {1,101,0})] // A0
[TestCase(new int[] { 101,102,103,0 }, 3, new int[] { 1 }, 1, new int[] {1,101,102,103})] // A1
Это затрачено два дня (в первый день 3 часа и во второй день 2 часа)
Формально: задача решена
честно расписал как видел варианты обхода
Достаточно много времени ушло на то, чтобы учесть все сценарии (штук пять тест-кейсов я сам нашлёпал, потом ещё верхних два (А5 и А6) мне сайт подкинул
И что я могу сказать даже не открывая решения других?
Я просто глядя на своё решение понимаю, что слишком оно длинное и явно я просто вообще куда-то не в ту степь решал
Это чисто случайно повезло, что в этой стороне тоже есть решение, пусть не оптимальное, но ведь его просто могло бы и не быть
смотрю на конкурентов
открываю первое попавшееся решение лучше моего
public void Merge(int[] nums1, int m, int[] nums2, int n) {
    var mPoint = m-1;
    var nPoint = n-1;
    for(int i = m+n-1; i>=0; i--)
    {
        if(mPoint == -1)
            nums1[i] = nums2[nPoint--];
        else if(nPoint == -1)
            nums1[i] = nums1[mPoint--];
        else if(nums1[mPoint] > nums2[nPoint])
            nums1[i] = nums1[mPoint--];
        else
            nums1[i] = nums2[nPoint--];
    }
}
Понимаю: да, вот это явно хорошее решение. Многократно короче моего - уже плюс, я прямо чувствую, что если начну читать его то сразу подумаю "блиииииииииин, ну ПОЧЕМУ Я не подумал в эту сторону???"
Если что: да, я читал хинты и там была вот такая подсказка:
You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?
Вот почему я эту подсказку смотрел и всё равно не так применил (в общем-то я тоже ведь сравниваю два числа), а кто-то другой понимает так, что получается кратко и изящно?
@tym32167 Они мало того, что сложно подбираемые... они какие-то кривые, нет в них изящности, даже если удалось решить -- вот какая мысль.
@tym32167 пойду гляну и эту книгу... вдруг в ней что-то попадётся такое, что повернёт мне мозги в нужную сторону
пока у меня впечатление: это только с опытом придёт, когда решишь какое-то количество задач, посмотришь свои решения с более оптимальными и какие-то ходы для себя запомнишь.
Пока что сложно идёт, небыстро.
 
7:22 PM
@AK об этом и речь. Вы де не думаете, что за пару дней выучите алгоритмы и будете красиво решать задачи? Вот вы ООП с самого начала использовали со всеми паттернами и практиками? Я, например, поначалу даже не понимал, где хороший код, а где лапша. Хотите преуспеть в решении задач - читать теорию мало, надо решать задачи. Много решать.
 
A K
@tym32167 То есть "Алгоритмические трюки для программистов" не особо помогут , да? Или это там есть хотя бы краем?
 
Не, там ловить нечего. Мне по крайней мере это не помогло никак. На собеседовании трюки показывать пойдет как бонус. А если вы не решаете задачу, то трюки вам не помогут
 
A K
Тогда значит только фигачить и фигачить как можно больше
и разбирать более оптимальные решения, сравнивая как они думали
 
Я когда-то был упорный, мне надо было всё решать самому, я не хотел тратить время на теорию, я хотел "вот прям ща сяжу и разнесу задачу", я думал, что я самый умный и гордо не глядел теорию и не смотрел ответы. В итоге вот, поглядите сюда acm.timus.ru/status.aspx?author=123649 - некоторые залачи заняли у меня по 2 года :)
Знаете, когда я решать их массов стал? Когда прошел курс алгоритмов и прочитал кнниги по алгоритмам. Базовые структуры данных мне дали пинка. Я и знать не знал, например, про Union-Find или Trie. А уже вооруженный теорией и спустивгись на землю, дело пошло гораздо быстрей.
Ваша задача же тут- научиться решать. Я смотрел оптимальные решения всех сложных задач. Конечно, хорошо сначала самому решить задачу, а потом поглядеть на лушчее решение. Но если сам не справляешься, не надо зацикливаться - я просто иду, гляжу решение, и пытаюсь понять, как бы я мог до него додуматься
@AK потому если вы без знания теории пошли просто решать задачи - то это как писать классы без знания ООП. Если вы только теорию изучаете - то это как читать про ООП, но не писать код. Вам надо и то и другое, чтобы понять, как решать задачи
 
A K
@tym32167 А я вот не знаю, когда я их массово начну решать. Книжки эти я поверхностно листал и раньше. Даст ли буст глубокое чтение? Или буст лежит в наработке? Пока не знаю.
Я в общем-то сейчас делаю задачи только на массивы, уж чего-чего, а в них вообще ничего такого нет сложного в теории.
Это вот только сегодня решил, что как-то долго идёт одна тема - надо хотя бы две паралельно решать, чтобы если какой затык, то в паралели идти вперёд
 
7:34 PM
@AK Открываете книгу - смотрите структуры данных - если вы уже знаете, что это за структура и можете сами её написать, то листайте дальше. С алгоритмом то же - если можете просто сейчас по памяти напистать MergeSort или CountingSort - то вам не надо про него читать. Теория вам дать дожна инструменты, если вы ими уже умеете пользоваться, то нет смысла перечитывать.
 
A K
И взял как раз linked list, вот и посмотрю насколько у меня "примерно понимаю о чём речь хватит для решения". Так-то я вроде односвязанные списки понимаю, как делаются, просто никогда не писал сам с нуля и не подглядывая.
 
Красиво решать алгориммы - это только с практикой. Вот вы если бы прочитали книгу по Asp.Net MVC - вы ж не смогли бы сходу писать красивый код для него? Вот с алгоритмами также. Пишите больше, тренируйтесь больше
 
A K
@tym32167 Из сортировок я по памяти только сортировку вставками и пузырёк могу минут за 10 набросать, остальное надо смотреть в книги. Тупо не помню даже сам алгоритм. Просто помню "Quick sort - одна из наиболее эффективных, её часто берут в качестве дефолтной реализации сортировок в разных библиотеках" А что там за алгоритм.. его так навскидку не обьяснишь, не вспомнишь.
 
@AK я по LinkedList столько задач решил, что мне вообще не проблема прямо сейчас сесть и решить на нем какую то задачу. Например, нахождение цикла в односвязном списке - типичная задача, или реверс односвязного списка - вообще нет проьблем, хотя я задачи уже как года 1.5 не решал совсем
@AK ""Quick sort - одна из наиболее эффективных, её часто берут в качестве дефолтной реализации сортировок в разных библиотеках"" - ну а вот вы можете сказать, почему так? Почему не MergeSort - ведь у них типа похожие асимптотики?
 
A K
А мне кстати попадалась задача на собесе на нахождение цикла в односвязном списке. Устно сказал, что с такой задачей не сталкивался, попахивает ошибкой в реализации кода, но типа если надо найти то есть только идея за эн квадрат обходить каждый элемент и смотреть не придём ли мы к нему второй раз.
@tym32167 А вот не знаю, это для меня самого тоже вопрос был именно потому что у них одинаковая сложность.
 
7:40 PM
@AK не, это типичная задача о двух бегунках, её часто задают, мне даже 2 раза попадалась )
 
A K
@tym32167 я хотел одним бегунком обойтись
# Merge sort — сортировка слиянием
Время, худший и средний сценарий: O(N log N)
Память: зависит от реализации

# Quick sort — быстрая сортировка

Время, в среднем: O(N log N)
Время, в худшем сценарии: O(N^2)
Память: O(N log N)

вот собственно что есть пока в конспекте по этим темам ^^^
 
@AK один бегунок + HashSet тоже может подойти.
 
A K
То есть по факту чуть копнёшь -- и сразу поплыву, это заученные штуки, которые не осознанны и не попрактикованы
 
@AK ну вы видиите, что QuickSort в худшем случае даже медленней
 
A K
Ладно, пойду дальше руду добывать... пока выходные и можно чуть больше посидеть над задачами. Есть кстати смысл тут тоже зарегаться acm.timus.ru или лучше пока на leetcode + hackerrank остановиться?
 
7:44 PM
@AK в этом и смысл теории, чтобы понять что и как, а не просто знать прописные истины. Вот например, я однажды решал задачу по поиску подстроки, и меня спрсили, а чего не юзать регулярки для этого? Пришлось вспомнить и как регулярки работают, и Кнутта-Морриса-Пратта
 
A K
спасибо за советы, очень полезно послушать того, кто уже ходил этими тропами и может свой опыт рассказать
 
@AK да это без разницы по идее, просто на leetcode задачи больше похожи на задачи с собеседований, когда timus и codeforces - больше задачи для соревнований
 
A K
мне пока не до соревнований, я думаю, что мне надо нарыть как можно больше лёгких и средних задач, чтобы побыстрее выйти на какой-то уровень, когда задача easy на 15 минут будет в среднем, а medium - на полчаса-час хотя бы
 
@AK ну вот на этот уровень я бы и ориентировался. Вы же сказали, что у вас квартал времени - вот рассчитывайте весь квартал решать задачи. Хотя бы по 1-2 в день
+ не зацикливайтесь на легких задачах, если чувствуете себя комфортно с легкими, уменьшайте кол-во легких и увеличивайте кол-во средних
Если вы сможете по любой из тем, что я кидал пару дней назад сюда, взять средню задачу и за 30 минут её решить (просто чтобы решение прошгло), то вы считай уже готовы к собесу
* готовы для ProblemSolving :) не забывайте про дизайн и поведенческие вопросы, это не менее важно (а если вы не сеньора метите, то дизайн даже более важен)
 
8:33 PM
:56487141
Поглядел на задачу, что вы дали (не подсматривая в ответы) и решил её вот так
public class Solution
{
	public void Merge(int[] nums1, int m, int[] nums2, int n)
	{
		for (int i = m - 1; i >= 0; i--)
			nums1[i + n] = nums1[i];

		int ind1 = n;
		int ind2 = 0;
		int ind = 0;

		while(ind < m+n)
		{
			if (ind1 < (n+m) && ind2 < n)
				nums1[ind++] = nums1[ind1] <= nums2[ind2] ? nums1[ind1++] : nums2[ind2++];

			if (ind1 == (n+m) && ind < m+n) nums1[ind++] = nums2[ind2++];
			if (ind2 == n && ind < m+n) nums1[ind++] = nums1[ind1++];
попал в 85% , потом поглядел решение и понял, что да, можно было бы и просто мерджить с конца. Оно было бы и побыстрей чуть чуть. Но асимптотике моего решения такая же, как и лучшего. По пымяти тоже самое. Получается, что мое решение тоже норм подойдет. Просто мне было понятней сдвинуть масив и потом сделать обычный Merge, а лучшее решение будет сделать Merge с конца.
имхо оба решения были бы неплохими. @AK
btw, если бы вы помнили MergeSort - там примерно также решается часть про Merge - так как там на каждом этапе слияние 2 сортированных массивов
 

« first day (1953 days earlier)      last day (1078 days later) »