boaznahum
BAN USER"remove" should remove the last returend value.
so:
Iterator<String> iter = repeat("Test repeater", 7);
while (iter.hasNext()) {
System.out.println(iter.next());
iter.remove();
}
should print 7 values, I think you code doesn't. should be:
@Override
public void remove() {
// Simply do nothing
}
Use min heap to hold M values from M sorted arrays, O(N*log M), N total number of elements
static class Row<T> {
Iterator<T> aRow;
T currentValue;
public Row(Iterator<T> aRow) {
this.aRow = aRow;
// currentValue is undefined
}
T getV() {return currentValue ;}
boolean advance() {
if (aRow.hasNext()) {
currentValue = aRow.next();
return true;
} else {
return false;
}
}
@Override
public String toString() {
return currentValue + ":" + aRow.hasNext();
}
}
@SafeVarargs
static <T extends Comparable<T>> void merge(Consumer<T> downStream,
Collection<T> ... sources) {
PriorityQueue<Row<T>> heap = new PriorityQueue<>(sources.length,
Comparator.comparing(Row::getV));
for (Collection<T> it : sources) {
Row<T> row = new Row<>(it.iterator());
// row has any data?
if (row.advance()) {
heap.add(row);
}
}
while(! heap.isEmpty()) {
Row<T> row = heap.remove();
downStream.accept(row.getV());
// row has more data ?
if (row.advance()) {
heap.add(row);
}
}
}
public static void main(String[] args) {
List<Integer> l1 = Arrays.asList(1,3, 6, 10);
List<Integer> l2 = Arrays.asList(3,3, 10, 20);
List<Integer> l3 = Arrays.asList(1,1, 3);
List<Integer> l4 = Collections.emptyList();
merge(System.out::println, l1, l2, l3, l4);
}
This can be done in O(n), one scan and even in place.
Assume you counter nPostponed and last postponed character.
Imagine that this is buffer of nPostponed x postponed characters.
In addition you have a last character that was copied to output.
So in each iteration you first try to take from the 'postponed' buffer if it is different from 'last'
Otherwise you take next character from source string. If it is equal to 'last' then it also must equal to postponed or postponed is empty. In this case you add it to postponed buffet - increment nPostponed
Otherwise you add this character to output and set 'last' equal to it.
At end, if postponed is not empty than task can't be done.
O(n), one scan and even in place
static boolean rearrange(char[] ar) {
if (ar.length < 2) return true;
int s = 0; // source;
char last = ar[s++];
int t = 1; // destination - first char already there
char postponed = '?'; // buffer is empty it this value is ignored
int nPostponed = 0;
while (s < ar.length || nPostponed > 0) {
// is character in postponed buffer ?
if (nPostponed > 0 && postponed != last) {
// Remove from postponed buffer
ar[t++] = postponed;
--nPostponed;
last = postponed;
} else {
if ( ! (s < ar.length) ) {
// no more to take from
return false;
}
char c = ar[s++];
if (c != last) {
ar[t++] = c;
last = c;
} else {
// so it must equals postponed if the later is not empty
// Add to postponed buffer
++nPostponed;
postponed = c;
}
}
}
return true;
}
Repkalerkant98, abc at ADP
I am DennisRue, seeking an entry level position where my strong work ethics and ability to learn quickly will contribute ...
Replovercast172, Analyst at ADP
I am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...
Replonnacribbs, DIGITAL MARKETING at Athena Health
I am a Market Research Manager responsible for selecting the appropriate research methodology and supporting techniques to meet a defined ...
Repreetaharriet, Applications Developer at Achieve Internet
As a sales clerk, I deal with customers on a daily basis. My work face-to-face assisting customers with finding the ...
Repangilafinch, Applications Developer at Aristocrat Gaming
I am Angila, expert system operator in Linens'n from 2017, Where I interact with network providers and perform troubleshooting ...
@aka - After your fix - Is still linear ?
- boaznahum November 14, 2015