Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

package leetcode

import "fmt"

func lengthOfLongestSubstring(s string) int {
	l := len(s)
	i := 0
	j := 0
	ans := 0
	set := make(map[byte]bool)
	for i < l && j < l {
		if !set[s[j]] {
			set[s[j]] = true
			j += 1
			if j-i > ans {
				ans = j - i
			}
		} else {
			delete(set, s[i])
			i += 1
		}
	}
	return ans
}

func TestLengthOfLongestSubstring() {
	fmt.Println(lengthOfLongestSubstring("abcabcdefabcdedght"))
}

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
package leetcode

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummyHead := &ListNode{0, nil}
	p := l1
	q := l2
	carry := 0
	curr := dummyHead
	for p != nil || q != nil {
		x := 0
		if p != nil {
			x = p.Val
		}
		y := 0
		if q != nil {
			y = q.Val
		}
		sum := x + y + carry
		carry = sum / 10
		curr.Next = &ListNode{sum % 10, nil}
		curr = curr.Next
		if p != nil {
			p = p.Next
		}
		if q != nil {
			q = q.Next
		}
	}
	if carry > 0 {
		curr.Next = &ListNode{carry, nil}
	}
	return dummyHead.Next
}

func TestAddTwoNumbers() {
	node12 := ListNode{1, nil}
	node11 := ListNode{9, &node12}

	node22 := ListNode{9, nil}
	node21 := ListNode{9, &node22}

	n := AddTwoNumbers(&node11, &node21)
	for n != nil {
		fmt.Print(n.Val)
		n = n.Next
	}
	fmt.Println("")
}

Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

package leetcode

import "sort"

func ArrayPairSum(nums []int) int {
	sort.Ints(nums)
	r := 0
	for i := 0; i < len(nums); i = i + 2 {
		r += nums[i]
	}
	return r
}

Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
Note: The merging process must start from the root nodes of both trees.
package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func MergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	}
	if t2 == nil {
		return t1
	}
	t1.Val += t2.Val
	t1.Left = MergeTrees(t1.Left, t2.Left)
	t1.Right = MergeTrees(t1.Right, t2.Right)
	return t1
}

Hamming Distance

Hamming Distance

package leetcode

import "fmt"
import "math/big"

func HammingDistance(x int, y int) int {
	bin, diff := fmt.Sprintf("%b", x^y), 0
	for i := 0; i < len(bin); i++ {
		if string(bin[i]) == "1" {
			diff++
		}
	}
	return diff
}

func HammingDistance2(x int, y int) int {
	var count int
	z := x ^ y
	d := big.NewInt(int64(z))
	for _, x := range d.Bits() {
		for x != 0 {
			x &= x - 1
			count++
		}
	}
	return count
}

出梁庄记

读完<<出梁庄记>>想到的两句话:

我年纪还轻,阅历不深的时候,我父亲教导过我一句话,我至今还念念不忘。 “每逢你想要批评任何人的时候, ”他对我说,“你就记住,这个世界上所有的人,并不是个个都有过你拥有的那些优越条件。” ——菲茨杰拉德 了不起的盖茨比

他十几岁出去打工,我十几岁出去上学,我们的生活越来越远……想起他时,只是故乡回忆中的美好风景,至于那风景中真实的人和人生,我其实是不关心的。是的,很多时候,当风景中的人走出来,向你伸出求援之手,或者,只是到你的家里坐一坐,你真的如你想象中的那么热情吗?——梁鸿《出梁庄记》

Disruptor with multiple consumers so that each event is only consumed once?

There are 2 approaches, the first is to use the WorkerPool. The second it to use the ‘striped’ EventHandler approach described below.

If we have 4 handlers and assign each an ordinal (0 through 3), then the consumer need only do a modulo operation using the sequence number and the number of consumers and compare it to its ordinal value.

public final class MyHandler implements EventHandler<ValueEvent>
{
    private final long ordinal;
    private final long numberOfConsumers;

