Given the interface IntIterator
defined in the following, implement the method isDistanceZeroOrOne(IntIterator a, IntIterator b)
to return if the distance between a
and b
is at most one, where the distance is defined as the minimum number of modifications to make them equal to each other. Modifications can be: 1) change an int in a
. 2) insert an int to a
. 3) remove an int from a
. For example, the method should return true
for 1, 2, 2 and 1, 3, 2, 2.
-
public class IteratorDistanceTest {
-
-
interface IntIterator {
-
boolean hasNext();
-
int next();
-
}
-
-
static boolean isDistanceZeroOrOne(IntIterator a, IntIterator b) {
-
boolean trying = false;
-
boolean changable = false;
-
boolean insertable = false;
-
boolean removable = false;
-
for(int aPrevious = 0, bPrevious = 0, aCurrent = 0, bCurrent = 0;
-
; aPrevious = aCurrent, bPrevious = bCurrent) {
-
if(a.hasNext()) {
-
aCurrent = a.next();
-
if(b.hasNext()) { // a != null, b != null.
-
bCurrent = b.next();
-
if(trying) {
-
if(changable) {
-
if(aCurrent != bCurrent) {
-
changable = false;
-
}
-
}
-
if(insertable) {
-
if(bCurrent != aPrevious) {
-
insertable = false;
-
}
-
}
-
if(removable) {
-
if(aCurrent != bPrevious) {
-
removable = false;
-
}
-
}
-
if(!changable && !insertable && !removable) {
-
return false;
-
}
-
} else if(aCurrent != bCurrent) {
-
// start trying all the possibilities.
-
trying = true;
-
changable = true;
-
insertable = true;
-
removable = true;
-
}
-
} else { // a != null, b == null.
-
if(trying) {
-
if(removable && aCurrent == bPrevious) {
-
return !a.hasNext();
-
} else {
-
return false;
-
}
-
} else { // remove a.
-
return !a.hasNext();
-
}
-
}
-
} else {
-
if(b.hasNext()) { // a == null, b != null.
-
bCurrent = b.next();
-
if(trying) {
-
if(insertable && bCurrent == aPrevious) {
-
return !b.hasNext();
-
} else {
-
return false;
-
}
-
} else { // insert b.
-
return !b.hasNext();
-
}
-
} else { // a == null, b == null.
-
// can only fulfill changable if we are trying.
-
return trying ? (changable ? true : false) : true;
-
}
-
}
-
}
-
}
-
-
static IntIterator from(final int[] ints) {
-
return new IntIterator() {
-
-
int i = 0;
-
-
@Override
-
public boolean hasNext() {
-
return i < ints.length;
-
}
-
-
@Override
-
public int next() {
-
return ints[i++];
-
}
-
};
-
}
-
-
@Test
-
public void test() {
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {})
-
, from(new int[] {})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1})
-
, from(new int[] {})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {})
-
, from(new int[] {1})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2})
-
, from(new int[] {1, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 3})
-
, from(new int[] {1, 3, 3})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2})
-
, from(new int[] {1, 3})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {1, 2})
-
, from(new int[] {1, 3, 2, 2})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {1, 3, 2, 2})
-
, from(new int[] {1, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 2})
-
, from(new int[] {1, 3, 2, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 3, 2, 2})
-
, from(new int[] {1, 2, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 2, 2})
-
, from(new int[] {1, 3, 2, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 3, 2, 2})
-
, from(new int[] {1, 2, 2, 2})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {1, 3, 2, 2, 4})
-
, from(new int[] {1, 2, 2, 2, 5})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 3, 2, 3, 4, 5})
-
, from(new int[] {1, 2, 3, 4, 5})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 3, 4, 5})
-
, from(new int[] {1, 3, 2, 3, 4, 5})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {2, 2, 2, 2, 1, 1, 1, 1})
-
, from(new int[] {1, 1, 1, 1, 2, 2, 2, 2})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1})
-
, from(new int[] {2, 1, 2, 1, 2, 1, 2, 1, 2, 1})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {1, 1})
-
, from(new int[] {2, 1, 1, 1})));
-
Assert.assertFalse(isDistanceZeroOrOne(
-
from(new int[] {2, 1, 1, 1})
-
, from(new int[] {1, 1})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2})
-
, from(new int[] {1, 2, 3})));
-
Assert.assertTrue(isDistanceZeroOrOne(
-
from(new int[] {1, 2, 3})
-
, from(new int[] {1, 2})));
-
}
-
}
Post new comment