[2018-Interview] String to Integer

Original question: https://leetcode.com/problems/string-to-integer-atoi/description/

My answer: Leverage the method to determine if number is overflow: http://yizheliu.blogspot.com/2018/01/2018-interview-reverse-string.html

class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        int sign = 1;
        int i = 0;
        while (str.charAt(i) == ' ') {
            i ++;
        }
        if (str.charAt(i) == '-') {
            sign = -1;
            i ++;
        } else if (str.charAt(i) == '+') {
            i ++;
        } 
        
        int res = 0;
        int temp = 0;
        while ( i < str.length() &&
            str.charAt(i) <= '9' &&
            str.charAt(i) >= '0') {
            temp = res * 10 + sign * Integer.valueOf(str.charAt(i) - '0');

            if ((temp / 10) != res) {// overflow
                if (sign > 0) {
                    return Integer.MAX_VALUE;
                } else {
                    return Integer.MIN_VALUE;
                }
            }
            res = temp;
            i ++;
        }
        return res;
    }
}

[2018-Interview] Valid Palindrome

Original question: https://leetcode.com/problems/valid-palindrome/description/


My answer: Better solution would be using 2 pointers, 1 at front, 1 at end, and skip the invalid characters, but logic is similar as the 2nd while loop.

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        LinkedList<Character> validStr = new LinkedList<Character>();
        for (int i = 0; i < s.length(); i++) {
            Character lowerOne = Character.toLowerCase(s.charAt(i));
            if ((lowerOne >= 'a' && lowerOne <= 'z') ||
               (lowerOne >= '0' && lowerOne <= '9')) {
                validStr.add(lowerOne);   
            }
        }
        while (validStr.size() > 1) {
            if (!validStr.removeFirst().equals(validStr.removeLast()) ) {
                return false;
            }
        }
        return true;
    }
}

[2018-Interview] Valid Anagram

Original question: https://leetcode.com/problems/valid-anagram/description/


My answer:

class Solution {
    public boolean isAnagram(String s, String t) {
        if ((s == null && t == null) || (s.length() <= 1 && s.equals(t))) {
            return true;
        }
        if (s == null || t == null || s.length() != t.length() || s.equals(t)) {
            return false;
        }
        Map<Character, Integer> charCounts = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i ++) {
            int count = charCounts.getOrDefault(s.charAt(i), 0);
            count ++;
            charCounts.put(s.charAt(i), count);
            count = charCounts.getOrDefault(t.charAt(i), 0);
            count --;
            charCounts.put(t.charAt(i), count);
        }
        for (Character charInSt : charCounts.keySet()) {
            if (charCounts.get(charInSt) != 0) {
                return false;
            }
        }
        return true;
    }
}

[2018-Interview] First Unique Character in a String

Original question: https://leetcode.com/problems/first-unique-character-in-a-string/description/


My answer: Tried to find a solution using only 1 single loop, but failed.

