Algorithms, data structure and programming challenges

The implemented algorithms so far

Java

• Various Interview Cake challenges
• LRU (last recently used) cache
• Trees
  • Binary search tree
    • add nodes
    • find the second largest value
    • construction from given preorder list
    • traversals: preorder, inorder, postorder
• String related challenges
  • Reverse string in place O(n) time, O(1) space
• Fibonacci
  • iterative
  • recursive
  • recursive with memoize
• Classic fizz buzz
• Singly linked list
  • add nodes
  • loop detection O(n) time, O(1) space
  • reverse the order in place O(n) time, O(1) space

JavaScript

• String related challenges
  • Minify string

Ruby

• Find the sub array of an array of integers which has the biggest sum
• Fibonacci
  • iterative
  • recursive
  • recursive with memoize
• Find unique integer in a list that contains duplicated integers and one single not duplicated one
• Classic fizz buzz challenge
• Find the highest product of 3 integers in an array
• Singly linked list
  • add nodes
  • loop detection O(n) time, O(1) space
  • reverse the order in place O(n) time, O(1) space
• LRU (last recently used) cache
• Merge ranges challenge
• Multiplication every number in an array except the current index
• Rectangular overlapping
• String related challenges
  • Reverse string in place O(n) time, O(1) space
  • Reverse words in place O(n) time, O(1) space
  • Any palindrome
    • Find out if we could build up a palindrome from the given string by permute its letters
  • Generate all permutations of a string, use recursive function anyway
  • Count the substrings
    • We have a random string, the task is to answer how many at least two character long substrings does it contain which has maximum two different letters.
• Trees
  • Binary search tree
    • add nodes
    • find the second largest value
    • determine the height of a tree (both recursive and iterative)
    • determine the width of a tree (The width of a tree is the number of nodes on the longest path between two terminal nodes (leaves) in the tree)
    • construction from given preorder list
    • traversals: preorder, postorder