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]
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]
Find largest 1M numbers in 1B numbers
Problem Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.
Solutions Method 1 - Sorting
We can certainly sort those numbers and return the last 1 million of them. That takes O(n log n).
Method 2 - Sort partially using some pivot
If we think about it, we actually do not need to sort them.
[Read More]
Shortest distances between two words in a file
Problem You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?
OR
Find the minimum distance between 2 numbers in the array?
Example File contains:
as was is the as the yahoo you me was the and
[Read More]
Count the number of 2s between 0 and n
Problem Write a method to count the number of 2s between 0 and n.
Example Input Range : between 0-20, Output : 3 (i.e 2, 12 , 20))
Solution We need recursion. The number n can be broken down into a couple of ranges. The number of 2’s of numbers in each range is independent of each other. For example, 3345 can be broken into [0, 3000] and (3000, 3345].
[Read More]
Randomly generate m integers from an array of size n
Problem Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen.
Solution This question depends on 2 things:
how random number generation works? Fisher yates algorithm or Knuth Shuffle? Now that we have fisher yates algorithm in our quiver, we can solve this problem :
let m be the number of elements to select for i = 1; i <= m; i++ pick a random number from 1 to n, call it j swap array and array (assuming 1 indexed arrays) n-- public static int chooseNFromM(int array, int m) { if (m > array.
[Read More]
Add two numbers without using arithmetic operators
Problem
Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).
Solution
We can get carry by &(and) operator and bit by ^ (xor) operator. We have already seen, how we can use bit-wise operators to replace arithmetic operators i.e. implement arithmetic operators using bitwise operators.
Method 1 - Iterative method
int Add(int x, int y) { // Iterate till there is no carry while (y !
[Read More]