Amazon Interview Question
Software Engineer / DevelopersIt does not look like we need to move pointers its an array random access is possible. It seems all one has to do is either sift elements by one position either towards left or right depending upon the vacant space (i.e. upon encountering the occupied middle one needs to look for the first empty slot in both directions and sift the elements accordingly). Correct me if i am wrong.
#include<stdio.h>
void insert_at(int* arr, int size, int inx, int* obj)
{
if ( size <= inx )
return;
int i = 0;
for ( i = size - 1; i > inx; i--)
{
arr[i] = arr[i-1];
}
arr[i] = *obj;
}
int main()
{
int arr[10] = {0,1,2,3,4,5};
int obj = 55;
insert_at(arr, 10, 8, &obj);
int i = 0;
for ( i = 0 ; i < 10; i++ )
{
printf("%3d ",arr[i]);
}
printf("\n");
}
Problem:
================
How would you add an element in the middle of the array...
Example:
================
A[123567]
N= 4
ALGO:
================
1. Run two pointers when Increment second pointer twice and when second reaches the end then 1st reached middle
Insert the element and rearrange the rest of array
2. Get size of array
take size/2
check if odd or even
insert an element and rearragen the array
CODE:
================
public InsertMiddle(Array A[], int N)
{
For (i=0,J=0 ; A[i]<0 ; i++) \\USED A[I]<0 FOR OUT OF ARRAY ADDRESS
{
IF(A[J]<0)
{
iNSERT(I,N)
}
J += 2
}
INSERT(INT I,INT N)
{
FOR(;A[I]<0;I++)
{
TEMP=A[I+1]
A[I+1]=N
A[I+2]=TEMP
}
}
}
ORDER:
================
O(N^2)
create a new array and insert the one in the middle if no space left in the original array
- Anonymous March 06, 2010