Interview Question for Software Developers
- 0of 0 votes
Suppose two arrays are given A and B. A consists of integers and the second one consists of 0 and 1.- AN October 11, 2019 in India
Now a operation is given - You can choose any adjacent bits in array B and you can toggle these two bits ( for example - 00->11, 01->10, 10->01, 11->00) and you can perform this operation any number of times.
The output should be the sum of A*B+A*B+....+A[N-1]*B[N-1] such that the sum is maximum
During the interview, my approach to this problem was to get the maximum number of 1's in array B in order to maximize the sum.
So to do that , I first calculated the total number of 1's in O(n) time in B. Let count = No. Of 1's=x
Then I started traversing the array and toggle only if count becomes greater than x or based on the elements of array A(for example : Let B[i]=0 and B[i+1]=1 & A[i]=51 and A[i+1]=50
So I will toggle B[i] B[i+1] because A[i]>A[i+1])
But the interviewer was not quite satisfied with my approach and was asking me further to develop a less time complex algorithm.
Can anyone suggest a better approach with lesser time complexity??
| Report Duplicate | Flag | PURGE
Software Developer Algorithm
Interview Type: In-Person
Open Chat in New Window