Algorithms and Data Structures

Solutions to interesting programming problems with additional insight provided in the comments and test coverage through TestNG.

Arrays and Strings

• hasAllUniqueChars - determines whether a String repeats any characters - O(N)
• isPermutation - determines whether one String could be rearranged into another given String - O(N)
• urlify - replaces spaces in a character array with the characters '%', '2', and '0' - O(N)
• isPalindromePermutation - determines whether a String can be rearranged into a pallindrome - O(N)
• compress - removes any repeated characters and replaces them with a count of that character - O(N)
• isOneEditAway - determines whether one String has had a single character addition, subtraction or modification from as compared to another String - O(N)
• rotate90 - given a square matrix of integers, rotates values in place so the matrix appears shifted 90 degrees O(N²)

Linked Lists

• LinkedList - a basic linked list class for testing
• LinkedListNode - a basic node class for testing
• removeDuplicates - removes any repeated elements with help of a HashSet - O(N)
• removeDuplicatesWithoutBuffer - removes any repeated elements in place - O(N²)
• getKthFromLast - returns element that is k away from end of list - O(N)
• removeFromMiddle - removes an element from the middle of a list - O(1)
• partition - reorders list so elements less than partition value come before elements equal to or greater than partition value - O(N)
• reverse - reverses order of elements in list - O(N)
• sumLists - creates a new list of integers representing the sum of two given lists of integers - O(N)
• isPalindrome - determines if a list is a palindrome by utilizing a stack - O(N)
• getIntersectingNode - returns the node where two singly linked lists intersect (or null if they don't) - O(N+M)
• getStartOfLoop - returns the node where a list loops back onto itself (or null if it doesn't) - O(N)