Adobe Interview Question
Country: India
Interview Type: In-Person
This is a better solution than the "automaton" solution because you can easily change this for any number. If the question was to calculate remainder when dividing by 99, and you wanted to solve using the automaton solution, you would have to list all possible states.
@Anonymous: if you interpret the number as being base 10, yes. Since it's 0s and 1s I would think we're talking about a binary representation.
@Bonzo: yes, it's a lot more general. I don't want to diss the automaton solution too much, though, since it's a useful optimization idea to keep on the backburner for this specific situation should you find yourself needing to optimize. It might or might not actually improve performance.
@eugene I don't understand why people are saying that the automaton solution is optimized either. Can you really say that a couple of arithmetic operations are slower than branch (if-else) statements? Or the other way round?
If-statements can be slow, but modulo is a particularly slow arithmetic operation. Actually, now that I think about it, if I really had to optimize, I'd try this and measure to see if it's faster (I think it should be on most systems):
const int MODULUS = 5;
value = 2*value + new_bit;
if (value >= MODULUS)
{
value -= MODULUS;
}
Still general and maintainable, though now we're more tied to the fact that the representation is base 2 than before.
The if-statement could be optimized away with some bit tricks too.
Use a finite automata [DFA] & keep changing the states. At the end of the stream, if final state is reached, it is a divisible by 5.
Here is the complete code.
#include <stdio.h>
int getState(int state,char bit)
{
if(state==0)
return bit==0?0:1;
else if(state==1)
return bit==0?2:3;
else if(state==2)
return bit==0?4:0;
else if(state==3)
return bit==0?1:2;
else if(state==4)
return bit==0?3:4;
}
int isDivisible(char *seq)
{
int state=0,i;
for(i=0;seq[i];++i)
{
state=getState(state,seq[i]);
}
return state==0?1:0;
}
int main()
{
char seq[20];
fgets(seq,20,stdin);
isDivisible(seq)?printf("Yes"):printf("No");
return 0;
}
It is better than the above approaches because it works on bits & we do not require any arithmetic(modulo & + to calculate the remainder)
let n bits be read so far and value corresponding to that be no..
now we get another bit say newbit...
new value of no will be no*2+newbit
we need to find mod 5 so (no*2+newbit)%5
(no%5*2+newbit)%5
what is the initial values of "no" value...
lets take no = 0 initially
ex: 01
for first bit - 0*2+1 = 1 -> correct
now no is 1
for second bit - 1*2+0 = 2 -> wrong ???
please correct me if I am wrong.
automata solution is always better in modulo problems....as itz kind of parsing.... shondik nice solution
@eugene, LOC doesn't matter at all.
You can also write a complex for loop in a single line which does the same work if it was written in a simpler version of 5 lines.
Better code means processor will take less clock cycles to execute the instructions.
Have you ever thought why bit-wise operations are assumed to be better?
Suppose we need to check whether a number is even or odd,Which of the two version would you prefer?
if(n%2==1)//for odd
or
if(n&1)//for odd
The same explanation also lies here.
Lines of code don't matter, but complexity matters. It's not all about writing the most efficient code. It's about achieving a certain tradeoff between complexity and efficiency.
It's one thing to develop a complex algorithm to achieve, say, NlogN performance on an interview problem where a simpler algorithm could only achieve N^2. The more efficient solution may be much more difficult, and may illustrate much more skill to an interviewer than a naive solution. Still, in practice, if I were implementing an algorithm at work let's say, I would think about whether the perf benefits are worth the increased code complexity. If N is always small, for instance, an N^2 algo may be sufficient.
Back to the problem at hand: the state machine solution is considerably less readable and maintainable, and also more complex and less elegant. It's basically a case by case enumeration of all the possibilities defined and explained by my one line of code. And, it's not a dramatic perf difference: the best you can hope for is to gain a small constant factor on a solution that's already quite efficient. My solution is unlikely to even be CPU-bound. Furthermore, a compiler might even optimize it some. Absent an obvious indication that the modulo operations are causing a perf bottleneck, the state machine is just premature optimization.
It's a good solution to know about, though, I'll agree on that, if you do end up needing trying to squeeze more performance out of the code. But at best it's a small constant factor.
if a number has 0 at unit place then the remainder is 0, if it has 1 at unit place the remainder is 1
so no need to store the full sequence just check whatever number comes in that, it will be at unit place so that number itself is a remainder..
Even i think this solution is correct. Since there are only 1's and 0's the remainder after dividing by 5 totally depends on the unit's place. So answer would what the unit's place is. If 1 then ans 1 . If 0 then ans 0.
Is there any mistake in my understanding? Please Comment!!
Just keep what the current number is modulo 5, and apply with each element:
- eugene.yarovoi June 25, 2012numMod5 = (numMod5*2 + bitThatJustCameIn) % 5