Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Тестовое задание Yandex (https://javascript.ru/forum/misc/72457-testovoe-zadanie-yandex.html)

xShift 30.01.2018 16:13

Тестовое задание Yandex
 
Собственно, на задание отведено 15 минут и запрещено запускать консоль. Можно писать код в блокноте и объяснять ход мыслей.

Задача: Есть строка вида "AAAADEEESSQQQQQQ";
Нужно сделать простейший архиватор и выдать что-то вроде: "A4DE3S2Q6".

Поскольку собеседование я засрал, но интерес остался - вот потуги моей деятельности за 3 часа мозго-секса.


var originalString = 'HRRAAAABBZGGU';

		function archiver(data) {

			var elements = data.split("");
			var compressedData = "";
			var compressRate = 1;

			var repeats = [];

			var rate = '';

			for( var i in elements ) {

				if( elements[i++] === elements[i] ) {

					var currentRate = compressRate++;

					repeats.push(currentRate);
					rate += currentRate - "";
				
				} 
				else {

					compressRate = 1;
					repeats = [];
					rate = '';

				}

				i--;

				compressedData += ( repeats.length > 0 ) ? elements[i] + (Math.max.apply(null, rate.split('')) + 1 ) : ( typeof elements[i] !== 'undefined' ) ? elements[i] + '1' : '';
				
			}


			var compressedResult = compressedData.split('');
			var testLetter = '';

			for( var x in compressedResult) {

				if( compressedResult[x++] !== compressedResult[x] ) {
					x--;
					testLetter += ( typeof compressedResult[x] !== 'undefined' ) ? compressedResult[x] : ''; 
				}

			}


			function pairs(testLetter) {
				var pairs = [];

				for( var i = 0; i < testLetter.length / 2; i++ ) {
					pairs.push( testLetter.slice( 2 * i, 2 * i + 2 ) );
				}
				return pairs;
			}


			var compressedDataString = '';


			for( var n in pairs(testLetter) ) {

				if( n == 0 && pairs(testLetter)[n].split('')[1] === '1') {
					compressedDataString += pairs(testLetter)[n].split('')[0];
				}

				var first = pairs(testLetter)[n];
				var second = ( typeof pairs(testLetter)[(n - 0)+1] !== 'undefined' ) ? pairs(testLetter)[(n - 0)+1] : '';

				if( (n - 0) > 0) {

					if( first.split('')[0] == second.split('')[0] ) {

						compressedDataString += first.split('')[0] + first.split('')[1];
					} 
					else {
						//n++
					}
				}

			}

			console.log( compressedDataString );


			return compressedData;

		}

		archiver(originalString);


Она выдает: HR2A2A3A4B2G2

Собсно, я знаю что это говнокод и знаю что неприкольно не доводить до конца, но пока я решал задачу дома - пришло письмо с отказом(мол не тот уровень). Кодить я бросил и предлагаю рушить задачу либо дописав мой говнокод, либо написав с нуля. Просто интересно во сколько по времени вы оцените решение данной постановы.

Я лично припарился :D Не знаю что там насчет 15 минут - слишком много подводных камней бьют по мизинцам.

Nexus 30.01.2018 16:28

Сделал "на коленке" минут за 5 (не засекал):

<input type="text" id="input" />
<div id="display"></div>
<script>
    document.getElementById('input').addEventListener('input', function() {
        document.getElementById('display').innerHTML = pack(this.value);
    });

    function pack(str) {
        var last_char,
            counter = 1,
            res = [];

        (str + '.').split('').forEach(function(char, i, list) {
            if (last_char == char)
                counter++;
            else {
                res.push(last_char);
                if (counter > 1)
                    res.push(counter);

                last_char = char;
                counter = 1;
            };
        });

        return res.join('');
    };
</script>

xShift 30.01.2018 16:39

Не поверил конечно, но ладно. Спасибо за вариант.

p.s.: пошел убивать прослушку. видимо у меня совсем мозг не работает.

Nexus 30.01.2018 16:49

Цитата:

Сообщение от xShift
Не поверил конечно

Во время реализации?

ksa 30.01.2018 16:59

Предложу такой вариант...

var str="AAAADEEESSQQQQQQ";
alert(arh(str));
function arh(Str){
	var cnt=0;
	var old=Str.slice(0,1);
	var arh=old;
	for (var i=1; i<Str.length; i++){
		var val=Str.slice(i,i+1);
		if (val==old) {
			++cnt;
		} else {
			arh=arh+((cnt==0)? '': ++cnt)+val;
			old=val;
			cnt=0;
		};
	};
	if (cnt>0) {
		arh=arh+(++cnt);
	};
	return arh;
};

Aetae 30.01.2018 17:09

Я начал делать, а потом подумал: что если среди символов цифры?.. Что если символов больше 256 подряд?.. Нужны какие-то разделители?.. Тащем понял, что тупо конечно можно сделать действительно за 5 минут, но если нужна работающая реализация для любых строк, с нормальным кпд, которую потом ещё и разархивировать можно, то это уже надо отдельно думать.)

