LeetCode Top Interview Questions - Easy Collection

This post was migrated from Tistory. You can find the original here.

https://leetcode.com/explore/interview/card/top-interview-questions-easy/

Notes from working through the LeetCode top interview questions - easy collection.

---

Array

Rotate Image

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/770/

in-place, which means you have to modify the input 2D matrix directly. Do NOT allocate another 2D matrix and do the rotation.

An in-place algorithm is one that operates directly on the input data structure without needing extra space proportional to it (in other words, it solves the problem using only the already-allocated input data structure, without creating a separate copy).

For a matrix, “in-place” means you need to swap elements one at a time.

(If you swapped whole rows or columns, you’d need an extra data structure.)

At first glance, the problem doesn’t seem to have an obvious one-to-one swap rule,

but there is a rule that gets you to the answer after two rounds of one-to-one swaps.

1. Flip along the middle row

2. Flip along the diagonal (transpose)

or

1. Transpose the matrix

2. Reverse the order within each row

Key takeaway: “in-place” for a matrix means one-to-one swaps. If the rule isn’t obvious, try approaching it as a sequence of a few swaps.

Strings

Reverse Integer

https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/880/

If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Not being allowed to store 64-bit integers means: don’t use long.

Point 1.

How do you catch an int value going past the 32-bit integer range without using long?

Check before updating the int value.

class Solution {
    public int reverse(int x) {
        int y = 0;
        while (x!=0) {
            int digit = x % 10;
            x /= 10;
            
            if (y > (Math.pow(2, 31)-1)/10 || y < (Math.pow(-2, 31))/10) return 0;
            
            y = y * 10 + digit;
        }
        return y;
    }
}

By pre-applying the range (-2^31 to 2^31 - 1) to the value you’re about to update, you can tell whether it would overflow before actually updating the int.

Point 2.

Also, when reversing 123, I initially approached it with logic like 300 + 20 + 1

(this approach requires first figuring out the number of digits),

but as in the solution above, you can also approach it like this:

step 1 = 3

step 2 = (3) * 10 + 2

step 3 = (32) * 10 + 1

---

More to be added