31 NVIDIA Java Developer Interview Questions & Answers

I would shuffle the array in place with the Fisher-Yates algorithm. I start at the last index and move left. At each step, I pick a random index j from 0 to i and swap a[i] with a[j]. That keeps the shuffle unbiased, because each remaining position has the same chance to be chosen. I process the array at most once. The time is O(n), and the extra space is O(1).

This problem asks you to rearrange the numbers in an array so the order looks random and fair. Fair means every possible ordering has the same chance. A good way to do that is to lock one position at a time from the end, choose one random element from the still-free part, and swap it into place. That keeps the shuffle unbiased because each remaining element is picked with equal probability before the next position is fixed. That is the Fisher-Yates shuffle.

1. Should I shuffle the array in place, or may I return a new array?
2. Do you want a normal random source, or a stronger one like SecureRandom?

The input is an integer array. The output is the same array in a random order. The goal is not to sort it. The goal is to create one fair permutation.

I use the Fisher-Yates shuffle. I walk from right to left. At index i, I pick a random j from 0 to i. Then I swap a[i] and a[j]. This is fair because each of the i + 1 choices is equally likely.

The diagram uses [1, 2, 3, 4, 5]. First, i = 4 and j = 1, so 5 swaps with 2 and the array becomes [1, 5, 3, 4, 2]. Then i = 3 and j = 3, so nothing changes. Next, i = 2 and j = 0, so 3 swaps with 1 and the array becomes [3, 5, 1, 4, 2]. Then i = 1 and j = 1, so nothing changes. One valid shuffled result is [3, 5, 1, 4, 2].

The Java code uses SecureRandom to pick the random index. The loop starts at the last index and stops at 1. Each step does one random pick and one swap. That matches the diagram exactly. The time is O(n). The extra space is O(1).

The key idea is to fill the array from right to left. At step i, every element in positions 0 through i is still free. I choose one of those elements uniformly at random and swap it into position i. After that swap, position i is final and will not change again. The central invariant is that the suffix to the right of i is already a uniformly random shuffle of the values it contains. Because each remaining choice is equally likely, the final array is unbiased.

We look at the array one position at a time from right to left. That means the array is processed at most once. Each step does one random pick and one swap, so the total time is O(n). We do not build another array. We only use a few extra variables, so the extra space is O(1).

A common mistake is picking j from the whole array every time. That makes the shuffle biased. Another mistake is forgetting that the random range must shrink as i moves left. Some candidates also create a second array when the goal is an in-place shuffle. Another easy mistake is thinking j can never equal i. It can, and that is part of the algorithm. Finally, people sometimes claim the result is only one specific order, but any permutation is valid.

Say the invariant out loud: the suffix on the right is already fixed and uniformly random. Then show how one swap extends that suffix by one more position.

I find the common numbers by first putting every value from array A into a HashSet, then scanning array B and adding only the values that are already in that set into a second set. This keeps each common number once, even if it appears many times. I process each array at most once. Because HashSet lookup and insert are O(1) on average, the total time is O(n + m) expected time, and the extra memory is O(n + min(n, m)).

This question asks me to compare two big lists of numbers and return the values that appear in both lists. I do not need the positions. I only need each common value once. The best approach is to remember the values from the first list, then check each value in the second list against that memory. That makes each check fast and keeps the answer unique. It also uses extra space only for the values I store, so it is a good fit when the arrays are very large.

1. Do you want each common value only once, or should duplicates be counted too?
2. Does the output need a specific order, or is any order fine?

The input is two arrays of 64-bit signed numbers. The output is the distinct numbers that appear in both arrays. The diagram shows values, not indices. It also shows that the result is a set of common numbers, so duplicates should not appear twice.

I use a HashSet. First, I store every value from array A in one set called seen. Then I scan array B. If a value from B is already in seen, I add it to the result set. This is fast because set lookup is quick on average, and duplicates are removed automatically.

I start with an empty seen set and an empty result set. seen means values that were already found in A. result means values that were found in both A and B. The first loop begins at the start of array A. The second loop begins at the start of array B. The invariant is simple: seen always contains the unique values from A that have been processed so far.

The diagram uses: A = [7, -3, 15, 22, -3, 42, 7, 19, 100] B = [19, 7, -3, 88, 42, 100, 7, -3, 5]

