damluar
BAN USERThis algorithm reverses a list as it goes through it. For example, let's say we have a list e -> b -> c -> b -> a -> b -> c -> h. When we reach 'a', the list will look something like this e <- b <- c <- b <- a -> b -> c -> h. Now we just go in both directions from `a` and compare characters.
We check for both cases: if palindrome is even (aabb) and odd (abcba).
This "solution" goes through large array even if only a single log record was passed to it.
The array is not required. You use it to order start and end times.
Instead you could just have 2 arrays of log records: one sorted by start time and another by end time. Or you could have a single array where you put both start and end times. Then you can sort and process it.
Here is a working solution in O(n * logn) time, and O(n) space.
The idea is to have one array sorted by start time and another one by end time. This allows us to track currently "open" logs.
We go through logs and increase the current memory usage when some interval is opening and decrease memory usage when some interval is closing:
public class MaximumMemoryUsageInLogs {
public static void main(String[] args) {
LogRecord[] logs = new LogRecord[]{new LogRecord("100207", "100209", 4), new LogRecord("100305", "100307", 5),
new LogRecord("100207", "100208", 2), new LogRecord("111515", "121212", 1)};
System.out.println(computeMaximumUsage(logs));
logs = new LogRecord[]{new LogRecord("100207", "100211", 2), new LogRecord("100209", "100215", 5),
new LogRecord("100214", "100218", 3), new LogRecord("100211", "100213", 6),
new LogRecord("100208", "100209", 4)};
System.out.println(computeMaximumUsage(logs));
}
private static String computeMaximumUsage(LogRecord[] logs) {
LogRecord[] byStart = Arrays.copyOf(logs, logs.length);
Arrays.sort(byStart, LogRecord.BY_START);
LogRecord[] byEnd = Arrays.copyOf(logs, logs.length);
Arrays.sort(byEnd, LogRecord.BY_END);
int currentUsage = 0, maxUsage = 0;
String maxTime = "";
int i = 0, j = 0;
while (i < byStart.length) {
if (byStart[i].start.compareTo(byEnd[j].end) > 0) {
currentUsage -= byEnd[j].usage;
j++;
} else {
currentUsage += byStart[i].usage;
if (currentUsage > maxUsage) {
maxUsage = currentUsage;
maxTime = byStart[i].start;
}
i++;
}
}
return maxTime;
}
private static class LogRecord {
private String start;
private String end;
private int usage;
private static Comparator<LogRecord> BY_START = Comparator.comparing(l -> l.start);
private static Comparator<LogRecord> BY_END = Comparator.comparing(l -> l.end);
public LogRecord(String start, String end, int usage) {
this.start = start;
this.end = end;
this.usage = usage;
}
@Override
public String toString() {
return "LogRecord{" +
"start='" + start + '\'' +
", end='" + end + '\'' +
", usage=" + usage +
'}';
}
}
}
One should be careful when to return true. I thought the task asked that the difference is at most 1. But after re-reading think we should find the difference equal exactly 1.
So when we traverse prefix tree and parameter == 0 and we find some node, then we can return true. But if parameter stays 1, we have to search further, because all characters are equal so far.
I would start from amount = 1 and double the amount each time the transaction is successful.
When we get unsuccessful transaction we divide amount by 2 each time until we reach empty account (basically when we can't withdraw 1):
int amount = 1;
while (account.withdraw(amount) > 0) {
amount *= 2;
}
while (!(amount == 1 && account.withdraw(amount) == 0)) {
account.withdraw(amount);
if (amount > 1) {
amount /= 2;
}
}
Your solution is O(n) exactly as any other using split() method. May be it's more efficient by some factor (1,5 or so), but it is easy to make a mistake in your code. I wrote another version using indexOf() instead of split() and it has slightly better performance than yours (tested on a 10^7 element path), but stays still readable.
- damluar July 17, 2015public class PathNormalization {
public static void main(String[] args) {
String path = "\\a\\b\\..\\c\\.\\foo.txt";
System.out.println(path);
System.out.println(normalize(path));
}
public static String normalize(String path) {
List<String> structure = new ArrayList<>();
String[] splittedPath = path.split("\\\\");
for (String dir : splittedPath) {
dir = dir.trim();
if (".".equals(dir) || dir.isEmpty()) {
continue;
}
if ("..".equals(dir.trim())) {
structure.remove(structure.size() - 1);
} else {
structure.add(dir.trim());
}
}
StringBuilder sb = new StringBuilder();
for (String s : structure) {
sb.append("\\");
sb.append(s);
}
return sb.toString();
}
}
public class IncrementIntegerAsArray {
public static void main(String[] args) {
int[] number = {1, 2, 3};
for (int i = 0; i < 876; i++) {
increment(number);
}
System.out.println(Arrays.toString(number));
increment(number);
}
public static void increment(int[] number) {
increment0(number, number.length - 1);
}
public static void increment0(int[] number, int position) {
if (position < 0) {
throw new IllegalArgumentException();
}
if (number[position] < 9) {
number[position]++;
} else {
number[position] = 0;
increment0(number, position - 1);
}
}
}
public class FindMissingNumber {
public static void main(String[] args) {
int[] numbers = {3, 3, 4, 0, 10, 3, 0, 10, 0, 10, 4};
System.out.println(findMissing(numbers));
}
public static int findMissing(int[] numbers) {
Set<Integer> unique = new HashSet<>();
int uniqueSum = 0;
int realSum = 0;
for (int number : numbers) {
realSum += number;
if (!unique.contains(number)) {
uniqueSum += number;
unique.add(number);
}
}
return 3 * uniqueSum - realSum;
}
}
Simple recursive solution:
private static void findCommonPrefixRec(String[] phrases, StringBuilder sb, int pos) {
String sample = phrases[0];
boolean match = Arrays.stream(phrases).allMatch(s -> s.length() > pos && s.charAt(pos) == sample.charAt(pos));
if (match) {
sb.append(phrases[0].charAt(pos));
findCommonPrefixRec(phrases, sb, pos + 1);
}
}
Java implementation that does non-recursive in-order traversal using a stack.
public class TreeIterator implements Iterator<TreeNode> {
Stack<TreeNode> inorder = new Stack<>();
public TreeIterator(TreeNode node) {
goAsLeftAsPossible(node);
}
public void inorderTraversal() {
goAsLeftAsPossible(inorder.pop().right);
}
private void goAsLeftAsPossible(TreeNode node) {
while (node != null) {
inorder.push(node);
node = node.left;
}
}
@Override
public boolean hasNext() {
return !inorder.isEmpty();
}
@Override
public TreeNode next() {
if (!hasNext()) {
throw new IllegalStateException();
}
TreeNode next = inorder.peek();
inorderTraversal();
return next;
}
}
copy paste from stackoverflow
- damluar November 30, 2015