Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 31 32 33 34 35 [36] 37 38 39 40 .. 42   вперед  Ctrl
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
MKZM
Member

Откуда:
Сообщений: 5135
Basil A. Sidorov
Atum1
Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.
(Решение нужно через метод Монте Карло)
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?

Это пролог. Решается 10 строками.
23 дек 17, 01:29    [21056875]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Atum1
int d = Integer.bitCount(i & 0xff000000) == count ? 1 : 0;
int c = Integer.bitCount(i & 0xff0000) == count ? 1 : 0;
int b = Integer.bitCount(i & 0xff00) == count ? 1 : 0;
int a = Integer.bitCount(i & 0xff) == count ? 1 : 0;
return a + b + c + d;
int result = 0;
if (count == Integer.bitCount(i & 0xff000000)) ++result;
if (count == Integer.bitCount(i & 0x00ff0000)) ++result;
if (count == Integer.bitCount(i & 0x0000ff00)) ++result;
if (count == Integer.bitCount(i & 0x000000ff)) ++result;
return result;
?
23 дек 17, 01:30    [21056879]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Basil A. Sidorov
Atum1
Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.
(Решение нужно через метод Монте Карло)
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?


Воот, это самый интересный вопрос : мы берем 1 int = 4 байта - можно и считать что все байты в нем случайные , если инт случайный ?
23 дек 17, 12:57    [21057174]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Atum1
Basil A. Sidorov
пропущено...
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?


Воот, это самый интересный вопрос : мы берем 1 int = 4 байта - можно и считать что все байты в нем случайные , если инт случайный ?


автор
56/256 = 0.21875


тут две особенности -

обычный Random намного медленее чем ThreadLocalRandom из за cas операции внутри .

+ мы берем 1 int = 4 байта оптимизация


В вот проверка на c++
автор
:~/cpp$ g++ coin.cpp -o coin
:~/cpp$ time ./coin
Time taken: 1.23s

0.232375

real 0m1.238s
user 0m1.229s
sys 0m0.000s


#include <stdio.h>      /* printf, scanf, puts, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */



 static int numberOfSetBits(int i)
{

     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

static int sumBitsCounter(int i, int count) 
{
        int d = numberOfSetBits(i & 0xff000000) == count ? 1 : 0;
        int c = numberOfSetBits(i & 0xff0000) == count ? 1 : 0;
        int b = numberOfSetBits(i & 0xff00) == count ? 1 : 0;
        int a = numberOfSetBits(i & 0xff) == count ? 1 : 0;
        return a + b + c + d;

}


int main ()
{
  /* initialize random seed: */
  srand (time(NULL));

int n = 100000000;
int m = 3;
int r = 0;
//printf("%d ", n );
//printf("%d ", m );

 clock_t tStart = clock();

for (int i = 0; i < n/4; i++) {
           r+=sumBitsCounter(rand(),m);
}

printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
printf("%f ", 1.0*r/n );

  return 0;
}
23 дек 17, 13:03    [21057179]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Atum1
Воот, это самый интересный вопрос : мы берем 1 int = 4 байта - можно и считать что все байты в нем случайные , если инт случайный ?
Любая подпоследовательность случайной последовательности - случайна. Так что это вопрос исключительно качества генератора.
23 дек 17, 15:47    [21057396]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Basil A. Sidorov
Atum1
Воот, это самый интересный вопрос : мы берем 1 int = 4 байта - можно и считать что все байты в нем случайные , если инт случайный ?
Любая подпоследовательность случайной последовательности - случайна. Так что это вопрос исключительно качества генератора.


я тоже всегда всем так говорю , доказательство где найти :) ?
3 янв 18, 10:26    [21079783]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Atum1
я тоже всегда всем так говорю , доказательство где найти :) ?
Дык, эта ...
Из определения же: последовательность случайна, если нет никаких корреляций между её элементами. Если "разбить целые на байты" и обнаружить корреляцию - какая же эта случайная последовательность.
Другой вопрос, что исходная последовательность не истинно случайная, а псевдослучайная (да ещё и конечная).
А вот проверка качества генератора псевдослучайной последовательности - задача, как я понимаю, сильно нетривиальная.
3 янв 18, 11:45    [21079855]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
Ну, граждане джависты... есть задачка:
http://acm.timus.ru/print.aspx?space=1&num=1001
Input

The input stream contains a set of integer numbers Ai (0 <= Ai <= 1018). The numbers are separated by any number of spaces and line breaks. A size of the input stream does not exceed 256 KB.

