James Liu
BAN USER- 0of 0 votes
Answersint a,i;
- James Liu in United States
(i++)=a;
(++i)=a;
which statement is correct? --explain the reason in the view of compiler.
note: it's not related to initialization or not. say i=2, a=5. I think it is a nice question to test the interviewee's knowledge of compiler.| Report Duplicate | Flag | PURGE
Intel Software Engineer / Developer Compiler
// My idea is based on regular permutation implementation, and it is easy to understand. By iteratively swap 0 with others element in the array, we can get desired permutation(target). Also, swapping two non-zero values require some trick.
say src={1,0,2,3}, dest={3,2,0,1}
By swapping forward, we get: {1}+0+perb(2,3),{1,2}+perb(0,3), {1,3}+perb(2,0);
by swapping backward, we get: 0+perb(1,2,3)
src={...., 0, ...}, the first part contains i elements before 0 and the second part contains j elements after 0, and i+1+j=n
//swap forward and permutation
for(int k=i+1;k<n;k++){ // 0 is at the pos of i+1
swap(0,src[k]);
int first[]=src[0...k-1];
int second[]=perb(src,k+1,n,k);
int result[]=first+second;
}
//swap backward
...
// note we are unable to do swap(a[i],a[j]) directly, and use swap_ex to replace swap
void swap_ex(int a[], int i, int j, int h){// h is the position of 0
swap(&a[i],&a[h]);
swap(&a[h],a[j])
}
void perb(int src[], int k, int n, const int h){ // h is the pos of 0
{
if (k==n){
// we have a chance here to find if src matches target
return;
}
else{
for(int j=k;j<n;j++){
swap_ex(src[k],src[k+1],h);
perb(src,k+1,n);
swap_ex(src[k],src[k+1],h);
}
}
}
Time and space complexity is ok(if the input is a huge string, it might be a problem!)
I felt confused about swap with 0. Does it mean swap(&a[i], &[j]) when a[i] or a[j] has value 0?
- James Liu September 15, 2013