рони 30.01.2018 17:27

:write:
было задание массив соединение диапазонов
решено так:
<script>
function fn(f) {
  var c = void 0;
  return f.reduce(function(e, d, a, b) {
    a = d + 1 == b[++a];
    b = void 0 === c;
    a && b ? c = d : a || b ? !a && b && e.push(d) : (e.push(c + "-" + d), c = void 0);
    return e;
  }, []);
};
var data = [35, 3, 6, 9, 11, 12, 13, 14, 15, 39, 9, 21, 25, 26, 27];
document.write(JSON.stringify(data) + '<br>' + JSON.stringify(fn(data)))
</script>

...лёгким росчерком переделано в архиватор :)
<script>
function fn(f) {
  var c = void 0;
  return f.split('').reduce(function(e, d, a, b) {
    a = d == b[++a];
    b = void 0 === c;
    a && b ?(c = 2) : a && c++ || b ? !a && b && e.push(d) : (e.push(d + c), c = void 0);
    return e;
  }, []).join('');
};
var data = 'AAAADEEESSQQQQQQ';
document.write(JSON.stringify(data) + '<br>' + JSON.stringify(fn(data)))
  </script>


...продолжение
<script>
function fn(f) {
  var c = 0;
  return f.split("").reduce(function(e, d, a, b) {
    (a = d == b[++a]) && !c ? c = 2 : a && c++ || !c ? !a && !c && (e += d) : (e += d + c, c = 0);
    return e;
  }, "");
};
var data = 'AAAADEEESSQQQQQQ';
document.write(JSON.stringify(data) + '<br>' + JSON.stringify(fn(data)))
  </script>

ещё чуть-чуть :write:
<script>
function fn(f) {
  var c = 0;
  return f.split("").reduce(function(e, d, a, b) {
     (a = d == b[++a]) && !c && (c = 1);
      a ? c++ : (e += d, c && (e += c, c = 0))
     return e;
  }, "");
};
var data = 'AAAADEEESSQQQQQQ';
document.write(JSON.stringify(data) + '<br>' + JSON.stringify(fn(data)))
  </script>

laimas 30.01.2018 18:06

alert('AAAADEEESSQQQQQQ'.split('').reduce(function(m, c, i, a) {
    if(c == a[i+1]) m[m.length-1]++; 
    else {
        m[m.length-1] = c+m[m.length-1];  
        if(a[i+1]) m.push(1);
    }
    return m
}, [1]).join(''));

laimas 30.01.2018 18:17

Завтра Яшка всем тут отказы напишет. :D

xShift 30.01.2018 18:19

Вариант рони понравился ибо украсть этот код не получится. Такая последовательность никогда не просплойтиться и идею не возможно будет утащить тупо прослушкой.

А я, увы, похоже больше не смогу развиваться в этом ключе. :cray:

6 лет с депутатами, беретами и киношниками и еще всех не упомнить уже сделали мой мозг не восприимчивым к таким формам мышления. Как застрял в 2011 - так там и торчу в области программирования. С версткой еще как-то мозг развивается немного. ;)

Все не плохо. Если не могу работать сам - значит за меня будут работать другие, а я получать за то, чтобы им работать не мешали. :victory:

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

Alexandroppolus 30.01.2018 18:36

если я правильно понял, надо "схлопнуть" одинаковые символы, и указать их количество, если более одного.

var str = 'AAAADEEESSQQQQQQ';

var result = str.replace(/(.)\1+/g, function(m, c) { return c + m.length; });

alert(result);

MallSerg 30.01.2018 20:58

Так это уже тысячу раз обсуждалось. Сжатие по хафману хорошо работает. с построением дерева и расчета весов на узел. Можно еже добавить семейство алгоритмов LZMA и получим самый настоящий zip.

Цитата:

Сообщение от Alexandroppolus
если я правильно понял, надо "схлопнуть" одинаковые символы,

Это называется алгоритм RLE

Aetae 30.01.2018 21:20

А теперь с такой строкой, пожалуйста:
'AAAADEEESSQQQQ1111122QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ'
естесно с возможностью распаковать:)

