BenC
BAN USERpublic static void findLeafs(int[] arr) {
if (arr == null || arr.length == 0)
return;
Stack<Integer> stack = new Stack<>();
for(int n = 1, c = 0; n < arr.length; n++, c++) {
if (arr[c] > arr[n]) {
stack.push(arr[c]);
} else {
boolean found = false;
while(!stack.isEmpty()) {
if (arr[n] > stack.peek()) {
stack.pop();
found = true;
} else
break;
}
if (found)
System.out.println(arr[c]);
}
}
System.out.println(arr[arr.length-1]);
}
you could create a map of sets. the keys are variables, the set is all the variables it's equal to. then run through each non-equal equation and verify the lhs is not in the rhs's equivalency set, and vice versa.
public static boolean validateFunctions(String[][] equals, String[][] notEquals) {
Map<String, Set<String>> equivalencyMap = new HashMap<>();
// Assume print 2xN matrix where row 0 = lhs and row 1 = rhs
final int lhs = 0;
final int rhs = 1;
for(int i = 0; i<equals.length; i++) {
// Store lhs equivalence
String l = equals[lhs][i];
String r = equals[rhs][i];
addToMap(equivalencyMap, l, r);
addToMap(equivalencyMap, r, l);
}
for(int i = 0; i<equals.length; i++) {
// Store lhs equivalence
String l = notEquals[lhs][i];
String r = notEquals[rhs][i];
if(checkMap(equivalencyMap, l, r))
return false;
if (checkMap(equivalencyMap, r, l))
return false;
}
return true;
}
// Using a second array. More memory consumption, but cleaner for small datasets
// Not tested
public static int[] sortZeros(int[] arr) {
if (arr == null)
return null;
int[] nArr = new int[arr.length];
int j = arr.length - 1;
for (int i = 0; i< arr.length; i++) {
if (arr[i] != 0)
nArr[j--] = arr[i];
}
return nArr;
}
I'm really no expert on this subject, but I'm pretty sure your statement is wrong. From what I remember an NP problem means it cannot be solved in polynomial time by a deterministic machine. So therefore it must be solved in exponential time by a deterministic machine. The above problem is being solved O(n) = O(n^1) (polynomial). Please correct me if I'm way off here, it's been a while.
- BenC March 25, 2014This seems to satisfy all but the 80 character max. You could stop printing '*' after you've reached 80, but this does not produce a proper histogram. A character with 80 repeats will look identical as a character with 1000 repeats. You should store the max number of characters and use some algebra to calculate the # of '*' to print.
Ex. Max Number of repeats from all characters = 1000
Char 'n' is repeated 400 times
1000/80 = 400/x => 1000x = 32000 => 32000/1000 = 32.
Therefore, you should print '*' 32 times for the letter n. To generalize this we can say you would for a given ni (number of repeats for character i) and a given max number of repeats m, you would print '*' (ni*80)/m times.
Just a breadth first search of an undirected graph. You can use a hashmap to keep track of visited nodes and current levels.
I did not compile or test this so it may have bugs, but it should be close.
public static void printSocialGraph(Member m)
{
if (m == null)
return;
Queue<Member> q = new LinkedList<Member();
Map<Member, Integer> visited = new HashMap<Member, Integer>();
q.add(m);
int level = -1
visited.put(m, level+1);
while(!q.isEmpty())
{
Member curr = q.poll();
if(visited.get(curr) > level)
{
System.out.println("Level " + (++level));
}
System.out.print(member + " ");
for(Member friend: curr.friends)
{
if(!visited.containsKey(friend))
{
visited.put(friend, level+1);
q.add(friend);
}
}
}
}
@mithya
I am not familiar with KMP, but I like what your attempting to do. Resetting the first value that was decremented in the "current_stats" array once you've realized it does not fit in the pattern. Your proposed solution however seems flawed. It appears that the else statement you've added is unreachable. The above code will catch if a value is 0 in the array (and reset), or greater than zero (and decrement it by one). Since no values start at < 0, you will never get to your new code. Also, the current_count variable becomes disjointed with the current_stats array when the increment takes place. This may be by design but if so it's very confusing.
This may not be the cleanest implementation, but it's pretty straight forward.
Given that the tree structures may be different, using a single recursive function is not possible. Instead, we can use an iterative approach modified to iterate through both trees.
Here is an iterative solution of inorder traveral....
public static void iterativeInorder(Node n){
Node curr = n;
Stack<Node> s = new Stack<Node>();
while( !s.isEmpty() || curr != null ){
if (curr != null){
s.push(curr);
curr = curr.left;
}
else if(!s.isEmpty()){
curr = s.pop();
curr.print();
curr = curr.right;
break;
}
}
}
When we print the the current node, we want the next print to be on the subsequent tree. We can duplicate the same inorder traversal on the second tree just after the print to achieve this. After the second iteration prints, we can break and continue with the first iteration and so on an so forth...
public static void iterativeInorderTwoNodes(Node n1, Node n2){
Node curr1 = n1;
Node curr2 = n2;
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
while(!s1.isEmpty() || curr1 != null){
if (curr1 != null){
s1.push(curr1);
curr1 = curr1.left;
}
else if(!s1.isEmpty()){
curr1 = s1.pop();
curr1.print();
while( !s2.isEmpty() || curr2 != null ){
if (curr2 != null){
s2.push(curr2);
curr2 = curr2.left;
}
else if(!s2.isEmpty()){
curr2 = s2.pop();
curr2.print();
curr2 = curr2.right;
break;
}
}
curr1 = curr1.right;
}
}
}
int[] newArr = Arrays.copyOf(arr, arr.length-1);
- BenC February 16, 2017