The Six Most Common Species Of Code

[АццкоМото]

Не, кошкин код прекрасен, хоть и бажный

[crypto5]

Кстати, характерно, что ни один вариант не использует unsigned int

В jvm нету unsigned типов, нет и проблем с ними ))

[Zorkus]

А вот и прекрасный вопрос для интервью. Как добавить в JVM unsigned int?

[Интеррапт]

А вот и прекрасный вопрос для интервью. Как добавить в JVM unsigned int?

Что значит в JVM? На уровне байт-кода?

[Zorkus]

Открытый вопрос для обсуждения Предположим, у меня есть исходники javac/hotspot, я хочу добавить новый примитивный тип uint, 32-битный, беззнаковый. Я естественно хочу, чтобы все было сделано аккуратно и оптимально. Расскажите, какие изменения в javac и JVM и где будут нужны.

[crypto5]

Открытый вопрос для обсуждения Предположим, у меня есть исходники javac/hotspot, я хочу добавить новый примитивный тип uint, 32-битный, беззнаковый. Я естественно хочу, чтобы все было сделано аккуратно и оптимально. Расскажите, какие изменения в JVM и где будут нужны.

Лучше сразу лаптоп с сорцами дать и время засечь когда будет готово ))

[Интеррапт]

Открытый вопрос для обсуждения Предположим, у меня есть исходники javac/hotspot, я хочу добавить новый примитивный тип uint, 32-битный, беззнаковый. Я естественно хочу, чтобы все было сделано аккуратно и оптимально. Расскажите, какие изменения в javac и JVM и где будут нужны.

Боюсь, что я завалил бы такое интервью.

[Сабина]

А вот и прекрасный вопрос для интервью. Как добавить в JVM unsigned int?

Опоздал
https://blogs.oracle.com/darcy/entry/unsigned_api

[Интеррапт]

А вот и прекрасный вопрос для интервью. Как добавить в JVM unsigned int?

Опоздал
https://blogs.oracle.com/darcy/entry/unsigned_api

Не... это совсем не то. Я этот блог еще в прошлом году читал. Тут чувак пишет про несколько добавленных классов во фреймворк, но уж никак не на уровне JVM добавление беззнаковых типов.

[Zorkus]

Открытый вопрос для обсуждения Предположим, у меня есть исходники javac/hotspot, я хочу добавить новый примитивный тип uint, 32-битный, беззнаковый. Я естественно хочу, чтобы все было сделано аккуратно и оптимально. Расскажите, какие изменения в javac и JVM и где будут нужны.

Боюсь, что я завалил бы такое интервью.

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

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

- К нему не подготовиться по книжке "cracking the coding interview: 150 typical questions"
- позволяет выделить людей, кто заглядывал под капот платформе, с которой работает
- людей, которые могут быстро набросать план решения задачи, которая кажется крайне трудной сходу

[crypto5]

Открытый вопрос для обсуждения Предположим, у меня есть исходники javac/hotspot, я хочу добавить новый примитивный тип uint, 32-битный, беззнаковый. Я естественно хочу, чтобы все было сделано аккуратно и оптимально. Расскажите, какие изменения в javac и JVM и где будут нужны.

Боюсь, что я завалил бы такое интервью.

