Programming Techniques

From Computing Study
Jump to: navigation, search

Regular Expressions

If you want to test a regular expression that you have created, you can do so on this website https://regex101.com/

Basic Options

\d - represent any number
\D - represents anything not a number
\s - represents a space
\S - anything but a space
\w - any character
\W - anything but a character
\b - a space that precedes or follows a whole word

{n} - number of repetitions
\d{5} - search for 5 digits
\d{1,5} - search for between 1 and 5 digits

The following characters need to be escaped if you want to search for them

$ - end of a sentence
. - any character except for a line break
(
)
* - 0 or more repetitions
+ - one or more of the code that precedes it
? - 0 or 1 repetitions - can be used as 'maybe there, maybe not'
[
\ - used for escaping or to define one of the above codes
^ - beginning of a line of text
{ - curly braces are for defining the number of times the preceding code should be evaluated
| - Boolean operator OR

\$\d*\.\d{2} - matches $100.00

\e - escape
\f - form feed
\n - new line
\r - carriage return
\t - tab

To search for either Calendar or Calender
Calend[ae]r

[a-z] - all lower case letters
[0-9] - all single digit numbers
[A-Fa-t0-4] - Capital letters A to F, or lower case letters a to t, or numbers 0 to 4
'(Jennifer|Jen|Jenny)\b\w+\b' - Searches for any example of Jennifer, Jen, or Jenny, followed by a space, then another word, then a space
'Je(nnifer|nny|n){1,6}\s\w+\s' - Another way of writing the same

Adding \1 will redo the code in brackets

'(Cat\s.+$)' - Will find 'Cat' but not cats or catty when it appears at the beginning of a sentence, and then returns the whole sentence


Using regex in Python

import re

f = open('randomcharacters.txt')

strToSearch = ''

for line in f:
    strToSearch += line

print(strToSearch)    # will print all the characters in the file 'randomcharacters.txt'

patFinder1 = re.compile('Aa18')

findPat1 = re.search(patFinder1, strToSearch)    # returns the string if it is found in the document

print(findPat1.group())    # prints the found text
print(findPat1.start())    # prints the starting index where the text was found
print(findPat1.end())      # prints the index after the last character found
print(findPat1.span())     # prints the range where the text was found

findPat1 = re.findAll(patFinder1, strToSearch)    # Finds all instances of the text in the file

for i in findPat1:
    print()            # prints all the found instances of text

splitFound = patFinder1.split(strToSearch)
print(splitFound)      # shows text that splits (is located between) the string you are looking for

subFound = patFinder1.sub('Real Text', strToSearch)
print(subFound)        # substitutes the pattern with the text in quotes
patFinder2 = re.compile('b3b2c', re.IGNORECASE)
findPat2 = re.search(patFinder2, strToSearch)

if (findPat2):
    print(findPat2.group())
else:
    print("Nothing found")
patFinder2 = re.compile('.*', re.IGNORECASE)
findPat2 = re.search(patFinder2, strToSearch)    # prints everything that is not a new line
patFinder2 = re.compile('[a-z]', re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)

for i in findPat2:
    print(i)            # prints each result on a new line

for i in findPat2:
    print(i,end='')     # prints everything on the same line
patFinder2 = re.compile('[#$\*/\?0-9]'. re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)

for i in findPat2:
    print(i, end='')
# Searches for any number, anything not a number, any space, anything not a space, anything, anything not a character, any character

patFinder2 = re.compile('\d\D\s\S.\W\w', re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)

for i in findPat2:
    print(i, end='')
# Searches for the word Jennifer or Jenny or Jen, of 1 to 6 characters, followed by a space, followed by the whole next word (e.g. a surname), followed by a space

patFinder2 = re.compile('(je[nnifer|nny|n]{1,6}\s\w+\s)', re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)

for i in findPat2:
    print(i, end='')

# This query returns the same result because it matches 1 to 6 characters of anything in the square brackets, although it would also return Jeff etc.

patFinder2 = re.compile('(je[nifery]{1,6}\s\w+\s)', re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)
# Locates the value of pi (or similar looking number) in a string of text

patFinder2 = re.compile('\d\.\d*)\w'), re.IGNORECASE)
findPat2 = re.search(patFinder2, strToSearch)

print(findPat2.group())
# Finds 3 digits, followed by maybe a hyphen, followed by another 3 digits, followed by maybe a hyphen, followed by 4 digits OR the same with optional brackets. In other words a US phone number

patFinder2 = re.compile('([0-9]{3}-?[0-9]{3}-?[0-9]{4})|(\(?[0-9]{3}\)?[0-9]{3}-?[0-9]{4}'), re.IGNORECASE)
findPat2 = re.findAll(patFinder2, strToSearch)

