[misc] #algorithms

fibonacci.py

def fibonacci(n):
  pass

getMiddleNodeOfLinkedList.java

public Node getMiddleNode() {
 
   Node fastPointer = this.head;
   Node slowPointer = this.head;
 
   while(fastPointer.getNextNode() != null && fastPointer.getNextNode().getNextNode() != null) {
      fastPointer = fastPointer.getNextNode().getNextNode();
      slowPointer = slowPointer.getNextNode();
   }
 
   return slowPointer;
}

heapifyBinaryTree.java

public static Node heapifyBinaryTree( Node root ){
	int size = traverse( root, 0, null ); 
	Node[] nodeArray = new Node[size]; 
	traverse( root, 0, nodeArray );
	// Count nodes
	// Load nodes into array values, using Comparator object
	// Sort array of nodes based on their 
	Arrays.sort( nodeArray, new Comparator<Node>(){
		@Override public int compare( Node m, Node n ){
			int mv = m.getValue(), nv = n.getValue(); 
			return ( mv < nv ? -1 : ( mv == nv ? 0 : 1 ) );
		} 
	});
	// Reassign children for each node 
	for ( int i = 0; i < size; i++ ){
		int left = 2*i + 1;
		int right = left + 1;
		nodeArray[i].setLeft( left >= size ? null : nodeArray[left] );
		nodeArray[i].setRight( right >= size ? null : nodeArray[right] );
	}
	
	return nodeArray[0]; // Return new root node 
}

public static int traverse( Node node, int count, Node[] arr ){ if ( node == null )
	return count; 
	if ( arr != null )
		arr[count] = node;
	
	count++;
	count = traverse( node.getLeft(), count, arr ); 
	count = traverse( node.getRight(), count, arr ); 
	return count;
}

intersects.py

def intersects(a, b):
  return not (a.top_left.x > b.bottom_right.x 
              or a.top_left.x < b.bootom_right.x 
              or a.bottom_right.y > b.top_left.y 
              or a.bottom_right.y < b.top_left.y)

isAnagram.java

public static void isAnagram(char[] s1, char[] s2) {
 
   if(s1.length!=s2.length) return false;
 
   Arrays.sort(s1);
   Arrays.sort(s2);
 
   for(int i=0;i<s1.length;i++)
      if(s1[i]!=s2[i])
        return false;
 
   return true;
}

isLittleEndian.c

int isLittleEndian(){ 
    union {
        int theInteger;
        char singleByte; 
    } 
    endianTest;
    endianTest.theInteger = 1;
    return endianTest.singleByte; 
}

isMaxHeap.java

public boolean isMaxHeap(int[] heap) {
 
        //if node with index i -> 2*i+2>=N then we know it is a leaf node and
        //there is no need to check leaf nodes. So there are (N-2)/2 non leaf nodes
        //we have to consider and check
	for(int i=0;i<=(heap.length-2)/2;i++){
            //if the left child or right child is greater than the parent: the heap
            //properties are violated so return false
            if(heap[i]<heap[2*i+1] || heap[i]<heap[2*i+2])
               return false;
        }
 
        return true;
}

isPalindrome.java

public static boolean palindrome(String s) {
 
	int i = 0;
	int j = s.length()-1;
	int k = (i+j)/2;
 
	for(int index = i;index<=k;index++) {
 
		if( s.charAt(i) == s.charAt(j) ) {
			i++;
			j--;
		} else {
			return false;
		}
	}
 
	return true;
}

lruCache.cpp

// https://www.geeksforgeeks.org/lru-cache-implementation/

numOnesInBinary.c

int numOnesInBinary( int number ) { 
    int numOnes = 0;
    while ( number != 0 ){
        if ( ( number & 1 ) == 1 ) { 
            numOnes++;
        }
        number = number >>> 1;
    }
    return numOnes;
}

reverseArray.java

