Question

link

Given an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other?

Solution

We can keep a HashMap for storing the previous occuring position of a number.

Code

public boolean dupWithinK(int k, int[] arr) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < arr.length; i++) {
        if (set.contains(arr[i])) {
            return true;
        }
        if (i < k) {
            // the first k numbers
            set.add(arr[i]);
        } else {
            // the (k+1) th number and onwards
            set.add(arr[i]);
            set.remove(arr[i - k]);
        }
    }
    return false;
}

Question

link

Analysis

This basically is a binary search question. Instead of checking the values, we check the slope (upgoing or downslope).

The important point is the special cases like [1, 2, 3] or [3, 2, 1], we need to return the corner values. Well there’re 2 ways to handle these corner cases.

Solution

First, referring to G4G, the corner case is handled in this way:

if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
        (mid == n-1 || arr[mid+1] <= arr[mid]))
    return mid;

The code 1 below is doing similar things. That code is readable and easy to come up with. I recommend this solution during a interview.

For those who are interested, there is a extremely concise solution thanks to Duplan. I have the Java version posted below as code 2.

Code

Code 1

public class Solution {
    public int findPeakElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        } else if (num.length == 1) {
            return 0;
        } else if (num[0] > num[1]) {
            return 0;
        } else if (num[num.length - 2] < num[num.length - 1]) {
            return num.length - 1;
        }
        // now the leftmost edge is increasing
        // and the rightmost edge is also increasing backwards
        return helper(num, 0, num.length - 1);
    }

    public int helper(int[] num, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left + 2 == right) {
            return mid;
        } else if (num[mid] > num[mid + 1]) {
            // middle is decreasing, so peak on the left side
            return helper(num, left, mid + 1);
        } else {
            return helper(num, mid, right);
        }
    }
}

Code 2

public class Solution {
    public int findPeakElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    public int helper(int[] num, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left == right) {
            return left;
        } else if (num[mid] > num[mid + 1]) {
            // middle is decreasing, so peak on the left side
            return helper(num, left, mid);
        } else {
            return helper(num, mid + 1, right);
        }
    }
}

Question

link

0.1 < 1.1 < 1.2 < 13.37

Analysis

I’ve seen a couple of interesting ideas on other people’s blogs, including one that uses String.split() to convert input to an array, and this one which uses 2 pointers to compare.

My solution might seem more intuitive for some. See below for my solution.

Solution

The idea is to identify what the current number is (before end of string, or before the next ‘.’). If there’s no more string, value = 0, so the case of (1.0, 1) essentially equals. Without further ado, let’s look at the code.

Code

public class Solution {
    public int compareVersion(String version1, String version2) {
        if (version1 == null || version2 == null) {
            return 0;
        }
        return helper(version1, version2);
    }

    private int helper(String v1, String v2) {
        if (v1.length() == 0 && v2.length() == 0) {
            return 0;
        }

        int num1 = 0;
        int num2 = 0;

        if (v1.length() != 0) {
            int p1 = 0;
            while (p1 < v1.length() && v1.charAt(p1) != '.') {
                p1++;
            }
            num1 = Integer.parseInt(v1.substring(0, p1));
            if (p1 < v1.length()) p1++;
            v1 = v1.substring(p1);
        }

        if (v2.length() != 0) {
            int p2 = 0;
            while (p2 < v2.length() && v2.charAt(p2) != '.') {
                p2++;
            }
            num2 = Integer.parseInt(v2.substring(0, p2));
            if (p2 < v2.length()) p2++;
            v2 = v2.substring(p2);
        }

        if (num1 != num2) {
            return (num1 - num2) / Math.abs(num1 - num2);
        } else {
            return helper(v1, v2);
        }
    }
}

Question

link

Analysis

Wow, this is just another incredible question on Leetcode. Quite a few difficult corner cases in the OJ.

Current AC rate is first lowest at 12.4%.

Solution

There’re 3 things that we must take note:

1. Handle positive/nagetive cases well. Note that both numerator and denominator can be negative number. And there’re also case like:

1 / -3 = -0.(3)

1. Note that we have to match the repetation of the actual numerator. Not the quotient. What do I mean by that?

