?

Log in


dva_il in hitech_tests

Задача с интервью в Google

 Есть головоломка судоку (http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B4%D0%BE%D0%BA%D1%83)
Нужно написать алгоритм (код c/c++ или java) проверяющий правильность заполнения судоку. Т.е. цифры могут быть только от 1 до 9 и они не могут повторяться в маленьких квадратах, и в одном столбце и в одной строке большого квадрата тоже не должны встречаться одинаковые цифры.


PS. говорят, решение простое, как раз для интервью. На всё даётся максимум минут 30-ть.

Comments

а в чем проблема? надо проверить 27 блоков по 9 цифр, чтобы внутри все цифры были разные (например 9-и битовым счетчиком). что тут полчаса писать?
да, хороший вариант битовый счётчик, к сожалению на интервью в голову не пришло.
Блоки (доступ к данным) должен быть релевантным судоку, т.е. структура не всех 27-ми блоков одинакова
ну да, разная структура, и что с того? бегать тупо по массиву )

(Anonymous)

Всех одинакова, если использовать массив 3×3×3×3.

(Anonymous)

Действительно очень просто. А если квадрат заполнен не полностью? То есть все равно просто, конечно, но хотелось бы поэлегантнее.
а если не полностью, то придется перед поднятием бита проверять, что он еще не поднят

(Anonymous)

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

Но я не задаю вопросов на интервью ;)
сумма чисел в одном массиве всегда должна быть = 45.
45 х 9 х 3 = 1215
Но если заполнить все клетки одними 5-ми, то тоже будет 1215
Или могут быть ещё какие-то решения, которые будут давать сумму 1215.
в общем да, принципиальных сложностей никаких, проверяется умение быстро писать работающий код
скорее всего проверялось умение мыслить, находить не стандартные решения
например?

(Anonymous)

слабо верится что это задача на интервьюировании из конторы типа Гугл, там предпочитают давать разные головоломки, задавать глубокие теоретические вопросы. Им нужны люди которые знают алгоритмы, математику на уровне аспирантуры, а технологии на уровне документации. Им нужны те кто сможет создать огромную масштабируемую систему и проработать для неё матчасть, а не те кто может проверить наличие цифр по горизонтали вертикали и в квадрате вокруг.
А эта задача "на вшивость", просто что бы убедиться что кандидат не олень. Это даже не олимпиадная задача из какого-нибудь topcoder'а элементарного уровня сложности. Это зада для одиннадцатиклассника неспециализированной школы. Она стоит 30-и минут на школьном экзамене по информатике, рабочее время интервьирующего специалиста компании стоит несоизмеримо больше, и решение этой задачи не повлияет на решение брать ли вас в гугл, следовательно её нет смысла спрашивать.
Так что не пишите сюда больше ерунды.

(Anonymous)

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

(Anonymous)

Действительно. Три куска почти одинакового кода, чем плохо?
Не стоит так уж фанатично избегать дублирования кода. Самое главное - простота понимая кода, из которой следует меньшая вероятность багов и большая простота поддержки. И несколько кусков одинакового кода часто гораздо проще понять, чем что-то заумное и мудреное, написанное только ради отсутствия дублирования.
+1, вообще вопрос - бред. Любой человек с красным рейтингом на Топкодере реализует это не более чем за пять минут :)
Тут нигде не писалось, что это супер-мего сложная задача. Но, и я человек не с топкада, и тем более не из его красного рейтинга, и написал бы её в простом варианте (в лоб), скажем за час.
Однако, в гугле не задают задач без некоторого подвоха, соответственно и для этой задачи есть какое-то особое, красивое решение.

October 2014

S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 
Powered by LiveJournal.com