First, I add every value from A into seen. After that pass, seen contains {7, -3, 15, 22, 42, 19, 100}. Then I scan B in order. 19 is in seen, so I add it. 7 is in seen, so I add it. -3 is in seen, so I add it. 88 is not in seen, so I skip it. 42 is in seen, so I add it. 100 is in seen, so I add it. The next 7 and -3 are already in the result set, so they do not change the answer. 5 is not in seen, so I skip it. The final distinct common values are {-3, 7, 19, 42, 100}.

Every value in seen came from A. When I add a value from B only if it is already in seen, that value must be in both arrays. The result set removes duplicates, so each common value appears once. That is the key invariant. We process each element at most once and stop when the scan is done.

The Java code creates a HashSet<Long> for seen and fills it with all values from A. Then it creates another HashSet<Long> for common and scans B. For each value in B, it checks seen.contains(value). If the check is true, it adds the value to common. At the end, it converts the set to a list and returns it. The main method runs the exact example from the diagram.

The solution takes O(n + m) expected time because it scans each array once and set operations are average O(1). The extra memory is O(n + min(n, m)) because seen can store all unique values from A and common can store up to the smaller unique count from the two arrays. Important edge cases are empty arrays, no common numbers, duplicate values, negative numbers, and zero.

The key idea is to use a HashSet for fast membership checks. First, I insert every value from A into seen. Then I scan B. If a value from B is already in seen, I add it to common. The invariant is that seen contains the unique values from A, and common contains only unique values that appear in both arrays. This works because every common value must be present in both arrays, and the set automatically removes duplicates.

We walk through A once and B once. HashSet lookup and insertion are O(1) on average, so the total time is O(n + m) expected time. The extra memory is the seen set plus the common set, so the auxiliary space is O(n + min(n, m)). That matches the memory tradeoff shown in the diagram.

A common mistake is returning values with duplicates instead of a distinct set. Another mistake is scanning B without first storing A, which makes membership checks slow. Some candidates also forget that negative numbers, zero, and repeated values must work. Another mistake is assuming the output order is guaranteed when a HashSet does not promise that. Finally, do not claim worst-case guaranteed O(1) behavior for hashing.

Say the invariant out loud: seen holds all unique values from A, and common only grows when a value from B is already in seen.

I would keep the running sum in two doubles, hi and lo, so tiny rounding losses are not thrown away. For each value, I add it to the high part, capture the error, fold that error into the low part, and renormalize the pair. That keeps the best possible double result for the numbers seen so far. I process each item at most once. The time is O(n), and the extra space is O(1).

I would add the numbers in a way that keeps the small bits that normal addition can drop. A plain left-to-right sum can lose tiny values when very large values come first. So I keep a main total and a small leftover part. Each new number updates both parts before I move on. That gives the closest double result while still using one pass and very little memory. It is a good fit when the array is huge and the order of addition affects the final answer.

1. Should I return one best double value, or do you want the exact mathematical sum too?
2. Can the input contain NaN or infinity, and should I follow normal Java double rules?

The input is a very large array of floating-point numbers. The output is one double. The goal is the most accurate value that a double can hold.

I keep hi for the main total and lo for the tiny leftover bits. Together, hi + lo is the best running answer for the values I have already processed.

The diagram uses [1e16, 1.0, -1e16, 1.0]. A normal sum loses the first 1.0. The compensated sum keeps it. The final result is 2.0.

I start with hi = 0.0 and lo = 0.0. After 1e16, the state becomes (1e16, 0). After 1.0, the low part stores 1.0. After -1e16, the high part drops back to 0, but the low part still keeps 1.0. After the last 1.0, the pair becomes (1.0, 1.0), so hi + lo = 2.0.

The key invariant is simple: hi holds the main sum and lo holds the lost rounding error. Each new number is added in a way that keeps those lost bits instead of discarding them. That is why the result is much more accurate than a plain running sum.

The Java code does the same three-step repair for each value. First it adds the value to hi. Then it adds the error into lo. Then it renormalizes the pair so the large part stays in hi and the small part stays in lo.

The code reads the array once, so the time is O(n). It uses only a few doubles, so the extra space is O(1). If the array is empty, the result is 0.0. If the array contains NaN or infinity, Java double rules apply.

The key idea is to store the sum as two doubles, hi and lo. hi keeps the main value. lo keeps the small error that would usually be lost to rounding. For each new number, I first add it to hi, then I add the rounding error into lo, and then I renormalize the pair. The invariant is that hi + lo is the most accurate running double for the numbers already seen. This is better than a plain left-to-right sum because it preserves tiny values that would otherwise disappear.

