Grokking LinkedIn Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 years ago

I just wanted to suggest a more subtle way of explaining it that may be a bit better. So, binary search is applied here because we are searching for a value in a specific range of values, which is a range of sorted numbers. That value we are looking for is the largest value n such that n * n <= x. So, we can use a variable to store the result, and if we ever find a value whose square is <= x, update the result to that. However, since our goal is to find the largest, toss that pivot out and set left = mid + 1. If the square is too large, then we want to lower our right bound and set right = mid - 1.

class Solution {
  public int mySqrt(int x) {
    int left = 0;
    int right = x;
    int res = 0;

    while(left <= right){
      int mid = left + (right - left) / 2;

      if((long
R

Roberto Pantoja

· 3 years ago

I came up with the following solution.

class Solution {
public:
  int mySqrt(int x) {
    int i = 0;

    while(i * i <= x){i++;}

    // TODO: Write your code here
    return i - 1;
  }
};

Basically, just increment i until you pass the square root, then return previous value.

Am I missing something? Why is the more complex solution the example?

Show 8 replies
Vishnu S Nair

Vishnu S Nair

· a year ago

For any integer x, the square root of x will lie between 0 and x/2 (inclusive) for x > 2.

The upper bound rule does not always hold for small values of x, particularly for x = 3.

Show 1 reply
Jlsegb

Jlsegb

· 6 months ago

You can ask an LLM to explain it. But this is a neat way of calculating a root. Probably better to use the binary tree solution but this one performs better O(log log n)

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;

        int r = x;
        while (r > x / r) {   // instead of r*r > x
            r = (r + x / r) / 2; // this is Newton's method.
        }
        return (int)r; // floor(sqrt(x))
    }
};

Note that we should avoid a possible integer overflow from r*r by re-arranging the equality or using a bigger container.

Manuel

Manuel

· 2 years ago

As you first stated sqrt (x) is in the range 0 - x/2

Then, why are you doing this verification if (num > x) instead of if (num > x/2) ?

Thanks

Show 1 reply
V

vladyslav.chikov

· 8 months ago

There is a solution which in terms of big-O notation is not that good as binary search, but good enough for the most of modern numbers.

The first instinct you want to go is:

class Solution:
  def mySqrt(self, x: int) -> int:
    i = 0
    step = 1
    while (i+1) * (i+1) <= x:
      i += 1
    return i

This algo is O(X^{1/2}) which is not bad and will work on any modern CPU all the way till 10^14-10^16

But you quickly realise that if your input is, say, 10**16, and you do i = 1, then likely do i=2,3,4,5 is pretty useless.

Instead we can do an incremental jump size too to increase the growth. Once we cross the bar, we slow down the growth until it stops:

class Solution:
  def mySqrt(self, x: int) -> int:
    i = 0
    step = 1
    while (i+step) * (i+step) <=