CareerCup

you can publish a paper if you solve it ten years ago

And I doubt the author of that paper couldn't come up with the solution within 20 mins or so

such interview question is nonsense

you can publish a paper if you solve it ten years ago

And I doubt the author of that paper couldn't come up with the solution within 20 mins or so

such interview question is nonsense

O(n) or O(1) space ?

O(n) space is trivial.

Is it even possible to do it in O(n) time and O(1) space?

Has it to be in place? [without using any extra space, I mean]

use recursive solution by dividing the array into two and merge the re-arranged two sub-arrays.

Interviewer asked How to convert it by swapping variables ??

consider the following psudo code

re-arrange(int * p, int size) {
if (size == 4) {
swap(p[1], p[3])
}
if (size == 3) {
return;
}
re-arrange(p, size/2);
re-arrange(p + size/2, size/2);

for(int i = 1; i < size/4; i++) {
int nSwap = p[2*i];
p[2*i] = p[2*i + size/2 - 1] ;
p[2*i + size/2 - 1] = nSwap ;
}
}

Essentially, if we chang the array a1a2...aNb1b2...bN->a1a(N/2+1)a2a(N/2+2)a3a(N/2+3)..a(N/2)aN b1b(N/2+1)b2b(N/2+2)...b(N/2)bN. By swapping the a(N/2) with b1, a(N/2+1) with b2... aN with b(N/2-1) is the array we need. In addition, the two subarry a1a(N/2+1)a2a(N/2+2)a3a(N/2+3)..a(N/2)aN and b1b(N/2)b2b(N/2+1)...b(N/2-1)bN can be considerd as the same re-arrange of a1a2...a(N/2)c1c2...c(N/2) (c1 = a(N/2+1), c2=a(N/2+2).. c(N/2) = aN). However, we need to consider the case N is an odd number though.

With the approach, the solution can be solved in O(N) time and O(1) space

O(1) space solution is required and you give a recursive method? Well... that solution is kind of, er... moronic.

There are too many crap posts on this site, I can sympathise with the person who said moron, but nothing justifies an attack on the person instead of the idea.

Everyone does stupid things some of the time. It does not mean they are completely stupid.

consider the following psudo code

re-arrange(int * p, int size) {
if (size == 4) {
swap(p[1], p[3])
}
if (size == 3) {
return;
}
re-arrange(p, size/2);
re-arrange(p + size/2, size/2);

for(int i = 1; i < size/4; i++) {
int nSwap = p[2*i];
p[2*i] = p[2*i + size/2 - 1] ;
p[2*i + size/2 - 1] = nSwap ;
}
}

Essentially, if we chang the array a1a2...aNb1b2...bN->a1a(N/2+1)a2a(N/2+2)a3a(N/2+3)..a(N/2)aN b1b(N/2+1)b2b(N/2+2)...b(N/2)bN. By swapping the a(N/2) with b1, a(N/2+1) with b2... aN with b(N/2-1) is the array we need. In addition, the two subarry a1a(N/2+1)a2a(N/2+2)a3a(N/2+3)..a(N/2)aN and b1b(N/2)b2b(N/2+1)...b(N/2-1)bN can be considerd as the same re-arrange of a1a2...a(N/2)c1c2...c(N/2) (c1 = a(N/2+1), c2=a(N/2+2).. c(N/2) = aN). However, we need to consider the case N is an odd number though.

With the approach, the solution can be solved in O(N) time and O(1) space


assume this solution is f(n). Then f(n) = f(n/2) + f(n/2) + O(n/4). f(n) = 2f(n/2) + O(n/4). if f(1) = f(2) = f(3) = f(4) =1. Then, f(n) = O(n)

Hi, Moron,

Looks who is the moron now

Hi, Moron,

Looks who is the moron now

I guess the solution the interviewer wants is the one replace the above recursive to while loop

Adobe are a bunch of morons because unlike the published O(n) solution, the O(n log n) solution is cache-oblivious and thus almost certainly faster on real computers.

