Blue Jeans Interview Question
Principal Software EngineersCountry: India
Interview Type: In-Person
public String[] sortArray(String[] input) {
for (int i = 0; i < input.length-1; i++) {
input[i+1]=getNextElement(input[i]);
}
return input;
}
private String getNextElement(String element) {
String c = element.substring(0,1);
int index = Integer.valueOf(element.substring(1));
if(c.equals("a")){
return "b" + index;
}
return "a"+ (index+1);
}
public String[] sortArray(String[] input) {
for (int i = 0; i < input.length-1; i++) {
input[i+1]=getNextElement(input[i]);
}
return input;
}
private String getNextElement(String element) {
String c = element.substring(0,1);
int index = Integer.valueOf(element.substring(1));
if(c.equals("a")){
return "b" + index;
}
return "a"+ (index+1);
}
Code Written in C
#include <stdio.h>
void print(int a[],int len){
int i=0;
for(;i<len;i++){
printf("%d\t",a[i]);
}
puts("");
}
int main()
{
int a[]={1,3,5,7,2,4,6,8};
int len=(sizeof(a)/sizeof(int)),mid=len/2;
int hit=1,dup=mid,i=0;
while(hit<=mid){
dup=mid++;
while(dup!=hit){
int temp=a[dup-1];
a[dup-1]=a[dup];
a[dup]=temp;
dup--;
}
hit+=2;
}
print(a,len);
return 0;
}
This swap progressively smaller chunks of the array.
a1 [a2 a3 a4] [b1 b2 b3] b4
a1 b1 [b2 b3] [a2 a3] a4 b4
a1 b2 a2 [a3] [b2] b3 a4 b4
a1 b2 a2 b2 a3 b3 a4 b4
int _tmain(int argc, _TCHAR* argv[])
{
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
InterlaceArray(array, 10);
DumpArray(array, 10);
return 0;
}
void InterlaceArray(int* inputArray, int arraySize)
{
// Swap a chunk
for (int startIndex = 1; startIndex < arraySize / 2; startIndex++)
{
// Swap elements in a chunk
for (int swapIndex = startIndex; swapIndex < arraySize / 2; swapIndex++)
{
std::swap(inputArray[swapIndex], inputArray[swapIndex + (arraySize/2 - startIndex)]);
}
}
}
private static void SortArray(int[] a)
{
for(int i: a)
System.out.print(i+ " ");
System.out.println();
int t = a.length/2;
int index = 1;
for(int i = t; i < a.length;i++)
{
for(int j = i; j > index;j--)
{
a[j] = a[j] + a[j-1];
a[j-1] = a[j] - 2*a[j-1];
a[j-1] = (a[j] + a[j-1])/2;
a[j] = a[j] - a[j-1];
}
index+=2;
}
for(int i:a)
System.out.print(i + " ");
}
private static void SortArray(int[] a)
{
for(int i: a)
System.out.print(i+ " ");
System.out.println();
int t = a.length/2;
int index = 1;
for(int i = t; i < a.length;i++)
{
for(int j = i; j > index;j--)
{
a[j] = a[j] + a[j-1];
a[j-1] = a[j] - 2*a[j-1];
a[j-1] = (a[j] + a[j-1])/2;
a[j] = a[j] - a[j-1];
}
index+=2;
}
for(int i:a)
System.out.print(i + " ");
}
private static void SortArray(int[] a)
{
for(int i: a)
System.out.print(i+ " ");
System.out.println();
int t = a.length/2;
int index = 1;
for(int i = t; i < a.length;i++)
{
for(int j = i; j > index;j--)
{
a[j] = a[j] + a[j-1];
a[j-1] = a[j] - 2*a[j-1];
a[j-1] = (a[j] + a[j-1])/2;
a[j] = a[j] - a[j-1];
}
index+=2;
}
for(int i:a)
System.out.print(i + " ");
}
public static void main (String[] args) throws java.lang.Exception
{
String a[] = new String[]{"a1","a2","a3","b1","b2","b3"};
reorder(a, 3);
}
public static void reorder(String a[], int n){
String b[] = new String[a.length];
int k = 0;
for(int i = 0; i < n; i++) {
b[k] = a[i];
k ++;
b[k] = a[i+n];
k++;
}
System.out.println("Original " + Arrays.toString(a));
System.out.println("ReOrdered " + Arrays.toString(b));
}
import java.util.Arrays;
public class ElementPairingFromSingleArray {
public static void main(String[] args) {
int[] arr = new int[] {1,2,3,4,5,11,22,33,44,55} ;
System.out.println(Arrays.toString(arr));
int size = arr.length/2;
int k = 1;
for(int i = 1; i < arr.length -1; i = i + 2) {
while(size != i) {
arr[size] = arr[size] + arr[size - 1];
arr[size - 1] = arr[size] - arr[size -1];
arr[size] = arr[size] - arr[size - 1];
size--;
System.out.println(Arrays.toString(arr));
}
size = arr.length/ 2 + k;
k++;
System.out.println("-------------------------------------");
}
}
}
public class ElementPairingFromSingleArray {
public static void main(String[] args) {
int[] arr = new int[] {1,2,3,4,5,11,22,33,44,55} ;
System.out.println(Arrays.toString(arr));
int size = arr.length/2;
int k = 1;
for(int i = 1; i < arr.length -1; i = i + 2) {
while(size != i) {
arr[size] = arr[size] + arr[size - 1];
arr[size - 1] = arr[size] - arr[size -1];
arr[size] = arr[size] - arr[size - 1];
size--;
System.out.println(Arrays.toString(arr));
}
size = arr.length/ 2 + k;
k++;
System.out.println("-------------------------------------");
}
}
}
O/P
[1, 2, 3, 4, 11, 5, 22, 33, 44, 55]
[1, 2, 3, 11, 4, 5, 22, 33, 44, 55]
[1, 2, 11, 3, 4, 5, 22, 33, 44, 55]
[1, 11, 2, 3, 4, 5, 22, 33, 44, 55]
-------------------------------------
[1, 11, 2, 3, 4, 22, 5, 33, 44, 55]
[1, 11, 2, 3, 22, 4, 5, 33, 44, 55]
[1, 11, 2, 22, 3, 4, 5, 33, 44, 55]
-------------------------------------
[1, 11, 2, 22, 3, 4, 33, 5, 44, 55]
[1, 11, 2, 22, 3, 33, 4, 5, 44, 55]
-------------------------------------
[1, 11, 2, 22, 3, 33, 4, 44, 5, 55]
-------------------------------------
I'll admit I couldn't figure this out on my own and had to look it up.
This is what I found:
Algorithm:
First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.
Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4
I'm not really sure, conceptually how it works, so if someone has some insight on that, that would be great. Nevertheless, here is some code implementation of it:
- SK March 21, 2015