Circular shift an array:
It is a common interview questions that is asked during phone screen or onsite technical interviews. It requires basic understanding of the arrays and its widely popular data structures used for technical interviews. I myself have encountered a lot of questions on arrays so its always good to have a good grasp on basic operations of arrays.
In this the interviewing is looking for your analytical capability and how well you can think through a problem. Below mentioned is the detailed step by step algorithm. In a nutshell it request a storage array to keep the arrays elements that are shifted across.
Algorithm :
Step 1: Declare and initialize the required arrays and variables with given values.
Array a[5] (Input array),
0 1 2 3 4
Array b[5] to store results (Output array),
0 1 2 3 4
location = 2 k = 0 total = 5
Step 2: Using for loop print the original array ‘a’ to the console.
total = 5
Iteration 1:
i=0 and 0<5 -> condition true
0 1 2 3 4
a[0] = 1
Print : 1
i = 1 (incremented by one)
Iteration 2:
i=1 and 1<5 -> condition true
0 1 2 3 4
a[1] = 2
Print : 2
i = 2 (incremented by one)
Iteration 3:
i=2 and 2<5 -> condition true
0 1 2 3 4
a[2] = 3
Print : 3
i = 3 (incremented by one)
Iteration 4:
i=3 and 3<5 -> condition true
0 1 2 3 4
a[3] = 4
Print : 4
i = 4 (incremented by one)
Iteration 5:
i=4 and 4<5 -> condition true
0 1 2 3 4
a[4] = 5
Print : 5
i = 5 (incremented by one)
Iteration 6:
i=5 and 5<5 -> condition false.
Terminate the loop.
Final output of this loop :
Input array : 1 2 3 4 5
Step 3: Using for loop shift the array ‘a’ from the given index 3 till the end to the resultant array ‘b’.
Location = 2 total = 5 k = 0
Initially, i = 5 - 2 (i = total - location)
I = 3
Iteration 1:
i = 3 and 3 < 5 ->condition true
b[0] = a[3] here a[3] = 4
0 1 2 3 4
k = 1 (incremented by 1)
i = 4 (incremented by 1)
Iteration 2:
i = 4 and 4 < 5 ->condition true
b[1] = a[4] here a[4] = 5
0 1 2 3 4
k = 2 (incremented by 1)
i = 5 (incremented by 1)
Iteration 3:
i = 5 and 5 < 5 ->condition false
Terminate the loop.
Step 4: Using for loop shift the array from the index 0 till the given index value 2.
total - location = 5 - 2 => 3
Iteration 1:
k = 2, i = 0 and 0 < 3 -> Condition true
b[2] = a[0] here a[0] = 1
0 1 2 3 4
k = 3 (incremented by 1)
i = 1 (incremented by 1)
Iteration 2:
k = 3, i = 1 and 1 < 3 -> Condition true
b[3] = a[1] here a[1] = 2
0 1 2 3 4
k = 4 (incremented by 1)
i = 2 (incremented by 1)
Iteration 3:
K = 4, i = 2 and 2 < 3 -> condition true.
b[4] = a[2] here a[2] = 3
0 1 2 3 4
k = 5 (incremented by 1)
i = 3 (incremented by 1)
Iteration 4:
K = 5, i = 3 and 3 < 3 -> condition false.
Terminate the loop.
Step 6: Using for loop printing the resultant array to the console.
total = 5
Iteration 1:
i=0 and 0 < 5 -> condition true
0 1 2 3 4
b[0] = 4
Print : 4
i = 1 (incremented by one)
Iteration 2:
i=1 and 1<5 -> condition true
0 1 2 3 4
b[1] = 5
Print : 5
i = 2 (incremented by one)
Iteration 3:
i=2 and 2<5 -> condition true
0 1 2 3 4
b[2] = 1
Print : 1
i = 3 (incremented by one)
Iteration 4:
i=3 and 3<5 -> condition true
0 1 2 3 4
b[3] = 2
Print : 2
i = 4 (incremented by one)
Iteration 5:
i=4 and 4<5 -> condition true
0 1 2 3 4
b[4] = 3
Print : 3
i = 5 (incremented by one)
Iteration 6:
i=5 and 5<5 -> condition false.
Terminate the loop.
Final output of this loop : Shifted array : 4 5 1 2 3
Implementation:
#include <iostream>
int main()
{
int b[5],a[5] = {1,2,3,4,5};
int location = 2,k=0;
int total = 5;
//Printing original array
std::cout<<"Input array : ";
for(int i=0;i<total;i++)
std::cout<<a[i]<<"\t";
//Starting with shifting the array from location=2+1 till end
for(int i=(total-location);i<total;i++)
b[k++] = a[i];
std::cout<<"\n"; //newline
//Starting from location=2 till the condition fails
for(int i=0;itotal-location;i++)
b[k++] = a[i];
std::cout<<"Shifted array : ";
for(int i=0;i<total;i++)
std::cout<<b[i]<<"\t";
std::cin>>k;
return 0;
}
Dry run of sample output:
Input array : 1 2 3 4 5
Shifted array : 4 5 1 2 3
Algorithm Complexity :
O(n)
Space complexity:
O(n)
No comments:
Post a Comment