20 fastest-hiring San Francisco tech employers

[Мальчик-Одуванчик]

Задача: представим, что блоки данных в этом устройстве образуют логический contiguous массив памяти размером 4K*N

Нужно: написать функцию, которая, используя get_block(), копирует любой заданный подмассив из этого массива, получая в качестве аргументов offset, length и указатель на блок памяти, куда копировать, т.е.

int get_bytes(size_t offset, size_t len, char* buff);

- подразумевается, что память на которую указывает buff (ну, если он не NULL) аллокирована/управляется вызывающим кодом
- возвращать тоже надо 0/не ноль
- (тут навскидку и 30 строчек кода не наберется)

А то, куда копировать, тоже находится в этом самом массиве памяти?

[Big Cheese]

А то, куда копировать, тоже находится в этом самом массиве памяти?

Нет, в "обычной" памяти

[Мальчик-Одуванчик]

А то, куда копировать, тоже находится в этом самом массиве памяти?

Нет, в "обычной" памяти

Тогда самый простой способ - выделить память N*4K и скопировать туда весь этот непрервыный массив, используя get_block(),
и после применить обычное memcpy.

[АццкоМото]

Ну вы же не про код как таковой запилили, а про pointer arithmetic. Что проверить по телефону — как два пальца об асфальт.

Я, наверно, неудачно выразился - я имел в виду написание функции на 20-30 строк, алгоритм которой требует, кроме прочего, хорошего понимания указателей..

Если не секрет - а давайте мы эту функцию тут обсосем со всех сторон? С одной стороны, бессмысленно, с другой - бывает интересно

Не секрет. Вот, например: есть некоторое устройство, которое хранит данные в блоках размером, допустим по 4KB каждый. К нему есть интерфейсная функция, которая имеет такой вот прототип:

int get_block(size_t block_id, char* data_buf);

где

block_id: идентификатор блока данных [0 .. N-1]
data_buf: указатель на область памяти, по которому get_block() копирует содержание заданного блока

возвращает 0 в случае успеха, не ноль при ошибке

Задача: представим, что блоки данных в этом устройстве образуют логический contiguous массив памяти размером 4K*N

Нужно: написать функцию, которая, используя get_block(), копирует любой заданный подмассив из этого массива, получая в качестве аргументов offset, length и указатель на блок памяти, куда копировать, т.е.

int get_bytes(size_t offset, size_t len, char* buff);

- подразумевается, что память на которую указывает buff (ну, если он не NULL) аллокирована/управляется вызывающим кодом
- возвращать тоже надо 0/не ноль
- (тут навскидку и 30 строчек кода не наберется)

Спасибо, задачка хорошая. Она, конечно, элементарная и именно что проверить, умеет ли кандидат кодить вообще, но есть два момента:
1. именно на таких простых задачах есть шанс засуетиться и все провалить - даже если вне рамок интервью "решал" бы такое, как два пальца об асфальт
2. выдать элегантный код сразу не так легко. я пока на перекур сходил и еще плюс несколько минут "в голове" код напейсал, но гузкой чувствую, что можно и красивше. даже, наверное поупражняюсь, чтобы вышла конфетка

[АццкоМото]

А то, куда копировать, тоже находится в этом самом массиве памяти?

Нет, в "обычной" памяти

Тогда самый простой способ - выделить память N*4K и скопировать туда весь этот непрервыный массив, используя get_block(),
и после применить обычное memcpy.

фуфуфу!

[Мальчик-Одуванчик]

А то, куда копировать, тоже находится в этом самом массиве памяти?

Нет, в "обычной" памяти

Тогда самый простой способ - выделить память N*4K и скопировать туда весь этот непрервыный массив, используя get_block(),
и после применить обычное memcpy.

фуфуфу!

Ха-ха! - В задаче ведь не оговаривается,что нельзя пользоваться дополнительной памятью.
Неэффективен - да!, но работает 100%. Если N достаточно мало, то другим решением я бы и не заморачивался.
Понятно что его легко оптимизировать до размеров временного буфера 4K*[len\4k+1].
Интереснее, если кроме buf ничем другим нельзя пользоваться, но это условие как-бы и не оговаривалось.

[Big Cheese]

Спасибо, задачка хорошая. Она, конечно, элементарная и именно что проверить, умеет ли кандидат кодить вообще, но есть два момента:
1. именно на таких простых задачах есть шанс засуетиться и все провалить - даже если вне рамок интервью "решал" бы такое, как два пальца об асфальт
2. выдать элегантный код сразу не так легко. я пока на перекур сходил и еще плюс несколько минут "в голове" код напейсал, но гузкой чувствую, что можно и красивше. даже, наверное поупражняюсь, чтобы вышла конфетка

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

[Мальчик-Одуванчик]

Спасибо, задачка хорошая. Она, конечно, элементарная и именно что проверить, умеет ли кандидат кодить вообще, но есть два момента:
1. именно на таких простых задачах есть шанс засуетиться и все провалить - даже если вне рамок интервью "решал" бы такое, как два пальца об асфальт
2. выдать элегантный код сразу не так легко. я пока на перекур сходил и еще плюс несколько минут "в голове" код напейсал, но гузкой чувствую, что можно и красивше. даже, наверное поупражняюсь, чтобы вышла конфетка

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

