Problem
Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.
Solution
This is DP problem. Here is the good solution.
References
Find max subsquare whose border values are all 1
Problem Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
Solution We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size.
[Read More]
Transform one word into another by changing only one letter at a time
Problem Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
Solution Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter.
[Read More]
Search a long string for small strings in an array
Problem Given a string s and an array of smaller strings T, design a method to search s for each small string in T.
Solution Method 1 - Using suffix tree
We can first get all the suffices of s and check for each element t in T to see if t is the beginning part of any suffices. To make this more efficient, we can build a suffix tree and do the operations.
[Read More]
Pattern Searching - Boyer Moore Algorithm – Bad Character Heuristic
Searching Patterns - Finite Automata
Rabin-Karp Algorithm
Suffix Array
Suffix tree
Longest word made of other words in an array
Problem Write a program to find the longest word made of other words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester
Solution
This problem can be easily solved using a “Trie data structure” First I sort the strings in descending order “Lengthwise”, so longest string comes first. Start with the first string and loop over sorted strings Check if it can be made of other words by dividing strings into all possible combinations and doing same thing for each splits.
[Read More]