Тестовое задание 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 минут - слишком много подводных камней бьют по мизинцам. |
Сделал "на коленке" минут за 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> |
Не поверил конечно, но ладно. Спасибо за вариант.
p.s.: пошел убивать прослушку. видимо у меня совсем мозг не работает. |
Цитата:
|
Предложу такой вариант...
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; }; |
Я начал делать, а потом подумал: что если среди символов цифры?.. Что если символов больше 256 подряд?.. Нужны какие-то разделители?.. Тащем понял, что тупо конечно можно сделать действительно за 5 минут, но если нужна работающая реализация для любых строк, с нормальным кпд, которую потом ещё и разархивировать можно, то это уже надо отдельно думать.)
|
: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> |
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('')); |
Завтра Яшка всем тут отказы напишет. :D
|
Вариант рони понравился ибо украсть этот код не получится. Такая последовательность никогда не просплойтиться и идею не возможно будет утащить тупо прослушкой.
А я, увы, похоже больше не смогу развиваться в этом ключе. :cray: 6 лет с депутатами, беретами и киношниками и еще всех не упомнить уже сделали мой мозг не восприимчивым к таким формам мышления. Как застрял в 2011 - так там и торчу в области программирования. С версткой еще как-то мозг развивается немного. ;) Все не плохо. Если не могу работать сам - значит за меня будут работать другие, а я получать за то, чтобы им работать не мешали. :victory: Пошел накачаю какого нибудь сутулого беднягу красноглазика, который круглосуточно пишет код и не подозревает о том что кто-то его бережно разрабатывает ;) |
если я правильно понял, надо "схлопнуть" одинаковые символы, и указать их количество, если более одного.
var str = 'AAAADEEESSQQQQQQ'; var result = str.replace(/(.)\1+/g, function(m, c) { return c + m.length; }); alert(result); |
Так это уже тысячу раз обсуждалось. Сжатие по хафману хорошо работает. с построением дерева и расчета весов на узел. Можно еже добавить семейство алгоритмов LZMA и получим самый настоящий zip.
Цитата:
|
А теперь с такой строкой, пожалуйста:
'AAAADEEESSQQQQ1111122QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ'естесно с возможностью распаковать:) |
Aetae,
var str = 'AAAADEEESSQQQQ1111122QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ'; var result = str.replace(/(.)\1+/g, function(m, c) {return c + '('+m.length+')'}); alert(result); |
j0hnik, вооот, уже разделители пошли, а на средне "шумном" - это приведёт не к сжатию а к увеличению.)
А ещё надо учитывать, что в строке могуть быть скобочки.) Тащем архиватор - это вам не хухры-мухры. Впрочем собес я получается тоже завалил: слишком много думаю. Есть тз, должен быть результат. Думать не надо. Любые доработки - за отдельные деньги.) |
Aetae,
Это же тестовое задание, тут цель эксперимента проверить способность испытуемого, а не придумать новый алгоритм сжатия который будет лучше существующих. |
именно. Алгоритм сжатия - это было бы задание дома сделать и прислать ответ. А если "на 15 мин в сраном блокнотике" - как раз простое схлопывание повторяющихся символов в строке только из букв. Ну и конечно, простое очевидное решение с регексом делается за минуту, хотя они, скорее всего, ожидали с циклом что-то..
|
Цитата:
|
Цитата:
|
Цитата:
|
Вы еще и работаете? xD Я пришел - прослушку им впердолил и смотался, сижу получаю помаленьку ...
У кого много времени - возьму к себе ;) |
и что слышно?
|
Цитата:
Я 5 лет назад по ошибке когда меня в прослушку взяли сбежал из москвы с системной программой и засплойтил без малого пол Екатеринбургских IT компаний после чего долго сидел и п3,14здился с системниками. К слову, альфа волны это такая тема на маленькой частоте которая работает по всему покрытию сотовой связи почти через любые бытовые приборы даже с простейшими интегральными схемами. А вы сидите у компьютера и ничего не подозреваете, постоянно то яблоко то зеленого человечка к уху подносите и в руках крутите ... :agree: Собсно, оно просто называется прослушка - на деле это гораздо большее, наушники например не нужны. У меня даже чириканье воробьев модулируется в голос или даже шум бегущей воды из крана. То что мы слышим через эту херню - это вообще не звук даже по своей природе. :write: А яшки - че они? Екатеринбургский оффис не так интересен. Сложнее в московский штаб было залезти. Они с психиатрической клиникой разрабатывались. Меня приглашали Алису разрабатывать, но я в то время с ними не подружился - мне интереснее было засплойтится в Apple или Intel. Вместо этого нас со всеми друзьями угрохали об армию и войну в Сирии с самого прямо с начала нашей новой жизни в прослушках. Не интересно короче с Яндексами - мы их подставили - они такси разработали, чтобы когда их сожрет Google они не остались с членом во рту. Но, пока им как-то везет и все хорошо. Зашел, подцепил девушку HR и юношу deva, который собеседует. Подсплойтил дежурный ноутбук :D Вот и все. Будет нужда - зацепим весь оффис сразу через них же. :thanks: У меня к ним прослушка есть, а у них ко мне нет. Я их софтом не пользуюсь. Раньше я вообще прошивку даже на телефон перерабатывал до такой степени что там ни одной программы от Google не оставалось и жили мы чисто с системными программистами. А сейчас мы разработали систему тут в РФ и нас уже не просплойтить так просто. Не взламываемся почти что. И людей берем только молодых, активных, рисковых и здоровых. :victory: |
Часовой пояс GMT +3, время: 06:35. |