LINUX.ORG.RU

А вы бы приняли такой ответ?

 , ,


0

2

Привет ЛОР!

Недавно,между делом, хотел пройти маленький тест на php задача была такова: нужно объявить массив, в цикле от 1 до 100 заполнить его случайными цифрами (тоже от 1го до 100), и в итоге получить массив с уникальными значениями, реализовать минимальным кол-вом строк

Чтоб решить по-быстрому и красиво я прибегнул к жульничеству:

<?php
$arr = range(1, 100);
shuffle($arr);
foreach ($arr as $key) {
    echo "$key ";
    }
?>

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

А сжульничал я во-первых, потому, что если генерировать случайные числа через mt_rand() нам нужно после избавиться от дублей и, в то же время, обеспечить, чтобы в массиве точно были все числа от 1 до 100.

Во-вторых, потому, что посчитал это красивым решением да и требовали минимум строк :-)

Пацаны это лечится?!

★★★★★

Последнее исправление: Twissel (всего исправлений: 2)
Ответ на: комментарий от ilovewindows

А так ты афигенно крут, посмотрел перед собеседованием функции для работы с массивами и общаться не желаешь - это давай до свидания.

Вообще то знание стандартной библиотеки очень хорошо коррелирует с опытом. И такие вопросы имеет смысл задавать. Тем более у PHP она мелкая.

A1
()
Ответ на: комментарий от Twissel

эм.. ващет это решение на массивах.. возможно они могли хотеть, чтобы ты сам реализовал shuffle, что вполне логично спросить на собеседовании. И достаточно просто сделать в 3 строки.

qnikst ★★★★★
()
Ответ на: комментарий от ilovewindows

Тоже самое что и в функции asctime, если тебе не повезло и ты не пользуешься ей каждый день то ни хрена не помнишь что она точно делает

Ну глянешь в доки, будешь знать. Не понимаю проблемы.

no-such-file ★★★★★
()
Ответ на: комментарий от monk

Если я не ошибаюсь, то питоновский list таки умеет индексацию за константное время, так что его можно назвать массивом.

Aswed ★★★★★
()

нужно объявить массив, в цикле от 1 до 100 заполнить его случайными цифрами (тоже от 1го до 100), и в итоге получить массив с уникальными значениями

Я хз что проверялось этим вопросом. Если умение писать код - то да, принял бы. А вот если умение читать то нет, ибо тогда ты должен был как минимум сказать что в промежутке от 1 до 100 всего 9 цифр и спросить, могут ли исходный и выходной массивы быть разными объектам.

ya-betmen ★★★★★
()
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от ilovewindows

В этом есть доля истины, конечно, я подошел к вопросу несколько спекулятивно.

Но решение А вы бы приняли такой ответ? (комментарий) мне понравилось.

А ты, что о нём скажешь?

Twissel ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

Ну здесь ты цепляешься к понятиям цифра и число :-)

Если рекрутер сам в этом путается, нафиг такого!

Twissel ★★★★★
() автор топика
Ответ на: комментарий от Twissel

Ну тогда ой. Решение получающее случайную перестановку чисел от 1 до 100 у тебя хорошее, а если нужно было не это, то пускай уточнят постановку задачи.

TeopeTuK ★★★★★
()
Ответ на: комментарий от ilovewindows

Это очень-очень плохой алгоритм. Чем больше чисел уже выпадет, тем дольше и дольше придется ждать, поска выпадет следующее свободное. Сложность квадратичная, да еще и со стохастической составляющей, да еще и масса ценных случайных чисел пропадет. Если уж хочется с циклом, то можно сгенерировать 100 случайных чисел между нулем и единицей, сцепить их с арифметической прогрессией от 1 до 100, упорядочить по этим самым случайным и расцепить. Сложность nln(n), что приемлемо (не знаю, можно ли лучше). Но упомянутые в условии «случайные цифры от 1 до 100» здесь не фигурируют, увы.

TeopeTuK ★★★★★
()
Ответ на: комментарий от TeopeTuK

сцепить их с арифметической прогрессией от 1 до 100, упорядочить по этим самым случайным и расцепить

И получится тот же shuffle, вид сбоку.

