[Hard] interview questions #10

[rygh4775]

[rygh4775]

Solution 1

Brute force w/o time complexity limit

int findMajaorElement(int[] array) {
  for (int x : array) {
    if(validate(array, x)) {
      return x;
    }
  }
  return -1;
}

boolean vlidate(int[] array, int x) {
  int count = 0;
  for(int n : array) {
    if(x == n) {
      count++;
    }
  }
  return count >= array.length / 2;
}

Solution 2

3	1	7	1	1	7	7	3	7	7	7
0	1	2	3	4	5	6	7	8	9	10

validate(3)
    sess 3 -> countYes = 1, countNo = 0
    sess 1 -> countYes = 1, countNo = 1
    TERMINATE. 3 is not majority anymore.
validate(1)
    sess 1 -> countYes = 1, countNo = 0
    sess 7 -> countYes = 1, countNo = 1
    TERMINATE. 1 is not majority anymore.
validate(7)
        sess 7 -> countYes = 1, countNo = 0
        sess 1 -> countYes = 1, countNo = 1
        TERMINATE. 7 is not majority anymore.
validate(1)
    sess 1 -> countYes = 1, countNo = 0
    sess 1 -> countYes = 2, countNo = 0
        sess 7 -> countYes = 2, countNo = 1
        sess 7 -> countYes = 2, countNo = 2
        TERMINATE. 1 is not majority anymore.
validate(1)
    sess 1 -> countYes = 1, countNo = 0
    sess 7 -> countYes = 1, countNo = 1
    TERMINATE. 1 is not majority anymore.
validate(7)
    sess 7 -> countYes = 1, countNo = 0
    sess 7 -> countYes = 2, countNo = 0
    sess 3 -> countYes = 2, countNo = 1
    sess 7 -> countYes = 3, countNo = 1
    sess 7 -> countYes = 4, countNo = 1
    sess 7 -> countYes = 5, countNo = 1

validate(3)
    sess 3 -> countYes = 1, countNo = 0
    sess 1 -> countYes = 1, countNo = 1
    TERMINATE. 3 is not majority anymore.
validate(7)
    sess 7 -> countYes = 1, countNo = 0
    sess 1 -> countYes = 1, countNo = 1
    TERMINATE. 7 is not majority anymore.
validate(1)
    sess 1 -> countYes = 1, countNo = 0
    sess 7 -> countYes = 1, countNo = 1
    TERMINATE. 1 is not majority anymore.
validate(7)
    sess 7 -> countYes = 1, countNo = 0
    sess 3 -> countYes = 1, countNo = 0
    TERMINATE. 7 is not majority anymore.
validate(7)
    sess 7 -> countYes = 1, countNo = 0
    sess 7 -> countYes = 2, countNo = 0
    sess 7 -> countYes = 3, countNo = 0

int findMajorityElement(int[] array) {
  int candidate = getCandidate(array);
  if(validate(array, candidate) {
  return candidate;  
}
  return -1;
}

int getCandidate(int[] array) {
  int majority = 0;
  int count = 0;
  for(int n : array) {
    if(count == 0) {
      majority = n;
    }
    if(n == majority) {
      count++;
    } else {
      count--;
    }
  }
}

boolean validate(int[] array, int majority) {
  int count = 0;
  for (int n : array) {
    if(n == majority) {
      count++;
    }
  }
  return count > array.length / 2;
}