We read the array once, so the time grows linearly with the number of values: O(n). We only keep hi, lo, and a few temporary doubles, so the extra memory is O(1). This is a sequential algorithm, so the order of addition matters for accuracy.

A common mistake is using a plain running sum and losing tiny values when a huge value comes first. Another mistake is returning only hi and forgetting the low part that still holds useful error. Some candidates change the order of addition or sort the values, which changes the rounding behavior. It is also easy to think the goal is the exact mathematical sum, but the diagram asks for the best possible double result.

Say the invariant out loud: hi keeps the main sum, lo keeps the lost bits, and each loop step repairs the rounding error before the next number arrives.

I would use Floyd’s cycle detection with two pointers. Slow moves one node at a time and fast moves two. If there is a loop, the fast pointer will eventually catch the slow pointer inside the cycle. If fast reaches null, there is no loop. I process each node at most once and stop when the answer is found. That gives O(n) time and O(1) extra space.

This problem asks whether a chain of linked items ever comes back to an earlier item and starts repeating. I begin at the first item and move through the chain in two ways. One moves slowly and the other moves faster. If there is a loop, the fast one will eventually catch the slow one inside that loop. If the fast one reaches the end, then the chain stops normally and there is no loop. This fits well because it finds a loop without storing the whole chain.

1. Do you only want a yes or no answer, or should I also find the node where the loop starts?
2. Can I assume the list is not changing while I traverse it?

The input is the head node of a singly linked list. The output is a boolean. I only need to tell whether a cycle exists. The answer must use node references, not node values.

I use Floyd’s cycle detection. I keep two node references. Slow moves one step. Fast moves two steps. The invariant is simple. If there is a cycle, the fast pointer will eventually meet the slow pointer inside the loop. If fast reaches null, the list ends and there is no cycle.

I start both pointers at the head. That matches the diagram. If the list is empty or has one node with no self-loop, I can return false early because no cycle is possible.

The diagram uses the list 1 -> 2 -> 3 -> 4 -> 5 and then the tail points back to node 3. Step 0: both pointers start at node 1. Step 1: slow moves to 2 and fast moves to 3. Step 2: slow moves to 3 and fast moves to 5. Step 3: slow moves to 4 and fast moves to 4. They meet, so the list has a cycle. The diagram also shows the optional start-of-loop idea. If I needed the entry node, I would move one pointer back to head and move both one step at a time until they meet at node 3.

The key reason is that fast moves faster than slow. Inside a cycle, fast keeps closing the gap. So if a cycle exists, the two pointers must meet. If there is no cycle, fast reaches the end first. That is why the method returns true for a loop and false for a normal list.

The Java code checks the easy empty-list cases first. Then it creates slow and fast pointers at the head. The while loop runs only while fast can safely move two steps. Inside the loop, slow moves one step and fast moves two steps. After each move, the code checks whether slow and fast point to the same node. If they do, it returns true. If the loop ends, fast reached null, so the code returns false.

The time is O(n) because the pointers move through the list in linear time. The extra space is O(1) because I only keep two pointers. Important edge cases are an empty list, one node with no cycle, one node that points to itself, a cycle that starts at the head, and a cycle that starts later in the list.

The key idea is Floyd’s cycle detection. I keep two node references. Slow moves one step. Fast moves two steps. If the list has no cycle, fast reaches the end and I return false. If the list has a cycle, fast keeps moving inside the loop and must eventually meet slow. That meeting proves the cycle exists. The invariant is that fast keeps closing the gap whenever both pointers are in the same cycle.

We process the input at most once. The fast pointer either reaches the end or meets the slow pointer inside a loop. So the time is O(n). I do not use a map or set. I only keep two pointers, so the extra memory is O(1).

A common mistake is to compare node values instead of node references. Another mistake is to move the fast pointer without first checking that fast and fast.next are not null. Some candidates move both pointers by one step, which can miss the cycle. Others forget that an empty list and a single node without a self-loop both return false. Also, stop as soon as the two pointers meet.

Say the invariant out loud. Fast moves twice as fast as slow, so if a cycle exists, fast must eventually catch slow inside the loop.

I would use two pointers. Each pointer starts at one head, then switches to the other list when it reaches the end. That makes both pointers walk the same total distance, so they meet at the first shared node by reference, or at null if the lists do not intersect. I process each node at most once, so the time is O(m + n) and the extra space is O(1).