class Solution {
    public int firstUniqChar(String s) {
        // Solution 1
        Map<Character, Integer> charCountMap = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i ++) {
            Integer count = charCountMap.getOrDefault(s.charAt(i), 0);
            count += 1;
            charCountMap.put(s.charAt(i), count);
        }
        for (int i = 0; i < s.length(); i ++) {
            if (charCountMap.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

[2018-Interview] Reverse Integer

Original question: https://leetcode.com/problems/reverse-integer/description/

My answer: Not good one. Got impacted by the reverse-string question. Many cases were not taken into account at 1st step, like -2147483648(-2^31), 0, 10. Should have verified code using such cases.

Better solution has been posted below, which doesn't have to handle case where number is negative, and can be extended if we want to reverse Long

class Solution {
    public int reverse(int x) {
        int sign = 1;
        long maxAbsoluteIntValue = Long.valueOf(Integer.MAX_VALUE);
        if (x < 0) {
            sign = -1;
            maxAbsoluteIntValue = Math.abs(Long.valueOf(Integer.MIN_VALUE));
        } else if (x == 0) {
            return 0;
        }
        while ( x % 10 == 0) {
            x /= 10;
        }
        String rawNumStr = String.valueOf(x);
        String numStr = rawNumStr;
        if (sign < 0) {
            numStr = rawNumStr.substring(1, rawNumStr.length());
        }
        int i = 0;
        char temp = ' ';
        char[] numArray = numStr.toCharArray();
        while (i < numArray.length/2) {
            temp =  numArray[i];
            numArray[i] = numArray[numArray.length - 1 - i];
            numArray[numArray.length - 1 - i] = temp;
            i ++;
        }
        String reverseStr = String.valueOf(numArray);
        if (Long.valueOf(reverseStr) > maxAbsoluteIntValue) {
            return 0;
        } else {
            return Integer.valueOf(reverseStr) * sign;
        }
        
    }
}

Better solution:

public class Solution {
    /**
     * @param n the integer to be reversed
     * @return the reversed integer
     */
    public int reverseInteger(int n) {
        int reversed_n = 0;
        
        while (n != 0) {
            int temp = reversed_n * 10 + n % 10;
            n = n / 10;
            if (temp / 10 != reversed_n) {
                // if overflow
                reversed_n = 0;
                break;
            }
            reversed_n = temp;
        }
        return reversed_n;
    }
}

[2018-Interview] Reverse String

Original question: https://leetcode.com/problems/reverse-string/description/

My answer:

class Solution {
    public String reverseString(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        // solution 1: use stack
        // LinkedList<Character> stack = new LinkedList<Character>();
        // StringBuilder sb = new StringBuilder();
        // for (int i = 0; i < s.length(); i++) {
        //     stack.addLast(s.charAt(i));
        // }
        // while(!stack.isEmpty()) {
        //     sb.append(stack.pollLast());
        // }
        // return sb.toString();

        // solution 2: in-place, one time traverse -> swap
        char[] letters = s.toCharArray();
        char temp = '0';
        int distance = 0;
        do {
            temp = letters[distance];
            letters[distance] = letters[s.length() - 1 - distance];
            letters[s.length() - 1 - distance] = temp;
            distance ++;
        } while(2 * (distance + 1) <= s.length());
        return String.valueOf(letters);
    }
}

One interesting solution: Explanation is here: http://www.cnblogs.com/suoloveyou/archive/2012/04/25/2470292.html

Basically it is using XOR bitwise operation

public static String reverseString5(String s) {
        char[] ch = s.toCharArray();
        int start = 0;
        int end = ch.length - 1;
        while (start < end) {
            ch[start] = (char) (ch[start] ^ ch[end]);
            ch[end] = (char) (ch[start] ^ ch[end]);
            ch[start] = (char) (ch[start] ^ ch[end]);
            start++;
            end--;
        }
        return new String(ch);
    }

Another one is using recursive way to always reverse 1st half and 2nd falf

[2018-Interview] Rotate Image

Original question: https://leetcode.com/problems/rotate-image/description/

My answer: Logic here is that, given specific level, rotate values at that level one by one. The key thing is to find out index of next one to be swapped. One hand-draw picture will be attached. Be careful of that no need to rotate the last element of that level.

class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length < 1 || matrix.length != matrix[0].length || matrix.length == 1) {
            return;
        }
        int level = 0;

        do {
            for (int j = level; j < matrix.length - 1 - level; j ++) {
                int right = matrix[j][matrix.length - 1 - level];
                matrix[j][matrix.length - 1 - level] = matrix[level][j];
                int bottom = matrix[matrix.length - 1 - level][matrix.length - 1 - j];
                matrix[matrix.length - 1 - level][matrix.length - 1 - j] = right;
                int left = matrix[matrix.length - 1 - j][level];
                matrix[matrix.length - 1 - j][level] = bottom;
                matrix[level][j] = left;
            }
            level ++;
        } while(2* (level + 1) <= matrix.length);
    }
}

Attached image explaining how to find where to swap:

[2018-Interview] Two Sum

Original question: https://leetcode.com/problems/two-sum/description/

My answer: Actually we can combine two for loop into one

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return new int[0];
        }
        // solution: Map<target - element, index>
        Map<Integer, Integer> targetRemainingIndex = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i ++) {
            int targetRemaining = target - nums[i];
            targetRemainingIndex.put(targetRemaining, i);
        }
        for (int i = 0; i < nums.length; i ++) {
            // edge case where target is 6, nums is [3, 2, 4]
            if (targetRemainingIndex.containsKey(nums[i]) && 
                 targetRemainingIndex.get(nums[i]) != i // don't sum with itself
            ) {
                int [] result = new int[2];
                result[0] = i;
                result[1] = targetRemainingIndex.get(nums[i]);
                return result;
            }
        }
        return new int[0];
    }
}

[2018-Interview] Move Zeros

Original question: https://leetcode.com/problems/move-zeroes/description/

My answer:

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == 0) {
                count ++;
                continue;
            }
            nums[i - count] = nums[i];
        }
        // clear the last number of #{count} elements to 0
        for (int i = nums.length - 1; i > nums.length - 1 - count; i --) {
            nums[i] = 0;
        }
    }
}

Better answer: this method actually is using variable "left" to keep 0s position, and "right" to keep non-0 position. "right" is always increasing, while "left" doesn't change if 0 is encountered.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, right = 0;
        while (right < nums.size()) {
            if (nums[right]) {
                swap(nums[left++], nums[right]);
            }
            ++right;
        }
    }
};

[2018-Interview] Plus One

Original question: https://leetcode.com/problems/plus-one/description/

Answer: Simple question. My code can be easily improved, like using less space, reducing lines. Not every interested in improving it as question is too simple. Answer from other blogs: http://www.cnblogs.com/grandyang/p/4079357.html

