soodongStudying
BAN USERThis is a fast set.
By set's concept of set and get, you can add and remove element in O(1).
Issue here is, you can not get random element from this DS.
What we need to do for resolving this, we need one map and one array.
In map, we will have key and value (let's say that value is a Node)
In array, there will be a item like the following:
Node.1 - Node.2 - Node.3 - Node.4
In Map, there will be key value-pairs like
<key.1, Node.1>, <key.2, Node.2>, <key.3, Node.3>, <key.4, Node.5>
In this case, add certainly be O(1), since you can add new node to list and map via O(1).
Get random element also be O(1) since you can retrieve any value from the list.
Real issue remaining at this point is: then, how do delete something at O(1)?
There is a magic:
When you need to delete with some element that is located interim of list.
Swap that element with the last element of the list. Then delete the last.
Yes!, since you remove last element from the list, it will be O(1).
Code will look like:
public class FastSet { // add, remove, get, all behaviors are done at O(1)
private static final Random RANDOM = new Random();
private final Map<String, FastSetNode> strCache;
private final List<FastSetNode> posCache;
private int position = 0;
FastSet() {
strCache = new HashMap<>();
posCache = new ArrayList<>();
}
public boolean addItem(String input) {
if (strCache.containsKey(input)) {
return false;
}
FastSetNode n = new FastSetNode(input, position);
strCache.put(input, n);
posCache.add(position++, n);
return true;
}
public boolean removeItem(String input) {
if(!strCache.containsKey(input)) {
return false;
}
FastSetNode removal = strCache.remove(input); //Change this removal node with end node
FastSetNode finalOne = posCache.remove(--position);
// Delete the final element from list
if (removal.equals(finalOne)) {
return true;
}
posCache.set(removal.position, finalOne);
finalOne.position = removal.position;
return true;
}
public String get() {
int randomPosition = RANDOM.nextInt(position);
return posCache.get(randomPosition).data;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
posCache.stream().forEach((dNode) -> {
str.append(dNode.toString()).append("\n");
});
return str.toString().substring(0, str.toString().length() - 1);
}
public static class FastSetNode {
private final String data;
private int position;
private FastSetNode(String data, int position) {
this.data = data;
this.position = position;
}
}
Server capacity limits: 1, 3
Task capacity needs: 4
In this case, the above code returns 'true' that is not expected behavior.
servers[j] >= tasks[i] needs be changed into '>'?
If we use a Set, we can do this at O(n).
If str is not existed -> add
if str is existed -> delete
That is, odd number occurrence will lead "existence". However, even number occurrence will lead "not existence" in a set.
public static Optional<String> findEvenNumberExistedWord(String[] arr) {
Set<String> cache = new HashSet<>();
for (String str : arr) {
if (!cache.add(str)) {
cache.remove(str);
}
}
for (String str : arr) {
if (!cache.contains(str)) {
return Optional.of(str);
}
}
return Optional.absent();
}
public static void main(String[] args) {
String[] input = {"abc","def","klm", "lod", "lod", "abc","def","klm" , "abc","def","klm"};
Optional<String> result = findEvenNumberExistedWord(input);
print(result.get());
}
To solve this question, we can use a Topological Sort.
Actually, we need starting nodes that do not have any dependency. (That is, no incoming edge)
Let's call that those nodes are 'starting' nodes.
From 'starting' nodes, we can get each edge from them. And remove connections.
For example, if I have the following build dependencies:
a -> d
a- > b
b -> c
Only 'a' is a starting node. From 'a', I can remove from/to relationships from other nodes.
When other node also become 'starting' node that is not having incoming edges, I use this node again.
If I keep continuing this processes, I will get build file processing order.
public class TopologicalSort {
public static String retrieveBuildsOrder(Task[] tasks) {
checkArgument(tasks != null && tasks.length > 0);
Map<String, Graph.Node> cache = intialize(tasks);
List<Graph.Node> startingNodes = new ArrayList<>();
cache.entrySet().stream().filter(
(entry) -> (entry.getValue().inEdges.isEmpty())).forEach((entry) -> {
startingNodes.add(entry.getValue());
});
List<Graph.Node> result = new ArrayList<>();
while (!startingNodes.isEmpty()) {
Graph.Node removal = startingNodes.remove(0);
result.add(removal);
int j = 0, outEdgeSize = removal.outEdges.size();
while (j < outEdgeSize) {
Graph.Edge e = removal.outEdges.remove(0);
Graph.Node target = e.to;
// Remove <-> relationship from/to nodes.
target.inEdges.remove(e);
// If target node's inEdges is empty, this target node can be categorized as a new starting node.
if (target.inEdges.isEmpty()) {
startingNodes.add(target);
}
j++;
}
}
for(Map.Entry<String, Graph.Node> entry : cache.entrySet()) {
if (!entry.getValue().inEdges.isEmpty()) {
investigateCyclicNode(entry.getValue());
throw new IllegalArgumentException("Cyclic connection detected");
}
}
StringBuilder stringResult = new StringBuilder();
for (Graph.Node n : result) {
stringResult.append(n.toString()).append(",");
}
return stringResult.append("end").toString();
}
private static Map<String, Graph.Node> intialize(Task[] tasks) {
Map<String, Graph.Node> cache = new HashMap<>();
for (Task task : tasks) {
Graph.Node n1 = cache.get(task.from);
if (n1 == null) {
n1 = new Graph.Node(task.from);
cache.put(task.from, n1);
}
Graph.Node n2 = cache.get(task.to);
if (n2 == null) {
n2 = new Graph.Node(task.to);
cache.put(task.to, n2);
}
n1.addEdge(n2);
}
return cache;
}
private static void investigateCyclicNode(Graph.Node node) {
print("Name of node creating cyclic: " + node.toString());
for (Graph.Edge e : node.inEdges) {
print(e);
}
}
public static void main(String[] args) {
Task task1 = new Task("7", "11");
Task task2 = new Task("7", "8");
Task task3 = new Task("5", "11");
Task task4 = new Task("3", "8");
Task task5 = new Task("3", "10");
Task task6 = new Task("11", "2");
Task task7 = new Task("11", "9");
Task task8 = new Task("11", "10");
Task task9 = new Task("8", "9");
Task task10 = new Task("8", "10");
Task[] tasks = new Task[]{task1, task2, task3, task4, task5, task6, task7, task8, task9, task10};
print(retrieveBuildsOrder(tasks)+"\n");
Task invalidBuild = new Task("2", "11");
tasks = new Task[]{task1, task2, task3, task4, task5, task6, task7, task8, task9, task10, invalidBuild};
try {
print(retrieveBuildsOrder(tasks));
} catch(IllegalArgumentException expected) {
print("Cyclic detected, there should be an exception");
}
}
}
class Task {
final String from;
final String to;
Task(String from, String to) {
this.from = from;
this.to = to;
}
}
The solution for this question is knowing the repetition of quotient.
For example, 1/3 is 0.33333, so it would be 0.(3)
If we see detail of this:
1/3 = 0, remainder :1
1 * 10 -> 10/3 -> 3, remainder :1
1 * 10 -> 10/3 -> 3, remainder: 1 (Now, we can know that same quotient is detected, since
this is decimal places based number, actually, if you detect same quotient + remainder combo, you come to know that there will be repetition)
public static String divisionToString(int num1, int num2){
int quotient = num1 / num2;
int remains = num1 % num2;
if (remains == 0) {
return String.valueOf(quotient);
}
StringBuilder remainder = new StringBuilder(quotient + ".");
remains *= 10;
Map<String, Integer> cache = new HashMap<>();
int position = 2;
while(remains != 0) {
int q = remains / num2;
remains = remains % num2;
String key = q+","+remains;
if (cache.containsKey(key)) { // Repition happens
int prePosition = cache.get(key);
String temp = remainder.toString();
return temp.substring(0, prePosition) + "(" + temp.substring(prePosition, position) + ")";
}
remainder.append(q);
cache.put(key, position++);
remains *= 10;
}
return remainder.toString();
}
We can use bit mapping concept to make a subset.
For example, if we have the set like {a, b, c};
We will have no a, no b, no c, yes a, no b, no c, and so on until yest a, yes b, yes c.
public static Set<List<String>> getAllPowerSets(List<String> input) {
assert(input != null);
int maxNumOfSets = 1 << input.size();
int i = 0;
Set<List<String>> result = new HashSet<>();
while (i < maxNumOfSets) {
result.add(getEachSubSet(input, i));
i++;
}
return result;
}
private static List<String> getEachSubSet(List<String> input, int cutOff) {
int index = 0;
List<String> subSet = new ArrayList<>();
while(cutOff > 0) {
if ((cutOff & 1) == 1) {
subSet.add(input.get(index));
}
cutOff = cutOff >> 1;
index++;
}
return subSet;
}
Can we just simply get sums of two arrays? Then, sum of server capacity is greater than sum of tasks, it will be true. Am I missing anything?
- soodongStudying August 05, 2014There can be three cases:
1. {1,2,3,4,5,7,1,1,1,1} // 1 is the answer
2. {1,2,3,5,9,10,3,3,3,3} // 3 is the answer
3. {1,2,9,9,9,6,7,9,9,4} // 9 is the answer
If we use quick select for the 5th position (5 is half of 10)
Array will be sorted like
1. {1,1,1,1,1, other numbers greater than 1}
2. {numbers less than 3, 3,3,3,3,3, numbers greater than 3}
3. {1,2,7,6,8,9,9,9,9,9}
In any case, you can do quick select for 5th index number.
Then, for case.1 and case.2, you can simply check that there are 5 numbers of this value.
In case.3, all numbers from index.5 to index.9 will be equal.
Codes:
public static int findFiveTimesRepetiveNum(int[] arr) {
assert(arr != null || arr.length == 10);
int selectedNum = arr[quickIndexSelect(arr, 5)];
int count = 0;
for (int i : arr) {
if (i == selectedNum) {
count++;
}
}
if (count == 5) return selectedNum; // It covers case.1 and case.2
for (int j = 5; j < arr.length; j++) {
// In case.2, we need to figrue out all numbers from index 5~inedx.9 are equal
if (arr[j] != arr[5]) {
return -1;
}
}
return arr[5];
}
public static void main (String[] args) {
int[] case1 = new int[]{1,2,3,4,5,7,1,1,1,1};
int[] case2 = new int[]{1,2,3,5,9,10,3,3,3,3};
int[] case3 = new int[]{1,2,9,9,9,6,7,9,9,4};
print("Expect 1: " + findFiveTimesRepetiveNum(case1));
print("Expect 3: " + findFiveTimesRepetiveNum(case2));
print("Expect 9: " + findFiveTimesRepetiveNum(case3));
int[] canNotFound = new int[]{1,2,3,4,5,6,7,8,9,10};
print("Expect -1(Can not found): " + findFiveTimesRepetiveNum(canNotFound));
9, 9, 9, 8, 10, << input you posted is not sorted.
Can we assume that array was already sorted and then this was rotated to the right by a certain distance?
Actually, this question is very similar to 'how to find kth item in two sorted array with size N'.
For median, if sum of length is even, we need to find, 2n/2 + 2n/2+1. When sum of length is odd, we can simply find the number at 2n/2 position.
public static double findMedian(int[] a /* array1 */, int[] b /* array2 */) {
int median = getMedian(a.length, b.length);
if (median == 0) throw new IllegalArgumentException("Can not get median");
if (a[a.length - 1] <= b[0] || b[b.length-1] <= a[0]) {
return preProcessing(a, b, median);
}
if ((a.length + b.length)%2 == 0) {
return (findMedian(a, 0, b, 0, median) + findMedian(a, 0, b, 0, median + 1))/ 2; // 2logK -> O(logK)
}
return findMedian(a, 0, b, 0, median); // logK
}
private static double findMedian(int[] a, int aS, int[] b, int bS, int median /* median */) {
if (median == 1) {
return min(a[aS], b[bS]);
}
if (a[aS + median/2 -1] <= b[bS + median/2 -1] ) {
return findMedian(a, aS + median/2, b, bS, median - (median/2));
} else{
return findMedian(a, aS, b, bS + median/2, median - (median/2));
}
}
How about this?
I can solve without extra storage.
1. First, I will do quick select for the median position.
2. See the left side of median to find maximum candidate.
1 will take 2n on the vatage, 2 will take n, so total 3n, leading O(n).
public static Result findMax_N_Num_HavingMorethanOrEqual_N_Num_in_unsortedArray(int[] arr) {
validateArray(arr);
assert(arr.length >= 2);
int halfLen = arr.length/2 + arr.length%2;
int medianIndex = quickIndexSelect(arr, halfLen);
int maxNum = 0;
boolean isFound = false;
for (int i = medianIndex; i >=0; i--) {
if (arr[i] <= (halfLen)) {
isFound = true;
maxNum = Math.max(maxNum, arr[i]);
}
}
return new Result(isFound, isFound ? maxNum : null);
}
private static class Result {
private final boolean isFound;
private final Integer num;
private Result(boolean isFound, Integer num) {
this.isFound = isFound;
this.num = num;
}
}
Is palindrome can be a compared string?
So, KOK, or LOL can be a string?
Can you run the following result?
It returns 6, we expect 5:
8, 1, 2, 4, 0, 7, 1, 3, 8
When I provide input 4, 6 ( a == 4, b == 6), it returns 256, however, expected result is 4096.
- soodongStudying April 29, 2014We do not need 'nlogn', we only need O(n). As mentioned above, it is a Kadane Algorithm.
int length ;
int a[]={-12, 14, 0, -4, 61, -39};
length = a.length;
int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
for (int index = 0; index < length;index++) {
localMax= localMax + a[index];
if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
if(absoluteMax < localMax) {
absoluteMax = localMax;
lastIndex = index;
startIndex = tempStartIndex;
}
}
How about this?
list of string -> Map of Integer to List.
For key of this map, I will use hash function which just take ascii value of chars in each string.
It's like pre-processing.
If one of those key has a value of list whose size is bigger than 1, it means that this list 'may' have a candidate of anagram.
In this case, I sort every string in this list, and put them into a 'Set'. If there are collisions,
it means "there is a anagram".
public static boolean checkAnagrams(String[] strings) {
Map<Integer, List<String>> result = createMap(strings);
for (int key : result.keySet()) {
if (result.get(key).size() > 1) {
Set<String> set = new HashSet<>();
for (String s : result.get(key)) {
char[] target = s.toCharArray();
Arrays.sort(target);
if (set.contains(new String(target))) {
return true;
}
set.add(new String(target));
}
}
}
return false;
}
private static Map<Integer, List<String>> createMap(String[] strings) {
System.out.println("Come to createMap");
Map<Integer, List<String>> info = new HashMap<>();
for (String s: strings) {
int currentHash = getHash(s);
List<String> results;
if (info.containsKey(currentHash)) {
results = info.get(currentHash);
} else {
results = new ArrayList<>();
}
results.add(s);
info.put(currentHash, results);
}
return info;
}
private static int getHash(String input) {
int hashValue = 0;
for (char c : input.toCharArray()) {
hashValue += (int) c;
}
return hashValue;
}
What is the Big-O notation for this? Since you iterate array at most 2 times, it will be 2n, so O(n)?
- soodongStudying April 26, 2014What do we need to change on @babula code if we do not want to use an additional memory?
- soodongStudying April 19, 2014
What does 'p[2000011]' mean?
- soodongStudying November 23, 2014Very big size of int array?