We need to return the first shared node of two linked lists. The shared part is by reference, not by value. The idea in the diagram is to use two pointers. Each pointer walks one list, then switches to the other list when it reaches the end. That makes both pointers travel the same total distance. So they meet at the shared node, or at null if there is no intersection.

1. Should I return the node reference itself, or only its value?
2. Can I assume both lists are acyclic?

The input is two singly linked lists. The output is the first common node by reference, not the first equal value. In the example, list A is 4 → 1 → 8 → 10 → 5 and list B is 6 → 3 → 10 → 5. The first shared node is the node with value 10.

Use two pointers, one for each list. No extra data structure is needed. The key idea is that each pointer will walk both lists, so each one covers the same total distance. That is why they line up at the meeting point.

Set pA = headA and pB = headB. These pointers store node references, not values. Start both pointers at the two list heads. The invariant is simple: both pointers always move one node at a time.

pA starts on 4, then 1, then 8, then 10. pB starts on 6, then 3, then 10. When a pointer reaches null, it switches to the other list head. So pA later walks through list B, and pB later walks through list A. Because both pointers travel the same total distance, they meet at the shared node with value 10.

Each pointer travels lenA + lenB nodes in total. If the lists share a tail, the extra nodes in one list are canceled by the switch to the other head. That is why the pointers arrive at the first shared node together. If there is no shared node, both pointers become null at the same time.

The loop runs while pA != pB. Inside the loop, each pointer either moves to next or jumps to the other head when it becomes null. When the loop stops, pA and pB are the same reference. That reference is the meeting node, or null if there is no intersection.

The time is O(m + n), where m and n are the lengths of the two lists. The extra space is O(1) because the code uses only two pointers. Important edge cases are a shared head, one empty list, different list lengths, and no intersection.

The key invariant is that both pointers walk the same total distance. Pointer A starts at headA and pointer B starts at headB. When one pointer reaches the end, it jumps to the other list's head. That equalizes the path length. If the lists intersect, the pointers meet at the first shared node by reference. If they do not intersect, both pointers become null together. This is why the two-pointer solution is correct and uses only O(1) extra space.

The code walks through the two lists with two pointers. Each pointer may visit both lists once, so the total work is O(m + n). We process each node at most once and stop as soon as the two pointers are the same. The extra memory is O(1) because we keep only the two pointers and no map or set.

A common mistake is comparing node values instead of node references. Two nodes can hold the same number and still be different nodes. Another mistake is moving only one pointer or forgetting to switch heads after null. That breaks the equal-distance idea. People also stop too early when one list ends, or they add a set even though the diagram uses O(1) extra space.

When you explain this solution, say one sentence about equal total distance. That is the core invariant the interviewer wants to hear.

I build a bounded FIFO queue with one ReentrantLock and two Condition objects. Producers call enqueue, and they wait on notFull when the queue is full. Consumers call dequeue, and they wait on notEmpty when the queue is empty. Inside the lock, addLast and removeFirst keep FIFO order. After each state change, I signal the opposite side so one waiting thread can continue. Each successful operation is O(1) amortized, and the queue uses O(N) extra space.

The problem asks for a queue that many threads can use at the same time without breaking order. When the line is full, new items must wait. When the line is empty, removal must wait. The goal is to keep the first item in, first item out order and to avoid race conditions. A single shared lock with two wait signals fits this well because it lets one side sleep until the queue changes.

1. Should the queue have a fixed maximum size, or should it grow without a limit?
2. When the queue is full or empty, should the method block, time out, or return a failure?
3. Do you want fair scheduling so waiting threads get a more even chance?

The input is a capacity and items that may be added or removed by many threads. The output is a safe queue that keeps FIFO order. If the queue is full, producers wait. If it is empty, consumers wait. The dequeue result is the removed item.

I use one ReentrantLock to protect one LinkedList. The LinkedList is the queue storage. I use two Condition objects. notEmpty means there is at least one item. notFull means there is room for one more item. The key invariant is simple: only the lock holder changes the queue, and the queue always keeps FIFO order.

I start with an empty queue, the given capacity, and a lock created with the fair option when needed. Then I create notEmpty and notFull from the same lock. This makes both waiting signals part of the same safe critical section.

