rajat.shrivastava.aw
BAN USERpublic class Repeat {
public static <T> Iterator<T> repeat(T object, int n) {
return new MyIterator(object, n);
}
private static class MyIterator<T> implements Iterator<T> {
final T object;
int n;
public MyIterator(T object, int n) {
this.object = object;
this.n = n;
}
@Override
public boolean hasNext() {
return n > 0 ? true : false;
}
@Override
public T next() {
if (!hasNext()) throw new IllegalStateException("No element to iterate over");
n--;
return object;
}
}
}
My O(nlogn) solution using TreeSet and custom comparator
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;
/**
* Created by rshrivastava on 10/27/15.
*/
public class CountLargerElements {
private static class Node {
int val;
int count;
int index;
public Node(int v, int i) {
val = v;
index = i;
}
@Override
public boolean equals(Object obj) {
Node other = (Node) obj;
return other.val == val && other.index == index;
}
@Override
public int hashCode() {
return val + index;
}
}
public static int[] countGreater(int[] input) {
Comparator<Node> treeComparator = (first, second) -> {
if (first.equals(second)) return 0;
if (first.val < second.val) {
first.count = second.count + 1;
return -1;
} else {
return 1;
}
};
TreeSet<Node> treeSet = new TreeSet<>(treeComparator);
for (int i = input.length - 1; i >= 0; --i) {
Node node = new Node(input[i], i);
treeSet.add(node);
}
int[] result = new int[input.length];
treeSet.stream().forEach(node -> result[node.index] = node.count);
return result;
}
public static void main(String[] args) {
int[] input = new int[]{3, 4, 5, 9, 2, 1, 3};
System.out.println(Arrays.toString(countGreater(input)));
}
}
Solution using heap
public class MergeArrays {
public int[] mergeSortedArrays(List<int[]> input) {
PriorityQueue<HeapNode> priorityQueue = new PriorityQueue<>();
input.stream().forEach(arr -> priorityQueue.offer(new HeapNode(arr, 0)));
ArrayList<Integer> result = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
HeapNode node = priorityQueue.poll();
result.add(node.arr[node.index]);
if (node.index < node.arr.length - 1) priorityQueue.offer(new HeapNode(node.arr, node.index + 1));
}
return result.stream().mapToInt(i -> i).toArray();
}
private static class HeapNode implements Comparable {
int[] arr;
int index;
public HeapNode(final int[] input, int i) {
arr = input;
index = i;
}
@Override
public int compareTo(Object o) {
HeapNode other = (HeapNode) o;
if (this.arr[index] < other.arr[other.index]) return -1;
if (this.arr[index] > other.arr[other.index]) return 1;
return 0;
}
}
}
public int[] mergeSortedArrays(List<int[]> input) {
TreeMap<Integer, Integer> hash = new TreeMap<>();
for (int[] arr : input) {
for (int i : arr) {
if (!hash.containsKey(i)) hash.put(i, 1);
else {
hash.put(i, hash.get(i) + 1);
}
}
}
ArrayList<Integer> list = new ArrayList<>();
for (Entry<Integer, Integer> entry : hash.entrySet()) {
int count = entry.getValue();
while (count > 0) {
list.add(entry.getKey());
count--;
}
}
return list.stream().mapToInt(i -> i).toArray();
}
public class GoogleLogs {
private static int[] durationLogs;
public static final int MAX = 123123;
public static final int MIN = 10100;
public static void main(String[] args) throws IOException {
durationLogs = new int[MAX - MIN + 1];
String dirPath = args[0];
String fileName = args[1];
// run loop in case of multiple files
readFile(dirPath, fileName);
int maxUsage = Integer.MIN_VALUE, duration = 0;
for (int i = 1; i < MAX - MIN; ++i) {
durationLogs[i] += durationLogs[i - 1];
if (durationLogs[i] > maxUsage) {
maxUsage = durationLogs[i];
duration = i + MIN;
}
}
System.out.printf("Max Usage %d is at time %d", maxUsage, duration);
}
private static void readFile(String dir, String fileName) throws IOException {
Path path = Paths.get(dir, fileName);
try (Stream<String> lines = Files.lines(path)) {
lines.forEach(line -> {
String[] words = line.split(" ");
int start = Integer.parseInt(words[0]);
int end = Integer.parseInt(words[1]);
int usage = Integer.parseInt(words[2]);
durationLogs[start - MIN] += usage;
});
}
}
}
what should happen if I have additional log entry like 100205 100207 5 in your example????
- rajat.shrivastava.aw September 22, 2015Most of the solution I am seeing assumes that we have memory large enough to store all the logs in memory for sorting. How would solution change if I cannot bring all the nodes in memory for sorting??? Just curious!!!!!
- rajat.shrivastava.aw September 22, 2015public class ListCompression {
public static void compressList(List<Integer> input) {
for (int i = 0; i < input.size(); ++i) {
int j = i;
while (j + 1 < input.size() && input.get(j + 1) - input.get(j) <= 1) j++;
if (input.get(j) != input.get(i))
System.out.print(input.get(i) + "-" + input.get(j) + ",");
else
System.out.print(input.get(i) + ",");
i = j;
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(10);
list.add(25);
list.add(26);
list.add(30);
list.add(31);
list.add(32);
list.add(33);
compressList(list);
}
}
Repcinderellagale, Financial Application Engineer at Continental
Working as a Forecasting Analyst at Thorofare for more than three years. There, I am responsible for developing detailed business ...
RepAadhikLee, abc at 8x8
Expedite data entry efforts and bank reconciliation under the direct guidance of the senior accountant, ensuring clean, accurate financial records ...
Repha1904536, Android test engineer at ABC TECH SUPPORT
Hello, I am an Executive recruiter. My role is to fill executive, high-level positions at companies. I have been practicing ...
Repnnelsonvance, Animator at Cognzant Technology Solutions
I am the learning and development manager and play a key role in coordinating all corporate learning and development activities ...
RepSimonPister, Blockchain Developer at Absolute Softech Ltd
Simon , a food scientist , records the Tracking status of all existing ingredients during the review and updating process and communicates ...
In java there is a data structure called LinkedHashMap which has properties of both map and list.. not sure what the interviewer was looking for..
- rajat.shrivastava.aw November 16, 2015