Day3 Interview

1. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Approach:

Linear approach

Check each letter, if does not exist put into hash map, else update hash map value

My Solution:

public class Solution {
public int lengthOfLongestSubstring(String s) {

int index1 = 0;
int index2 = 0;
int sameLetterIndex = 0;
int tempLength = 0;
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for (int i = 0; i < s.length(); i++) {
// check whether in hashMap
if (map.containsKey(s.charAt(i))) {
sameLetterIndex = map.getValue(s.charAt(i));
if (sameLetterIndex < index1) {
index1 = index1;
// map.changeKey s.charAt(i)’s value to i.
map.put(s.charAt(i), i);
} else {
index1 = sameLetterIndex + 1;
// map.changeKey s.charAt(i)’s value to i.
map.put(s.charAt(i), i);
}
} else {
// map.add key as s.charAt(i), value as i; hashmap.put(key, hashmap.get(key) + 1);
map.put(s.charAt(i), i);
// map.addKey(s.charAt(i));
// map.addValue(i) forKey(s.charAt(i));
}
index2++;
tempLength = (index2 – index1) > tempLength? index2 – index1 : tempLength;
}

return tempLength;
}
}

Above code does not correct. The following code was accepted by leetcode.

 

2. Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Approach:

This problem can be converted to the problem of finding kth element, k is (A’s length + B’ Length)/2.

If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.
If k == 0, the kth element is the first element of A or B.

For normal cases(all other cases), we need to move the pointer at the pace of half of an array length.

public static double findMedianSortedArrays(int A[], int B[]) {
	int m = A.length;
	int n = B.length;
 
	if ((m + n) % 2 != 0) // odd
		return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
	else { // even
		return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1) 
			+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
	}
}
 
public static int findKth(int A[], int B[], int k, 
	int aStart, int aEnd, int bStart, int bEnd) {
 
	int aLen = aEnd - aStart + 1;
	int bLen = bEnd - bStart + 1;
 
	// Handle special cases
	if (aLen == 0)
		return B[bStart + k];
	if (bLen == 0)
		return A[aStart + k];
	if (k == 0)
		return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
 
	int aMid = aLen * k / (aLen + bLen); // a's middle count
	int bMid = k - aMid - 1; // b's middle count
 
	// make aMid and bMid to be array index
	aMid = aMid + aStart;
	bMid = bMid + bStart;
 
	if (A[aMid] > B[bMid]) {
		k = k - (bMid - bStart + 1);
		aEnd = aMid;
		bStart = bMid + 1;
	} else {
		k = k - (aMid - aStart + 1);
		bEnd = bMid;
		aStart = aMid + 1;
	}
 
	return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s