The diagram uses capacity 5 and this order: E(10), E(20), E(30), D(), E(40), D(), D(), E(50). Start: queue = [], head = 0, tail = 0, size = 0. After E(10): queue = [10]. After E(20): queue = [10, 20]. After E(30): queue = [10, 20, 30]. After D(): remove 10, so queue = [20, 30], returned = 10. After E(40): queue = [20, 30, 40]. After D(): remove 20, so queue = [30, 40], returned = 20. After D(): remove 30, so queue = [40], returned = 30. After E(50): queue = [40, 50]. The final state is the same in every section: queue = [40, 50], head = 40, tail = 50, size = 2.

The lock prevents two threads from changing the queue at the same time. notFull stops producers only when the queue is full. notEmpty stops consumers only when the queue is empty. Because items are added at the tail and removed from the head, FIFO order never changes.

The constructor checks that capacity is positive. enqueue first rejects null, then locks, waits while the queue is full, adds the item to the tail, signals notEmpty, and unlocks in finally. dequeue locks, waits while the queue is empty, removes the head item, signals notFull, returns the item, and unlocks in finally. The demo code runs the same example from the diagram and prints the final queue state.

Each successful enqueue and dequeue does constant work, so the time is O(1) amortized per operation. The queue stores at most N items, so auxiliary space is O(N). Important edge cases are a full queue, an empty queue, interrupted threads, null items, and optional fair locking.

I use one lock to protect the whole queue. That makes every change safe. The queue stays FIFO because new items go to the tail and removed items come from the head. Two Conditions control blocking. notFull waits when the queue has no room. notEmpty waits when the queue has no items. After an enqueue, I wake one waiting consumer. After a dequeue, I wake one waiting producer. The invariant is that the queue state is always valid when a thread leaves the lock.

Each enqueue and dequeue does a small fixed amount of work once the thread gets the lock. So the time is O(1) amortized per operation. The queue can hold at most N items, so the extra memory is O(N). If a thread must wait, that waiting time depends on contention, but the core queue work is still constant.

A common mistake is using if instead of while around await(). Spurious wakeups can happen, so the code must check the condition again. Another mistake is signaling the wrong condition after a change. After enqueue, the queue is no longer empty, so notEmpty should be signaled. After dequeue, the queue has room, so notFull should be signaled. Some candidates forget to lock every access to the shared queue. That breaks safety. Another mistake is removing from the tail or adding to the head, which breaks FIFO order. A final mistake is ignoring InterruptedException or allowing null items when the policy forbids them.

Say the invariant out loud: one lock protects the whole queue, and each state change wakes the opposite side with the right Condition.

I would convert the number by repeated division by 11. Each remainder becomes the next base-11 digit, and I store the digits from right to left, then reverse them at the end. For 175, the remainders are 10, 4, and 1, so the final answer is 14A. This works because each division removes one base-11 place value. The time is O(log_11 n), and the extra space is also O(log_11 n).

The question asks us to change 175 from ordinary counting into base 11. That means we keep dividing by 11, save each leftover number, and then read those leftovers in reverse order. For 175, the leftovers are 10, 4, and 1. In base 11, 10 is written as A, so the final answer is 14A. This method fits well because every step is simple, exact, and easy to check by hand. It also matches the Java code one step at a time.

1. Do you want only the base-11 string, or do you also want the conversion steps?
2. Should I support only base 11, or any base from 2 to 36?

The input is the decimal number 175. The output is its base-11 form. We only need the final converted string, not indices or extra data.

The cleanest method is repeated division. Each remainder is one base-11 digit. This is better than trying to build the number by guessing digits.

Start with n = 175 and an empty list of digits. The list stores digits from least significant to most significant. That means the first digit we find goes on the right side of the final answer.

First, divide 175 by 11. The quotient is 15 and the remainder is 10, which is A in base 11. Then divide 15 by 11. The quotient is 1 and the remainder is 4. Then divide 1 by 11. The quotient is 0 and the remainder is 1. The saved digits are 10, 4, and 1. Reading them backward gives 14A.

At every step, n = 11 × quotient + remainder. That means the remainder is always the next correct digit in base 11. When n becomes 0, all place values are finished, so reversing the collected digits gives the exact answer.

The Java code keeps dividing the number by 11, converts remainder 10 to 'A', appends each digit, and reverses the result at the end. The main method runs the example 175, so the printed answer is 14A.

The number of divisions is small and depends on how many base-11 digits the number has. The extra memory also grows with the number of digits. For 175, there are three digits. The main edge cases are n = 0 and values smaller than 11.