1 / 6 = 0.1(6)

1 / 333 = 0.(003)

1. Note below is how to override the equals() method (first one is wrong and second is right):

   public boolean equals(Pair p) {

   }

   public boolean equals(Object obj) {

   }

One more thing: Most other guys' solutions like this, this and this are using Hashing. It’s fine and definitely good. I used linearly search though, which is a small time compromise. I am presenting my code below and please just consider it as something different. Keep in mind it’s not the optimized solution.

Code

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long quotient = (long) numerator / denominator;
        long reminder = (long) numerator % denominator;
        if (reminder == 0) {
            return String.valueOf(quotient);
        }

        // The result has 3 parts: sign, integer part, and fraction part
        // eg. -4 / 3 = -1 and the result of (1/3) = (3)
        String sign = ((long) numerator * denominator >= 0) ? "" : "-";
        long integer = Math.abs(quotient);
        String fraction = fraction(Math.abs((long)reminder), Math.abs((long)denominator));

        // why do we have to seperate sign from integer?
        // cuz 1 / -3 = -0.(3), while quotient is 0. 
        // So, we can't simply concatenate quotient with fraction
        return sign + integer + "." + fraction;
    }

    String fraction(long num, long denum) {
        // eg. num = 1, denum = 4, should return "25"

        List<Pair> list = new ArrayList<Pair>();
        String result = "";
        while (num != 0) {
            num *= 10;
            long digit = num / denum;

            // eg. 1 / 333 = (003), so the pairs would be like this:
            // {10, 0}, {100, 0}, {1000, 3}, {10, 0}...
            Pair cur = new Pair(num, digit);
            num %= denum;

            // now add cur Pair to the list
            if (list.indexOf(cur) == -1) {
                list.add(cur);
            } else {
                // found a recurring dicimal in the previous output stream
                int pos = list.indexOf(cur);
                for (int i = 0; i < pos; i++) {
                    result += list.get(i).digit;
                }
                result += "(";
                for (int i = pos; i < list.size(); i++) {
                    result += list.get(i).digit;
                }
                result += ")";
                break;
            }
        }

        // if there is recurring digit, the result should have already been generated
        if (result.length() == 0) {
            for (Pair p: list) {
                result += p.digit;
            }
        }
        return result;
    }

    class Pair {
        long num;
        long digit;

        public Pair(long a, long b) {
            num = a;
            digit = b;
        }

        public boolean equals(Object obj) {
            // note the equals interface passes in (Object obj)
            // instead of a Pair object
            Pair p = (Pair) obj;
            return this.num == p.num && this.digit == p.digit;
        }
    }
}

Question

link

A:          a1 ? a2
                   ?
                     c1 ? c2 ? c3
                   ?            
B:     b1 ? b2 ? b3

Analysis

This question is very similar to [LeetCode Plus] Lowest Common Ancestor of Binary Tree (II).

Solution

This is a pretty nice answer. The following explanation is quoted from g4g:

1. Get count of the nodes in first list, let count be c1.

2. Get count of the nodes in second list, let count be c2.

3. Get the difference of counts d = abs(c1 – c2)

4. Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.

