Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.

Question

Pale · Accepted Answer

Besides the returning format, and according the algorithm above, I would write in C the following function:

void div(int N, int D) {
	int Q = 0;
	int x = N;
	int it = 1;
	while (x >= D) {
		if ( x < (D << it) ) {
			x -= (D << (it-1));
			Q += (1 << (it-1));
			it = 0;
		}
		it++;
	}
	cout << "Quotient: " << Q << " Remainder: " << x << endl;
}

Anonym · Answer

1. multiply 3 with 2 until it gets bigger than 29: 6,12,24,48
2. Go back one: 24 =>8
3. Sub that out: 39-24 = 15
1. multiply 3 with 2 until it gets bigger than 15: 6,12,24
2. Go back one: 12 =>4
3. Sub that out: 15-12 = 3
1. multiply 3 with 2 until it gets bigger than 3: 6
2. Go back one: 3=>1
3. Sub that out: 3-3 = 0
Answer: 8+4+1 = 13

Beau · Answer

I think you're very close, but perhaps the interviewer was suggesting to think of the quotient in terms of being a binary number.
        
        // QuickDivide, implemented in Java
	public static String QuickDivide(int num, int denom)
	{
		int quotBits = 1;  // start with a single bit quotient
		int quot = 0;
		
		// get number of quotient bits
		while (Math.pow(2,quotBits) * denom = 0; bitExp--)
		{
			if (num >= Math.pow(2, bitExp)* denom)
			{
				// add to quotient and subtract from numerator
				quot += Math.pow(2,bitExp);
				num -= Math.pow(2, bitExp) * denom;
			}
		}
		
		// numerator is holding remainder
		return String.format("%1$d R %2$d", quot, num);
	}

mike · Answer

despite these comments, I would do a binary search on the quotient. the upper bound is the dividend

Sigiloso · Answer

Answer 1: Use subtraction and keep a count of how many times subtracted. When the remainder is smaller than the divisor, count is your answer, and whatever is left is the remainder.

Was then asked the complexity in terms of binary. After that, was asked to come up with a solution with better complexity.

Answer 2: Multiply the divisor by two until it is larger than the dividend. Go back one, subtract that out, multiply again. This solution will have a much better complexity.

NehaGupta · Answer

I could not get second solution. Though its really interesting ....
 e.g. 39/3 
1. multiply 3 with 2 until it gets bigger 3->6->12->24->48 (using 8
3. Sub that out 39-24 = 14
4. Go to 1

MrB · Answer

public class Division
{
   public static void main(String[] args)
   {
   	int num = 23, denom = 7;
   	
   	System.out.println(Divide(num, denom));
   }
	
	public static String Divide(int num, int denom)
   {
       int quotBits = 1; // start with a single bit quotient
       int quot = 0;

       // get number of quotient bits
       while ((denom = 0; bitExp--)
       {
           if (num >= (denom<

pit kelev · Answer

// gets leftmost bit position
    public native static int __builtin_clz(int n);

    /**
     * Divide x by y. 
     * @return {result, reminder}
     */
    public static int[] div(int x, int y) {
        int py = __builtin_clz(y);
        int res = 0;

        while(x > 0) {
            int px = __builtin_clz(x) - py;
            x -= y << px;
            if (x < 0) {
                x += y;
                px--;
            }
            res += 1 << px;
        }
        return new int[] {res, x};
    }

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas