Сообщение Re[11]: Что вы всегда спрашиваете на собеседовании? от 14.06.2019 3:40
Изменено 14.06.2019 3:44 Артём
Re[11]: Что вы всегда спрашиваете на собеседовании?
Здравствуйте, Lexey, Вы писали:
L>%>Т.е. там выделяется массив размером с макс число на входе?
L>Что такое "макс. число на входе"? Если размер алфавита, то да.
Например, алфавит из 3 символов: 0, 1, (2^64-1).
L>%>Cемантически, то же самое, что завести 3 BitSet, выставить каждому бит по индексу входного числа, сделать AND и вывести нижний бит (если он есть)?
L>Типа того. Только у него в случае неотсортированных массивов выведется не наименьший символ, а первый, который встретится во всех 3-х массивах. В случае отсортированных массивов разницы не будет.
Раз уж "в лоб" решение и утверждается про "нетребование к упорядоченности", то нужно затянуть до конца. И уже потом искать наименьший общий символ.
L>%>И по сути, проще тогда завести TreeMap<character, byte>, выставлять 0..2 бит в его value. По окончании, перебрать это rbtree до первого нода с 3 выставленными битами.
L>Это уже O(N log K) (где K — размер алфавита), вместо O(N).
А ничего, что памяти оно требует овердофига? (maxSym-minSym).
L>%>Т.е. там выделяется массив размером с макс число на входе?
L>Что такое "макс. число на входе"? Если размер алфавита, то да.
Например, алфавит из 3 символов: 0, 1, (2^64-1).
L>%>Cемантически, то же самое, что завести 3 BitSet, выставить каждому бит по индексу входного числа, сделать AND и вывести нижний бит (если он есть)?
L>Типа того. Только у него в случае неотсортированных массивов выведется не наименьший символ, а первый, который встретится во всех 3-х массивах. В случае отсортированных массивов разницы не будет.
Раз уж "в лоб" решение и утверждается про "нетребование к упорядоченности", то нужно затянуть до конца. И уже потом искать наименьший общий символ.
L>%>И по сути, проще тогда завести TreeMap<character, byte>, выставлять 0..2 бит в его value. По окончании, перебрать это rbtree до первого нода с 3 выставленными битами.
L>Это уже O(N log K) (где K — размер алфавита), вместо O(N).
А ничего, что памяти оно требует овердофига? (maxSym-minSym).
Re[11]: Что вы всегда спрашиваете на собеседовании?
Здравствуйте, Lexey, Вы писали:
L>%>Т.е. там выделяется массив размером с макс число на входе?
L>Что такое "макс. число на входе"? Если размер алфавита, то да.
Например, алфавит из 3 символов: 0, 1, (2^64-1).
L>%>Cемантически, то же самое, что завести 3 BitSet, выставить каждому бит по индексу входного числа, сделать AND и вывести нижний бит (если он есть)?
L>Типа того. Только у него в случае неотсортированных массивов выведется не наименьший символ, а первый, который встретится во всех 3-х массивах. В случае отсортированных массивов разницы не будет.
Раз уж "в лоб" решение и утверждается про "нетребование к упорядоченности", то нужно затянуть до конца. И уже потом искать наименьший общий символ.
L>%>И по сути, проще тогда завести TreeMap<character, byte>, выставлять 0..2 бит в его value. По окончании, перебрать это rbtree до первого нода с 3 выставленными битами.
L>Это уже O(N log K) (где K — размер алфавита), вместо O(N).
Да, ты прав. С HashMap можно затянуть все массивы, потом с фильтром вывести наименьшее из совпавших чисел.
L>%>Т.е. там выделяется массив размером с макс число на входе?
L>Что такое "макс. число на входе"? Если размер алфавита, то да.
Например, алфавит из 3 символов: 0, 1, (2^64-1).
L>%>Cемантически, то же самое, что завести 3 BitSet, выставить каждому бит по индексу входного числа, сделать AND и вывести нижний бит (если он есть)?
L>Типа того. Только у него в случае неотсортированных массивов выведется не наименьший символ, а первый, который встретится во всех 3-х массивах. В случае отсортированных массивов разницы не будет.
Раз уж "в лоб" решение и утверждается про "нетребование к упорядоченности", то нужно затянуть до конца. И уже потом искать наименьший общий символ.
L>%>И по сути, проще тогда завести TreeMap<character, byte>, выставлять 0..2 бит в его value. По окончании, перебрать это rbtree до первого нода с 3 выставленными битами.
L>Это уже O(N log K) (где K — размер алфавита), вместо O(N).
Да, ты прав. С HashMap можно затянуть все массивы, потом с фильтром вывести наименьшее из совпавших чисел.