j0hnik 30.01.2018 21:42

Aetae,
var str = 'AAAADEEESSQQQQ1111122QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ';
var result = str.replace(/(.)\1+/g, function(m, c) {return c + '('+m.length+')'});
alert(result);

Aetae 30.01.2018 22:56

j0hnik, вооот, уже разделители пошли, а на средне "шумном" - это приведёт не к сжатию а к увеличению.)
А ещё надо учитывать, что в строке могуть быть скобочки.)
Тащем архиватор - это вам не хухры-мухры.

Впрочем собес я получается тоже завалил: слишком много думаю. Есть тз, должен быть результат. Думать не надо. Любые доработки - за отдельные деньги.)

j0hnik 30.01.2018 23:08

Aetae,
Это же тестовое задание, тут цель эксперимента проверить способность испытуемого, а не придумать новый алгоритм сжатия который будет лучше существующих.

Alexandroppolus 30.01.2018 23:33

именно. Алгоритм сжатия - это было бы задание дома сделать и прислать ответ. А если "на 15 мин в сраном блокнотике" - как раз простое схлопывание повторяющихся символов в строке только из букв. Ну и конечно, простое очевидное решение с регексом делается за минуту, хотя они, скорее всего, ожидали с циклом что-то..

laimas 31.01.2018 02:21

Цитата:

Сообщение от Alexandroppolus
хотя они, скорее всего, ожидали с циклом что-то.

Можно быть уверенным в этом, очевидное с regex не дает представления о возможностях мышления тестируемого. Хотя может быть и прокатило бы, и был бы зачет, но тогда впоследствии были бы проблемы.

ksa 31.01.2018 08:35

Цитата:

Сообщение от laimas
Завтра Яшка всем тут отказы напишет.

Пойдем в управдомы... :D

laimas 31.01.2018 12:22

Цитата:

Сообщение от ksa
Пойдем в управдомы...

Теплые места как всегда заняты, только дворником. )

xShift 17.02.2018 20:55

Вы еще и работаете? xD Я пришел - прослушку им впердолил и смотался, сижу получаю помаленьку ...

У кого много времени - возьму к себе ;)

j0hnik 17.02.2018 20:57

и что слышно?

xShift 17.02.2018 21:53

Цитата:

Сообщение от j0hnik (Сообщение 478451)
и что слышно?

Вы что нибудь слышали про альфа волны? Не просто слышно, но еще и можно подхватить чужие манеры. Лично я их не прослушиваю ...

Я 5 лет назад по ошибке когда меня в прослушку взяли сбежал из москвы с системной программой и засплойтил без малого пол Екатеринбургских IT компаний после чего долго сидел и п3,14здился с системниками.

К слову, альфа волны это такая тема на маленькой частоте которая работает по всему покрытию сотовой связи почти через любые бытовые приборы даже с простейшими интегральными схемами. А вы сидите у компьютера и ничего не подозреваете, постоянно то яблоко то зеленого человечка к уху подносите и в руках крутите ... :agree: Собсно, оно просто называется прослушка - на деле это гораздо большее, наушники например не нужны. У меня даже чириканье воробьев модулируется в голос или даже шум бегущей воды из крана. То что мы слышим через эту херню - это вообще не звук даже по своей природе. :write:

А яшки - че они? Екатеринбургский оффис не так интересен. Сложнее в московский штаб было залезти. Они с психиатрической клиникой разрабатывались.

Меня приглашали Алису разрабатывать, но я в то время с ними не подружился - мне интереснее было засплойтится в Apple или Intel.

Вместо этого нас со всеми друзьями угрохали об армию и войну в Сирии с самого прямо с начала нашей новой жизни в прослушках.

Не интересно короче с Яндексами - мы их подставили - они такси разработали, чтобы когда их сожрет Google они не остались с членом во рту. Но, пока им как-то везет и все хорошо.

Зашел, подцепил девушку HR и юношу deva, который собеседует. Подсплойтил дежурный ноутбук :D Вот и все. Будет нужда - зацепим весь оффис сразу через них же. :thanks:

У меня к ним прослушка есть, а у них ко мне нет. Я их софтом не пользуюсь. Раньше я вообще прошивку даже на телефон перерабатывал до такой степени что там ни одной программы от Google не оставалось и жили мы чисто с системными программистами.

А сейчас мы разработали систему тут в РФ и нас уже не просплойтить так просто. Не взламываемся почти что. И людей берем только молодых, активных, рисковых и здоровых. :victory:


Часовой пояс GMT +3, время: 06:35.