Amazon Interview Question Software Engineer / Developers
Country: -
Interview Type: Phone Interview
dude.... the question is not just to print the values, the question is about getting the modified array (transposed matrix in your case) in place. Now I must blame you for not reading the question :P
nope this is a brilliant idea ! you just needed to develop it further.
your logic is correct: what we need is to transpose an M x 3 matrix stored in a row-major manner using in-place algorithm.
The main difficulty is that in-place algorithm generates
loops during permutations..
Discussions be found here: en.wikipedia.org/wiki/In-place_matrix_transposition
Simply use Quick Sort on indices, with modified definitions for less than. This will do in O(nlgn) time
//repSize=n
bool isLessThan(int p,int q, int repSize){
p1 = normalize(p, repSize);
q1 = normalize(q, repSize);
//1,n+1,2n+1 will be equal after normalization
if(p1 == q1)
return p<q;
return p<q;
}
int normalize(int num, int n){
if(num < n)
return num;
if(num < 2n)
return num-n;
return num-2n;
}
Please note that except a1 and cN all the elements are in the wrong slot in the input array.
So consider the function GetCorrectIndex() that returns the correct index in which an element should be placed given its place in the input array.
int GetCorrectIndex( int i)
{
if ( i < N )
return 3 *i;
else if ( i < 2 *N )
return 3 *(i-N) + 1;
else
return 3 *( i - 2 *N ) + 2;
}
Now the algorithm consists of starting a2 and trying to place it in it correct slot. Then we place the element where a2 is supposed to be in its correct slot and so forth...
int j = 1;
int element = input[j];
int m = 3 * N - 1;
while ( --m > 0 )
{
int correctIndex = GetCorrectIndex( j );
int newelement = input[ correctIndex ];
input[ correctIndex ] = element;
element = newelement;
j = correctIndex;
}
Every element has only one correct slot and every iteration of the loop places one element in its correct slot so after 3 * N - 2 iterations all the elements will be placed in their respective places
Does not work for N = 3: it puts a2 in its correct spot (the spot where b1 is now), then puts b1 in its correct spot (where a2 was now), then it goes into a loop switching these elements.
<pre lang="" line="1" title="CodeMonkey77804" class="run-this">#include<stdio.h>
#include<iostream.h>
int n;
int i;
int r;
void transfer(int a[],int temp,int j)
{
cout<<j<<"\n";
int k=j/n;
if(j%n==0)
k=k-1;
int temp1;
temp1=a[j];
a[j]=temp;
if(j!=i)
{
j=((j-n*k)-1)*r+k+1; //its the location where it should be.
transfer(a,temp1,j) ;
}
}
void shift(int a[],int n,int k)
{
int j,temp;
for(i=2;i<=n-1;i++)
{
j=(i-1)*k+1;
temp=a[i];
transfer(a,temp,j);
}
}
void main()
{
int a[20];
n=4,r=3; //r =total length /n as in a1,b1,c1, r=3
for(i=1;i<=12;i++)
cin>>a[i];
shift(a,n,3);
for(i=1;i<=12;i++)
cout<<a[i];
}</pre><pre title="CodeMonkey77804" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey79446" class="run-this">/** The easiest solution in JAVA. */
char[] mergeStrings(char[] a, char[] b, char[] c) {
if ((a.length != b.length) || (a.length != c.length)) return null;
char[] res = new char(3 * a.length);
int k = 0;
for(int i =0; i < a.length; i++) {
res[k++] = a[i];
res[k++] = b[i];
res[k++] = c[i];
}
return res;
}
</pre><pre title="CodeMonkey79446" input="yes">
</pre>
/** Modification of solution JAVA. */
char[] mergeStrings(char[] s) {
if (s % 3 != 0) return null;
int n = s / 3;
char[] res = new char(s.length);
int k = 0;
for(int i =0; i < n; i++) {
res[k++] = s[i];
res[k++] = s[i + 1 + n];
res[k++] = s[i + 1 + 2*n];
}
return res;
}
I am posting a modified version of tck's solution which is more clear in terms of N and Length of the array. This solution works basically on the principle that all the elements except first and last are out of place. so we run a loop for len - 2 times, shifting each element to its correct position one at a time. There cannot be overlaps because each element can only go to its position and so the currentelement is always in a new position that we haven't encountered.
int GetIndex(int i, int len) {
int n = len / 3;
if (i < n)
return i * 3;
else if (i < 2 * n)
return (i - n) * 3 + 1;
else
return (i - (2 * n)) * 3 + 2;
}
void Sort (int[] a, int len) {
int m = len - 2, i = 1, currentelement = a[i];
while (m--) {
int correctposition = GetIndex(i, len);
int temp = a[correctposition];
a[correctposition] = currentelement;
currentelement = temp;
i = correctposition;
}
}
Here is a solution in C# that moves from left-to-right rotating
sub-arrays. It can also handle alphabets larger than {'a,'b','c'}.
This is the program output:
Starting array
a1,a2,a3,b1,b2,b3,c1,c2,c3
Re-arranged array
a1,b1,c1,a2,b2,c2,a3,b3,c3
Starting array
a1,a2,a3,b1,b2,b3,c1,c2,c3,d1,d2,d3,e1,e2,e3
Re-arranged array
a1,b1,c1,d1,e1,a2,b2,c2,d2,e2,a3,b3,c3,d3,e3
Starting array
a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4
Re-arranged array
a1,b1,c1,d1,a2,b2,c2,d2,a3,b3,c3,d3,a4,b4,c4,d4
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CareerCup
{
class Program
{
static void Reverse<T>(IList<T> items, int start, int end)
{
while (start < end)
{
T tmp = items[start];
items[start] = items[end];
items[end] = tmp;
start++;
end--;
}
}
static void RotateLeft<T>(IList<T> items, int start, int moves)
{
Reverse(items, start, start + moves - 1);
Reverse(items, moves + start, items.Count - 1);
Reverse(items, start, items.Count - 1);
}
static void RearrangeArray<T>(IList<T> items, int m)
{
int n = items.Count / m;
for (int i = n - 1, j = 1; i > 0; i--)
for (int k = 0; k < m; j++, k++)
RotateLeft(items, j, i);
}
static List<String> CreateArray(int n, int m)
{
List<String> strs = new List<string>();
for (int i = 0; i < m; i++)
{
char c = 'a';
for (int j = 0; j < n; j++)
strs.Add(string.Format("{0}{1}", (char)(c + i), j + 1));
}
return strs;
}
static void PrintArray<T>(IList<T> strs)
{
Console.WriteLine(String.Join(",", strs));
}
static void InPlaceRearrange(int m, int n)
{
var items = CreateArray(n, m);
Console.WriteLine("Starting array");
PrintArray(items);
RearrangeArray(items, m);
Console.WriteLine("Re-arranged array");
PrintArray(items);
}
static void Main(string[] args)
{
InPlaceRearrange(3, 3);
InPlaceRearrange(5, 3);
InPlaceRearrange(4, 4);
}
}
}
Here is a solution in C# that moves from left-to-right rotating
sub-arrays. It can also handle alphabets larger than {'a,'b','c'}.
This is the program output:
Starting array
a1,a2,a3,b1,b2,b3,c1,c2,c3
Re-arranged array
a1,b1,c1,a2,b2,c2,a3,b3,c3
Starting array
a1,a2,a3,b1,b2,b3,c1,c2,c3,d1,d2,d3,e1,e2,e3
Re-arranged array
a1,b1,c1,d1,e1,a2,b2,c2,d2,e2,a3,b3,c3,d3,e3
Starting array
a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4,d1,d2,d3,d4
Re-arranged array
a1,b1,c1,d1,a2,b2,c2,d2,a3,b3,c3,d3,a4,b4,c4,d4
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CareerCup
{
class Program
{
static void Reverse<T>(IList<T> items, int start, int end)
{
while (start < end)
{
T tmp = items[start];
items[start] = items[end];
items[end] = tmp;
start++;
end--;
}
}
static void RotateLeft<T>(IList<T> items, int start, int moves)
{
Reverse(items, start, start + moves - 1);
Reverse(items, moves + start, items.Count - 1);
Reverse(items, start, items.Count - 1);
}
static void RearrangeArray<T>(IList<T> items, int m)
{
int n = items.Count / m;
for (int i = n - 1, j = 1; i > 0; i--)
for (int k = 0; k < m; j++, k++)
RotateLeft(items, j, i);
}
static List<String> CreateArray(int n, int m)
{
List<String> strs = new List<string>();
for (int i = 0; i < m; i++)
{
char c = 'a';
for (int j = 0; j < n; j++)
strs.Add(string.Format("{0}{1}", (char)(c + i), j + 1));
}
return strs;
}
static void PrintArray<T>(IList<T> strs)
{
Console.WriteLine(String.Join(",", strs));
}
static void InPlaceRearrange(int m, int n)
{
var items = CreateArray(n, m);
Console.WriteLine("Starting array");
PrintArray(items);
RearrangeArray(items, m);
Console.WriteLine("Re-arranged array");
PrintArray(items);
}
static void Main(string[] args)
{
InPlaceRearrange(3, 3);
InPlaceRearrange(5, 3);
InPlaceRearrange(4, 4);
}
}
}
Here is the solution .. basic idea is left shifting the elements.
void reArrange(vector<int>& arr, int k)
{
// k is no of unique chars
// for a1,a2,a3,b1,b2,b3,c1,c2,c3 -- k = 3 (for a,b,c)
int totalSize = arr.size();
//subset size
int subSetSize = arr.size()/k;
//we have to shift (subSetSize - 1) elements by nTimes
int nTimes = k-1;
//start index from where we have to start left shift
int start = 1;
//end element where we have to place shifted left element
int end = arr.size()-2;
//now start shifting element by shiftLeftByElements at a time for nTimes
//e.g. shiftLeftByElements == 2 nTimes == 2 , start= 1, end = 7
// then for a1,a2,a3,b1,b2,b3,c1,c2,c3
// for first iteration of outerloop, it will be a1, b1,c1,c2,a2,a3,b2,b3, c3
for(int shiftLeftByElements = subSetSize - 1; shiftLeftByElements >0 ; --shiftLeftByElements)
{
for(int i = 1; i<=nTimes; i++)
{
rotateLeft(arr, start, end, shiftLeftByElements);
start++;
}
end--;
}
}
void rotateLeft(vector<int>& arr, int start, int end, int shiftLeftByElements)
{
while(shiftLeftByElements != 0 && start < end)
{
int val = arr[start];
while(start != end)
{
arr[start] = arr[start + 1];
start++;
}
arr[start] = val;
shiftLeftByElements--;
}
}
void arraySort(String[] a)
{
a = doInplaceSort(a, 0, a.Length);
for (int i = 0; i < a.Length; i++)
{
Console.Write(a[i]);
}
}
String[] doInplaceSort(String[] a, int start, int end)
{
if ((end - start) == 3)
{
return a;
}
else
{
int n = (end - start) / 3;
int i = start + 1;
int cIndex = i + (2 * n - 1);
String tempC = a[cIndex];
for (int j = cIndex; j >= (i + n); j--)
{
a[j] = a[j - 1];
}
int bIndex = i + (n - 1);
String tempB = a[bIndex];
for (int k = bIndex + 1; k > i; k--)
{
a[k] = a[k - 2];
}
a[i] = tempB;
a[i + 1] = tempC;
i = i + 2;
doInplaceSort(a, i, a.Length);
}
return a;
}
The following algorithm is O(nLogn). I don't think there's a linear algorithm.
int a[100];
void Swap(int * x, int * y) {
int z = *x;
*x = *y;
*y = z;
}
void Swap(int p, int q, int m) {
for (int i=0; i<m; i++) {
Swap(&a[p+i], &a[q+i]);
}
}
void Work(int p, int n) {
//a[p]...a[p+3*n-1]
if (n == 1) return;
int m = n/2;
Swap(p+n+m, p+2*n, m);
Swap(p+m, p+n, m);
Swap(p+n, p+n+m, m);
if (n % 2 == 1) {
int x = a[p+n-1];
int y = a[p+2*n-1];
int q = p+n-1;
for (int i=n; i<=2*n-2; i++) a[q++] = a[p+i];
for (int i=2*n; i<=3*n-2; i++) a[q++] = a[p+i];
a[p+3*n-3] = x;
a[p+3*n-2] = y;
Work(p, m);
Work(p+n+m-1, m);
} else {
Work(p, m);
Work(p+n+m, m);
}
}
int main() {
int n = 9;
for (int i=0; i<n*3; i++) a[i] = i;
Work(0, n);
for (int i=0; i<n*3; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
I'll try to build upon Ram's idea since its execution will be linear.
1. As the first element is in correct place a1, we'll start from 2nd element.
2. Using the function GetCorrectIndex(i, len), we'll find the correct index of a2 which is 3
3. Before replacing the existing value, we'll capture the index and Element as PrevIndex and PrevElement.
4. Push a2 to the CorrectIndex in the array.
5. Repeat Process 1-4, Counter of the Loop to be incremented till the function has replaced Length - 1 replacements.
Or you can break when PrevIndex and CorrectIndex match. This will only happen when all the elements are in correct places.
the idea is good but you have to do few other things
for eg consider
a1a2a3b1b2b3c1c2c3
now a2 correct place is b1's and vice versa
similarly a3 correct place is c1's and vice versa
so there can be at most three such cases
a set and b set case
eq are 3*index(a) = index(b) ......(1)
3*(index(b) - N) = index(a) .....(2)
and similar equation for (a set and c set )(b set and c set)
so you have to solve them explicitly and then run the loop
with value that does not belong to these solutions and
the first and last are already at correct places and if n is odd then b(n+1)/2 is also at correct place so run the counter keeping these into account
<pre lang="" line="1" title="CodeMonkey19173" class="run-this">
public class test {
public static void ReplaceFun(){
//ArrayList test=new ArrayList();
String[] testArray=new String[]{"a1","a2","a3","b1","b2","b3","c1","c2","c3"};
int k=0;
String temp="";
for(int i=1;i<=testArray.length/3;i++){
for(int j=0;j<testArray.length;j++){
if(Integer.parseInt(testArray[j].substring(1))==i){
temp=testArray[k];
testArray[k]=testArray[j];
testArray[j]=temp;
k++;
}
}
}
for(int m=0;m<testArray.length;m++){
System.out.println(testArray[m]);}
}
public static void main(String[] args) {
ReplaceFun();
}
</pre><pre title="CodeMonkey19173" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey2273" class="run-this">
public class test {
public static void ReplaceFun(){
//ArrayList test=new ArrayList();
String[] testArray=new String[]{"a1","a2","a3","b1","b2","b3","c1","c2","c3"};
int k=0;
String temp="";
for(int i=1;i<=testArray.length/3;i++){
for(int j=0;j<testArray.length;j++){
if(Integer.parseInt(testArray[j].substring(1))==i){
temp=testArray[k];
testArray[k]=testArray[j];
testArray[j]=temp;
k++;
}
}
}
for(int m=0;m<testArray.length;m++){
System.out.println(testArray[m]);}
}
public static void main(String[] args) {
ReplaceFun();
}
</pre><pre title="CodeMonkey2273" input="yes">
</pre>
I view this question as a matrix transpose -- swap row and column. The first array looks like 3xN matrix where column is 'a', 'b', and 'c'. The result matrix is to swap between row and column. It is tempting to write a wrap up code to transfer index i in the first matrix to its transposed version. Doing this you still have O(1) data access without the need to swap an array O(N). Nah don't blame me that I didn't read the question. Just to propose something different and believe it or not, it's only 3 lines.
- Anonymous October 13, 2011public static void transpose(int index){ String array1[] = {"a1","b1","c1","a2","b2","c2","a3","b3","c3"}; /** * @observation: This look like an Nx3 matrix and given index i. * a) i % 3 == 0 a[i] is 'a' -- 1st column and i / 3 is row# * b) i % 3 == 1 a[i] is 'b' -- 2nd column and i / 3 is row# * c) i % 3 == 2 a[i] is 'c' -- 3rd column and i / 3 is row# * * So it is tempting to write a wrap up function which take * int index and return the correct position. */ int row = index % 3; int col = index / 3; System.out.println(array1[3*row+col]); }//end transpose