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

Откуда: СПБ
Сообщений: 1836
Задача

Есть два односвязных массива, у которых есть общая часть. Нужно выяснить индексы массивов, с которых начинается общая часть.
Примеры массивов:

- a b c x y z
- d e a d b e e f x y z
12 окт 16, 11:16    [19772378]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
scf
Member

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

можно вот это адаптировать: https://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока
12 окт 16, 11:22    [19772402]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Atum1
Есть два односвязных массива, у которых есть общая часть. Нужно выяснить индексы массивов, с которых начинается общая часть.
Примеры массивов:

- a b c x y z
- d e a d b e e f x y z

Даже в примере этих частей не одна:
a
b
x
xy
xyz


Короче суффиксное дерево тебе в помощь. :)
12 окт 16, 13:05    [19773011]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Сергей Арсеньев
Atum1
Есть два односвязных массива, у которых есть общая часть. Нужно выяснить индексы массивов, с которых начинается общая часть.
Примеры массивов:

- a b c x y z
- d e a d b e e f x y z

Даже в примере этих частей не одна:
a
b
x
xy
xyz


Короче суффиксное дерево тебе в помощь. :)


про суффиксные деревья думал

...

нашел в книге жемчужины программирования код на Хаскеле - как я понял решается за O(n+m)

но как то что написано на хаскеле перевести на обычный язык?

Бёрд Р. - Жемчужины проектирования алгоритмов. Функциональный подход.pdf
12 окт 16, 22:38    [19775744]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Задача из серии как можно написать короче ?

Есть https://projecteuler.net/problem=16

что дано

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2**1000?


Answer:
1366

Решение на питоне :
sum(map(int,str(2**1000)))

или так 

sum = 0
for n in str(2**1000):
	sum += int(n)
print sum


как можно написать на java ?

я с ходу делаю так :

   int s=  BigInteger
                .valueOf(2)
                .pow(1000)
                .toString()
                .chars()
                .mapToObj(Character::getNumericValue)
                .mapToInt(i->i).sum();
              
              System.out.println(s); 


но как говорит Никита слишком много букв :(


вопрос как записать решение короче?
13 окт 16, 22:59    [19779584]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Вопрос с собеседования :

Почему крышки канализационных люков круглые?


Если вы знаете ответ , или уверены в том что знаете то вам под кат :

+

Почему дождеприемники прямоугольной формы (ливневые решетки) ?
1 ноя 16, 16:08    [19846987]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4113
Atum1
Если вы знаете ответ , или уверены в том что знаете то вам под кат :

+ Главное умение - обосновать почему именно так надо было

Картинка с другого сайта.

+ Хотя умный люди говорят, что ответ на первоначальный вопрос гласит
бóльшим отношением площади сечения лаза круглого люка к длине окружности его корпуса, чем у квадратного или прямоугольного, что позволяет снизить себестоимость производства за счёт сокращения расхода материалов без ухудшения эксплуатационных показателей.

Это же и объясняет ответ и про люк ливневки.
1 ноя 16, 17:05    [19847397]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Сергей Арсеньев
Atum1
Если вы знаете ответ , или уверены в том что знаете то вам под кат :

+ Главное умение - обосновать почему именно так надо было

Картинка с другого сайта.

+ Хотя умный люди говорят, что ответ на первоначальный вопрос гласит
бóльшим отношением площади сечения лаза круглого люка к длине окружности его корпуса, чем у квадратного или прямоугольного, что позволяет снизить себестоимость производства за счёт сокращения расхода материалов без ухудшения эксплуатационных показателей.

Это же и объясняет ответ и про люк ливневки.


спасибо :) очень интересно.
1 ноя 16, 17:17    [19847456]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
just_vladimir
Member

Откуда:
Сообщений: 869
Atum1
Вопрос с собеседования :

Почему крышки канализационных люков круглые?


Если вы знаете ответ , или уверены в том что знаете то вам под кат :

+

Почему дождеприемники прямоугольной формы (ливневые решетки) ?

Ну это всем давно должно быть известно, что это ради того, чтобы черепашкам ниндзя было удобно в них полазить
1 ноя 16, 22:10    [19848430]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Эль классико :

(утро разминка для мозга :)
что напечатает код и почему :

public class NewClass {

    static int a = 1111;

    static {
        a = a-- - --a;//2
    }

    {
        a = a++ + ++a;
    }

    public static void main(String[] args) {
        System.out.println(a);
    }
}
16 ноя 16, 09:09    [19898660]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Alexey Tomin
Member

Откуда: Самара
Сообщений: 1687
Atum1
Эль классико :

(утро разминка для мозга :)
что напечатает код и почему


Правильный ответ - "код не пройдёт код-ревью и ничего не напечатает".

А если серьёзно- а какая цель задающего вопрос?
Что он хочет узнать о кандидате на собеседовании?
Я серьёзно не понимаю смысла в этих вопросах в контексте "задачка для собеседования".
16 ноя 16, 09:40    [19898782]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Alexey Tomin
Atum1
Эль классико :

(утро разминка для мозга :)
что напечатает код и почему


Правильный ответ - "код не пройдёт код-ревью и ничего не напечатает".

А если серьёзно- а какая цель задающего вопрос?
Что он хочет узнать о кандидате на собеседовании?
Я серьёзно не понимаю смысла в этих вопросах в контексте "задачка для собеседования".


На с++ будет warn - но соберется ...

для java - все ок ! типа это нормальный код :)
16 ноя 16, 17:26    [19900947]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
вот хороший вопрос :

(искал в гугле нет решения :)

Найти все размещения без повторений из n элементов по k