for i in findPat2:
    print(i)

Algorithms

Arrays

Find largest difference between two elements such that the element of lesser value must come before the greater element.

public class FindLargestDifference {
	
	protected static int findLargestDifference(int[] numbers) {
		
		// If there is only one element there is no difference
		if(numbers.length <= 1) { return -1; }
		
		int currentMin = numbers[0];
		int currentMaxDifference = 0;
		
		for (int i = 1; i < numbers.length; i++) {
			if (numbers[i] > currentMin && (numbers[i] - currentMin > currentMaxDifference)) {
				currentMaxDifference = numbers[i] - currentMin;
			} else if (numbers[i] < currentMin) {
				currentMin = numbers[i];
			}
		}		
		if (currentMaxDifference <= 0) { return -1; }
		
		return currentMaxDifference;
	}

	public static void main(String[] args) {
		
		// Returns 11 not 14 because 15 comes before 1
		int[] numbers = {7, 8, 4, 9, 15, 3, 1, 10};
		
		int maxDifference = findLargestDifference(numbers);		
		System.out.println("The maximum difference according to the rules is: " + maxDifference);
	}
}

Given an array of integers, find the largest product yielded from three of the integers.

public class FindLargestProduct {
	
	// Greatest product is either (min1 * min2 * max3) or (max1 * max2 * max3)
	protected static int computeProduct(int numbers[]) {
		int lastElementIndex = numbers.length - 1;
		int product1 = 1; int product2 = 1;
				
		// Find max1 * max2 * max3
		for (int i = lastElementIndex; i > lastElementIndex - 3; i--) {
			product1 = product1 * numbers[i];
		}
		System.out.println("Product1: " + product1);
		
		// Find min1 * min2 * max3
		product2 = numbers[0] * numbers[1] * numbers[lastElementIndex];
		System.out.println("Product2: " + product2);
		
		if (product1 > product2) {
			return product1;
		} else {
			return product2;
		}		
	}

	public static void main(String[] args) {
		
		int numbers[] = {-18, 5, 24, 40, 3, -13, -77};		
		Arrays.sort(numbers);
		
		int largestProduct = computeProduct(numbers);		
		System.out.println("The largest product of 3 values from the numbers array is " + largestProduct);
	}

}

Given an unsorted array containing n - 1 of n consecutive numbers where the bounds are defined, find the missing number in o(n) time

public class FindMissingNumber {
	
	protected static int findMissingNumber(int numbers[], int upperBound, int lowerBound) {
		// Find the sum of the numbers in the given array
		int sumOfNumbers = 0;
		for (int i = 0; i < numbers.length; i++) {
			sumOfNumbers += numbers[i];
		}
		
		int theoreticalSum = 0;
		// Find the sum of numbers if all were present
		for (int i = lowerBound; i <= upperBound; i++) {
			theoreticalSum += i;
		}	
		return theoreticalSum - sumOfNumbers;
	}

	public static void main(String[] args) {
		int numbers[] = {2, 5, 1, 4, 9, 6, 8, 7};
		int upperBound = 9;
		int lowerBound = 1;
		
		int missingNumber = findMissingNumber(numbers, upperBound, lowerBound);
		System.out.println("The missing number in the array is: " + missingNumber);
	}

}

Remove duplicates of an array and return an array of only unique elements

public class RemoveDuplicates {
	
	protected static int[] removeDuplicates(int[] numbers) {
		ArrayList<Integer> uniqueArrayList = new ArrayList<Integer>();
		
		for (int i = 0; i < numbers.length; i++) {
			if(!uniqueArrayList.contains(numbers[i])) {
				uniqueArrayList.add(numbers[i]);
			}
		}
		
		// Convert back to primitive array
		int[] uniqueArray = new int[uniqueArrayList.size()]; int i = 0;
		for (Integer n : uniqueArrayList) {
			uniqueArray[i++] = n;
		}		
		return uniqueArray;
	}

