[Hard] interview questions #5

[rygh4775]

Letters and Numbers: Given an array filled with letters and numbers, find the longest subarray with an equal number of letters and numbers.

[rygh4775]

문자와 숫자로 구성된 주어진 배열로부터, 문자와 숫자의 개수가 같으면서 가장 긴 부분배열을 구하라

Array: [a, 1, b, c, 2, 3, d]

문자: a / 숫자: 1 --> [a, 1, a, a, 1, 1, a]
count(a, subarray) = count(1, subarry)

Solution 1

len	7	6	6	5	5	5	...1
i	0	0	1	0	1	2	...6
subarray	0,6 (6)	0,5 (5)	1,6 (5)	0,4 (4)	1,5 (4)	2,6 (4)	...6,6 (1)

char[] findLongestSubArray(char[] array) {
  for(int len = array.length; leng > 1; len--) {
    for(int i = 0; i <= array.length - len; i++) {
            if (hasEqualLettersNumbers(array, i, i + len -1)){
            return extractSubArray(array, i, i + len -1);
      }
    }    
  }
}

boolean hasEqualLettersNumbers(char[] array, int start, int end) {
  int counter = 0;
  for(int i = start; i <= end; i++) {
    if(Character.isLetter(array[i]) {
      conter++;
    } else if(Character.isDigit(array[i])) {
      counter--;
    }
  }
    return counter == 0;
}

char[] extractSubarray(char[] array, int start, int end) {
  char[] subarray = new char[end - start + 1];
  for(int i = start; i <= end; i++) {
    subarray[i - start] = array[i];
  }
  return subarray;
}

• Time complexity: O(N²), N is a length of the array

Solution 2

Array: [a, 1, 1, a, 1, a]

	a	1	1	a	1	a
#a	1	1	1	2	2	3
#1	0	1	2	2	3	3

Array: [a, 1, a, a, 1, a, a, 1, 1, a, 1, a]

	a	1	a	a	a	1	a	1	1	a	1	a
#a	1	1	2	3	4	4	5	5	5	6	6	7
#1	0	1	1	1	1	2	2	3	4	4	5	5
-	1	0	1	2	3	2	3	2	1	2	1	2

4 - 2 = 7 - 5
deltaA = deltaB
subarray = (array, index of deltaA + 1, index of deltB)

char[] findLongestSubarray(char[] array) {
  int[] deltas = computeDeltaArray(array);

  int[] match = findLongestMatch(deltas);

  return extract(array, match[0]+1, match[1]);
}

int[] computeDeltaArray(char[] array) {
  int[] deltas = new int[array.length];
  int delta = 0;
  for(int i = 0; i < array.length; i++) {
    if(Character.isLetter(array[i])) {
    delta++;
    } else if(Character.isDigit(array[i])) {
      delta--;
    }
    deltas[i] = delta; 
  }
  return deltas;
}

int[] findLongestMatch(char[] deltas) {
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>;
  map.put(0, -1);
  int[] max = new int[2];
  for (int i = 0; i < deltas.lengt; i++) {
    if(!map.containKey(deltas[i])) {
      map.put(deltas[i], i);
    } else {
      int match = map.get(deltas[i]);
      int distance = i - match;
      int longest = max[1] - max[0];
      if(distance > longest) {
        max[0] = match;
        max[1] = i;
      }
    }
  }
  return max;
}

• Time complexity: O(N), N is a length of the array