The key insight is that repeated division by 11 gives the base-11 digits from right to left. The remainder is the next digit, and the quotient becomes the next number to divide. The invariant is simple: after each step, the collected remainders are exactly the digits already found, in reverse order. When the quotient becomes 0, reversing the collected digits gives the final base-11 representation.

This process uses one division loop for each base-11 digit. So the time is O(log_11 n). The extra memory also grows with the number of digits, because we store the remainders before reversing them. So the auxiliary space is O(log_11 n). In simple words, we process the number a small number of times, not once per decimal digit.

A common mistake is forgetting that remainder 10 must be written as A. Another mistake is reading the digits in the same order they were found, instead of reversing them. Some candidates also stop too early and forget to keep dividing until n becomes 0. A final mistake is mixing up the quotient and remainder, which breaks the place values.

When you explain it, say one short rule: the remainder is the next digit, and the last remainder becomes the leftmost digit after reversing.

I would use the Babylonian, or Newton-Raphson, method. I start with a positive guess, then I keep replacing it with the average of the guess and x divided by the guess. That moves the value quickly toward √x. I stop when the change is smaller than the tolerance. If x is negative, I throw an error. This runs in O(log log(x / ε)) time and uses O(1) extra space.

The problem asks for a square root of one non-negative number, but it does not want the direct built-in answer. I start with one positive guess and improve it again and again using the number itself. Each new guess is the average of the current guess and x divided by that guess. That makes the guess move quickly toward the square root. I stop when the change is tiny. This works well because the guess gets much better very fast, and the code stays small and easy to explain.

1. Should I treat negative input as an error, and do you want a tolerance like ε for the stop rule?
2. Do you want the raw approximation, or do you want it printed to a fixed number of decimal places?

The input is one number x. The output is an approximation of √x. The diagram uses x >= 0, a double value, and it stops when the change between two guesses is small enough.

I use the Babylonian, or Newton-Raphson, update: next = 0.5 * (y + x / y). The state is just the current guess y, the next guess next, and the tolerance eps. The central idea is that each new guess is better than the last one.

If x < 0, the code throws an error. If x is 0, the answer is 0. The code also returns infinity unchanged. For a positive number, the initial guess is x when x >= 1.0, otherwise it is 1.0. This avoids a bad starting point and keeps y positive.

The diagram uses x = 2 and eps = 10^-12. Start with y0 = 1.0. Then next = 0.5 * (1.0 + 2 / 1.0) = 1.5. Then next = 0.5 * (1.5 + 2 / 1.5) = 1.4166666666666667. Then next = 1.4142156862745099. Then next = 1.4142135623746899. Then next = 1.4142135623730951. At that point the change is tiny, so the loop stops and returns the approximation.

The update comes from Newton's method for f(y) = y^2 - x. The guess stays positive, and each step moves it closer to √x. The diagram shows that the number of correct digits grows very fast once the guess is close. That is why the method converges quickly.

The method sqrtNewton(double x, double eps) does the same steps as the diagram. It first handles NaN, x < 0, x == 0, and infinity. Then it sets the initial guess. Inside the loop, it computes next with the Babylonian formula. If Math.abs(next - y) <= eps * next, it returns next. Otherwise it copies next into y and repeats. The main method runs the diagram's example with x = 2.0 and eps = 1e-12.

Each loop round does constant work, so the total time is O(log log(x / ε)) and the extra space is O(1). The important edge cases are NaN, x < 0, x == 0, very large x, and very small positive x. The chosen initial guess and relative stop rule help with those cases.

The key idea is to use Newton's method on f(y) = y^2 - x. The update y_next = 0.5 * (y + x / y) moves the guess toward √x very fast. The invariant is simple: y is always the current positive guess, and next is the improved guess. We stop when the relative change is tiny, so the approximation is stable.

Each round does a constant amount of math: one division, one addition, one multiply, and one comparison. Because Newton's method converges very fast, the number of rounds is O(log log(x / ε)). So the total time is O(log log(x / ε)) and the extra space is O(1).

A common mistake is to use the built-in square root instead of the iterative method. Another mistake is to start with a bad initial guess, such as 0, which can break the division step. Candidates also forget the special cases for NaN, x < 0, and x == 0. A final mistake is to use the wrong stop test, or to keep iterating after the answer is already stable.

Say the update formula out loud, then point out the stop rule. That shows you know both the math and the code.