## Posts

Showing posts from January, 2012

### [AMAZON]Length of the LIS

Given an integer array sequence, return the length of the longest increasing subsequence (LIS)
A longest increasing subsequence is defined as a subsequence in the given sequence of integers such that the elements in the subsequence are in sorted order, lowest to highest and in which the subsequence is as long as possible

Sample Test Cases:

Input #00:
1, 2, 3

Output:
3

Explanation:
The sequence in itself is an increasing one

Input #01:
4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5, 4, 6, 7, 8, 9, 0, 6, 7

Output #01:
8

Explanation:
The length of the LIS is 8. The LIS elements from the sequence are highlighted: 4, 5, 6, 7, 8, 1, 2,1, 2, 3, 5, 4, 6,7, 8, 9, 0, 6, 7

### [AMAZON]Print Anagrams

Given an array of strings, please complete the function printAnagrams which prints each anagram pair in every line. Any word that exactly reproduces the letters in another order is an anagram. Anagrams are case-insensitive
Sample Test Cases:

Input #00:
Resistance, Ancestries, Gainly, Laying, test, troop

Output #00:
Resistance Ancestries
Gainly Laying

Explanation
Re-arranging "Resistance" gives "Ancestries", similarly re-arranging "Gainly" results in "Laying".
As stated in the problem, anagrams are case-insensitive

### [AMAZON]File_Mapping

Write a program that reads a series of data sets representing a computer file structure. A data set ends with a line containing a single *, and the end of valid data is denoted by a line containing a single #. The data set contains a series of file and directory names. (The root directory is assumed to be the starting point.) The end of a directory is denoted by a ']' Directory names begin with a lower case 'd' and file names begin with a lower case 'f' File names may or may not have an extension (such as fmyfile.dat or fmyfile). File and directory names may not contain spaces.

Output:

Note that the contents of any directory should list any subdirectories first, followed by files, if any. All files should be in alphabetical order within each directory. Note that each data set output is marked by the label "DATA SET x:" where x denotes the number of the set, beginning at 1. Note also the blank line between the output data sets. …

### Check brace expression are valid

Implement an algorithm to check whether brace expressions are valid or not

boolean isGood(String s, String braces);  //assume braces are valid,{}[]()

### [Amazon]Implement LRU cache

Implement the LRU cache algorithm. Given following interface. CacheStrategy<K, T> {// get the data by key from the cache. T get(K key); // put <key, data> pair to the cache voidput(K key, T data); } where k is key and T is data part. Note: All operation should be o(1).

### Find index of special symbol

Given an infinite array in which the first n cells contain integers in sorted order and the rest of the cells are filled with some special symbol (say \$).Assume we do not know the 'n' value.Give an algorithm that finds the index of the symbol.
Note :size of the array is not known.