Interview Questions - A Little Help

Question

I came across thos quesiton in a google search ... they look pretty often, but I could not find a decent answer. any tips / links?

1.Remove duplicates in an array in O (n) without an additional array

2. Record a program whose printed output is an exact copy of the source. Needless to say, simply echoing the actual source file is not allowed.

Answer 1

(1) impossible if the array is not defined. The main answer is to hold two pointers in an array, one to go forward looking for unequal elements, and one trailing pointer. When the direct pointer encounters an unequal element, it copies it to the trailing pointer and increases the trailing pointer.

(2) I do not have at hand. That sounds like a pretty awful interview question. In most interpreted languages, a 0-byte (empty) source file is a valid input and does not output anything that needs to be counted.

Answer 2

For (1), you probably need more restrictions than you indicated. However, look at radix sorting.

For (2) find quine.

Answer 3

google for quine !

Answer 4

, - ( ) - O (n), , . , , , .

2 ? ( , ).

Edit:

Perl - ++ :

# 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 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 g++ STL , ).

Answer 6

# 2 : http://www.nyx.net/~gthompso/quine.htm

quine ++: http://npcomplete.weebly.com/1/post/2010/02/self-reproducing-c-program-quine.html