    public MyHandler(final long ordinal, final long numberOfConsumers)
    {
        this.ordinal = ordinal;
        this.numberOfConsumers = numberOfConsumers;
    }

    public void onEvent(final ValueEvent entry, final long sequence, final boolean onEndOfBatch)
    {
        if ((sequence % numberOfConsumers) == ordinal)
        {
            // Process the event
        }
    }
}

Some would ask if one consumer takes too long on a transaction it will block all queued on that ordinal. Technically this is possible but one must consider that the batching effect then kicks in thus saving cost for those behind. With this approach the concurrency costs are so low you may find even small stalls are less costly than a queue based alternative.

DisruptorFrequently-Asked-Questions
并发框架Disruptor译文

Java gotchas

https://www.owasp.org/index.php/Java_gotchas

Equality

Object equality is tested using the == operator, while value equality is tested using the .equals(Object) method.

For example:

String one = new String("abc");
String two = new String("abc");
String three = one;
if (one != two) System.out.println("The two objects are not the same.");
if (one.equals(two)) System.out.println("But they do contain the same value");
if (one == three) System.out.println("These two are the same, because they use the same reference.");

The output is:

The two objects are not the same.
But they do contain the same value
These two are the same, because they use the same reference.

Also, be aware that:

String abc = "abc"

and

String abc = new String("abc");

are different. For example, consider the following:

String letters = "abc";
String moreLetters = "abc";
System.out.println(letters==moreLetters);

The output is:

true

This is due to the compiler and runtime efficiency. In the compiled class file only one set of data “abc” is stored, not two. In this situation only one object is created, therefore the equality is true between these object. However, consider this:

String data = new String("123");
String moreData = new String("123");
System.out.println(data==moreData);

The output is:

false

Even though one set of data “123” is stored in the class, this is still treated differently at runtime. An explicit instantiation is used to create the String objects. Therefore, in this case, two objects have been created, so the equality is false. It is important to note that “==” is always used for object equality and does not ever refer to the values in an object. Always use .equals when checking looking for a “meaningful” comparison.

Immutable Objects / Wrapper Class Caching

Since Java 5, wrapper class caching was introduced. The following is an examination of the cache created by an inner class, IntegerCache, located in the Integer cache. For example, the following code will create a cache:

Integer myNumber = 10

or

Integer myNumber = Integer.valueOf(10);

256 Integer objects are created in the range of -128 to 127 which are all stored in an Integer array. This caching functionality can be seen by looking at the inner class, IntegerCache, which is found in Integer:

 private static class IntegerCache 
 {
   private IntegerCache(){}
   
   static final Integer cache[] = new Integer[-(-128) + 127 + 1];
 
   static 
   {
     for(int i = 0; i < cache.length; i++)
     cache[i] = new Integer(i - 128); 
   }
 }
    
 public static Integer valueOf(int i) 
 {
	final int offset = 128;
	if (i >= -128 && i <= 127) // must cache 
        { 
	    return IntegerCache.cache[i + offset];
	}
        return new Integer(i);
 }

So when creating an object using Integer.valueOf or directly assigning a value to an Integer within the range of -128 to 127 the same object will be returned. Therefore, consider the following example:

Integer i = 100;
Integer p = 100;
if (i == p)  System.out.println("i and p are the same.");
if (i != p)   System.out.println("i and p are different.");	
if(i.equals(p))  System.out.println("i and p contain the same value.");

The output is:

i and p are the same.
i and p contain the same value.

It is important to note that object i and p only equate to true because they are the same object, the comparison is not based on the value, it is based on object equality. If Integer i and p are outside the range of -128 or 127 the cache is not used, therefore new objects are created. When doing a comparison for value always use the “.equals” method. It is also important to note that instantiating an Integer does not create this caching. So consider the following example:

Integer i = new Integer (100);
Integer p = new Integer(100);
if(i==p) System.out.println(“i and p are the same object”);
if(i.equals(p)) System.out.println(“ i and p contain the same value”);