	public static void main(String[] args) {
		int numbers[] = {1, 2, 3, 5, 1, 5, 9, 1, 2, 8};
		
		int[] uniqueArray = removeDuplicates(numbers);		
		Arrays.sort(uniqueArray);
		
		System.out.println("Original array: " + Arrays.toString(numbers));
		System.out.println("Duplicates removed: " + Arrays.toString(uniqueArray));
	}
}

Strings

Reverse each word in a sentence keeping the order of the words the same

public class ReverseEachWord {
	
	protected static String reverseLetters(String sentence) {
		String reversed = "";
		for (int i = sentence.length() - 1; i >= 0; i--) {
			reversed += sentence.charAt(i);
		}
		
		return reversed;
	}
	
	protected static String reverseSentence(String sentence) {
		String reversed = "";
		
		String[] sentenceArray = sentence.split(" ");
		
		for (int i = sentenceArray.length - 1; i >= 0; i--) {
			reversed += (sentenceArray[i] + " ");
		}
		
		return reversed;
	}

	public static void main(String[] args) {
		String sentence = "Welcome to this Java Guide!";
		
        // First reverse all the letters in the sentence
		String lettersReversed = reverseLetters(sentence);
		
        // Then reverse the order of the words back to the original order
		String sentenceReversed = reverseSentence(lettersReversed);
		
		System.out.println("The sentence reversed is: " + sentenceReversed);
	}

}

Given two words check if they are an anagram of each other

public class IsItAnagram {
	
	protected static boolean isItAnagram(String first, String second) {
		String firstLower = first.toLowerCase();
		String secondLower = second.toLowerCase();
		
		String[] firstArray = firstLower.split("");
		Arrays.sort(firstArray);
		
		String[] secondArray = secondLower.split("");
		Arrays.sort(secondArray);		
		
		return Arrays.equals(firstArray, secondArray);
	}

	public static void main(String[] args) {
		String first = "Mary";
		String second = "Army";
		
		boolean answer = isItAnagram(first, second);
		System.out.println("The words: " + first + " and " + second + " are anagrams? " + answer);
	}

}

Check if a word or sentence is a palindrome. Spaces should be ignored.

public class IsItPalindrome {
	
	protected static boolean isPalindrome(String string) {
		String lettersOnly = string.toLowerCase().replaceAll(" +", "");
		String lettersReversed = reverseLetters(lettersOnly);
		return lettersOnly.equals(lettersReversed);
	}
	
	protected static String reverseLetters(String sentence) {
		String reversed = "";
		for (int i = sentence.length() - 1; i >= 0; i--) {
			reversed += sentence.charAt(i);
		}		
		return reversed;
	}

	public static void main(String[] args) {
		boolean racecar = isPalindrome("racecar");
		boolean race_car = isPalindrome("race car");
		
		System.out.println("Racecar is a palindrome? " + racecar);
		System.out.println("Race car is a palindrome? " + race_car);
	}
}

Check if a given string is a isomorphic

/**
 * For two strings to be isomorphic, all occurrences of a character in string A can be replaced with another character
 * to get string B. The order of the characters must be preserved. There must be one-to-one mapping for ever char of
 * string A to every char of string B.
 */
public class IsIsomorphic {
	
	protected static boolean isIsomorphic(String s, String t) {
		//Check if the strings are the same length, if not they cannot be isomorphic
		if(s.length() != t.length()) { return false; }
		
	    Map<Character, Integer> m = new HashMap<Character, Integer>();
	    Map<Character, Integer> n = new HashMap<Character, Integer>();
	    
	    for (Integer i = 0; i < s.length(); i++)
	        if (m.put(s.charAt(i), i) != n.put(t.charAt(i), i))
	            return false;
	    return true;
	}

	public static void main(String[] args) {
		boolean first = isIsomorphic("egg", "add"); // true
		boolean second = isIsomorphic("paper", "title"); // true
		boolean third = isIsomorphic("kick", "side"); // false
		
		System.out.println(first);
		System.out.println(second);
		System.out.println(third);
	}
}

Stacks and Queues

Recursion

Numbers