т.е. на входе вам задано : (2,4) или (5 , 36)

на выходе список всех комбинаций без повторений (1,2 === 2,1) - Это одно и тоже

с ходу для (2,4) [1,2,3,4]


      int[] a = IntStream.rangeClosed(1, 4).toArray();
        int size = a.length;
        for (int i1 = 0; i1 < size; i1++) {
            for (int i2 = i1 + 1; i2 < size; i2++) {
                String s = String.format("%d %d\n", a[i1], a[i2]);
                System.out.println(s);
            }

        }



1 2

1 3

1 4

2 3

2 4

3 4


а как написать универсальный / паралельный / способ ?
16 ноя 16, 17:35    [19900971]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Локшин Марк
Member

Откуда: Воронеж
Сообщений: 3144
Atum1
вот хороший вопрос :

(искал в гугле нет решения :)

Найти все размещения без повторений из n элементов по k


Издеваешься? Классическая задача из комбинаторики и не нашел в гугл решения?
16 ноя 16, 20:41    [19901291]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Alexey Tomin
Member

Откуда: Самара
Сообщений: 1687
Atum1
для java - все ок ! типа это нормальный код :)


Не любой код, который проходит копиляцию - нормальный.
Тут скорее задача "найдите и объясните весь г@внокод в этом примере".
17 ноя 16, 07:48    [19902035]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Локшин Марк
Atum1
вот хороший вопрос :

(искал в гугле нет решения :)

Найти все размещения без повторений из n элементов по k


Издеваешься? Классическая задача из комбинаторики и не нашел в гугл решения?


Я не нашел универсального решения для любых (k,n) ( видимо рекурсия без переполнения стека )
но хочется увидеть как эта задача решается на стримах и как она отлично паралелиться .
17 ноя 16, 10:29    [19902407]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
+ рекурсия примерно так
public class Perestanovka {
  private int[] result;
  public Perestanovka(int k) {
    result = new int[k];
  }
  public void iterate(int n, int k) {
    for (int i=n;i>=k-1;i--) {
      result[k-1]=i;
      if (k==1) {
        System.out.println(Arrays.toString(result));
      } else {
        iterate(i-1,k-1);
      }
    }
  }
  public static void main(String... args) {
    Perestanovka p = new Perestanovka(4);
    p.iterate(6, 4);
  }
}

Можно еще унаследоваться от Observable для полного счастья.
А вот параллелить без повторов сложновато
17 ноя 16, 11:45    [19902767]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 848
С этими нулевыми индексами запутался, в цикле ошибка. Должно быть i>=k
for (int i=n;i>=k;i--)
17 ноя 16, 11:51    [19902787]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Локшин Марк
Member

Откуда: Воронеж
Сообщений: 3144
Atum1
Я не нашел универсального решения для любых (k,n) ( видимо рекурсия без переполнения стека )

Тынц.
17 ноя 16, 14:32    [19903824]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
Локшин Марк,

Ок.

опираясь на Ваш вашем алгоритм - нужно построить генератор


Stream.generate


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

т.е. хочу вызывать его из разных потоков и получать следующую пермутацию (а идеале любую которую еще не сгенерировали )

чтобы генерировать их параллельно , без гонок .

и так пока не закончатся комбинации ....


Хранить в памяти их все - немозможно - ибо их очень много

файл для 5 из 36 - будет давать ~ 5 мб

для 7 из 49 еще больше :)
21 ноя 16, 13:40    [19915878]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 40558
Up. Хорошая тема стухла.

Предлагаю сравнить стратегии использования коллекций Java+Scala.
Можно даже с возвратом к самым первым постам.
27 янв 17, 01:12    [20151671]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
mayton
Up. Хорошая тема стухла.

Предлагаю сравнить стратегии использования коллекций Java+Scala.
Можно даже с возвратом к самым первым постам.


почему стухла ?!

вот отличная задачка : по sql

для примера БД mysql

Есть таблица
CREATE TABLE Tickets (
transactionId BIGINT NOT NULL GENERATED ALWAYS AS IDENTITY, 
creationDate DATETIME, 
login BIGINT NOT NULL, 
phone BIGINT NOT NULL, 
ticket BLOB  FOR BIT DATA , 
ticketId BIGINT DEFAULT 0  NOT NULL, 
PRIMARY KEY (transactionId));


Нужно найти последний проданный билет для указанного логина и телефона .

что для этого ( нужно написать sql, как минимум )?

Который бы решал бы эту задача самым оптимальным способом .
1 фев 17, 13:24    [20169404]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
mayton
Up. Хорошая тема стухла.

Предлагаю сравнить стратегии использования коллекций Java+Scala.
Можно даже с возвратом к самым первым постам.


Java+Scala

вроде как скала медленно отмирает ? ибо перемудрил Одесски со своими функционально объектно миксами ?

не?

http://www.tiobe.com/tiobe-index/
1 фев 17, 13:26    [20169413]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
забыл ник
Member

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

вроде как скала медленно отмирает ?


Да не сказал бы, в нише Machine Learning + DataMining он все более и более востребован на мой взгляд
1 фев 17, 13:34    [20169464]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Atum1
Member

Откуда: СПБ
Сообщений: 1836
забыл ник
Atum1
вроде как скала медленно отмирает ?


Да не сказал бы, в нише Machine Learning + DataMining он все более и более востребован на мой взгляд


тогда скажем так - скала нашла свое место .
1 фев 17, 15:02    [20169904]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 25 26 27 28 29 [30] 31 32 33 34 .. 42   вперед  Ctrl
Все форумы / Java Ответить