вопросы интервью - небольшая помощь

Question

Я столкнулся с thos quesiton в поиске Google ... они выглядят довольно часто, но я не мог найти достойного ответа. любые советы/ссылки?

1.Remove дубликатов в массиве в O (N) без дополнительного массива

2.Write программу, в которой печатная продукция является точной копией источника. Излишне говорить, что просто повторение фактического исходного файла недопустимо.

Answer 1

(1) невозможно, если массив не настроен. Основной ответ состоит в том, чтобы держать два указателя в массиве, один идти вперед, ища неравные элементы, и один трейлинг-указатель. Когда прямой указатель встречает неравный элемент, он копирует его в трейлинг-указатель и увеличивает трейлинг-указатель.

(2) У меня нет под рукой. Это звучит как довольно ужасный вопрос интервью. В большинстве интерпретируемых языков 0-байтовый (пустой) исходный файл является допустимым входом и не выводит ничего, что должно подсчитываться.

Answer 2

Для (1) вам, вероятно, потребуется больше ограничений, чем вы указали. Однако посмотрите radix sort.

Для (2), посмотреть quine.

Answer 3

Для вашего второго вопроса google for quine вы найдете много ответов!

Answer 4

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

Для 2 будет разрешена только ручная печать содержимого файла? (если так, то вопрос более чем немного бессмыслен).

Edit:

Вот быстрая версия Perl моего решения к первой - в C++ вы должны создать хэш вручную:

# Return an unsorted version of an array without duplicates 
sub unsortedDedup { 
    my %seen, my @return; 

    map { 
     $seen{$_} = 1 
     && push @return, $_ 
     unless (defined $seen{$_}) 
    } @_; 

    @return; 
} 

Answer 5

STL часто не вариант в таких вопросы интервью, но вот один из способов сделать # 1 с использованием STL, хотя он понесет дополнительный вид (как объяснено Terry's answer):

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    int a[] = { 2, 2, 3, 2, 1, 4, 1, 3, 4, 1 }; 
    int * end = a + sizeof(a)/sizeof(a[0]); 

    std::sort(a, end);   // O(n log n) 
    end = std::unique(a, end); // O(n) 

    std::copy(a, end, std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 
} 

Вот результат :

$ ./a.out 
1 2 3 4 

std::unique() обычно реализуется с использованием той же методики, описанной Терри в своем ответе (см bits/stl_algo.h в г ++ реализация STL 's для примера того, как его реализовать).

Answer 6

Для # 2, существует целый ряд ответов на разных языках здесь: http://www.nyx.net/~gthompso/quine.htm

Существует также альтернативный Куайн в C++ здесь: http://npcomplete.weebly.com/1/post/2010/02/self-reproducing-c-program-quine.html