Questions d'entretien

Entretien de Senior Software Engineer

-Vancouver, BC

Amazon

Write a function that divides one number by another, without using the division operator, and make it better than O(n).

Répondre

Réponses aux questions d'entretien

7 réponse(s)

6

Use logarithms? O(1) log(x/y) = log(x) - log(y) = log(answer) answer = 10 ^ log(answer)

J Story le

2

why not just a * b^(-1) :-)

Utilisateur anonyme le

2

This can be done in a recursive function, the following code is in Python. # get result of a/b without using a "divide" operator def div(a,b): if a < b: return 0 else: return div(a-b, b)+1 This is how human being do the division naturally, however, the running time of this is O(n/m), where n is the size of a, and m is the size of b, which means, O(n/m) is guaranteed to be less than O(n), when m is larger than 1. -Maxim

Maxim Mai le

1

Convert the number to divide into the base of the number that you are dividing with and then shift the 'bits' to the right by 1 then convert back to decimal

Utilisateur anonyme le

0

Totally agree with Vasil. Other option: Long Division Algorithm. O(log n) anyway.

Utilisateur anonyme le

0

// Write a function that divides one number by another, without using the division operator, // Assume that x%y = 0 // O(log n) (function() { 'use strict'; var divide = function(x, y) { var xLength = (x + '').length; var i = 0; var result = 0; var xAry = ('' + x).split(); var xStart = ''; for (i = 1; i = y) { xStart -= y; result = parseInt(result, 10) + 1; } } } return result; }; console.log(divide(1000, 4)); })();

Leo le

2

The answer above is still O(n). We can use binary search and find the answer in the interval [1,a] and use multiplication operator.

Vasil Vasilev le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.