Re: Interview question
Erik Wikstr?m wrote:
On Mar 1, 6:17 am, "Jack" <accpac...@hotmail.com> wrote:
On Feb 28, 9:00 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
Jack wrote:
I was asked this question during an interview. It seems very simple
but I don't know if there is a more efficient way.
The question said, we have 2 arrays as follows
A = [2, 3, 5, 7]
B = [4, 6, 8, , , , ]
As you can see both arrays are sorted. Also we see that B has enough
space for all the elements in A. We want to put element A in to B
without using a third element.
My solution was to add all elements from A to the end of and then use
quick sort to sort B. The other way would be to traverse B for every
element in A but that wouldn't be too efficient since it will be
O(n^2).
This has nothing to do with C++. Please consider posting to
comp.programming.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
ummm, the program I was ask to write was in c++.
Yes, but the algorithm could be implemented in any language. Now if
you want a good C++ solution to the problem then I'd suggest to do as
you did, copy A to the end of B, then use std::sort() to sort B.
Now, going a bit OT, if the arrays were a lot larger and the sorting
was very critical for performance then I think I would take a look at
the merging-step of mergesort. I think that mergesort produces these
kind of things (two individually sorted sequences) and then merges
them. But as I said, the C++ way would be to use std::sort().
The following is undefined behavior, but I would guess it will generally
work:
#include <functional>
#include <iostream>
#include <iterator>
#include <algorithm>
typedef std::reverse_iterator<int*> rev_ptr;
int main ( void ) {
int A [4] = {2, 3, 5, 7};
int B [7] = {4, 6, 8};
rev_ptr A_rbegin ( &A[0] + 4 );
rev_ptr A_rend ( &A[0] );
rev_ptr B_rbegin ( &B[0] + 3 );
rev_ptr B_rend ( &B[0] );
rev_ptr where (&B[0] + 7 );
std::merge( A_rbegin, A_rend,
B_rbegin, B_rend,
where,
std::greater<int>() );
std::copy( &B[0], &B[0] + 7,
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
}
It is UB because the standard requires the resulting range for merge() not
to overlap with the source ranges. Maybe, this can be considered a defect.
Best
Kai-Uwe Bux