Subarray Sum

Easy Subarray Sum

21%

Accepted

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Have you met this question in a real interview? 

Yes

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note

There is at least one subarray that it's sum equals to zero.

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(map.containsKey(sum)){
                res.add(map.get(sum)+1);
                res.add(i);
                return res;
            }
            map.put(sum, i);
        }
        return res;
    }
}

Compare Strings

Compare two strings A and B, determine whether A contains all of the characters in B.

The characters in string A and B are all Upper Case letters.

Have you met this question in a real interview? 

Yes

Example

For A = "ABCD", B = "ACD", return true.

For A = "ABCD", B = "AABC", return false.

Note

The characters of B in A are not necessary continuous or ordered.

public class Solution {

    /**

     * @param A : A string includes Upper Case letters

     * @param B : A string includes Upper Case letter

     * @return :  if string A contains all of the characters in B return true else return false

     */

    public boolean compareStrings(String A, String B) {

        // write your code here

        

        int[] count = new int[26];

        for(int i = 0; i < A.length(); i++){

            count[A.charAt(i) - 'A']++;

        }

        

         for(int i = 0; i < B.length(); i++){

            count[B.charAt(i) - 'A']--;

            if(count[B.charAt(i) - 'A'] < 0) return false;

        }

        return true;

        

    }

}

Product of Array Exclude Itself

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.

Have you met this question in a real interview? 

Yes

Example

For A = [1, 2, 3], return [6, 3, 2].

public class Solution {

    /**

     * @param A: Given an integers array A

     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]

     */

    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {

        // write your code

        

        ArrayList<Long> result = new ArrayList<Long>();

        int n = A.size();

        long[] lProducts = new long[n];

        long[] rProducts = new long[n];

        lProducts[0] = (long) 1;

        for(int i = 1; i < A.size(); i++){

            lProducts[i] =  (long)lProducts[i-1]*A.get(i-1);

        }

        rProducts[n-1] = (long) 1;

        for(int i = A.size() - 2; i >= 0 ; i--){

            rProducts[i] = (long)rProducts[i+1]*A.get(i+1);

        }

        for(int i = 0; i < A.size(); i++){

            result.add((long)lProducts[i] * rProducts[i]);

        }

        return result;

    }

}

Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Have you met this question in a real interview? 

Yes

Example

Clarification

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
        // write your code
        char[] arr = s.trim().toCharArray();
        reverse(arr, 0, arr.length-1);
        for(int i = 0, j = 0; j <= arr.length; j++){
            if(j == arr.length || arr[j] == ' '){
                reverse(arr, i, j-1);
                i = j+1;
            }  
        }
        return new String(arr);
    }
   
    private void reverse(char[] s, int left, int right){
        while(left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

Fizz Buzz

Easy Fizz Buzz

80%

Accepted

Given number n. Print number from 1 to n. But:

• when number is divided by 3, print"fizz".
• when number is divided by 5, print"buzz".
• when number is divided by both 3 and 5, print "fizz buzz".

Have you met this question in a real interview? 

Yes

Example

If n = 15, you should return:

["1", "2", "fizz", "4", "buzz", "fizz", "7", "8", "fizz", "buzz"




class Solution {

    /**

     * param n: As description.

     * return: A list of strings.

     */

    public ArrayList<String> fizzBuzz(int n) {

     

        ArrayList<String> result = new ArrayList<String>();

        for(int i = 1; i <= n; i++){

            if(i % 15 == 0){

                result.add("fizz buzz");

            }else if(i % 5 == 0){

                result.add("buzz");

            } else if(i % 3 == 0){

                result.add("fizz");

            } else result.add(String.valueOf(i));

        }

        return result;

    }

}

Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Have you met this question in a real interview? 

Yes

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

class Solution {

    /**

     * Insert newInterval into intervals.

     * @param intervals: Sorted interval list.

     * @param newInterval: A new interval.

     * @return: A new sorted interval list.

     */

    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {

        ArrayList<Interval> result = new ArrayList<Interval>();

       

        // write your code here

        for(Interval interval : intervals){

            if(interval.end < newInterval.start){

                result.add(interval);

            } else if(interval.start > newInterval.end){

                result.add(newInterval);

                newInterval = interval;

            } else if(interval.end >= newInterval.start || interval.start <= newInterval.end){

                newInterval.start = Math.min(newInterval.start, interval.start);

                newInterval.end = Math.max(newInterval.end, interval.end);

            }

            

        }

        result.add(newInterval);

        return result;

    }

}

Binary Search

Binary Search

28%

Accepted

For a given sorted array (ascending order) and atarget number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Have you met this question in a real interview? 

Yes

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge

If the count of numbers is bigger than 2^32, can your code work properly?

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if(nums == null || nums.length == 0) return -1;
        int start = 0, end = nums.length - 1;
        int mid = 0;
        while(start <= end){
            mid = (start + end) / 2;
            if(nums[mid] == target) break;
            if(nums[mid] > target) end = mid - 1;
            else start = mid + 1;
        }
        while(mid >= 0 && nums[mid] == target){
            mid--;
        }
        if(mid < nums.length - 1 && nums[++mid] == target) return mid;
        return -1;
    }
}

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Have you met this question in a real interview? 

Yes

Example

Consider the following matrix:

[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = m * n - 1;
        while(i <= j){
            int mid = (i+j) / 2;
            if(matrix[mid/n][mid%n] < target) i = mid + 1;
            else if(matrix[mid/n][mid%n] > target) j = mid - 1;
            else {
                return true;
            }  
        }
        return false;
    }
}

Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.

Have you met this question in a real interview? 

Yes

Example

A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

class Solution {
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
        // write your code here
        if(A == null || B == null) return null;
        ArrayList<Integer> result = new ArrayList<Integer>();
        int i = 0, j = 0;
        while(i < A.size() || j < B.size()){
            if(i < A.size() && j < B.size()){
                if(A.get(i) <= B.get(j)){
                    result.add(A.get(i));
                    i++;
                } else {
                     result.add(B.get(j));
                     j++;
                }
            } else if(i < A.size()){
                result.addAll(A.subList(i, A.size()));
                break;
            } else if(j < B.size()){
                result.addAll(B.subList(j, B.size()));
                break;
            }
           
        }
        return result;
    }
}

Rotate String

Given a string and an offset, rotate string by offset. (rotate from left to right)

Have you met this question in a real interview? 

Yes

Example

Given "abcdefg".

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

Challenge

Rotate in-place with O(1) extra memory.

public class Solution {

    /*

     * param A: A string

     * param offset: Rotate string with offset.

     * return: Rotated string.

     */

    public char[] rotateString(char[] A, int offset) {

        // wirte your code here

        if(A == null || A.length == 0 || offset == 0) return A;

        offset = offset % A.length;

        reverse(A, A.length - offset, A.length-1);

        reverse(A, 0, A.length - offset - 1);

        reverse(A, 0, A.length-1);

        return A;

    }

    private void reverse(char[] A, int i, int j){

        while(i < j){

            char temp = A[i];

            A[i] = A[j];

            A[j] = temp;

            i++; j--;

        }

    }

};

Reverse Linked List

Reverse a linked list.

Have you met this question in a real interview? 

Yes

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        // write your code here
        if(head == null) return head;
        ListNode pre = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}