no-such-file ★★★★★
()
Ответ на: комментарий от Twissel

Ну здесь ты цепляешься к понятиям цифра и число :-)

Я же говорю что хз, что проверяли. Знаешь какая засада порой случается когда в тз написано слово «любой»?

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

ya-betmen ★★★★★
()
Ответ на: комментарий от no-such-file

Верно, но решение будет чуть ближе к условию, где явным образом указан цикл. Могу предложить еще алгоритм, который на Tcl выглядит так (не умею на PHP быстро, увы):

#!/usr/bin/tclsh
set N 100
set aux {}
for {set i 1} {$i <= $N} {incr i} {
    lappend aux $i
}
set res {}
for {set i $N} {$i > 0} {incr i -1} {
    set idx [expr {int($i*rand())}]
    lappend res [lindex $aux $idx]
    set aux [lreplace $aux $idx $idx]
}
puts $res
Удаляем из вспомогательного списка элемент со случайным индексом и добавляем этот элемент в список результатов. Много манипуляций со списками, поэтому это медленнее, чем сцепка-сортировка-расцепка.

TeopeTuK ★★★★★
()
Ответ на: комментарий от Twissel

А что скажу, если сам автор оговорок по случайные величины навставлял. Имхо, как-то так.

<?php

$flag = array_fill(1,100,0);
$value = array_fill(1,100,0);

for ($i = 1; $i <= 100;)
{
 $j = rand(1,100);//случайное число от 1 до 100
 if ($flag[$j]=0) //не было такого
 {
  value[$i]=$j;//запомнили число
  flag[$j]=$j;//запомнили что было
  $i++;
 } else continue; //было, еще раз
}

?>

ilovewindows ★★★★★
()
Последнее исправление: ilovewindows (всего исправлений: 1)
Ответ на: комментарий от ilovewindows

Вообще конструктивно было сделать как в задании - заполнить в цикле массив случайными числами, проверяя при этом этом выпадало число уже или нет. Записывать в другой массив флажок «уже было», выпавшее число как индекс использовать, например.

Да за такое и уволить могут, не то что взять на работу.

А так ты афигенно крут, посмотрел перед собеседованием функции для работы с массивами и общаться не желаешь - это давай до свидания.

Прошу заметить, что shuffle не решает задачу «сгенерировать 100 случайных чисел», то, что ее догадались использовать как часть решения общей задачи – несомненный плюс. Короче не вижу смысла из пустого в порожнее переливать, я остаюсь на позиции, что собеседующий должен уметь подстраиваться под не топорно мыслящего кандидата. И не хочу даже представлять, как выглядит их код.

staseg ★★★★★
()
Ответ на: комментарий от staseg

Ну и какая причина увольнения, сто байтов перерасход?

ilovewindows ★★★★★
()
Ответ на: комментарий от ilovewindows

Если собеседуемый один, а работодатели выстраиваются к нему в очередь, то можно применять сколь угодно неэффективные алгоритмы. А если конкуренция среди поступающих на работу хоть какая-то есть, то оправдаться словами «оно же работает» не выйдет — возьмут того, кто написал более эффективный код.

TeopeTuK ★★★★★
()
Ответ на: комментарий от TeopeTuK

Имхо, это что-то для начинающих, если у них «цифры» до 100.

Можешь так вот на глаз что быстрее shuffle или лишние вызовы rand в цикле? В принципе shuffle, где-то внутри должен делать вызовы rand в нужном количестве для определения нового индекса и также получать повторы, чем ближе к концу тем чаще. Если это честный shuffle, конечно.

ilovewindows ★★★★★
()

Отличное решение.

thesis ★★★★★
()

а мне первым в голову пришло такое

<?php

function rand_100($poher)
{
    return rand(0, 100);
}

foreach(array_flip(array_map('rand_100', range(0, 100))) as $value)
    echo $value . " ";

?>

Debasher ★★★★★
()
Ответ на: комментарий от ilovewindows

В справочник лень было лезть, выяснять что shuffle делает.

По-моему тут название функции однозначно говорит о том, что именно она делает.

RiseOfDeath ★★★★
()
Ответ на: комментарий от ilovewindows

Вообще конструктивно было сделать как в задании - заполнить в цикле массив случайными числами, проверяя при этом этом выпадало число уже или нет.