class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length < 1) {
            return new int[0];
        }
        int[] addOneResult = new int[digits.length + 1];
        int nextLevel = 0;
        for (int i = addOneResult.length - 1; i >= 0; i--) {
            int addOneSum = 0;
            if (i == 0) {
                addOneResult[i] = nextLevel;
                break;
            }
            if (i == addOneResult.length - 1) {
                addOneSum = digits[i - 1] + 1;
            } else {
                addOneSum = digits[i - 1] + nextLevel;
            }
            nextLevel = addOneSum / 10;
            addOneResult[i] = addOneSum % 10;
        }
        if (nextLevel != 0) {
            return addOneResult;
        } else {
            int [] result = new int[digits.length];
            for (int i = 0; i < digits.length; i ++) {
                result[i] = addOneResult[i + 1];
            }
            return result;
        }
    }
}

[2018-Interview] Intersection of Two Arrays II

Original question: https://leetcode.com/problems/intersection-of-two-arrays-ii/

Answer: Use a map to store the <number, count> pair, count is how many times the number appear in 1 single array.

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        Map<Integer, Integer> numsCountMap = new HashMap<Integer, Integer>();
        if (nums1.length >= nums2.length) {
            return helper(nums1, nums2, numsCountMap);
        } else {
            return helper(nums2, nums1, numsCountMap);
        }
    }

    private int[] helper(int[] numsLong, int[] numsShort, Map<Integer, Integer> numsCountMap) {
        int[] result = new int[numsShort.length];
        for (int num : numsLong) {
            int count = numsCountMap.getOrDefault(num, 0);
            count++;
            numsCountMap.put(num, count);
        }
        int index = 0;
        for (int num : numsShort) {
            if (numsCountMap.containsKey(num)) {
                int existingCount = numsCountMap.get(num);
                if (existingCount > 0) {
                    result[index] = num;
                    existingCount --;
                    numsCountMap.put(num, existingCount);
                    index ++;
                }
            }
        }
        int[] finalResult = new int[index];
        for(int i = 0 ; i < index; i++) {
            finalResult[i] = result[i];
        }
        return finalResult;
    }
}

[2018-Interview] Single Number

Original question: https://leetcode.com/problems/single-number/description/

Answer: Take use of bitwise XOR, because only when number XOR with itself, result would be 0. Thus, the result of whole array XOR should be that single number

class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int singleNumber =  0;
        for (int i = 0; i < nums.length ; i ++) {
            singleNumber ^= nums[i];
        }
        return singleNumber;
    }
}

[2018-Interview] Contains Duplicate

Original question: https://leetcode.com/problems/contains-duplicate/

Answer:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
// Hashset
// or sort it first, compare element with next one        
    }
}

[2018-Interview] Rotate Array

Original question: https://leetcode.com/problems/rotate-array/description/

Answer:
Solution 1): time O(n), space O(n)
Solution 2): time O(n), space O(1) - The underlying truth of rotation is actually reversing.
Solution 3): time O(n*k), space O(1)
Solution 4): time O(n), space O(1)- Basic logic of it is to move "smaller part" in the expected result first, then modify the remaining part, i.e. "bigger part" using same logic.

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length; 
        //(1) new array; 
        int[] oldNums = nums.clone();
        for(int i = 0; i< nums.length;i++){
            nums[(i+k)%nums.length] = oldNums[i]; 
        }
        
        //(2) reverse 3 times 
        // reverse(nums, 0, nums.length-1); 
        // reverse(nums, 0, k-1);
        // reverse(nums, k, nums.length-1); 
        
        //(3) move k times
        // while(k-->0){
        //     int tmp = nums[nums.length-1];
        //     for(int i = nums.length-1; i>0; i--){
        //         nums[i] = nums[i-1];
        //     }
        //     nums[0] = tmp; 
        // }
    }
    
    public void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start]; 
            nums[start] = nums[end]; 
            nums[end]=temp; 
            start++; end--; 
        }
    }
}

Solution 4)

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return;
        }
        helper(nums, 0, nums.length - 1, k % nums.length);
    }
    
    private void helper(int[] nums, int left, int right, int k) {
        if ( k <= 0 || left >= right) {
            return;
        }
        int steps = right - left + 1 - k;
        int temp;
        if (steps > k) {
            for (int i = 0; i < k; i ++) {
                temp = nums[i + left];
                nums[i + left] = nums[left + steps + i];
                nums[left + steps + i] = temp;
            }
            helper(nums, left + k, right, k);
        } else {
            if (steps < k) {
                for (int i = 0; i < steps; i ++) {
                    temp = nums[right - i];
                    nums[right - i] = nums[right - k - i];
                    nums[right - k - i] = temp;
                }
                helper(nums, left, right - steps, k - steps);
            } else {
                for (int i = 0; i < steps ; i ++) {
                 temp = nums[i + left];
                nums[i + left] = nums[left + k + i];
                nums[left + k + i] = temp;                   
                }
                return;
            } 
        }
        
    }
}