Ну это типичная задача Ферми (http://en.wikipedia.org/wiki/Fermi_problem), более многоуровневая чем скажем вопрос сколько пианистов живет в Чикаго. Нужно сделать ряд предположений, о том как люди пишут обычно виртуальные машины, и компиляторы, и какие изменения нужно что бы поддержать новый тип: типа лексический/семантический и т.д. анализатор, формат байтока, jit compiler, либы наверное какие то и АПИ переписать, тесты поправить.

[slozovsk]

Я большой любитель рекурсии, много писал на LISP в свое время (там, обычно, рекурсия используется вместо циклов). Но, за двойную рекурсию на пустом месте, на интервью, могут дать по голове. Итерация - лучше всего, в данном случае.

[dotcom]

Я большой любитель рекурсии, много писал на LISP в свое время (там, обычно, рекурсия используется вместо циклов). Но, за двойную рекурсию на пустом месте, на интервью, могут дать по голове. Итерация - лучше всего, в данном случае.

В данном случае как раз правильно написать с простой рекурсией, если не спрашивают другого. Как в оргигинальной картиинке было упомянуто, этому учат в CS, если не 101, то к 301 точно.

[Hamster]

Я большой любитель рекурсии, много писал на LISP в свое время (там, обычно, рекурсия используется вместо циклов). Но, за двойную рекурсию на пустом месте, на интервью, могут дать по голове. Итерация - лучше всего, в данном случае.

В данном случае как раз правильно написать с простой рекурсией, если не спрашивают другого. Как в оргигинальной картиинке было упомянуто, этому учат в CS, если не 101, то к 301 точно.

Лично для меня двойная рекурсия была бы красным флагом. Ее применение означает, что испытуемый закончил CS 101, но лишен всякого представления о производительности написанного им кода.

[NYgal]

Я большой любитель рекурсии, много писал на LISP в свое время (там, обычно, рекурсия используется вместо циклов). Но, за двойную рекурсию на пустом месте, на интервью, могут дать по голове. Итерация - лучше всего, в данном случае.

В данном случае как раз правильно написать с простой рекурсией, если не спрашивают другого. Как в оргигинальной картиинке было упомянуто, этому учат в CS, если не 101, то к 301 точно.

Лично для меня двойная рекурсия была бы красным флагом. Ее применение означает, что испытуемый закончил CS 101, но лишен всякого представления о производительности написанного им кода.

Я рекурсией баловалась, когда есче на C писала, сразу после института, в конце 80х. Красиииво. И работало, что самое интересное, свою миссию выполняло. Интересно было бы как-то восстановить етот код.

[Komissar]

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

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

Модные перцы пишут вот так:

Code: Select all

def fib: Stream[Int] = 0 #:: 1 #:: fib.zip(fib.tail).map{case (a,b) => a + b}

А еще вот так:

Code: Select all

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

[rorp]

Я большой любитель рекурсии, много писал на LISP в свое время (там, обычно, рекурсия используется вместо циклов). Но, за двойную рекурсию на пустом месте, на интервью, могут дать по голове. Итерация - лучше всего, в данном случае.

+100500


Говнокод

Code: Select all

def fibonacci(n: BigInt): BigInt = {
     @tailrec
     def fib(i: BigInt, a: BigInt, b: BigInt): BigInt = {
        if (i < 0)
           a
        else
           fib(i - 1, b, a + b)
     }
     
     fib(n, 0, 1)
  }

транслируется модным компилятором в реально кошерный код по типу динамического программирования

Code: Select all

  public BigInt fibonacci(BigInt n)
  {
    return fib$1(n, BigInt..MODULE$.int2bigInt(0), BigInt..MODULE$.int2bigInt(1));
  }

  private final BigInt fib$1(BigInt i, BigInt a, BigInt b)
  {
    while (true)
    {
      if (i.$less(BigInt..MODULE$.int2bigInt(0))) {
        return 
          a;
      }
      b = a.$plus(b); a = b; i = i.$minus(BigInt..MODULE$.int2bigInt(1));
    }
  }

[rorp]

Модные перцы пишут вот так:

Code: Select all

def fib: Stream[Int] = 0 #:: 1 #:: fib.zip(fib.tail).map{case (a,b) => a + b}

А еще вот так:

Code: Select all

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Те же яйца, вид сбоку. Если памяти не жалко, пойдет.

[dotcom]

Лично для меня двойная рекурсия была бы красным флагом. Ее применение означает, что испытуемый закончил CS 101, но лишен всякого представления о производительности написанного им кода.

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

[Hamster]

Лично для меня двойная рекурсия была бы красным флагом. Ее применение означает, что испытуемый закончил CS 101, но лишен всякого представления о производительности написанного им кода.

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

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

Если этот перец пишет код с двойной рекурсией, работающий за время O(2^n), на интервью, когда он может подумать еще минуту и написать код со временем O(n), то какие у меня будут гарантии, что он не станет так же подходить к написанию продукционного кода?

И в чем вообще смысл этой задачи? Проверить, что человек знает, что такое число Фибоначчи? Для этого необязательно писать код. Проверить, что он знает, что такое рекурсия? Подразумевается, что это знает любой человек, пытающийся устроиться на работу программистом. Логически следует, что это проверка на способность писать качественный код. Которым рекурсия, очевидно, не является.

[Hamster]

Кстати, а кто-нибудь может придумать, как посчитать в целых числах быстрее O(n)?

Вариант от Math Ph.D. это в принципе O(ln(n)), если считать, что экспоненциация это O(ln(n)). Но он на плавающей точке и на целые числа очевидным способом не обобщается.

Lookup table не предлагать (хотя в большинстве случаев это будет самым быстрым вариантом). Граничные условия: 1 <= n <= 93, fib(n) <= 2^64.

[crypto5]

По ссылке из самого первого поста темы есть за константу ))

[Dweller]

Кстати, а кто-нибудь может придумать, как посчитать быстрее

можно изгалиться с multi-threading или на hadoop, но в этом случае наверное лучше считать по приближенной формуле а не точное LongInt значение

[crypto5]

Кстати, а кто-нибудь может придумать, как посчитать в целых числах быстрее O(n)?

Вариант от Math Ph.D. это в принципе O(ln(n)), если считать, что экспоненциация это O(ln(n)). Но он на плавающей точке и на целые числа очевидным способом не обобщается.

Lookup table не предлагать (хотя в большинстве случаев это будет самым быстрым вариантом). Граничные условия: 1 <= n <= 93, fib(n) <= 2^64.

Известно точное решение за O(logn), думаю можно найти в википедии