Вон из профессии!

Это хоть что-то о человеке говорит, как оформил хотя бы.

Это говорит только о том, что человеку в самую пору мести улицы.

mix_mix ★★★★★
()
Ответ на: комментарий от mix_mix

На нормальных собеседованиях от тебя обычно ждут реализацию Тасования Фишера–Йетса.

Они прямо так скажут 'пиши реализацию Тасования Фишера–Йетса'? И нужно помнить их имена?

Debasher ★★★★★
()
Ответ на: комментарий от ilovewindows

Я заглянул в исходники PHP. Там алгоритм, похожий на тот, что я приводил в виде кода, только манипуляции не со списками, а с массивом указателей, поэтому такого оверхеда, как у меня, нет. Вот, примерно такое:

#!/usr/bin/tclsh
set N 100
set res {}
for {set i 1} {$i <= $N} {incr i} {
    lappend res $i
}
for {set i [expr {$N-1}]} {$i >= 0} {incr i -1} {
    set idx [expr {int(($i+1)*rand())}]
    set temp [lindex $res $i]
    lset res $i [lindex $res $idx]
    lset res $idx $temp
}
puts $res
Так как списками ворочать не надо, то на си этот алгоритм укладывается в о большое от n операций.

TeopeTuK ★★★★★
()
Ответ на: комментарий от Debasher

Нет, они поставят задачу, как в ОП-посте, а ты сам должен будешь до этого догадаться, во-первых, потому что это самый эффективный алгоритм, во-вторых, он достаточно простой чтобы даже не зная ничьих имён самостоятельно дойти до этого за две минуты (в отличии от какого-нибудь КМП). Не сможешь — мы вам перезвоним.

mix_mix ★★★★★
()
Ответ на: комментарий от Debasher

В твоем решении результат функции array_flip() будет скорее всего короче 100 элементов из-за коллизий функции rand_100().

TeopeTuK ★★★★★
()

Это и есть самое правильное решение.

i-rinat ★★★★★
()
Ответ на: комментарий от TeopeTuK

Да, верно. а разве это не подходит под условия задачи?) или я уже русский перестал понимать

т.е. вроде как не написано что результат должен быть из 100

Debasher ★★★★★
()
Последнее исправление: Debasher (всего исправлений: 1)
Ответ на: комментарий от ilovewindows

Имхо, это что-то для начинающих, если у них «цифры» до 100.

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

В принципе shuffle, где-то внутри должен делать вызовы rand в нужном количестве для определения нового индекса и также получать повторы, чем ближе к концу тем чаще. Если это честный shuffle, конечно.

Чем тебе кнутовый shuffle не честный? Каков критерий честности?

Ну и какая причина увольнения, сто байтов перерасход?

«По собственному желанию», очевидно.

staseg ★★★★★
()
Ответ на: комментарий от mix_mix

Ты похоже уже на профессию из вне смотришь, в любой профессии за невыполненное ТЗ дают люлей.

ilovewindows ★★★★★
()
Ответ на: комментарий от mix_mix

А можно просто в лоб написать с проверкой принадлежности, и ничего не случится, небо на голову не рухнет, а времени меньше уйдет на поиск решения.

Deleted
()
Ответ на: комментарий от mix_mix

Безусловно. Но твое (Фишера-Йетса) тасование работает только для конечного множества, как я понял, а тупая генерация с вспомогательным множеством для чего угодно.

Deleted
()
Последнее исправление: Deleted (всего исправлений: 2)
Ответ на: комментарий от staseg

Ладно, пока записи короче чем shuffle никто не придумал, знание о существовании shuffle ничего о знание алгоритмов соискателем не говорит, говорит о знании библиотеки. Это единственный маленький минус, ну или плюс, как повезет). Сначала напиши короче, чем мой вариант, потом будешь рассуждать о причинах увольнения. А так бла,бла. Критерий честности один - получить нужное количество случайных чисел. Числа должны быть уникальными, значит ты их должен сравнить с уже существующими. Чудес не бывает, надо 1. Получение случайного числа 2. Сравнение с существующим. Вот теперь расскажи, где ты будешь оптимизировать ? В получении случайных чисел, каким образом? Или в проверке на уникальность, тогда придумай что-нибудь проще сравнение двух (!) чисел. зы. shuffle наверняка быстрее, потому как в библиотеке на С.