Output

For each number Ai from the last one till the first one you should output its square root. Each square root should be printed in a separate line with at least four digits after decimal point.
Нужно решить через Stream-ы (java.util.stream.*) !!!

P.S.
Система поддерживает Java 8 (так что все ок)
6 янв 18, 17:59    [21084793]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
P.P.S.
http://acm.timus.ru/help.aspx?topic=java
6 янв 18, 18:13    [21084812]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Basil A. Sidorov
Atum1
Воот, это самый интересный вопрос : мы берем 1 int = 4 байта - можно и считать что все байты в нем случайные , если инт случайный ?
Любая подпоследовательность случайной последовательности - случайна. Так что это вопрос исключительно качества генератора.

Нет. Если изначально мы задали генерацию числа в диапазоне [0..2 000 000 000] (к примеру)
то некоторые байты будут принимать значения отличные от случайных. Правильнее сказать
их гистограмма будет не совсем линейной. Например 31-й бит (знаковый) будет равен нулю.

Еще сложнее с вещественными. Они имеют неоднородное распределение значений
на вещественной оси.

Поэтому предположение о случайных байтах требует детализации.
6 янв 18, 19:07    [21084869]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
mayton
Поэтому предположение о случайных байтах требует детализации.
"Мы пойдём простым логическим ходом ..."
Случайной называется последовательность, для которой вероятность определения (произвольным алгоритмом) очередного элемента не превышает вероятности случайного угадывания. Просто по определению.
Рассмотрим, для простоты, битовую последовательность, для которой вероятность угадать следующий бит - одна вторая. Как для того динозавра.

Внимание - вопрос!
Что изменится, если мы начнём угадывать не отдельные биты, а "нарежем" битовую последовательность на блоки? Ничего.
А если ещё раз порежем битовые блоки на подблоки? Опять ничего.
Ничего не меняется по той простой причине, что если, вдруг, мы умеем угадывать подпоследовательности случайной битовой последовательности, то вероятность угадать отдельные биты становится больше одной второй. Что противоречит исходному предположению о случайной последовательности. Тривиальное доказательство от противного.

С другой стороны, в реальной жизни у нас нет случайной последовательности - только псевдослучайная. Более того - циклическая (повторяющаяся) псевдослучайная последовательность. Именно по этой причине я сделал акцент на качестве генератора. Предполагая, естественно, что генератор ПСП - "достаточно хороший".

P.S. Нет никакой принципиальной разницы между int и float, между double и long - мощность этих типов совершенно одинакова по той простой причине, что состоят они из попарно одинакового числа бит.
Специальные значения вещественных чисел несколько уменьшают их мощность, но это совершенно непринципиально.
6 янв 18, 22:34    [21085167]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
mayton
Нет. Если изначально мы задали генерацию числа в диапазоне [0..2 000 000 000] (к примеру)
Давайте сначала нарушим случайность ошибочным или просто дебильным ограничением, а затем героически докажем, что случайности нет?
Так что ли? Демагогия становится модной не только в политике и наукообразных течениях, но и в инженерных дисциплинах?
6 янв 18, 22:37    [21085173]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Просто я люблю точность в начальной формулировке. Любое неоднозначное
толкование меняет суть. И каждый спорящий спорит не об истине а о своём
собственном восприятии задачи.

Посмотрите как описаны задачи в учебниках математики.
6 янв 18, 22:56    [21085207]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
mayton
Посмотрите как описаны задачи в учебниках математики.
Почитайте условный сопромат или, хотя бы, справочник по элементарной физике.
Куда как ближе к инженерной дисциплине, которой и является программирование. Как системное, так и прикладное.
7 янв 18, 01:06    [21085332]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
Usman
Нужно решить через Stream-ы (java.util.stream.*) !!!
Решается в одной Stream-цепочке: начиная с обработки ввода, вычисления и заканчивая выводом
7 янв 18, 10:05    [21085566]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Usman
Member

Откуда: من ألماتي
Сообщений: 5599
Usman
Ну, граждане джависты... есть задачка:
http://acm.timus.ru/print.aspx?space=1&num=1001
Input

The input stream contains a set of integer numbers Ai (0 <= Ai <= 1018). The numbers are separated by any number of spaces and line breaks. A size of the input stream does not exceed 256 KB.

Output

For each number Ai from the last one till the first one you should output its square root. Each square root should be printed in a separate line with at least four digits after decimal point.
Нужно решить через Stream-ы (java.util.stream.*) !!!