Я бы тоже однозначно проперся - почему-то offset у меня изначально ассоциировался со смещением относительно массива 0-N, то есть с номером блока. Блок по привычке ассоциировался со структурой, ну и смещение автоматически тоже уже относительно неё.

[Big Cheese]

Я бы тоже однозначно проперся - почему-то offset у меня изначально ассоциировался со смещением относительно массива 0-N, то есть с номером блока.

Я обычно рисую небольшую иллюстрацию на доске, поясняющую условия - ну, там, блоки 0..N, стрелка сверху "оффсет", отрезок "length" и тп - чтобы кандидату легче было понять. Одно из преимуществ white board-a перед форумом

[Big Cheese]

А то, куда копировать, тоже находится в этом самом массиве памяти?

Нет, в "обычной" памяти

Тогда самый простой способ - выделить память N*4K и скопировать туда весь этот непрервыный массив, используя get_block(),
и после применить обычное memcpy.

фуфуфу!

Ха-ха! - В задаче ведь не оговаривается,что нельзя пользоваться дополнительной памятью.
Неэффективен - да!, но работает 100%. Если N достаточно мало, то другим решением я бы и не заморачивался.
Понятно что его легко оптимизировать до размеров временного буфера 4K*[len\4k+2].
Интереснее, если кроме buf ничем другим нельзя пользоваться, но это условие как-бы и не оговаривалось.

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

[Мальчик-Одуванчик]

Нет, в "обычной" памяти

Тогда самый простой способ - выделить память N*4K и скопировать туда весь этот непрервыный массив, используя get_block(),
и после применить обычное memcpy.

фуфуфу!

Ха-ха! - В задаче ведь не оговаривается,что нельзя пользоваться дополнительной памятью.
Неэффективен - да!, но работает 100%. Если N достаточно мало, то другим решением я бы и не заморачивался.
Понятно что его легко оптимизировать до размеров временного буфера 4K*[len\4k+2].
Интереснее, если кроме buf ничем другим нельзя пользоваться, но это условие как-бы и не оговаривалось.

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

Даже в самое, казалось бы неэффективное на первый взгляд решение при определенном типе блочного устройства и заданного N, может оказаться сравнимым по эффективности со всеми остальными. К примеру если жесткий диск, как пример блочного устройства, хватает за раз М блоков и N < M, а дополнительным расходом памяти можно пренебречь. Понятно что с ленточным устройством такой вариант бы не прокатил.

[АццкоМото]

Понятно что его легко оптимизировать до размеров временного буфера 4K*[len\4k+1].

если заняться занудством, то эта оценка не всегда верна

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

ну кагбэ это.... опять анекдот вспоминается

В гостинице, куда поселились инженер, математик и физик возник пожар.
Инженер - унюхав запах гари, выбегает в коридор, подбегает к пожарному гидранту, и быстро заливает огонь водой.
Физик - поняв, что отель горит, оценив запасы горючих материалов и приняв во внимание теплоемкость воды и все такое прочее, тушит пожар минимально необходимым количеством воды затратив минимум энергии.
Математик - осознав, что все кругом полыхает, задумчиво смотрит на пожарный гидрант. И воскликнув: "О! Решение существует!" - спокойно возвращается к себе в номер

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

[АццкоМото]

Понятно что с ленточным устройством такой вариант бы не прокатил.

Ммм? пачиму?

[АццкоМото]

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

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

[Мальчик-Одуванчик]

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

Ну вот как выпускник матфака я сначала нахожу хоть какое-то решение, пусть самое простое и банальное.
Другими словами, убеждаюсь что оно существует. И лишь при необходимости подыскиваю более оптимальное.

[Big Cheese]

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

я, кстати, именно эту задачу в свое время практически завалил так что вполне могу понять

[Big Cheese]

Даже в самое, казалось бы неэффективное на первый взгляд решение при определенном типе блочного устройства и заданного N, может оказаться сравнимым по эффективности со всеми остальными. К примеру если жесткий диск, как пример блочного устройства, хватает за раз М блоков и N < M, а дополнительным расходом памяти можно пренебречь.

Ну, если уж развивать аналогию с жестким диском, то логично будет считать, что N здесь - это общее количество блоков (секторов, etc) в диске, так что N < M представляется сомнительным допущением с инженерной точки зрения

[Мальчик-Одуванчик]

Даже в самое, казалось бы неэффективное на первый взгляд решение при определенном типе блочного устройства и заданного N, может оказаться сравнимым по эффективности со всеми остальными. К примеру если жесткий диск, как пример блочного устройства, хватает за раз М блоков и N < M, а дополнительным расходом памяти можно пренебречь.

Ну, если уж развивать аналогию с жестким диском, то логично будет считать, что N здесь - это общее количество блоков (секторов, etc) в диске, так что N < M представляется сомнительным допущением с инженерной точки зрения

Ну так и инженерное решение сразу наклевывается: если N < M, то не заморачиваемся, а уж если больше....
Насколько помню название такого подхода: lazy optimization

[XpoH]

я тоже часто задаю те задачи, которые сам провалил.