public int[] reverseArray(int[] arr) {
  int start = 0;
  int end = arr.length -1;
  
  while(start< end){
  	temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
   return arr;
}

reverseInteger.java

public static void reverse(int n) {
 
   int reversed = 0;
   int remainder = 0;
 
   while(n>0) {
      //get the last digit of the integer n
      remainder = n%10;
      //get rid of the last digit
      n = n/10;
      //append that digit to the solution
      reversed = reversed*10+remainder;
   }
 
   return reversed;
}

reverseLinkedList.java

public void reverse() {
 
	Node currentNode = this.head;
        Node previousNode = null;
        Node nextNode = null;
 
	while(currentNode!=null) {
           nextNode = currentNode.getNextNode();
           currentNode.setNextNode(previousNode);
           previousNode = currentNode;
           currentNode = nextNode;
        }
 
	this.head = previousNode;
}

StringAlgo.java

public static void removeChars(StringBuilder str, String remove){
  boolean flags[] = new boolean[128];
  int src, dst = 0;
  
  for(char c : remove.toCharArray()){
    flag[c] = true;
  }
  
  for(src=0; src<str.length(); ++src){
    char c = str.charAt(src);
    if(!flag[c]){
      str.setCharAt(++dst, c)
    }
  }
  
  str.setLength(dst);
}


public static void reverseWords(String sentence){
  return reverseWords("", sentence, 0, 0)
}

public static string reverseWords(String dst, String src, int start, int pos){
  if(pos >= src.lenght()){
    return src.substring(start, pos+1) + dst;
  }
  
  if(src.charAt(pos) == ' '){
    dst = src.substring(start, pos) + " " + dst;
    start = pos + 1;
  }
  
  return reverseWords(dst, src, start, pos++) + " " + dst;
}

public static String reverseWords(String sentence){
  StringBuilder sb = new StringBuilder();
  
  int i =0;
  while(i < sentence.length()){
    String str="";
    while(sentence.charAt(i) != ''){
      str += "" + sentence.charAt(i);
    }
    sb.insert(0, " " + str);
    i++;
  }
  retrurn sb.toString().trim();
}

public static int strToInt(String str){
  int i = 0; num = 0;
  boolean isNeg = false;
  
  if(str.charAt(0) == '-'){
    isNeg = true;
    i = 1;
  }
  //123
  while(i < str.length()){
    num = num * 10;
    num = num + (str.charAt(i) - '0');
    i++;
  }
  
  return isNeg? -num : num;
}


public class Combinations {
	private StringBuilder out = new StringBuilder(); private final String in;
	
  public Combinations( final String str ){ 
    in = str; 
  }
  
	public void combine() { combine( 0 ); } private void combine( int start ){	
		for ( int i = start; i < in.length(); ++i ){ 
      out.append( in.charAt( i ) ); 
      System.out.println( out );
			if ( i < in.length() )
				combine( i + 1 ); out.setLength( out.length() - 1 );
			} 
  	}
}

StringAndListPermutation.java

public ArrayList<String> stringPermutations(String s) {
    ArrayList<String> result = new ArrayList<String>();
    stringPermutations(“”, s, result); 
    return result;
}
 
private void stringPermutations(String prefix, String suffix, List<String> results) {
    if (suffix.length() == 0) {
        results.add(prefix);
    } else {
        for (int i = 0; i < suffix.length(); i++) {
            stringPermutations(prefix + suffix.charAt(i), suffix.substring(0, i) + suffix.substring(i+1, suffix.length()));
        }
    }
}
 
 
public List<int[]> listPermutations(int[] a) {
    ArrayList<int[]> results= new ArrayList<int[]>();
    listPermutations(a, 0, results);
    return l;
}
 
private void listPermutations(int[] a, int start, List<int[]> result) {
    if (start >= a.length) {
        result.add(a.clone());
    } else {
        for (int i = start; i < a.length; i++) {
            swap(a, start, i);
            listPermutations(a, start+1, result);
            swap(a, start, i);
        }
    } 
}
 
private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

stringPermutations.java

// Java program to print all permutations of a 
// given string. 
public class Permutation {
  
	public static void main(String[] args) { 
		String str = "ABC"; 
		int n = str.length(); 
		Permutation permutation = new Permutation(); 
		permutation.permute(str, 0, n-1); 
	} 

	/** 
	* permutation function 
	* @param str string to calculate permutation for 
	* @param l starting index 
	* @param r end index 
	*/
	private void permute(String str, int l, int r){ 
		if (l == r) 
			System.out.println(str); 
		else { 
			for (int i = l; i <= r; i++) { 
				str = swap(str,l,i); 
				permute(str, l+1, r); 
				str = swap(str,l,i); 
			} 
		} 
	} 

	/** 
	* Swap Characters at position 
	* @param a string value 
	* @param i position 1 
	* @param j position 2 
	* @return swapped string 
	*/
	public String swap(String a, int i, int j) { 
		char temp; 
		char[] charArray = a.toCharArray(); 
		temp = charArray[i] ; 
		charArray[i] = charArray[j]; 
		charArray[j] = temp; 
		return String.valueOf(charArray); 
	} 

} 

towerHanoi.py

def towerOfHanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print('Move disk 1 from rod {} to rod {}'.format(from_rod, to_rod))
        return
    towerOfHanoi(n-1, from_rod, aux_rod, to_rod)
    print('Move disk {} from rod {} to rod {}'.format(n, from_rod, to_rod))
    towerOfHanoi(n-1, aux_rod, to_rod, from_rod)


towerOfHanoi(4, 'A', 'B', 'C')