5. Then we can traverse both the lists in parallel till we come across a common node.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        return helper(headA, headB, length(headA) - length(headB));
    }

    public ListNode helper(ListNode n1, ListNode n2, int offset) {
        if (offset < 0) {
            return helper(n2, n1, 0 - offset);
        }
        // move n1 to the distance of offset
        while (offset != 0) {
            n1 = n1.next;
            offset--;
        }
        while (n1 != null && n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    int length(ListNode node) {
        int len = 0;
        while (node != null) {
            node = node.next;
            len++;
        }
        return len;
    }
}

Apply for Google AdSense

My first request of AdSense is rejected because of “Site does not comply with Google policies”. I do not know the exact reason, but I did the following things to get it through:

1. I registered a top-level .COM domain name to replace the original github page’s domain.

2. I added “Privacy Policy” page, and added the link to the bottom of each blog post.

3. I re-wrote the “About Me” page, and added in administrator email address.

4. I updated a few more posts, making it more than 580 posts in total.

5. I set up Google Webmaster Tools, and updated sitemap.xml in the configurations.

6. I resubmitted my request of AdSense again.

Put AdSense in your blog

1. Create a new file: source/_includes/asides/advertise.html

2. Copy and paste the code from AdSense, eg.

    <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <!-- ad-name -->
    <ins class="adsbygoogle"
         ...............
    <script>
    (adsbygoogle = window.adsbygoogle || []).push({});
    </script>
   

3. Go to _config.yml, and look for “default_asides”, then add “asides/advertise.html, ” in the beginning of the array

    default_asides: [asides/advertise.html, asides/category_list.html, asides/recent_posts.html, asides/github.html, asides/delicious.html, asides/pinboard.html, asides/googleplus.html]
   

4. Now you’ve added advertisement in your side menu.

5. Go to source/_layouts/post.html and look for:

    if site.disqus_short_name and page.comments
   

6. Right below the article, and above the comments, add your AdSense code, again.

7. Now you’ve added advertisement above your comment area.

Thanks for the effort from this reference.

Updates

Apr 9th update: my re-submission of Google AdSense is not approached, because of “not enough content”. I don’t know what else to do, so I switched to another ad platform.

Apr 11th update: For the first time ever, my blog has more than 1,000 visit per day.

Question

link

Analysis

I’ve already cover this question in another post [Question] Min Stack.

My Code

class MinStack {

    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();

    public void push(int x) {
        stack.push(x);
        if (min.isEmpty() || min.peek() >= x) {
            min.push(x);
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        int topNum = stack.pop();
        if (topNum == min.peek()) {
            min.pop();
        }
    }

    public int top() {
        if (stack.isEmpty()) {
            return 0;
        }
        return stack.peek();
    }

    public int getMin() {
        if (min.isEmpty()) {
            return 0;
        }
        return min.peek();
    }
}

Question

link

Analysis

This is a pretty difficult question. It’s hard to write bug-free solution if you have never practised before.

So the first idea that comes to me is the case of array element = 0. Why this case? cuz the maximum subarray MUST NOT CONTAIN 0 unless the input is like {-1, 0, -1}. So we could divide array from 0s and calculate max sum seperately. This idea is good, though a little difficult in coding. Read it here or here.

Solution

After a bit exploration, I found a must easier apporach, thanks to code ganker and Yu. The idea is to simply ALWAYS CALCULATE preMax and preMin by using MAX/MIN(Val1, Val2, Val3) method.

My Code

public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        } else if (A.length == 1) {
            return A[0];
        }

        int preMax = A[0];
        int preMin = A[0];
        int max = A[0];

        for (int i = 1; i < A.length; i++) {
            int temp = preMin;
            preMin = Math.min(Math.min(preMin * A[i], preMax * A[i]), A[i]);
            preMax = Math.max(Math.max(temp * A[i], preMax * A[i]), A[i]);
            max = Math.max(max, preMax);
        }

        return max;
    }
}

Question

link

Solution

This question is simply a modified version of previous question. The special cases of the input makes it O(n) worst case complexity.

My Code

public class Solution {
    public int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    private int helper(int[] num, int left, int right) {
        if (num[left] < num[right] || left == right) {
            return num[left];
        } else if (num[left] == num[right]) {
            return helper(num, left + 1, right);
        } else if (left + 1 == right) {
            return num[right];
        }
        int mid = left + (right - left) / 2;
        if (num[mid] >= num[left]) {
            return helper(num, mid, right);
        } else {
            return helper(num, left, mid);
        }
    }
}

Question

link

Analysis

This question is very similar to [LeetCode 33] Search in Rotated Sorted Array. Note a few special cases.

Solution

Very good code can be found here and here.

My Code

public class Solution {
    public int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    private int helper(int[] num, int left, int right) {
        if (num[left] <= num[right]) {
            return num[left];
        } else if (left + 1 == right) {
            return num[right];
        }
        int mid = left + (right - left) / 2;
        if (num[mid] > num[left]) {
            return helper(num, mid, right);
        } else {
            return helper(num, left, mid);
        }
    }
}