Word ladder and maximum subarray in Java 2 questions in 3 chapters
Shortest word transformations
BFS over a word graph, using wildcard patterns to find one-letter neighbors.
1.1 How do you find the length of the shortest word ladder? Hard 4 min
I model this as BFS on an unweighted word graph. If the end word is not in the list I return zero. I bucket words under wildcard patterns like h*t, so one-letter neighbors share a pattern. Search starts at the begin word, visits each word once, and returns the word count when it reaches the end. That's roughly O(N L²). A follow-up is bidirectional BFS.
Read the full answer
Maximum subarray sums
Kadane's one-pass algorithm, plus indices, divide and conquer, and the circular variant.
2.1 How do you find the maximum sum of a contiguous subarray? Medium 5 min
I use Kadane's algorithm: one pass that keeps the best sum ending here and the best sum so far, in linear time and constant space. At each number I either extend the previous run or start a new one here, then update the global best. Both values start at the first element, so an all-negative array returns the largest element. Follow-ups are the indices, divide and conquer, and the circular variant.
Read the full answer