Interview question

[Jack]

Hi,
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).

 

[Victor Bazarov]

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

 

[Jack]

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

ummm, the program I was ask to write was in c++.

 

[John Harrison]

Hi,
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).

You can do better than that.

Start filing B from the back end. You can do this with one pass
(backwards) though A and B, no need for sorting, O(n).

john

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

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

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().

 

[Victor Bazarov]

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.

[..]
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 C++ way does not have to be to use 'std::sort'. The C++ way would
be to implement whatever algorithm the OP figures out for merging the
lists (supposedly starting from the ends and swapping the elements to
be inserted into the (end_1 + length_2) position and assigning... In
any way, the algorithm does not exist in C++ standard library (just
like countless others) so it has to be implemented by hand. However,
we cannot be spending all our time suggesting algorithms here. Please,
Jack, figure out the algorithm, try putting it into C++ terms, and if
you hit the wall, come back, post your results and ask particular
questions. And read the FAQ. And please do your [own] homework(tm).

V

 

[Jack]

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.

[..]
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 C++ way does not have to be to use 'std::sort'. The C++ way would
be to implement whatever algorithm the OP figures out for merging the
lists (supposedly starting from the ends and swapping the elements to
be inserted into the (end_1 + length_2) position and assigning... In
any way, the algorithm does not exist in C++ standard library (just
like countless others) so it has to be implemented by hand. However,
we cannot be spending all our time suggesting algorithms here. Please,
Jack, figure out the algorithm, try putting it into C++ terms, and if
you hit the wall, come back, post your results and ask particular
questions. And read the FAQ. And please do your [own] homework(tm).

V

Victor, As I said in the subject, this was a question I was asked
during an interview I had so it is not for homework. secondly, you're
not obligated to respond (ie. suggest an algorithm), if you don't want
to suggest things, get the out of my thread. and lastly my suggestion
as per my original post was to add A to B and then sort B. Next time
read the full message before posting some meaningless remark.

 

[throatslasher]

Next time read the full message before posting some
meaningless remark.

Next time read the FAQ before posting some retarded question (and--I
dare add--some retarded solution; you definitely shouldn't get the
job). Sorry if you can't stand being corrected, but the fact is that
you've posted this in the wrong group, regardless of what you assumed
this group was for and regardless of whatever weak justification
you've tried to frabricate to spare your pride.

 

[mlimber]

Victor, As I said in the subject, this was a question I was asked
during an interview I had so it is not for homework. secondly, you're
not obligated to respond (ie. suggest an algorithm), if you don't want
to suggest things, get the out of my thread. and lastly my suggestion
as per my original post was to add A to B and then sort B. Next time
read the full message before posting some meaningless remark.

Hi, Jack.

Victor is actually correct that this is not on-topic here just because
the program is in C++. This group discusses the C++ language proper,
not arbitrary algorithms developed in C++ (http://www.parashift.com/c+
+-faq-lite/how-to-post.html#faq-5.9). Now certainly there is some gray
area in what should be posted here, but unless you're asking what
language constructs or pieces of the standard library could help you
solve this problem, I think your question is pretty clearly off-topic.

Of course, if you can rephrase the question in terms of the language
itself, you'll get less open hostility and likely more direct help.

Cheers! --M

 

[Victor Bazarov]

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.

[..]
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 C++ way does not have to be to use 'std::sort'. The C++ way
would be to implement whatever algorithm the OP figures out for
merging the lists (supposedly starting from the ends and swapping
the elements to be inserted into the (end_1 + length_2) position and
assigning... In any way, the algorithm does not exist in C++
standard library (just like countless others) so it has to be
implemented by hand. However, we cannot be spending all our time
suggesting algorithms here. Please, Jack, figure out the algorithm,
try putting it into C++ terms, and if you hit the wall, come back,
post your results and ask particular questions. And read the FAQ.
And please do your [own] homework(tm).

V

Victor, As I said in the subject, this was a question I was asked
during an interview I had so it is not for homework.

Look in the dictionary for the definition of "homework". I don't
mean a course assignment. If you got a question on an interview (or
anywhere else) you could not answer, you should work on answering it,
preferably at home. As soon as you get into the habit, you will see
that it doesn't just give you the benefit of finding a solution.

secondly, you're
not obligated to respond (ie. suggest an algorithm), if you don't want
to suggest things, get the out of my thread.

It's not "your thread". If you don't like my replies, don't read them.

and lastly my suggestion
as per my original post was to add A to B and then sort B. Next time
read the full message before posting some meaningless remark.

I strongly recommend checking your attitude at the door if you expect
help. If you learn to do that, you're going to have better chances at
finding decent employment, as well.

V

 

[Kai-Uwe Bux]

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

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:stream_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

 

[Jim Langston]

Hi,
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).

I would just load a variable with the position of the last element of A one
one with the last element of B, and one with the last possition in B. Then
start filling in from the end whichever is the greater of the other two.
I think they were just looking for your problem solving skills. Something
along the lines of:

size_t PosA = 3;
size_t PosB = 3;
size_t Current = 6;

while ( PosA > 0 && PosB > 0 )
{
if ( A[PosA] >= B[PosB] )
B[Current--] = A[PosA--];
if ( B[PosB] > A[PosA] )
B[Current--] = B[PosB--];
}

// We are at PosA == 0 and PosB == 0, manually stuff them in checking
current.