## Adobe Interview Question

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

Just keep what the current number is modulo 5, and apply with each element:
numMod5 = (numMod5*2 + bitThatJustCameIn) % 5

Comment hidden because of low score. Click to expand.
0

correct!

Comment hidden because of low score. Click to expand.
0

it should be
num Mod 5 = (numMod5*10+bit just came in) % 5

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
3
of 5 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

HOW??

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

``````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.``````

Comment hidden because of low score. Click to expand.
0

Looks like your program assumes that data is coming from left to right i.e. Most significant bit to least significant bit... then this is correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````i=0;weight=1;
while(new bits are coming)
{
i=(weight*bit + i)%5;
weight<<=1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

automata solution is always better in modulo problems....as itz kind of parsing.... shondik nice solution

Comment hidden because of low score. Click to expand.
0

Why is it always better? The non-automaton solution is one line of code.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

How can you say the automaton solution is better? What if they asked you to calculate the remainder when dividing by 99? Then would you list down all possible states?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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..

Comment hidden because of low score. Click to expand.
0

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!!

Comment hidden because of low score. Click to expand.
0

Ah, I understand now, you're assuming base 10. I think most other posters here, myself included, were assuming base 2. There's nothing wrong with your solution if the number's base 10. The fact that it's 0s and 1s made most people think it's binary.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.