P.S.
Система поддерживает Java 8 (так что все ок)
Решение:
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.Collectors;
import java.util.stream.StreamSupport;

public class Solution {
    public static void main(String[] args) throws Exception {
        StreamSupport
            .stream(Spliterators.spliteratorUnknownSize(new Scanner(System.in), Spliterator.NONNULL), false)
            .mapToDouble(Double::valueOf)
            .map(Math::sqrt)
            .boxed()
            .collect(Collectors.toCollection(LinkedList::new))
            .descendingIterator()
            .forEachRemaining(r -> System.out.printf("%.4f\n", r));
    }
}
8 янв 18, 23:19    [21088463]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Usman
P.P.S.
http://acm.timus.ru/help.aspx?topic=java


оффтопик переходите на сайт

https://acmp.ru/

как то все по приятнее оформлено .

там на ютубюе даже есть канал с разбором задач :)

https://www.youtube.com/channel/UCM01TVLxMvqEXq4Z9AFl-jA
10 янв 18, 10:27    [21092490]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Basil A. Sidorov
Atum1
Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.
(Решение нужно через метод Монте Карло)
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?


Да , можно проверить подформуле

С хорошей точностью


А вот код на с++ нет и это странно .
14 мар 18, 20:29    [21256881]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Basil A. Sidorov
Atum1
Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 3 раза.
(Решение нужно через метод Монте Карло)
Скоростные показатели это хорошо.
Полученная вероятность соответствует формульной?


Да , можно проверить подформуле

С хорошей точностью


А вот код на с++ нет и это странно .
15 мар 18, 00:00    [21257299]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Добре утро .

Вопрос такой уже давно java 8(9)но в сети нет вопросов на собеседовании по стеку и нововведениям ?


Что обычно спрашивают ?


Есть куча тем с базовыми вопросами по java 7 , ООП , потокам , sql


Но мы уже давноживем в парадигме фп .


Сейчас нужно набрать 5 - 6 Java программистов , давно работаем с Java 8 , смотрим в Java 9,
Но спрашиваем На собеседовании базовый нафталин


Подскажите ?
21 мар 18, 07:27    [21273124]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Насколько я понял "из всякого" Java9/Java10 - проходные версии. Это, в основном, задел для обеспечения возможности изменений.
Первый выпуск с длительным сроком поддержки - Java11, запланированная на осень 2018 года.
Плюс, проблемы с модульной системой Java9 у всяческих (OSGI/etc) контейнеров.
Рано, в общем "новомодностям" в промышленную эксплуатацию.
21 мар 18, 07:38    [21273127]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Лично для меня, наиболее важное в Java8 - статические и умалчиваемые методы в интерфейсах.
Это открывает возможность "изящного" проектирования и, с моей кочки зрения, важнее "сахара и плюшек".
21 мар 18, 07:42    [21273129]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
scf
Member

Откуда:
Сообщений: 1480
Atum1,

Странно, живете в парадигме ФП и не знаете, что спрашивать)
Прежде всего - стримы и лямбды. что такое functional interface, как из коллекции людей найти всех мужчин, сгруппированных по месяцу рождения и т.п.

А вообще в джаве плохое ФП. Пример: реализовать вот такой метод
Optional<Integer> sum(Optional<Integer> x, Optional<Integer> y);
21 мар 18, 11:02    [21273578]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
andreykaT
Member

Откуда:
Сообщений: 2216
ява для таких вещей старовата. пример хороший. и как раз это и показывает
21 мар 18, 14:11    [21274468]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
andreykaT
ява для таких вещей старовата. пример хороший. и как раз это и показывает


вот все что нашел :
https://jsehelper.blogspot.ru/2016/05/java-8-2.html

самое интересно это дефолтовые и статик методы


Есть еще вопросы от одноклассников - но там код и решить его на листочке проблематично слишком мудрено ...

вопрос : сколько разных объектов Supplier породит следующий код

и почему ?


import java.util.HashSet;
import java.util.Set;
import java.util.function.Supplier;

public class SupplierTest 
{
    public static void main(String[] args) {
        Set<Supplier<Number>> set = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            final int n = i;
            set.add(()->0);
            set.add(()->n);
            set.add(Math::random);
        }
    }
}


ответ
+

12
21 мар 18, 18:43    [21275507]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 31 32 33 34 35 [36] 37 38 39 40 .. 42   вперед  Ctrl
Все форумы / Java Ответить