Алгоритм списка массивов - Интервью

Question

Мне задали этот вопрос в интервью сегодня. Я попробовал решение, но хотел бы знать, если есть лучший способ решить эту проблему:

Вопрос: У меня есть ArrayList сказать 500000 элементов таким образом, что значение каждого элемента ArrayList такое же, как индекс , Например: list.get (0) = 0; list.get (1) = 1 ... и т. д. Но только один элемент не синхронизирован с этим упорядочением [i.e list.get (i)! = I]. Как вы находите этот элемент.

Мой ответ: Итерируйте по списку, используя несколько потоков, каждый поток, обрабатывающий определенное сращивание арраиста каждый раз, сравнивая list.get (i) с i. Когда элемент найден, установите некоторую логическую переменную, чтобы указать другим потокам, что элемент был найден.

Есть ли способ решить эту проблему без повторения списка? Или лучший способ?

Answer 1

В худшем случае вам необходимо изучить каждый элемент, поэтому вы не можете улучшить сложность времени O(n).

С учетом этого лучшим алгоритмом является сканирование списка массивов от начала до конца. Таким образом, вы лучше всего используете доступную пропускную способность памяти.

Мне не совсем понятно, как и почему резьба вошла в картину. Это кажется неуместным. Было ли это частью вопроса?

Answer 2

Вы не можете сделать лучше, чем O(n).

И, во-вторых, я думаю, что это плохая идея говорить о потоках и многопоточности в этих проблемах. Они не представляют интереса вообще. В итоге у вас есть время выполнения O (независимо от того, где ваша константа удаляется в любом случае).

Возможно, интервьюер имел в виду сортированный массив с элементами от 0 до n-1 с индексом от 0 до n-1. Затем переместите один элемент в другую позицию. Но это означает, что все остальные элементы имеют разные индексы! В этом случае вы можете улучшить поиск с помощью двоичного поиска:

Затем вы можете получить элемент в O(log n). Начните посередине и проверьте, равен ли индекс элементу. Если он равен, делайте то же самое с верхней частью половины, если не используете другую часть.

Answer 3

В дополнение к ответу @ Aix, то как о выполнении 2 проверки в цикле:

for (int i = 0; i < list.size/2; i++) 
{ 
    if (i != list.get(i)) 
    { 
    return i; 
    } 
    else if (list.size - i != list.get(list.size - i) 
    { 
    return list.size - i; 
    } 
} 

Answer 4

1. iterate through the list 
2. check for the condition in the elements 
3. when that only element found break out the loop... 

Я не думаю, что тема выходит на арену ...

Answer 5

Ответ: один итерации , Ваше упоминание о параллельности причины - это то, за что они ловят рыбу.

Фактически, поскольку java 8, решение, параллельное или нет, простое. Я думаю, что больше всего бы принесли:

OptionalInt foundInt = IntStream.range(0, list.size()) 
    .parallelStream() 
    .filter(i -> i != list.get(i)) 
    .findAny();