Difference b/w Collection and Collections

Collections provide you views (annoymous class instances) for read-only

Implementation of an efficient MRU Cache in Java

LinkedHashMap with doubly linked list to keep the most recently accessed element at the head/tail of the list. Every bucket's list keeps its own elements in the singly linked list and the same elements are doubly linked as well

Difference between Comparable and Comparator

Comparator implementations can be used to define custom sorting even for Objects which already implement Comparable interface in TreeSet, HashSet

Find modulo (1 << k) division without using division

m = n & (d - 1); where d= (1 << k)

Find if the given integer is even or odd

Use of division is not permissible.

Bit Twiddling

Find the minimum and maximum of two numbers without any branching. Prohibiting branching means (a>b)?b:a is also prohibited.

Sorting for large data sizes

I have a computer file containing 1,000,000 non-negative integers, in no particular order. Imagine that they are the membership numbers of people who are enrolled in my internet club. A new person wants to join the club, and we need to find an unused number to allocate to them. How would you find, in a reasonable time, a number that was not already in the file?

Hint: Use Selection trees for finding the first missing integer among those 1,000,000 integers. The in memory amount of data that we have to keep is very small.

Reference: http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch6.html

Digits in a factorial

Find the "number of digits in the factorial of a number" without finding the factorial??

Hint: Algorithm should not take more than O(lg N) where lg = log10

1-0 array problem

Given an array A (n X n), which takes values from set {0, 1}; i.e.

A[i][j]= 0 or 1 for all i,j between 0 and n

Find a row i such that all elements in the row are 1s and a column j such that all elements are 0 except the intersecting element A[i][j] which is 1.

Another version of the same problem goes like this:
Given that every row of the array has all 1s and 0s together and 0s follow only after 1s in the row, find the maximum number of 1s in a row in the array.

Hint: O(n2) is a naive algorithm and O(n) is nice.

Finding repeated numbers in two arrays

Given two sorted integer arrays (array size may differ).

Find the number of values that appear in both arrays.

For example, given:

A: 1, 3, 5, 8, 10. 14, 16, 25, 28, 47
B: 2, 4, 7, 8, 11, 12, 14, 17, 47, 56, 64

The result should be 3, since value 8, 14, 47 appear in both array.

Hint: A simple approach would take O(m+n) however it can be done in O(nlogm) (a better bound if n is very small as compared to m)

Blogs, Tagging and Summary Problem

(Originally mentioned by Ghai uncle, this is an extended problem of the same kind)

A blogger just wrote a review on movie "Shivaji" starring Rajnikant and tagged it as "Rajnikant movie, Shivaji, movie review". For better surfing experience of the blogger, the blogging portal (your firm) wants to develop following features:

1. The moment the blogger posts his review, he is shown a list of other reviews on this movie. (To make it simple, the list contains links to blogs from his friends only)

2. There is an option to list all such blogs in a page. The listing page contains a shortest summary from each link containing all the tags and the tags highlighted properly in different colors in the summary. So for example, "Rajnikant movie" will be colored red, "Shivaji" would be colored blue, "movie review" will be colored green in the summary; however "Rajnikant" merit no coloring and "shivaji movie" merit coloring of "shivaji" only and likewise.

How would you do it?

Hint: There are essentially three problems:
1. finding blog links with similar tags.
2. finding shortest summary of text from a document containing all the tags in it.
3. finding out occurrences of a set of keywords/tags in a document.

Adobe Written interview questions

1. Write an algo to print all paths in a binary tree.
2. Write an algo to determine if 2 rectangles intersect.
3. If an identifier is defined as follows
letter followed any number of letters and digits then write its regular expression.
4. x=b, z=1;k=n; // n is constant
while(k!=0)
{
if(k is odd) z=z*x;

x=x*x;
k=floor(k/2);
}
what is z at the end in terms of b and n?
5. What is synchronized statement, synchronized function, transient, wait(), notify(), notifyAll();
6. String s = "Hello";
String t = s.append(" Dolly");
Which string do s and t point to ?
7. What is advantage of entity beans over session beans?

8. What are J2EE components?
9. What is multi-tier architecture ? In which layer does browser fits in ?