ilovewindows ★★★★★
()
Ответ на: комментарий от ilovewindows

Ладно, пока записи короче чем shuffle никто не придумал, знание о существовании shuffle ничего о знание алгоритмов соискателем не говорит, говорит о знании библиотеки.

Вот в этом твоя проблема. Даже не зная о готовой библиотечной функции, ты можешь догадаться и написать ее аналог сам.

Критерий честности один - получить нужное количество случайных чисел. Числа должны быть уникальными, значит ты их должен сравнить с уже существующими. Чудес не бывает, надо 1. Получение случайного числа 2. Сравнение с существующим. Вот теперь расскажи, где ты будешь оптимизировать ? В получении случайных чисел, каким образом? Или в проверке на уникальность, тогда придумай что-нибудь проще сравнение двух (!) чисел. зы. shuffle наверняка быстрее, потому как в библиотеке на С.

Алгоритм Кнута (он же Фишера-Йетса, как тут говорили) очень простой, прям дубовый, признаться, я до этого топика не знал, как он называется, он просто очевидный. Никаких сравнений на уникальность не делает. Он не честно перемешивает?

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

Теперь решил поупражняться в количестве строк?

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

staseg ★★★★★
()
Ответ на: комментарий от staseg

Вперед, реализацию алгоритма Кнута (он же Фишера-Йетса) в студию, желательно меньше пяти строк. Остальное бла-бла, сам понимаешь, игра на публику.

ilovewindows ★★★★★
()

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

n0044h
()
Ответ на: комментарий от ilovewindows
array = range(0, N);
L = length(array);
for(i = 0; i < L; i++)
    swap(array[i], array[rand(0, L)]);

Можешь кстати сэкономить строчку, придумай сам, performance engineer :)

staseg ★★★★★
()
Ответ на: комментарий от staseg

Ну да, согласен, это всяко сработает быстрее. Если так написать, да еще сделать вид, что никаго Фишера-Йетса не знаешь вообще хорошо. зы. Я ваще никакого отношения к программированию не имею, спасибо ,конечно, за performance engineer :)

ilovewindows ★★★★★
()
Ответ на: комментарий от Debasher

Твое прочтене условия уж какое-то совсем необычное получилось. Хотя и правда, ничего про длину результата не сказано. Более того, не исключено, что речь идет просто про прореживание массива — выбрасывание из него дубликатов (типа lsort -uniq $list в Tcl).

TeopeTuK ★★★★★
()
Ответ на: комментарий от staseg

Твоё решение очень плохо, опасно, и мы все умрём! Оно генерирует предвзятую выборку из-за того, что в каждой итерации ты переставляешь текущий элемент с вообще любым, а не из оставшихся. Случайное число нужно брать не от 0, а от i. Кстати, это наглядный пример почему не стоит самому браться реализовывать криптографию — конкретно обосраться можно уже и вот на такой мелочи. http://spin.atomicobject.com/2014/08/11/fisher-yates-shuffle-randomization-al...

mix_mix ★★★★★
()
Ответ на: комментарий от staseg

Да еще походу переврал, короче отсюда https://ru.wikipedia.org/wiki/Тасование_Фишера–Йетса

Для тасования массива a из n элементов (индексы 0..n-1):
  для всех i от n − 1 до 1 выполнить
       j ← случайное число 0 ≤ j ≤ i
       обменять местами a[j] и a[i]
и вообще это какой-то Дурштенфельд, а не Фишера–Йетса).

ilovewindows ★★★★★
()
Ответ на: комментарий от mix_mix

Конечно я лопух в криптографии. В свое оправдание могу сказать лишь то, что именно поэтому я рассуждал об алгоритмической сложности и советовал использовать уже готовый shuffle :)

Спасибо за ссылку.

staseg ★★★★★
()
for(int i=0; i<100; i++) {
    j = rand.nextInt(100);
    if(!nums.contains(j))
        nums.add(j);
            
    inums[i] = j;
}

строк столько же, профит очевиден :D

unt1tled ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.