On real computers, you just create a new array and be done with it :)

btw, what is the published solution? I can't seem to find it.

Thanks.

Ok Morons... Here's an O(n) time, O(1) space approach:

- Read the first string sequentially to determine, N, {l[1],l[2],....,l[k]} and store l[1], l[k], N. l[1]=a, l[2]=b, .... l[k]=some letter.
- Write the first string in place in a loop...
for(i=1;i<N;i++) { for (j=l[1];j<l[k];j++) { output j; output i; }

{
void shuffle (char arr[], int lower, int size)
{
int i = lower;
int mid = size/2;

while (mid < size) {
int temp = arr[mid];
for (int j = mid; j > i; j--) {
arr[j] = arr[j-1];
}
arr[j+1] = temp;
mid++;
i += 2;
}
}
}

{
void shuffle (char arr[], int lower, int size)
{
int i = lower;
int mid = size/2;

while (mid < size) {
int temp = arr[mid];
for (int j = mid; j > i; j--) {
arr[j] = arr[j-1];
}
arr[j+1] = temp;
mid++;
i += 2;
}
}
}

I think this can be solved using in-place quicksort's algorithm for conquerring.. (i.e. have a pointer point to the start of a_i array and another pointed at the end of b_i). Then, the problem is simply to swap elements and increment the pointer that received the swap. Equality would be defined for a_i < b_j where i < j.
a_i < a_j and b_i < b_j where i<j.

If the elements violate the rules above, then swap. Otherwise, increment the last pointer that received a swap.

Some one started it and now every one calling others moron.

This is possible with using below algorithm. With Constant space. i.e have 3 indexes

one @ index=i aN, another j @ bN and third index @end of the array (which initially points to end of the array )
Now for every iteration swap and make sure that i, j are poiting to right index that are to be swapped next time. and index = index -2;

Continue till index > 0. Should be doable in o(n/2) =~ o(n).

Here is a O(1) space O(n^2) solution. I'll just give an example:

Say the string is:
1 2 3 4 5 a b c d e. We just swap pairwise from middle to the outside, like so:
1 2 3 4 a 5 b c d e //swap the middle only
1 2 3 a 4 b 5 c d e //swap the middle 2
1 2 a 3 b 4 c 5 d e //swap the middle 3
1 a 2 b 3 c 4 d 5 e //swap the middle 4 and we are done

<pre lang="java" line="1" title="CodeMonkey87687" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}

</pre><pre title="CodeMonkey87687" input="yes">1
2
10
4909
11

</pre>

How abt this?
let each node "a1" "a2" b1 b2 be a node in link list.
step1 . reach mid point (cliched slow and fast pointer).
keep 2 pointers at start and at mid.

step 2. Call insertAfter first pointer and keep moving the pointer to b[i] also note that Ai will now move two steps next->next while Bi will move only next.
maintain the invariant till the first pointer reaches mid. then we are done

I think most people are comparing this with a general case merge which is pretty hard to do inplace with constant space. However this one is pretty trivial. Consider this.

assume N = 4 as an example
v = [ 0 , 2 , 4 , 6 , 1 , 3 , 5 , 7 ]

It is easy to see that for i = 0 and i = 7 element are in the right place.
if ( i < 4 ) it should go in the 2 * i slot
if ( i >= 4) it shoudl go in the ( i - 4 ) *2 + 1 slot.

With this in mind you take a element try to put it in its right slot. Now you the element you removed from right slot has to be the next one you put in the right slot.

const int N = 10;

int GetNewIndex( int oldIndex )
{
	if ( oldIndex < N )
		return 2 * oldIndex ;

	return (oldIndex -N ) * 2 + 1;
}

void InplaceMerge( vector<int> & arr )
{
	int j = 1;
	int temp = arr[j];
	for ( int i = 1 ; i < (2*N-1) ; ++i )
	{
		int z = GetNewIndex( j );
		int newtemp = arr[z];
		arr[z] = temp;
		j = z;
		temp = newtemp;
	}
}