In this circumstance, the output is only:

i and p contain the same value

Remember that “==” is always used for object equality, it has not been overloaded for comparing unboxed values.

This behavior is documented in the Java Language Specification section 5.1.7. Quoting from there:

If the value p being boxed is true, false, a byte, a char in the range \u0000 to \u007f, or an int or short number between -128 and 127, then let r1 and r2 be the results of any two boxing conversions of p. It is always the case that r1 == r2.

The other wrapper classes (Byte, Short, Long, Character) also contain this caching mechanism. The Byte, Short and Long all contain the same caching principle to the Integer object. The Character class caches from 0 to 127. The negative cache is not created for the Character wrapper as these values do not represent a corresponding character. There is no caching for the Float object.

BigDecimal also uses caching but uses a different mechanism. While the other objects contain a inner class to deal with caching this is not true for BigDecimal, the caching is pre-defined in a static array and only covers 11 numbers, 0 to 10:

// Cache of common small BigDecimal values.
private static final BigDecimal zeroThroughTen[] = {
new BigDecimal(BigInteger.ZERO,		0,  0),
new BigDecimal(BigInteger.ONE,		1,  0),
new BigDecimal(BigInteger.valueOf(2),	2,  0),
new BigDecimal(BigInteger.valueOf(3),	3,  0),
new BigDecimal(BigInteger.valueOf(4),	4,  0),
new BigDecimal(BigInteger.valueOf(5),	5,  0),
new BigDecimal(BigInteger.valueOf(6),	6,  0),
new BigDecimal(BigInteger.valueOf(7),	7,  0),
new BigDecimal(BigInteger.valueOf(8),	8,  0),
new BigDecimal(BigInteger.valueOf(9),	9,  0),
new BigDecimal(BigInteger.TEN,		10, 0),
};

As per Java Language Specification(JLS) the values discussed above are stored as immutable wrapper objects. This caching has been created because it is assumed these values / objects are used more frequently.

Incrementing Values

Be careful of the post-increment operator:

 int x = 5;
 x = x++;
 System.out.println( x );

The output is:

5

Remember that the assignment completes before the increment, hence post-increment. Using the pre-increment will update the value before the assignment. For example:

int x = 5;
x = ++x;
System.out.println( x );

The output is:

6

Garbage Collection

Overriding “finalize()” will allow you to define you own code for what is potentially the same concept as a destructor. There are a couple of important points to remember:

  • “finalize()” will only ever by called once (at most) by the Garbage Collector.
  • It is never a guarantee that “finalize()” will be called i.e. that an object will be garbage collected.
  • By overriding “finalize()” you can prevent an object from ever being deleted. For example, the object passes a reference of itself to another object.
  • Garbage collection behaviour differs between JVMs.

Boolean Assignment

Everyone appreciates the difference between “==” and “=” in Java. However, typos and mistakes are made, and often the compiler will catch them. However, consider the following:

boolean theTruth = false;
if (theTruth = true)
{
 System.out.println("theTruth is true");
}
else
{
 System.out.println("theTruth is false;");
}

The result of any assignment expression is the value of the variable following the assignment. Therefore, the above will always result in “theTruth is true”. This only applies to booleans, so for example the following will not compile and would therefore be caught by the compiler:

int i = 1;
if(i=0) {}

As “i” is and integer the comparison would evaluate to (i=0) as 0 is the result of the assignment. A boolean would be expected, due the “if” statement.

Conditions

Be on the look out for any nested “else if”. Consider the following code example:

int x = 3;
if (x==5) {}
else if (x<9)
{
  System.out.println("x is less than 9");
}
else if (x<6)
{
  System.out.println("x is less than 6");
}
else
{
  System.out.println("else");
}

Produces the output:

x is less then 9

So even though the second “else if” would equate to “true” it is never reached. This is because once an “else if” succeeds the remaining conditions will be not be processed.