NVIDIA Interview Question
let say
aar1=7,14,21
arr2=6,12
after inplace merging(requires no extra space)
arr1=6,7,12
arr2=14,21
Can something similar to insertion sort do it? Insert every element of arr2 into arr1 in a similar way as in an insertion sort. Time complexity is sort of high...
Lets say 2 arrays:
arr1[];
arr2[];
for ( i = 0; i<arr1.length;i++)
{
if ( arr1[i] > arr2[0] )
{
temp = arr1[i];
arr1[i] = arr2[0];
for ( j = 1; j < arr2.length; j++ )
{
if ( arr2[j] < temp )
{
arr2[j-1] = arr2[j];
}
else
{
arr2[j-1] = temp;
break;
}
}// end 2nd for loop
} // end if
}//end first for loop
Lets say 2 arrays:
arr1[];
arr2[];
for ( i = 0; i<arr1.length;i++)
{
if ( arr1[i] > arr2[0] )
{
temp = arr1[i];
arr1[i] = arr2[0];
for ( j = 1; j < arr2.length; j++ )
{
if ( arr2[j] < temp )
{
arr2[j-1] = arr2[j];
}
else
{
arr2[j-1] = temp;
break;
}
}// end 2nd for loop
} // end if
}//end first for loop
<pre lang="java" line="1" title="CodeMonkey88227" 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="CodeMonkey88227" input="yes">
12</pre>
arr1[] and arr2[] be the arrays
- Andrew October 22, 2011for(i=0;i<arr1.length();i++)
{
if(arr1[i]>arr2[0])
{
swap(arr[i],arr[0])
for(j=0;j<arr2.length-1;j++)
if(arr2[j]>arr2[j+1])
swap(arr2[j],arr2[j+1]);
else break;
}