Flex Ramblings

Producer Consumer problem in Java

2011-11-09T04:02:00.000-08:00

Next largest palindrome

2011-11-06T11:07:00.001-08:00

Q: A number is given as a palindrome, write a function to return the next largest palindrome.

Algorithm:

Case I: The given number is a palindrome..ex: 1234321 then simply increment the centre digit by 1 i.e the answer is 1235321

Case II: The given number is not a palindrome:

Subcase 1: The number to the left of the middle digit is greater than the number on the right ex:2194135 (here 219 > 135) then,reverse the left side numbers and replace the right side numbers with them, therefore the answer will be 2194912.

Subcase 2:The number to the right of the middle digit is greater than the number on the left ex:1354219 then,
then increment the middle digit by 1 and then reverse the left side numbers and replace the right side numbers with them. Therefore the answer would be 135 5(middle digit incremented) 531(reversed), resulting in 1355531, which is the next palindrome.
Note: in case the middle digit is 9 then incrementing it would make it 10, so put 0 instead of 9 and increment the first right and left neighbouring digit of 9 by 1.

Subsets that match a given sum in an array

2011-11-04T11:39:00.000-07:00

Q: Find subsets that match a given sum in an array

Common Element in a binary search tree

2011-11-04T09:48:00.001-07:00

Q: Given two BST's A, B, Find All elements of A which are present in B

You are given the root nodes of two BST and you have to print the common elements in them.

Max loss of the stock

2011-11-04T09:30:00.001-07:00

Given an array of stock prices from day 0 to N-1 of a company X, we have to find the max loss that is possible. Loss occurs if stock is bought at higher price and sold at lower price.
Ex: 1 2 3 7 5 8 9 4 6 10 12
Max Loss is 9 - 4 = 5 (Possible losses are 8-4 = 4, 7-5 = 2 etc). Max difference between stock price is 12 - 1 = 11 but max loss is 9 -4 = 5

Code:

Pythogorous triplets

2011-11-04T08:59:00.001-07:00

Q: How to find pythagorean triplets in an array?

Q: Given an array, find all such triplets i,j and k, such that a[i]² = a[j]²+a[k]²

Pythagorean triplet is a set {a,b,c} such that a² = b² + c². Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}

Algorithm:

Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".

Sort the array in ascending order. This takes O(n log n).
Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i. To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes. This takes O(i) operations.
Repeat step 2 for each index i. This way you'll need totally O(n²) operations, which will be the final estimate.

Code:

Time Complexity : Efficiency is(i) O(nlogn) : for sorting(ii) O(n^2) : for finding pairs adding equal to A[i]So total efficeincy is O(n^2)

Merging sorted 1st half and 2nd half

2011-10-16T06:29:00.001-07:00

Q: Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

The idea is to Insert all elements of second half into first half., like we do in Insertion Sort.

we need to keep the arrays sorted while we doing the swaps

Design a web crawler

2011-09-27T12:08:00.001-07:00

Web crawler is a program that traverses the hyperlinks structure of web pages. We crawler visits each web page by following the hyperlinks on previous page it visits. while it is crawling web pages to extract hyperlinks, a web crawler also save each page it has visited.

Crawler basic algorithm

Remove a URL from the unvisited URL list
Determine the IP Address of its host name
Download the corresponding document
Extract any links contained in it.
If the URL is new, add it to the list of unvisited URLs
Process the downloaded document
Back to step 1

Single Crawler

Multithreaded Crawler

Parallel Crawler

Search Engine : architecture

Search Engine : major components

Crawlers
Collects documents by recursively fetching links from a set of starting pages.Each crawler has different policies The pages indexed by various search engines are different
The Indexer
Processes pages, decide which of them to index, build various data structures representing the pages (inverted index,web graph, etc), different representation among search engines. Might also build additional structure ( LSI )
The Query Processor
Processes user queries and returns matching answers in an order determined by a ranking algorithm

Issues on crawler

General architecture
What pages should the crawler download ?
How should the crawler refresh pages ?
How should the load on the visited web sites be minimized ?
How should the crawling process be parallelized ?

Distributed crawler

The crawler system should consist of a number of crawler entities, which run on distributed sites and interact in peer-to-peer fashion. Each crawler entity has to have the knowledge to its URL subset, as well as mapping from URL subset to network address of corresponding peer crawler entity.

Whenever the crawler entity encounters a URL from a different URL subset, it should forward to the appropriate peer crawler entity based on URL subset to crawler entity lookup.

Each crawler entity should maintain its own database, which only stores the URL’s from the URL subset assigned to the particular entity. The databases are disjoint and can be combined offline when the crawling task is complete.

Crawler Entity Architecture

Each crawler entity consists of a number of crawler threads, a URL handling thread, a URL packet dispatcher thread and URL packet receiver thread. The URL set assigned to each crawler entity will be further divided into subsets for each crawler thread.

Each crawler thread should have its own pending URL list, a DNS cache. Each thread picks up an element from URL pending list, check to see if the IP corresponding to URL is available in the DNS cache, else does a DNS lookup, generates a HTTP fetch requests, gets the page and finally extracts more URL’s from the fetched page and puts them in the job pending queue of the URL handling thread.

URL handling thread will have a job queue. It will get a URL from the job queue, checks to see if the URL belongs to the URL set corresponding to the crawler entity, if it belongs to another entity it will put the URL on the dispatcher queue and get a new URL from the its job queue. If the URL belongs to its set, it firsts checks the URL-seen cache, if the test fails it queries the SQL database to check if the URL has been seen, and puts the URL in the URL-seen cache. It then puts the URL into URL pending list of one of the crawler threads. URLs are assigned to a crawler thread based on domain names. Each domain name will only be serviced by one thread; hence only one connection will be maintained with any given server. This will make sure that the crawler doesn’t overload a slow server.

URL dispatcher thread will communicate the URL’s corresponding crawler entity.

A URL receiver thread collects the URL’s received from other crawler entities i.e. communicated via dispatcher threads of those crawler entities and puts them on the job queue of the URL handling thread.

Buffer Overflow

2011-09-27T05:45:00.001-07:00

Question: What is a buffer overflow and how do you exploit it?

What is Buffer Overrun?

Buffer Over-run refers to problem where we can make program to use more than allotted ‘buffer’.All buffer overruns cannot be exploited as security vulnerability

What it could lead to?

Buffer overflows can be triggered by inputs that are designed to execute code, or alter the way the program operates. You get an access violation (AV). Your site becomes unstable.The attacker injects code into your application, executes it, and makes everyone an administrator of your site.

Types of Buffer Overrun

Stack Overruns
Heap Overruns
Array Indexing Errors
Format String
Unicode and ANSI Buffer size mismatch

A colleague of mine created a PPT on Buffer Overflow which we deal with here on daily basis. I removed some of the proprietary code and some other useful information.

Buffer OverFlow

View more presentations from Rambabu Duddukuri.

Max Black sub square matrix

2011-09-26T13:39:00.001-07:00

Imaging there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Algorithm to Exhibit Did You Mean Feature of Google Search Engine

2011-09-26T08:16:00.000-07:00

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , where words would have been inserted , you would have maintained a boolean variable to defined the end of word (eod)
An Example Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

You can solve this problem using a trie datastructure. Trie data structure implementation can be found here in my previous blog. The rest is just searching the trie

LRU Cache Implementation

2011-09-25T11:55:00.001-07:00

Linked List is a palindrome or not

2011-09-25T10:42:00.001-07:00

Question: Write a program to check if the given linked list is a palindrome or not

METHOD 1 (using recursion)

METHOD 2 (Using Stack)

Get the middle of the linked list.
Push the elements into the stack till the middle of the linked list
Compare the top of the stack and second half.

Next bigger number

2011-09-22T09:31:00.001-07:00

Q : You have given a positive number. You have to find a number which is immediate bigger than that by using same digits available in the number. use same digits with same number of time, coming in positive integer and if a small number is not possible then we have to return -1.

For example: (1) You have given a number 7585 , your output should be 7855 . (2) 7111, return –1

Algorithm:

Code:

Building Bridges:

2011-08-06T14:40:00.001-07:00

Problem: Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a1….an and n cities on the northern bank with x coordinates b1….bn. The cities on each bank are also numbered 1 through n and these numbers do not correspond to the ordering of the x-coordinates. You can only build a bridge from a city on the south bank to a city on the north bank with the same number. No two bridges may cross each other. An example of a valid bridge building is shown in Figure 1. Give an algorithm for finding the maximum number of bridges that can be built.

Solution:
Consider the sequences A = N(a1),……..,N(an) and B = N(b1),…….,N(bn) where N(ai) is the number of the city with x-coordinate ai. The length of the longest common subsequence of A and B is the maximum number of bridges. Since A and B are non-repeating, the length of the LCS for A and B can be calculated in O(n log n) time. Make sure you understand why that is the case!

Proof that length of the LCS is the maximum number of bridges: We show that the maximum number of bridges cannot be more than the length of the LCS and that the maximum number of bridges cannot be less than the length of the LCS.
Firstly, assume the length of the LCS is m. Let c1,…….,cm be a longest common subsequence of A and B, corresponding to cities ai₁……ai_m in A and bj₁,,,,,,,, bj_m in B. Then for 0 < k< = m, we can draw a bridge from ai_k to bi_k . None of these bridges intersect. Therefore, we can draw at least as many bridges as the length of the LCS.

Now assume we can draw at most m bridges from cities CA = ai₁,…..ai_m to cities CB = bj₁,….., bj_m and WLOG assume CA is ordered by increasing x-coordinate. Then N(ai_k ) = N(bj_k ) since we can draw a bridge between them. Moreover, bj_k must have a higher x-coordinate than any of bj₁,…..bj_k-1 and a lower x-coordinate than any of bj_k+1,…..,bj_m so that none of the bridges cross.Therefore CA is a subsequence of A and CB is a subsequence of B and we have found a common subsequence. Thus, the length of the LCS is at least the maximum number of bridges

Edit Distance

2011-08-06T14:27:00.001-07:00

Problem: Given two text strings A = a1a2….an of length n and B = b1b2…bm of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Give an algorithm for finding the edit distance from A to B.

Solution:
Recursion Relation: We recurse on m(i; j), the minimum number of operations to change A(1 : i) into B(1 : j). The relation is

Running Time: m has nm elements and evaluating each element takes O(1) time for a total running time of O(nm).

Balanced Partitions:

2011-08-06T14:22:00.001-07:00

Suppose you are given an array of n integers {a1,……, an} between 0 and M. Give an algorithm for dividing these integers into two sets x and y such that the difference of the sum of the integers in each set, is minimized.

For example, given the set {2,3,2,7,9}, you can divide it into {2, 2, 7} (sums to 11) and {3; 9} (sums to 12) for a difference of 1.

Solution:
Recursion Relation: Consider just the set of the numbers {a1,…..,aj}. What sums can we make with that set or subsets of it? We can make

Any sums we could make with a subset of {a1,….,aj-1}
Any sums we could make with a subset of {a1,….,aj-1} + aj

So: Let C_ij be 1 if a subset of {a1,…..,ai} adds to j and 0 otherwise. The recursion relation for C_ij is

We find the value of j, let it be b, closest to

such that C_nj = 1. The minimum difference is 2(T - b).
Running Time: We need only let j go to nM since the integers are bounded. Therefore, the size of C is n²M and filling it in takes O(1) per entry for a total running time of O(n²M).

A dynamic programming solution to this problem is provided in this video tutorial by Brian C. Dean. It is problem number 7.

Algorithm:
Firstly this algorithm can be viewed as knapsack problem where individual array elements are the weights and half the sum as total weight of the knapsack.

1.take a solution array as boolean array sol[] of size sum/2+1

2. For each array element,traverse the array and set sol [j] to be true if sol [j - value of array] is true

3.Let halfsumcloser be the closest reachable number to half the sum and partition are sum-halfsumcloser and halfsumcloser.

4.start from halfsum and decrease halfsumcloser once everytime until you find that sol[halfsumcloser] is true

Box Stacking

2011-08-06T14:05:00.001-07:00

Problem: You are given a set of boxes {b1,……,bn}. Each box bj has an associated width wj , height hj and depth dj . Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi, the 2D base of bi must be larger in both dimensions than the base of bj . You can of course, rotate the boxes to decide which face is the base, but you can use each box only once.
For example, given two boxes with h1 = 5;w1 = 5; d1 = 1 and h2 = 4;w2 = 5; h2 = 2, you should orient box 1 so that it has a base of 5x5 and a height of 1 and stack box 2 on top of it oriented so that it has a height of 5 for a total stack height of 6.

Solution:

Recursion: Memorize over H(j,R), the tallest stack of boxes with j on top with rotation R.

Running Time: The size of H is O(n |R_j|) where R is the number of possible rotations for a box.For our purposes, |R| = 3 (since we only care about which dimension we designate as the \height") so |H| = O(n). Filling in each element of H is also O(n) for a total running time of O(n²).

Code:

   1: public static int stackHeight(ArrayList<Box> boxes) {
   2:         if (boxes == null) {
   3:             return 0;
   4:         }
   5:         int h = 0;
   6:         for (Box b : boxes) {
   7:             h += b.height;
   8:         }
   9:         return h;
  10:     }
  11:     
  12:     public static ArrayList<Box> createStackR(Box[] boxes, Box bottom) {
  13:         int max_height = 0;
  14:         ArrayList<Box> max_stack = null;
  15:         for (int i = 0; i < boxes.length; i++) {
  16:             if (boxes[i].canBeAbove(bottom)) {
  17:                 ArrayList<Box> new_stack = createStackR(boxes, boxes[i]);
  18:                 int new_height = stackHeight(new_stack);
  19:                 if (new_height > max_height) {
  20:                     max_stack = new_stack;
  21:                     max_height = new_height;
  22:                 }
  23:             }
  24:         }
  25:         
  26:         if (max_stack == null) {
  27:             max_stack = new ArrayList<Box>();
  28:         }
  29:         if (bottom != null) {
  30:             max_stack.add(0, bottom);
  31:         }
  32:         
  33:         return max_stack;
  34:     }
  35:     
  36:     public static ArrayList<Box> createStackDP(Box[] boxes, Box bottom, HashMap<Box, ArrayList<Box>> stack_map) {
  37:         if (bottom != null && stack_map.containsKey(bottom)) {
  38:             return stack_map.get(bottom);
  39:         }
  40:         
  41:         int max_height = 0;
  42:         ArrayList<Box> max_stack = null;
  43:         for (int i = 0; i < boxes.length; i++) {
  44:             if (boxes[i].canBeAbove(bottom)) {
  45:                 ArrayList<Box> new_stack = createStackDP(boxes, boxes[i], stack_map);
  46:                 int new_height = stackHeight(new_stack);
  47:                 if (new_height > max_height) {
  48:                     max_stack = new_stack;
  49:                     max_height = new_height;
  50:                 }
  51:             }
  52:         }        
  53:         
  54:         if (max_stack == null) {
  55:             max_stack = new ArrayList<Box>();
  56:         }
  57:         if (bottom != null) {
  58:             max_stack.add(0, bottom);
  59:         }
  60:         stack_map.put(bottom, max_stack);
  61:         
  62:         return (ArrayList<Box>)max_stack.clone();
  63:     }
  64:         
  65:     
  66:     public static void main(String[] args) {
  67:         Box[] boxes = { new Box(1, 7, 4), new Box(2, 6, 9), new Box(4, 9, 6), new Box(10, 12, 8),
  68:                         new Box(6, 2, 5), new Box(3, 8, 5), new Box(5, 7, 7), new Box(2, 10, 16), new Box(12, 15, 9)};
  69:  
  70:         //ArrayList<Box> stack = createStackDP(boxes, null, new HashMap<Box, ArrayList<Box>>());
  71:         ArrayList<Box> stack = createStackR(boxes, null);        
  72:         for (int i = stack.size() - 1; i >= 0; i--) {
  73:             Box b = stack.get(i);
  74:             System.out.println(b.toString());
  75:         }
  76:     }
  77:  
  78: public class Box {
  79:     public int width;
  80:     public int height;
  81:     public int depth;
  82:     public Box(int w, int h, int d) {
  83:         width = w;
  84:         height = h;
  85:         depth = d;
  86:     }
  87:     
  88:     public boolean canBeUnder(Box b) {
  89:         if (width > b.width && height > b.height && depth > b.depth) {
  90:             return true;
  91:         }
  92:         return false;
  93:     }
  94:     
  95:     public boolean canBeAbove(Box b) {
  96:         if (b == null) {
  97:             return true;
  98:         }
  99:         if (width < b.width && height < b.height && depth < b.depth) {
 100:             return true;
 101:         }
 102:         return false;        
 103:     }
 104:     
 105:     public String toString() {
 106:         return "Box(" + width + "," + height + "," + depth + ")";
 107:     }
 108: }

Making change : Coin denomination problem

2011-08-06T13:55:00.001-07:00

Problem: You are given n types of coins with values {v1,…..,vn} and a cost C. You may assume v1 = 1 so that it is always possible to make any cost. Give an algorithm for finding the smallest number of coins required to sum to C exactly.
For example, assume you coins of values 1, 5, and 10. Then the smallest number of coins to make 26 is 4: 2 coins of value 10, 1 coin of value 5, and 1 coin of value 1.

Solution:

Recursion: We recurse on M(j), the minimum number of coins required to make change for cost j.

Running Time: M has C elements and computing each element takes O(n) time so the total running time is O(nC).

Working code:

All Possible Solutions

Optimal Solution

The optimal solution to this program can be found by using dynamic programming and its runtime can be considerably reduced by a technique called memoization.

Dynamic programming

2011-08-06T13:48:00.001-07:00

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.

We will look at some dynamic programming problems from easier to harder. Solutions to these problems, as with most DP problems, take the form of a recurrence relation, a short correctness proof of the recurrence relation and a running time analysis.

Q 1: Maximum value contiguous subsequence: Given a sequence of n real numbers, a1; a2; :::; an, give an algorithm for finding a contiguous subsequence for which the value of the sum of the elements is maximized.

Solution:
Recursion: We recurse on the maximum value subsequence ending at j:

With each element of M, you also keep the starting element of the sum (the same as for M(j -1) or j if you restart). At the end, you scan M for the maximum value and return it and the starting and ending indexes. Alternatively, you could keep track of the maximum value as you create M.
Running Time: M is size n and evaluating each element of M takes O(1) time for O(n) time to create M. Scanning M also takes O(n) time for a total time of O(n).

Merging two sorted arrays

2011-07-25T12:19:00.001-07:00

Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}.

Algorithm: use two pointer & points l to 1st & r to 2nd array
if element in 1st is smaller than 2nd array element at index i then increment 1st pointer
else
swap element at index i in both array &b increment 1st pointer & sort 2nd
array its not necessary only if we need sorted output in each array
Solution:
size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r

Converting a word into palindrome

2011-07-25T12:14:00.001-07:00

Q: Given a word, convert it into a palindrome with minimum addition of letters to it. letters can be added anywhere in the word. for eg if hello is given, result should be hellolleh.

Algorithm:

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome. Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack. The number of characters you need to add to the end of the original string is the number of characters on the stack. To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.

Windows 8 demo

2011-06-11T09:38:00.001-07:00

If you haven’t seen it already, may be you should. The video addresses many things in details and how windows 8 is going to change everything in developer market.

what happens when you type in a URL in browser

2011-05-06T02:18:00.001-07:00

browser checks cache; if requested object is in cache and is fresh, skip to #9
browser asks OS for server IP address
OS makes a DNS lookup and replies to browser
browser opens a TCP connection to server (this step is much more complex with HTTPS)
browser sends the HTTP request through connection
browser receives HTTP response and may close the TCP connection, or reuse it for another request
browser checks if the response is a redirect, authorization request, etc.; this is handled differently from normal responses
if cacheable, response is stored in cache
browser decodes response (e.g. if it's gzipped)
browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
browser renders response, or offers a download dialog for unrecognized types

Design Pattern:Decorator

2011-04-14T10:07:00.001-07:00

The Decorator attaches additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality.Also called as Wrapper.

Problem

Sometimes we want to add responsibilities to individual objects (aTextView ) not to an entire class. ( i.e. how to give control to client to decorate the component with a border / a scroll bar )

Illustration:

Solution

One way to add responsibilities is with inheritance.Inheriting a border with another class puts a border along very subclass instance ( inflexible solution ).
A more flexible approach is to enclose the component in another objects that adds the border. The enclosing object is called Decorator.
The Decorator confirm to interface of the component it decorate so that its presence is transparent to its components clients.

Applicability

Use Decorator

To add responsibilities to individual objects dynamically and transparently, that is, without affecting other objects.
For responsibilities that can be withdrawn.
When extension by subclassing in impractical. Sometimes a large number of independent extensions are possible and would produce an explosion of subclasses to support every combination. Or a class definition may be hidden or otherwise unavailable for subclassing.

Structure

Collaborations

Decorator forwards requests to its Component object. It may optionally perform additional operations before and after forwarding the request.

Consequences

More flexibility than static inheritance:

to add or delete responsibilities to objects at runtime simply by attaching and detaching them.
Providing different decorator classes for a specific component class lets you mix and match responsibilities.

Avoids feature-laden classes high up in the hierarchy:

Decorator offers a pay-as-you-go approach to adding responsibilities.Instead of trying to support all features in a complex, customizable class, you can define simple class and add functionality incrementally with Decorator objects.

A decorator and its component aren’t identical:

A decorator acts as a transparent enclosure.

Lots of little objects :

Decorator often results in system composed of lots of little objects that all look like, this may leed to maintenance nightmare and hard to learn.

Model

Related Patterns

Adapter: Adapter changes an object's interface, Decorator enhances an object's responsibilities. Decorator is thus more transparent to the client. As a consequence, Decorator supports recursive composition, which isn't possible with pure Adapters

Adapter provides a different interface to its subject. Proxy provides the same interface. Decorator provides an enhanced interface

Composite: A decorator can be viewed as a degenerate composite with only one component. However, a decorator adds additional responsibilities—it isn’t intended for object aggregation.

Design Pattern: Abstract Factory

2011-04-14T09:47:00.001-07:00

The purpose of the Abstract Factory is to provide an interface for creating families of related objects, without specifying concrete classes.

Problem:

• How should one go about designing applications which have to be adopted to different Look and feel standards?

Solution:

•One could solve this problem by defining abstract widgets factory class that declares an interface for creating each basic kind of widgets ( control ) .

•There is also an abstract class for each kind of widget, and concrete sub classes implement widgets for specific look and standards.

Illustration:

Applicability:

Use the Abstract Factory pattern when

A system should be independent of how its products are created, composed, and represented.
A system should be configured with one of multiple families of products.
A family of related product objects is designed to be used together, and you need to enforce this constraint.
You want to provide a class library of products, and you want to reveal just their interfaces, not their implementations.

Structure:

Collaborations

Normally a single instance of a ConcreteFactory class is created at run-time. This concrete factory creates product objects having a particular implementation. To create different product objects, clients should use a different concrete factory.

AbstractFactory defers creation of product objects to its ConcreteFactory subclass.

Consequences

It isolates concrete classes.
It makes exchanging product families easy.
It promotes consistency among products.
Supporting new kinds of products is difficult.

Model:

AbstractFactory classes are often implemented with factory methods, but they can also be implemented using Prototype.

Design Pattern: Observer

2011-04-07T10:33:00.001-07:00

The Observer defines a one to many relationship, so that when one object changes state, the others are notified and updated automatically.

The Observer design pattern is about passing notifications around to update a set of objects when some important event has occurred. You can add new observer objects at runtime and remove them as needed. When an event occurs, all registered observers are notified. Below Figure shows how it works; an observer can register itself with the subject.

And another observer, Observer 2, can register itself as well, as shown in below figure

Now the subject is keeping track of two observers. When an event occurs, the subject notifies both observers.

Illustration:

Solution:

The observer pattern describes how to establish these relationships. The key objects in this pattern are subject and observer.

A subject may have any number of dependent observer.
All observers are notified whenever the subject undergoes a change in state.
In response, each observer will query the subject to synchronize its state with the subject’s state.

Applicability:

Use the Observer pattern in any of the following situations:

When an abstraction has two aspects, one dependent on the other. Encapsulating these aspects in separate objects lets you vary and reuse them independently.
When a change to one object requires changing others, and you don’t know how many objects need to be changed.
When an object should be able to notify other objects without making assumptions about who these objects are. In other words, you don’t want these objects tightly coupled.

Structure

Collaborations

ConcreteSubject notifies its observers whenever a change occurs that could make its observers’ state inconsistent with its own.
After being informed of a change in the concrete subject, a ConcreteObserver object may query the subject for information. ConcreteObserver uses this information to reconcile its state with that of the subject.

Consequences

Abstract coupling between Subject and Observer
Support for broadcast communication.
Unexpected updates

Model

Design Pattern: Proxy

2011-04-07T10:16:00.001-07:00

The Proxy provides a surrogate or place holder to provide access to an object. You need to support resource-hungry objects, and you do not want to instantiate such objects unless and until they are actually requested by the client.

Say that you’ve got some local code that’s used to dealing with a local object as shown in the figure below

But now say that you want to deal with some remote object, somewhere else in the world. How can you make the local code think it’s dealing with a local object still when in fact it’s working with that remote object?

With a proxy. A proxy is a stand-in for another object that makes the local code think it’s dealing with a local object. Behind the scenes, the proxy connects to the remote object, all the while making the local code believe it’s working with a local object, as you can see in figure below

Illustration :problem

Consider a document editor ( Html creator ) that can embed graphical objects in a document. Some graphical objects, like large raster images, can be expensive to create. But opening a document should be fast, so we should avoid creating all the expensive objects at once when the document is opened. This isn’t necessary anyway, because not all of these objects will be visible in the document at the same time.

These constraints would suggest creating each expensive object on demand, which in this case occurs when an image becomes visible.

But what do we put in the document in place of the image? And how can we hide the fact that the image is created on demand so that we don’t complicate the editor’s implementation?

Illustration: solution

The solution is to use another object, an image proxy, that acts as a stand-in for the real image.
The proxy acts just like the image and takes care of instantiating it when it’s required.

The image proxy creates the real image only when the document editor asks it to display itself by invoking its Draw operation.
The proxy forwards subsequent requests directly to the image.
It must therefore keep a reference to the image after creating it.

Illustration: example Document Editor

Solution

Design a surrogate, or proxy, object that: instantiates the real object the first time the client makes a request of the proxy, remembers the identity of this real object, and forwards the instigating request to this real object.

Then all subsequent requests are simply forwarded directly to the encapsulated real object.

Applicability

Proxy is applicable whenever there is a need for a more versatile or sophisticated reference to an object than a simple pointer. Here are several common situations in which the Proxy pattern is applicable:

A remote proxy provides a local representative for an object in a different address space. NEXTSTEP uses the class NXProxy for this purpose.
A virtual proxy creates expensive objects on demand. The Image-Proxy described in the Motivation in an example of such a proxy.
A Protection proxy controls access to the original object. Protection proxies are useful when objects should have different access rights.
A smart reference is a replacement for a bare pointer that performs additional actions when an object is accessed.

Typical uses include

counting the number of references to the real object so that it can be freed automatically when them are no more references (also called smart pointers).
loading a persistent object into memory when it’s first referenced.
checking that the real object is locked before it’s accessed to ensure that no other object can change it

Structure

Object diagram of a proxy structure at run-time:

Collaborations

Proxy forward requests to RealSubject when appropriate, depending on the kind of proxy

Consequences

The proxy pattern introduces a level of indirection when accessing an object. The additional indirection has many uses, depending on the kind of proxy:

A remote proxy can hide the fact that an object resides in a different address space.
A virtual proxy can perform optimizations such as creating an object on demand.
Both protection proxies and smart references allow additional housekeeping tasks when an object is accessed.

Model

Design Pattern: Mediator

2011-04-07T09:53:00.001-07:00

The Mediator defines an object that controls how a set of objects interact. Loose coupling between colleague objects is achieved by having colleagues communicate with the Mediator, rather than with each other. Many a times in projects communication between components are complex.Due to this the logic between components becomes very complex. Mediator Pattern helps the objects to communicate in a disassociated manner, which leads to minimizing complexity.

Say that you’ve got a four-page Web site that lets users browse a store and make purchases. As things stand, the user can move from page to page. But there’s a problem — the code in each page has to know when to jump to a new page as well as how to activate the new page. You’ve got a lot of possible connections and a lot of duplicate code in the various pages.

You can use a mediator here to encapsulate all the navigation code out of the separate pages and place it into a mediator object instead. From then on, each page just has to report any change of state to the mediator, and the mediator knows what page to send the user to. You can build the mediator to deal with the internals of each page so the various pages don’t have to know the intimate details of the other pages (such as which methods to call). And when it’s time to modify the navigation code that takes users from page to page, that code is all collected in one place, so
it’s easier to modify.

Illustration: Problem

Consider the implementation of dialog boxes in a GUI. A dialog box uses a window to present a collection of widgets such as buttons, menus, and entry fields, as shown here.

Often there are dependencies between the widgets in the dialog. For example a button gets disabled or enabled when a certain entry in a list of choices of list box is selected .

Different dialog boxes will have different dependencies between widgets. So even though dialogs display the same kinds of widgets, they can’t simply reuse stock widget classes; they have to be customized to reflect dialog-specific dependencies. Customizing them individually by subclassing will be tedious, since many classes are involved.

Illustration:Solution

We can avoid previous said problem by encapsulating collective behavior in a separate mediator object. A mediator is responsible for controlling and coordinating the iterations of a group of objects. The mediator serves as an intermediary that keeps objects in the group form referring to each other explicitly. The objects only know the mediator, thereby reducing the number of interconnection

FontDialogDirector can be mediator between the widgets in a dialog box.

A FontDialogDirector object knows the widgets in a dialog and coordinates their interaction.

It acts as a hub of communication for widgets

In the above model notice who the director communicates with list box and entry field. Widgets communicate with each other only indirectly, through the director. All they know is the director and they in turn don’t know each other.

Furthermore, because the behavior is localized in one class, it can be changed or replaced by extending or replacing that class

Here’s the succession of events by which a list box’s selection passes to an entry field:

The following interaction diagram illustrates how the objects cooperate to handle a change in a list box’s selection.

1. The list box tells its director that it’s changed

2. The director gets the selection form the list box

3. The director passes the selection to the entry field

4. Now that the entry field contains some text, the director enables button(s) for initializing an action ( e.g. ‘demibold’,’oblique’

Applicability

Use the Mediator pattern when:

a set of objects communicate in well-defined but complex ways . The resulting interdependencies are unstructured and difficult to understand.
reusing an object is difficult because it refers to and communicates with many other objects.
a behavior that’s distributed between several classes should be customizable without a lot of sub classing.

Collaborations

Colleagues send and receive requests form a Mediator object. The mediator implements the cooperative behavior by routing between the appropriate colleague(s).

Consequences

It limits subclassing: mediator localizes behavior that otherwise would be distribured among various objects. Changing this behavior requires subclassing Mediator only; Colleagure classes can be reused as it is.
It decouples colleagues:
It simplifies object protocols: A one to many relationships are easier to understand, maintain, and extend. Thus mediator replaces many to many interactions with one-to-many interactions between the mediator and its colleagues.
It abstracts how objects cooperate:
It centralizes control:

Design Pattern : Command

2011-04-06T11:30:00.001-07:00

The Command pattern allows requests to be encapsulated as objects, thereby allowing clients to be parameterized with different requests, queue or log requests, and support undoable operations.It falls into Behavioral category.

Illustration: - Menus implemented using command

Each choice in a Menu is an instance of a MenuItem class. An Application class creates these menus and their menu items along with the rest of the user interface. The Application class also keeps track of Document objects that a user has opened.
The application configures each MenuItem with an instance of a concrete Command subclass. When the user selects a Menuitem, the Menuitem calls Execute on its command, and Execute carries out the operation.
MenuItems don’t know which subclass of Command they use. Command subclasses store the receiver of the request and invoke one or more operations on the receiver.
For example, PasteCommand supports pasting text from the clipboard into a Document. PasteCommand’s receiver is the Document object it is supplied upon instantiation. The Execute operation invokes Paste on the receiving Document.
OpenCommand’s Execute operation is different: it prompts the user for a document name, creates a corresponding Document object, adds the document to the receiving application, and opens the document.

In each of these examples, notice how the Command pattern decouples the object that invokes the operation from the one having the knowledge to perform it. This gives us a lot of flexibility in designing our user interface. An application can provide both a menu and a push button interface to a feature just by making the menu and the push button share an instance of the same concrete Command subclass. We can replace commands dynamically, which would be useful for implementing context-sensitive menus. We can also support command scripting by composing commands into larger ones. All of this is possible because the object that issues a request only needs to know how to issue it; it doesn’t need to know how the request will be carried out.

Solution

Command decouples the object that invokes the operation from the one that knows how to perform it. To achieve this separation, the designer creates an abstract base class that maps a receiver (an object) with an action (a pointer to a member function). The base class contains an execute() method that simply calls the action on the receiver.
All clients of Command objects treat each object as a "black box" by simply invoking the object's virtual execute() method whenever the client requires the object's "service".
Sequences of Command objects can be assembled into composite (or macro) commands.

Applicability

Use the Command pattern when you want to

parameterize objects by an action to perform, as MenuItem.
You can express such parameterization in a procedural language with a callback function, that is, a function that’s registered somewhere to be called at a later point. Commands are an object Oriented replacement for callbacks.
Specify, queue, and execute requests at different times. A Command object can have a lifetime independent of the original request. If the receiver of a request can be represented in an address space-independent way, then you can transfer a command object for the request to a different process and fulfill the request there.
Supports Undo
Support logging changes to that they can be reapplied in case of a system crash. - Recovering form a crash involves reloading logged commands form disk and re-executing them with the execute operation.
Structure a system around high-level operations built on primitives operations. Such structure is common in information system that support transactions.

Structure

Collaborations

The client creates a ConcreteCommand object and specifies its receiver.
An Invoker object stores the ConcreteCommand object.
The invoker issues a request by calling Execute on the command. When commands are undo-able, ConcreteCommand stores state for undoing the com-mand prior to invoking Execute.
The ConcreteCommand object invokes operations on its receiver to carry out the request.

The following diagram shows the interactions between these objects. It illustrates how Command decouples the invoker form the receiver ( and the request it carries out ).

Consequences

The Command pattern has the following consequences:

Command decouples the object that invokes the operation from the one that knows how to perform it.
Commands are first-class objects. They can be manipulated and extended like any other object.
You can assemble commands into a composite command. An example is the Macro Command class described earlier. In general, composite commands are an instance of the Composite pattern.
It’s easy to add new Commands, because you don’t have to change existing classes

Model:

Design Pattern: Adapter

2011-04-05T09:55:00.001-07:00

It falls into structural pattern category. The Adapter pattern allows otherwise incompatible classes to work together by converting the interface of one class into an interface expected by the clients. Adapter lets classes work together that couldn’t otherwise because of incompatible interfaces.

•Use the Adapter pattern when

You want to use an existing class, and its interface does not match the one you need.
You want to create a reusable class that cooperates with unrelated or unforeseen classes, that is, classes that don’t necessarily have compatible interfaces.
You need to use several existing subclasses, but it’s impractical to adapt their interface by subclassing every one. An object adapter can adapt the interface of its parent class.

Structure

Collaborations

Clients call operations on an Adapter instance. In turn, the adapter calls Adaptee operations that carry out the request.

Consequences:

Class and object adapters have different trade-offs.

A: class adapter:

1. Adapts Adapter to target by committing to a concrete Adapter class. As a consequence, a class adapter won’t work when we want to adapt a class and all its subclasses.

2. Lets-adapter override some of Adaptee’s behavior, since Adapter is a subclass of Adaptee.

3. Introduces only one object, and no additional pointer indirection is needed to get to the Adaptee

B: Object adapter:

1.Lets a single adapter work with many Adaptees-that is, the Adaptee itself and all of its subclasses (if any). The Adapter can also add functionality to all Adaptees at once.

2. Makes it harder to overide Adaptee behavior. It will require subclassing Adaptee and making Adapter refer to the subclass rather than the Adapter itself.

Issues to be considered while using adapter pattern:

1. How much adapting does Adapter do?

Pluggable adapters.
Using two-way adapters to provide transparency

Design Pattern : Facade

2011-04-05T08:56:00.001-07:00

It falls into structural pattern categories. The Facade Pattern defines a higher level interface to a subsystem, that makes it easier to use. It provides unified interface to a set of interfaces in a subsystem.

Use the Facade pattern when

•You want to provide a simple interface to a complex subsystem.

To tackle the complexity of subsystem as they evolve

Most patterns, when applied, result in more and smaller classes. This makes the subsystem more reusable and easier to customize, but it also becomes harder to use for clients that don’t need to customize it.

A façade can provide a simple default view of the subsystem that is good enough for most of the clients. Only clients needing more customizability will need to look beyond the façade

•Facade to decouple the subsystem for clients and other subsystems, thereby promoting subsystem independence and portability which tackle the disadvantage of dependencies between clients and the implementation classes on an abstraction.

•To layer your subsystem. Use façade to define an entry point to each subsystem level. If subsystems are dependent, then you can simplify the dependencies between them by making them communicate with each other solely through their facades.

The structure of the Façade Pattern looks as below

•Clients communicate with the subsystem by sending request to Façade, which forwards them to the appropriate subsystem object(s). Although the subsystem objects perform the actual work, the façade may have to do work of its own to translate its interface to subsystem interfaces.

•Clients that user the façade don’t have to access its subsystem objects directly.

The Facade Patterns offers the following benefits:

•1. It shields client from subsystem components, thereby reducing the number of objects that clients deal with and making the subsystem easier to use.

•It promotes weak coupling between the subsystem and its clients.

•It doesn’t prevent applications form using subsystem classes if they need to. Thus you can choose between ease of use and generality

Illustration: Problem

Consider for example a programming environment that gives application access to its compiler subsystem. This subsystem contains classes such as Scanner, Parser,ProgramNode, ByteCodeStream, and ProgramNodeBuilder that implements the Compiler. Some Specialized applications might need to access these classes directly.

But most clients of a compiler generally don’t care about details like parsing and byte code generation; they merely want to complier subsysem only complicate their task.

Illustration : solution

Compiler class in the above can act as a facade, which will provide higher-level interface that can shield clients form these classes, the compiler subsystem also includes a Compiler class. This class defines a unified interface to the compiler’s functionality.

It offers client a single, simple interface to the compiler subsystem. It glues together the classes that implement compiler functionality without hiding them completely.

[Compiler façade makes easier for most programmers without hiding the lower-level functionality form the few that need it]

Class Diagram Solution:

Database Input Issues

2011-03-30T11:36:00.001-07:00

This was a sample presentation which I created at my workplace to present Database security issues. Most of the content is taken from the book Writing Secure code. Hope it is helpful to someone.

Number to word converter

2011-03-30T10:48:00.001-07:00

Q: Take a number and give the equivalent number in British English words e.g.

1 = one

21 = twenty one

105 = one hundred and five

56945781 = fifty six million nine hundred and forty five thousand seven hundred and eighty one

etc.. up to 999,999,999 without using a tokenizer, or any external libraries

Working Code:

 import java.text.DecimalFormat;
  public class NumberToWord {
      private static final String[] tensWords = { "", " ten", " twenty",   
            " thirty", " forty", " fifty", " sixty", " seventy", " eighty",    
            " ninety" };
      private static final String[] words = { "", " one", " two", " three",   
            " four", " five", " six", " seven", " eight", " nine", " ten",    
            " eleven", " twelve", " thirteen", " fourteen", " fifteen",    
            " sixteen", " seventeen", " eighteen", " nineteen" };
      // Convert Number to word which is less than one thousand    
    private static String convertLessThanOneThousand(int number) {    
        String thousandWord;
          if (number % 100 < 20) {   
            thousandWord = words[number % 100];    
            number /= 100;    
        } else {    
            thousandWord = words[number % 10];    
            number /= 10;
              thousandWord = tensWords[number % 10] + thousandWord;   
            number /= 10;    
        }    
        
        if (number == 0)    
            return thousandWord;    
        
        return words[number] + " hundred" + thousandWord;    
    }
      
    //Converts any number to word between 0 to 999 999 999 999 billions millions    
    public static String convertNumberToWord(long number) throws Exception{
          if(number < 0)   
        {    
            throw new Exception("Negative numbers not supported");    
        }    
        
        if (number == 0) {    
            return "zero";    
        }
          String snumber = Long.toString(number);   
        if(snumber.length() > 13)    
        {    
            throw new Exception("Numbers greater than 999 billion are not supported");    
        }
          // pad with "0"   
        String mask = "000000000000";    
        
        // DecimalFormat converts 50 to 000000000050 based on the given mask    
        DecimalFormat df = new DecimalFormat(mask);    
        snumber = df.format(number);
          StringBuilder result = new StringBuilder();
          // XXXnnnnnnnnn   
        int billions = Integer.parseInt(snumber.substring(0, 3));    
        // nnnXXXnnnnnn    
        int millions = Integer.parseInt(snumber.substring(3, 6));    
        // nnnnnnXXXnnn    
        int hundredThousands = Integer.parseInt(snumber.substring(6, 9));    
        // nnnnnnnnnXXX    
        int thousands = Integer.parseInt(snumber.substring(9, 12));
          String wordBillions;   
        switch (billions) {    
        case 0:    
            wordBillions = "";    
            break;    
        case 1:    
            wordBillions = convertLessThanOneThousand(billions) + " billion";    
            break;    
        default:    
            wordBillions = convertLessThanOneThousand(billions) + " billion";    
        }
          result.append(wordBillions);
          String wordMillions;   
        switch (millions) {    
        case 0:    
            wordMillions = "";    
            break;    
        case 1:    
            wordMillions = convertLessThanOneThousand(millions) + " million";    
            break;    
        default:    
            wordMillions = convertLessThanOneThousand(millions) + " million";    
        }
          result.append(wordMillions);
          String wordHundredThousands;   
        switch (hundredThousands) {    
        case 0:    
            wordHundredThousands = "";    
            break;    
        case 1:    
            wordHundredThousands = "one thousand ";    
            break;    
        default:    
            wordHundredThousands = convertLessThanOneThousand(hundredThousands)+ " thousand";    
        }
          result.append(wordHundredThousands);
          result.append(convertLessThanOneThousand(thousands));
          return result.toString();   
    }
      public static void main(String[] args) {   
        
        String word = "";    
        try {    
            word = NumberToWord.convertNumberToWord(999999999999L);    
        } catch (Exception e) {    
            System.out.println("error: "+e.getMessage());    
        }    
        System.out.println(word);    
    }
  }

Serializing a binary tree

2011-03-27T01:31:00.001-07:00

Q: Design an algorithm and write code to serialize and deserialize a binary tree.

Advantages of serialization/deserialization include storing a binary into and restoring it for a later point of time, transmitting the tree over a network from one computer and load it in another computer.

One approach for this problem could be the nodes with NULL values using some kind of sentinel so that later nodes can be inserted In correct place while deserialization. Lets use the sentinel as # and we will use preorder traversal here serialization.

Assume we have a binary tree below:

The preorder traversal of the above tree can be written as

30 10 50 # # # 20 45 # # 35 # #

Finding Unique number

2011-03-23T08:51:00.001-07:00

Q: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
Fastest way to find that single integer

eg:
Input: {1,1,1,3,3,3,20,4,4,4};

Answer: 20

The logic is similar to finding the element which appears once in an array - containing other elements each appearing twice. There we do XOR all the elements and the result will be the unique number.

To apply the similar logic to this problem we maintain 2 variables

ones - This variable holds XOR of all the elements which have appeared only once.
twos - This variable holds XOR of all the elements which have appeared twice.

The algorithm goes as follows…

1. A new number appears - It gets XOR' ed to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twos".
3. A number appears for the third time - It gets removed from both "ones" and "twos".

The final answer will be in "ones" as it holds the unique element.

Working Java code:

Multiplication of numbers

2011-03-22T08:47:00.001-07:00

Q: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}

Since we should not use, division operator, Brute force approach would be O(n^2)

Other approach is by storing the result temporarily in an array.

Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.

Above approach requires O( n ) time and also O( n ) space.

We can actually avoid the temporary array. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left.

Robot Unique Paths

2011-03-22T08:18:00.001-07:00

Q: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

We can solve this problem using backtracking approach.

Other approach is using dynamic programming with memorization.

Longest Palindrome in a string

2011-03-21T09:28:00.001-07:00

Brute force Algorithm.

Have 2 for loops
for i = 1 to i less than array.length -1
for j=i+1 to j less than array.length
This way you can get substring of every possible combination from the array
Have a palindrome function which checks if a string is palindrome
so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
If you find next palindrome substring and if it is greater than the current one, replace it with current one.
Finally your string variable will have the answer

Brute force approach for this problem takes O(n3) time.

Another approach is

Reverse the string and store it in different string
Now find the largest matching substring between both the strings

This too will take O(n2) time

We can solve this problem using suffix trees, but constructing the suffix tree itself seems to be more complex in terms of both time and space complexity.

We can solve this problem using a better approach which will revolve around with a center for every single character.

For each position in the string we store an upper and lower pointer that tracks the upper and lower bounds of the largest palindrome centered at that position.

For instance, position 2 in the string "racecar" would start as:

At this point, the longest known palindrome at position 2 is the single character 'c'. We then increment the upper pointer and decrement the lower pointer and compare their respective values.

Since the upper and lower values are not the same, we stop and now know that the longest palindrome centered at position 2 is 'c'. We then start the process again at the next string position, 3.

We increment and decrement the upper and lower pointers and see that they are equal. Our current longest palindrome centered at position 3 is now 'cec'.

Since they were equal, we increment and decrement the pointers again and see that they are still equal. Our new longest palindrome centered at position 3 is now 'aceca'.

We continue incrementing and decrementing the upper and lower pointers until they don't match or they hit one of the ends of the string.

Since our pointers are equal, we increment and decrement them again. We hit an end of the string and the pointers are equal so we know that our longest palindrome centered at position 3 is 'racecar'.

We're done with position 3 and continue this same process again at position 4. We'll do this until we've covered every position in the string.

NOTE: We initially assumed that the palindrome had an odd length. This algorithm works for even palindromes as well. The only change we make is that when we initialize the pointers, instead of having the lower and upper pointer point to the same position we have the upper pointer point at the next position. Everything else with the algorithm remains the same. i.e. The initial pointers for an even palindrome 'centered' at position 3 would look like:

Runtime:

Worst-Case: O(N^2)

Best-Case: O(N)

The worst case is achieved when the string is a single repeated character because every substring is a palindrome.

The best case is achieved when the string contains no palindromes.

Typically if a string only contains a single palindrome (the fewer the better), the closer to O(N) it will run. This is because every time it checks a position in the string, it checks the character before and after that position, and if they don't match then it stops looking for the palindrome. Positions in the string can be discarded after only one lookup if that position doesn't have a palindrome, so if there are no palindromes you only do N comparisons.

JavaCode:

3 sum and 2 sum problem

2011-03-21T09:00:00.001-07:00

Q: Given an integer x and an unsorted array of integers, describe an algorithm to determine whether two of the numbers add up to x.

If we have hash table, we can just check for every number ‘a’, if x-‘b’ is present in hash table. This takes O( n ) with constant space for hashtable. What if the interviewer hates the hashtable.

Sort the array. Then, keep track of two pointers in the array, one at the beginning and one at the end. Whenever the sum of the current two integers is less than x, move the first pointer forwards, and whenever the sum is greater than x, move the second pointer backwards. This solution takes O(n log n) time because we sort the numbers.

Another approach for this problem could be…

Create a binary search tree containing x minus each element in the array. Then, check whether any element of the array appears in the BST. It takes O(n log n) time to create a binary search tree from an array, since it takes O(log n) time to insert something into a BST, and it takes O(n log n) time to see if any element in an array is in a BST, since the lookup time for each element in the array takes O(log n). Therefore step one takes O(n log n) time and step two takes O(n log n) time, so our total running time is O(n log n).

Variations for this problem would be, find three integers a,b,c in the array such that a+b=c

This will take O(n²) time complexity.

Other variation is Find three integers a,b,c in the array such that a+b+c =0

Big File containing billions of numbers

2011-03-20T10:57:00.001-07:00

Q: There is big file containing billions of numbers. How do we find maximum 10 numbers from those files?

Priority queue is the best data structure to answer such question. Of course loading all the data and building the heap is not such a good idea. Main challenge is how do we manage chunks of data in memory and arrive at the solution.

Divide the data into some sets of 1000 elements, make a heap of them and take 10 element from each heap one by one. Finally sort all the sets of 10 elements and take top 10 among those. But where do we store 10 element from each heap which may itself require large amount of memory as we have billions of numbers.

Reuse top 10 elements from earlier heap in subsequent elements can solve this problem. Take first block of 1000 elements and subsequent blocks of 990 elements. The last set of 990 elements or less than that and taking top 10 elements from the final heap will fetch you the answer.

Time Complexity would be O( (n/1000)*(complexity of heapsort of 1000 elements) = O( n )

Median of two sorted arrays

2011-03-18T23:21:00.001-07:00

This question is similar to the previous question which can solved in O(logn) using binary search approach. Lets see the algorithm….

Algorithm
1.Let the two arrays be a1,a2 with n elements each with n elements
2.Let med1 and med 2 be the medians of two arrays respcetively
3.if med1==med2 means the required median is med1(or med2)
4.if med1 < med2 that means the median can either lie in upper half of a1 or lower half of a2 5.if med1 >med2 that means the median can be in lower half of of a1 or upper half of a2
we continue this process until two elements are present in the array
if two elements are present in the array then we calculate the median as follows
median_required = (max(a1[0],a2[0])+min(a1[1]+a2[1])) /2

Kth Smallest element

2011-03-18T10:29:00.001-07:00

Q: Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

One approach we could think of is merge both arrays and the k-th smallest element could be accessed directly. Merging would require extra space of O(m+n). The linear run time is pretty good, but could we improve it even further?

Another approach is using two pointers, you can traverse both arrays without actually merging them, thus without the extra space. Both pointers are initialized to point to head of A and B respectively, and the pointer that has the larger of the two is incremented one step. The k-th smallest is obtained by traversing a total of k steps.

We can solve this problem in logarithmic time in O(lg m + lg n) using binary search approach.

We try to approach this tricky problem by comparing middle elements of A and B, which we identify as A_i and B_j. If A_i is between B_j and B_j-1, we have just found the i+j+1 smallest element. Therefore, if we choose i and j such that i+j = k-1, we are able to find the k-th smallest element. This is an important invariant that we must maintain for the correctness of this algorithm.

Maintaining the invariant
i + j = k – 1,

If B_j-1 < A_i < B_j, then A_i must be the k-th smallest,
or else if A_i-1 < B_j < A_i, then B_j must be the k-th smallest.

We can make an observation that when A_i < B_j, then it must be true that A_i < B_j-1. On the other hand, if B_j < A_i, then B_j < A_i-1.

Using the above relationship, it becomes clear that when A_i < B_j, A_i and its lower portion could never be the k-th smallest element. So do B_j and its upper portion. Therefore, we could conveniently discard A_i with its lower portion and B_j with its upper portion.

Saving a Binary Search Tree to a File

2011-03-18T09:10:00.001-07:00

Q: Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

Pre-order traversal is the perfect algorithm for making a copy of a BST. We can store the preorder traversal of the tree into File and then read it again to construct the tree. Assuming we have a file where the pre order traversal of the tree is written to it, We will now see how to read the file to construct that into BST.

Sorted List to Balanced Binary Search Tree

2011-03-18T08:29:00.001-07:00

Q: Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

We can solve this problem using bottom up approach with recursion. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes. Lets define the node structure for Binary Search Tree Node as follows

Below is the java code for converting a singly linked list to a balanced BST. The algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

Word Suggest

2011-03-16T10:12:00.001-07:00

This is general algorithm we use in search engines. Question is Given a dictionary suggest the words for a given misspelled word.

The word could be misspelled in either of the following 4 ways.

Transpositions: These are set of words where 2 adjacent characters in a word are trans positioned. Ex: hlelo –> hello . There are atmost n-1 trans positioned words for a given word.
Insertion: Word could be misspelled by inserting an extra character. Ex: helxlo –> hello There could be at the max n+1 words with this.
Substitution: Word could be misspelled by typing wrong character in place of another character. Ex: helxo –> hello . Max No. of Substituted words could 25 * ( n )
Omissions: These are set of words where a character is omitted Ex: hllo –> hello . Max No of omitted words could be 26*(n+1)

Lets code them now.

Suffix Trees

2011-03-16T08:46:00.001-07:00

Suffix Tree for a String T is Trie like data that represents the suffixes of T. For example, if your word were bibs, you would create the following tree.

Suffix trees answers the queries related to one string. There are many applications of suffix trees. Some of them are..

String Matching and Pattern Matching algorithm
Longest Repeated SubString
Longest palindrome
Longest common substring
Longest Common prefix

Sample java Implementation of Suffix Tree:

String Search

Searching for a substring, pat[1..m], in txt[1..n], can be solved in O(m) time (after the suffix tree for txt has been built in O(n) time).

Longest Repeated Substring

Add a special ``end of string'' character, e.g. `$', to txt[1..n] and build a suffix tree; the longest repeated substring of txt[1..n] is indicated by the deepest fork node in the suffix tree, where depth is measured by the number of characters traversed from the root, i.e., `issi' in the case of `mississippi'. The longest repeated substring can be found in O(n) time using a suffix tree.

Longest Common Substring

The longest common substring of two strings, T1 and T2, can be found by building a generalized suffix tree for T1 and T2 : Each node is marked to indicate if it represents a suffix of T1 or T2 or both. The deepest node marked for both T1 and T2 represents the longest common substring.

Equivalently, one can build a (basic) suffix tree for the string T1$T2#, where `$' is a special terminator for T1 and `#' is a special terminator for T2. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.

Palindromes

A palindrome is a string, P, such that P=reverse(P). e.g. `abba'=reverse(`abba'). e.g. `ississi' is the longest palindrome in `mississippi'.

The longest palindrome of T can be found in O(n) time, e.g. by building the suffix tree for T$reverse(T)# or by building the generalized suffix tree for T and reverse(T).

Linked List Question

2011-03-16T02:33:00.001-07:00

Q: Given a linked list with two pointers in node structure where one points to the next node and the other pointer points to some random node in the linked list. Write a program to create a copy of this linked list

The above problem can be solved in O( n ) time and in constant space complexity. Assuming the Node Structure as following..

Algorithm:

1)[Merge listst]Create list B this way: for each NodeA in A create a NodeB in B , copy NEXT ptr to NodeB: NodeB{NEXT} = NodeA{NEXT} and change NEXT ptr in NodeA to this newly created node in B: NodeA{NEXT}=NodeB;
2) go through the list A (NB: you have to jump through the nodes of B!) and set NEXTRND ptr in next B nodes to the next ptrs after next_random nodes: NodeA{NEXT}{NEXTRND}=NodeA{NEXTRNF}{NEXT};
After that all NEXTRND nodes in list B will be pointing to correct nodes in B;
3) [Un-merge]. For each node in A and in NEXT node B set correct NEXT ptrs:
node=headA;
while(node){tmp = node{NEXT}; node{NEXT}=tmp?tmp{NEXT}:NULL; node=tmp;}
After this process all {NEXT} nodes in both lists A and B will be correct

Java Code:

Best days to sell and buy stock, if array of stock prices given

2011-03-16T02:05:00.001-07:00

Q: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell

Algorithm: Go through the array in order, keeping track of the lowest stock price and the best deal you've seen so far. Whenever the current stock price minus the current lowest stock price is better than the current best deal, update the best deal to this new value.

Working Java Code:

Arranging elements in specific order

2011-03-15T10:58:00.001-07:00

n a given array of elements like [a1, a2, a3, a4, ..... an, b1, b2, b3, b4, ....... bn, c1, c2, c3, c4, ........ cn] without taking a extra memory how to merge like [a1, b1, c1, a2, b2, c2, a3, b3, c3, ............ an, bn, cn]

Triplet (x,y,z) whose distance is min

2011-03-15T10:50:00.001-07:00

Given 3 sorted arrays (in ascending order). Let the arrays be A(of n1 length), B(of n2 length), C(of n3 length). Let x be an element of A, y of B, z of C. The distance between x, y and z is defined as the max(|x-y|,|y-z|,|z-x|). Find the tuple with the minimum distance?

Working java Code:

External Merge Sort

2011-03-15T10:40:00.001-07:00

If data to be sorted doesn’t fit into main memory external sorting is applicable. External merge sort can be separated into two phases:

Create initial runs (run is a sequence of records that are in correct relative order or in other words sorted chunk of original file).
Merge created runs into single sorted file.

Let’s assume that M records at the same time are allowed to be loaded into main memory. One of the ways to create initial runs is to successively read M records from original file, sort them in memory and write back to disk.

The core structure behind this algorithm is priority queue. Taking one by one current minimum element out of the queue forms ordered sequence.

The algorithm can be described as follows:

Create two priority queues (that will contain items for current and next runs respectively) with capacity of M records.
Prefill current run priority queue from unsorted file with M records.
Create current run if there are elements in the current run priority queue:
1. Take minimum element out of current run priority queue and append it to current run (basically write it to disk).
2. Take next element from unsorted file (this is the replacement part of the algorithm) and compare it with just appended element.
3. If it is less then it cannot be part of the current run (or otherwise order will be destroyed) and thus it is queued to the next run priority queue.
4. Otherwise it is part of the current run and it is queued to the current run priority queue.
5. Continue steps 1 through 4 until current run priority queue is empty.
Switch current and next runs priority queues and repeat step 3.

At any given moment at most M records are loaded into main memory as single written element into current run is replaced with single element from unsorted file if any (depending on comparison it either goes into current or next run).

Next step is to merge created initial runs. For the merge step we will use simplified algorithm based on k-way merge.

Append created runs into a queue.
Until there are more than one run in the queue:
1. Dequeue and merge K runs into a single run and put it into the queue.
Remaining run represents sorted original file.

K-Way Merge

2011-03-15T10:27:00.001-07:00

The classic merge takes as input some sorted lists and at each step outputs element with next smallest key thus producing sorted list that contains all the elements of the input lists.

We can solve this problem using two ways.

Let the sorted arrays be A1, A2,...Ak

Way 1:
Merge (A1, A2), (A3, A4),...
Then there are k/2 sorted arrays now.
Repeat the above procedure to get the full array sorted. It is not always practical to have whole sequence in memory because of its considerable size nor to constraint sequence to be finite as only K first elements may be needed. Thus our algorithm must produce monotonically increasing (according to some comparison logic) potentially infinite sequence. This way wont work as the memory we can use is limited

Way 2:
Form a priority min heap from the first element of all the k arrays. Extract the min element. It is the min element among all the arrays. Now take the next element from the array from which the min element has come, and put it in the min heap. Repeat the procedure.

The queue will hold non empty sequences.
The priority of a sequence is its next element.
At each step we dequeue out of the queue sequence that has smallest next element. This element is next in the merged sequence.
If dequeued sequence is not empty it must be enqueued back because it may contain next smallest element in the merged sequence.

Thus we will have queue of size that doesn’t exceed m (number of sequences) and thus making total running time O(n log m). It works well with infinite sequences and cases where we need only K first elements and it fetches only bare minimum out of source sequences.

Selecting k smallest or largest elements

2011-03-15T09:59:00.001-07:00

There are cases when you need to select a number of best (according to some definition) elements out of finite sequence (list). For example, select 10 most popular baby names in a particular year or select 10 biggest files on your hard drive.

While selecting single minimum or maximum element can easily be done iteratively in O(n) selecting k smallest or largest elements (k smallest for short) is not that simple. One approach could be sort the elements and take the first k elements. But that requires O( nlogn) time.

Priority Queue can be used for better performance if only subset of sorted sequence is required. It requires O(n) to build priority queue based on binary min heap and O(k log n) to retrieve first k elements. Can we improve this further?

Quicksort algorithm picks pivot element, reorders elements such that the ones less than pivot go before it while greater elements go after it (equal can go either way). After that pivot is in its final position. Then both partitions are sorted recursively making whole sequence sorted. In order to prevent worst case scenario pivot selection can be randomized.

Basically we are interested in the k smallest elements themselves and not the ordering relation between them. Assuming partitioning just completed let’s denote set of elements that are before pivot (including pivot itself) by L and set of elements that are after pivot by H. According to partition definition L contains |L| (where |X| denotes number of elements in a set X) smallest elements. If |L| is equal to k we are done. If it is less than k than look for k smallest elements in L. Otherwise as we already have |L| smallest elements look for k - |L| smallest elements in H.

Working Java Code:

Queue based on single stack

2011-03-15T09:40:00.001-07:00

Queue based on 2 stacks is generally what we usually know of and probably would be on our minds while answering such questions. We could solve the same using one stack and taking advantage of recursion. We will see how we can solve this with no additional storage.

Assume that items come out of stack in the order they must appear in the queue (FIFO). Choosing the opposite order is also possible however is not practical. To make it happen we simply need to make sure that items in the stack (LIFO) are placed in the opposite order. Items queued first must appear at the top of the stack. This basically means that in order to queue item all items must be popped, the item pushed and then existent items pushed inversely to pop order. But we have no additional explicit storage requirement. Then store items implicitly through recursion.

Enqueue is a O(n) operation (where n is the number items in the stack). Dequeue and Peek is a O(1) operation.

Cumulative sum of a tree at each node.

2011-03-15T09:00:00.001-07:00

Q: Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order

This question can be answered in two ways. We can do it using two passes with constant space of with one pass and O( n ) space.

Lets say the tree node is as follows

Converting a Tree to a double Linked List

2011-03-15T08:24:00.001-07:00

Q: Write a program which will accept Binary Search Tree and convert it to a sorted Double Linked List.

For example if the Binary search tree is as shown below…

Then the converted doubly linked list should be

Lets define the Node structure of the tree as follows

We can use recursive approach to solve this by just arranging the pointers..

Algorithm:

If tree is not empty

Convert Left Subtree to List and let hLeft point to it

Convert Right Subtree to List and left hRight point to it.

Append hLeft to root and then hRight

Working java Code:

Minimum window that contains all characters

2011-03-14T10:24:00.001-07:00

Q: Find the smallest window in a string containing all characters of another string

Given set of characters P and string T find minimum window in T that contains all characters in P. Applicable solution is restricted to O(length(T)) time complexity. For example, given a string T “of characters and as” and set of characters T in a form of a string “aa s” the minimum window will be “and as”.

The problem can be broken into two parts:

How to select window?
How to check that selected window contains all characters from P?

Selecting every possible window (all unique pairs (i, j) where 0 <= i <= j < length(T)) will lead to solution worse than O(length(T)^2) because you still need to check if all characters from P are within selected window. Instead we will check every possible window ending position. Thus there are at least length(T) windows to consider.

Any feasible window has length equal to or greater than length(P). Performing recheck for any considered window will result in a solution no better than O(length(T)*length(P)). Instead we need to use check results from previous iteration.

Now we need to make sure that checking if a particular character is in P is done in an optimal way. Taking into account that a particular character may appear more than once and window thus must contain appropriate number of characters. We will use hash table to map unique characters from P to their count for fast lookup.

And now let’s tie all things together.

Until reached the end of T move by one current window ending position.
Append next character to the end of previous window which to this moment doesn’t contain all necessary characters. Char to count map is used to track the number of characters left to find. Basically if character is in P count is decremented. The number may become negative meaning that there are more than required characters.
If unmatched character count goes to zero the window contains all required characters. However there may be redundant characters. Thus we try to compact current window. It is ok to do this as we are looking for minimum window and any window that is extended from this one won’t be better.
Once window is compacted compare it with the minimum one and updated it if needed.
If current window contains all the characters remove from it the first one simply by moving by one starting position to make sure that at each iteration previous window doesn’t contain all the characters (there is no point in appending new characters to a window that already contains all of the required ones).

Working Java code:

   public static String findMinWindow(String t, String p)   
    {    
        // Create char to count mapping for fast lookup    
        // as some characters may appear more than once    
        HashMap<Character, Integer> charToCount = new HashMap<Character, Integer>();    
        for (char c : p.toCharArray())    
        {    
            if (!charToCount.containsKey(c))    
                charToCount.put(c, 0);    
            charToCount.put(c, charToCount.get(c)+1);    
        }    
     
        int unmatchesCount = p.length();    
        int minWindowLength = t.length() + 1,minWindowStart = -1;    
        int currWindowStart = 0, currWindowEnd = 0;    
        for (; currWindowEnd < t.length(); currWindowEnd++)    
        {    
            char c = t.charAt(currWindowEnd);    
            // Skip chars that are not in P    
            if (!charToCount.containsKey(c))    
                continue;    
            // Reduce unmatched characters count    
            charToCount.put(c, charToCount.get(c)-1);    
            if (charToCount.get(c) >= 0)    
                // But do this only while count is positive    
                // as count may go negative which means    
                // that there are more than required characters    
                unmatchesCount--;    
     
            // No complete match, so continue searching    
            if (unmatchesCount > 0)    
                continue;    
     
            // Decrease window as much as possible by removing    
            // either chars that are not in T or those that    
            // are in T but there are too many of them    
            c = t.charAt(currWindowStart);    
            boolean contains = charToCount.containsKey(c);    
            while (!contains || charToCount.get(c) < 0)    
            {    
                if (contains)    
                    // Return character to P    
                    charToCount.put(c,charToCount.get(c)+1);    
     
                c = t.charAt(++currWindowStart);    
                contains = charToCount.containsKey(c);    
            }    
     
            if (minWindowLength > currWindowEnd - currWindowStart + 1)    
            {    
                minWindowLength = currWindowEnd - currWindowStart + 1;    
                minWindowStart = currWindowStart;    
            }    
     
            // Remove last char from window - it is definitely in a    
            // window because we stopped at it during decrease phase    
            charToCount.put(c, charToCount.get(c)+1);    
            unmatchesCount++;    
            currWindowStart++;    
        }    
     
        return minWindowStart > -1 ?    
               t.substring(minWindowStart, minWindowLength) : "";    
    }

Every character is examined at most twice (during appending to the end and during compaction) so the whole solution has O(length(T)) time complexity assuming hash table lookup is O(1) operation.

Traversing binary tree in zig zag order

2011-03-14T09:50:00.001-07:00

The question is we need to traverse binary tree level by level in such a way that traversal direction within level changes from level to level thus forming a spiral.

We’ll start with a well know problem of traversing binary tree level by level It can be done using queue. But this problem seems to be tricky. Its not the obvious approach. Instead of going with queue approach we can solve this problem using two stacks. Let us say the two stacks are curr Level and nextLevel. Next level is a set of child nodes from current level. We also need a variable to keep track of the current level’s order. If next level must be traversed from left to right we must first push right child node and then left and in opposite order if next level will be traversed from right to left we will push the left child first and then right child.

Working Java Code:

  public void spiralOrderTraversal(BinaryTreeNode root)   
    {    
        Stack<BinaryTreeNode> currentLevel,nextLevel;    
        BinaryTreeNode temp;    
        int leftToRight = 1;    
        
        if(root == null)    
            return;    
        
        currentLevel = new Stack<BinaryTreeNode>();    
        nextLevel = new Stack<BinaryTreeNode>();    
        
        currentLevel.push(root);    
        
        while(!(currentLevel.isEmpty())    
        {    
            temp = currentLevel.pop();    
            if(temp)    
            {    
                System.out.println(temp.data);    
                if(leftToRight)    
                {    
                    if(temp.left)    
                        nextLevel.push(temp.left);    
                    if(temp.right)    
                        nextLevel.push(temp.right);    
                }    
                else    
                {    
                    if(temp.right)    
                        nextLevel.push(temp.right);    
                    if(temp.left)    
                        nextLevel.push(temp.left);    
                }    
                
                if(currentLevel.isEmpty())    
                {    
                    leftToRight = 1-leftToRight;    
                    swap(currentLevel,nextLevel)    
                }     
            }    
        }    
    }

Longest consecutive elements sequence

2011-03-14T09:22:00.001-07:00

For example, in {5, 7, 3, 4, 9, 10, 1, 6, 15, 1, 3, 12, 2, 11} longest sequence is {1, 2, 3, 4, 5,6}.

The first thing that comes into our mind is to sort given array in O(n log n ) and look for longest consecutive elements sequence. Can we do it in Linear time?

The next solution would be using bit vector indexed by numbers from original array. It may not be justified due to incomparable solution space and original array size (although time complexity is O(n)).

Lets see how to solve this problem in O( n ) time complexity with constant space assuming the hashtable has O(1) time complexity and constant space complexity.

By Knowing range boundaries we can definitely say what numbers are in there (for example, [1..3] contains 1, 2, 3). O(1) time complexity for range manipulation operations with O(1) space complexity for each range are the things we are looking for. We can do this using two hash tables:

‘low’ with range start numbers as keys and range end numbers as values
‘high’ with range end numbers as keys and range start numbers as values

For example, for a range [x..y] the tables will hold low[x] = y and high[y] = x. The algorithm looks the following:

Scan original array and for each element:
- If it already belongs to any range skip it
- Otherwise create unit size range [i..i]
- If there is a range next to the right [i+1.. y] merge with it to produce [i..y] range
- If there is a range next to the left [x..i-1] merge with it as well (either [i..i] or merged [i..y] will be merged with [x..i-1])
Scan through created ranges to find out the longest

Word in a Maze

2011-03-14T09:02:00.001-07:00

Q: Given a puzzle of letters/ characters e.g.

a e r o p s
b h a r l s
w r i s l o
a s n k t q

Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the third column and slow in the third row wrapped around.

Algorithm:

Idea is for each element in matrix find if it matches the first character, if it matches then we have to look in 4 directions. If there is match in that direction proceed till we are end of the string. If match return true if not return false. We have to look in all the directions because the string can be in any of 4 directions. Also Math.abs takes care of wrap around (this was my big bug)

Working Java Code:

 public class StringFinder {
      enum Direction {   
        up, down, left, right    
    };
      public static void main(String args[]) {   
        char[][] ar = new char[][] { { 'a', 'e', 'r', 'o','p','s' },    
                                     { 'b', 'h', 'a', 'r','l','s' },     
                                     { 'w', 'r', 'i', 's','l','o' },    
                                     { 'a', 's', 'n', 'k','t','q' },     
                                     { 'a', 'e', 'r', 'o','p','s' },    
                                     { 'b', 'h', 'a', 'r','l','s' },};    
        String str = "rain";    
        StringFinder sf = new StringFinder();    
        System.out.print(sf.stringFinder(ar, str));    
    }
      private boolean stringFinder(char[][] ar, String str) {   
        int size = ar.length;    
        if (str.length() > size + 1)    
            return false;    
        int k = 0;    
        char[] charArray = str.toCharArray();    
        for (int i = 0; i < size; i++)    
            for (int j = 0; j < size; j++)    
                if (ar[i][j] == charArray[k])    
                    return isMatch(ar, charArray, i, Math.abs((j + 1) % size),    
                            k + 1, Direction.right)    
                            || isMatch(ar, charArray, Math.abs((i + 1) % size),    
                                    j, k + 1, Direction.down)    
                            || isMatch(ar, charArray, Math.abs((i - 1) % size),    
                                    j, k + 1, Direction.up)    
                            || isMatch(ar, charArray, i,    
                                    Math.abs((j - 1) % size), k + 1,    
                                    Direction.left);    
        return false;    
    }
      private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k,   
            Direction dir) {    
        int size = ar.length;    
        if (k == charArray.length - 1) {    
            if (ar[i][j] == charArray[k])    
                return true;    
            else    
                return false;    
        }    
        if (ar[i][j] == charArray[k]) {    
            if (dir == Direction.down)    
                i = Math.abs((i + 1) % size);    
            else if (dir == Direction.right)    
                j = Math.abs((j + 1) % size);    
            else if (dir == Direction.left)    
                j = Math.abs((j - 1) % size);    
            else    
                // dir==Direction.up    
                i = Math.abs((i - 1) % size);
              return isMatch(ar, charArray, i, j, k + 1, dir);   
        }
          return false;   
    }
  }

Finding max and min

2011-03-14T08:45:00.001-07:00

Q: Given an array of n elements, find the min and max in 3n/2 comparisons even in worst case.

We usually think of the following approach as soon as we see the question

One scan through the array with two extra variables to store current min and max.
In this approach the worst case number of comparisons = 2n

Can we change the approach slightly to make sure that even the worst case number of comparisons is 3*n/2

Following is the approach..

1) take 2 number at a time ....

2) compare these 2 numbers .... (1st comparison)

3) compare the minimum of these two with current minimum (2nd comparison)

4) compare the max of these two with current max (3rd comparison)

as there are (n/2) pairs ... and 3 comparisons per a pair .... total comparisons are 3n/2 ....

No of occurrences of a number

2011-03-14T08:37:00.001-07:00

Q: Given a sorted array find number of occurrences of a given number

If the interviewer has mentioned that the given array is in sorted array then he is expecting the solution to be in log( n ) time.

We can solve this using binary search. To find the no of occurrences of the given number we can find the first occurrence of the number and the last occurrence of the number and return the difference between them.

To find the first occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data)

To find the last occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data)

Working Java Code:

 public class NoOfOccurences {
      public static int findFirstOccurence(int A[],int low,int high,int data)   
    {    
        int mid;    
        
        while(low <= high)    
        {    
            mid = low + (high-low)/2;    
            if(( mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data))    
            {    
                return mid;    
            }else if(A[mid] >= data)    
            {    
                high = mid-1;    
            }else    
            {    
                low = mid+1;    
            }    
        }    
        
        return -1;    
        
    }    
    
    public static int findLastOccurence(int A[],int low,int high,int data)    
    {    
        int mid;    
        
        while(low <= high)    
        {    
            mid = low + (high-low)/2;    
            if(( mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data))    
            {    
                return mid;    
            }else if(A[mid] <= data)    
            {    
                low = mid+1;    
            }else    
            {    
                high = mid-1;    
            }    
        }    
        
        return -1;    
    }    
     
     
    public static void main(String[] args) {    
        int a[] = {1,2,3,3,3,3,4,5,6};    
        int firstCount = NoOfOccurences.findFirstOccurence(a,0,8,3);    
        int lastCount = NoOfOccurences.findLastOccurence(a,0,8,3);    
        
        int noOfOccur = (lastCount - firstCount) +1;    
        System.out.print("No of occurences"+noOfOccur);
      }
  }

SubArray With sum zero.

2011-03-10T09:17:00.001-08:00

Q: An array contain positive and negative elements, find maximum subarray whose sum is equal to zero.

Algorithm:

Lets take input array as a[]={-3,2,4,-6,-8,10,11}

Make an array b [] such that b[i]=b[i-1]+a[i]; means b[i] = sum(a[0],..., a[i]);

So b[]={-3,-1,3,-3,-11,-1,10}

Now all those pairs at indexes (i,j)in array b[] having equal numbers are the indexes of subarrays from (i+1,j) having sum as zero.

we have to find some (i, j) so: a[i] + a[i+1] + ... + a[j] = 0. But a[i] + a[i+1] + ... + a[j] = b[j] - b[i-1].
when creating the map using b values, the key in map is the value from b and the value in map is the index of from b. if a new key exists, this means we found a solution.

Finding all pairs in O(n) can be done by using map.

Working JAVA Code --------------------------- import java.util.Comparator; public class Index implements Comparable{ Integer start; Integer end; public Integer getStart() { return start; } public void setStart(Integer start) { this.start = start; } public Integer getEnd() { return end; } public void setEnd(Integer end) { this.end = end; } public int compareTo(Object index1) { index1 = (Index) index1; Index index2 = (Index) this; Integer index1Distance = ((Index) index1).getEnd().intValue() - ((Index) index1).getStart().intValue(); Integer index2Distance = ((Index) index2).getEnd().intValue() - ((Index) index2).getStart().intValue(); if (index1Distance > index2Distance) return 1; else if (index1Distance == index2Distance) return 0; else return -1; } }

  import java.util.HashMap;   
import java.util.Map;    
public class SubarraywithSumZero {    
    public Index findLongestSubArraywithSumZero(long[] inputArray) {    
        // 1. Generate a cummulative array    
        for (int i=1; i < inputArray.length; i++) {    
            inputArray[i] += inputArray[ (i-1)];    
        }    
        //2. Read the array, store it in map    
        // For a subraary with 0 there should + and - numbers    
        // we need to figure the longest distance indexes which have same numbers    
        // since our array is cummulative postives and negatives which sum to 0 will bring the    
        // intermittent array back to same number where it started    
        // eg intermittent array = -6, -8, -10, -6, -4, 1, 2, 3, 4, 1    
        // now from -6 we again reach -6    
        // and later from 1 back to 1 which implies these two arrays are summing to 0    
        // we just need the longest one    
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();    
        Index maxIndex = null;    
        for (int i=0; i < inputArray.length; i++) {    
            Integer index = new Integer(i);    
            Integer val = new Integer((int) inputArray[i]);    
            if (indexMap.get(val) == null) {    
                indexMap.put(val, index);    
            }    
            else {    
                if (maxIndex == null) {    
                    maxIndex = new Index();    
                    //collosion found the subarray    
                    maxIndex.setStart(indexMap.get(val));    
                    maxIndex.setEnd(new Integer(i));    
                }    
                else  {    
                    Index index1 = new Index();    
                    index1.setStart(indexMap.get(val));    
                    index1.setEnd(new Integer(i));    
                    if (maxIndex.compareTo(index1) <= 0) {    
                        maxIndex = index1;    
                    }    
                }    
            }    
        }    
            return maxIndex;        
    }    
    public static void main(String[] args) {    
        long inputArray[] = {3,2,4,-6,-8,10,11};    
        SubarraywithSumZero subarraywithSumZero = new SubarraywithSumZero();    
        Index maxIndex = subarraywithSumZero.findLongestSubArraywithSumZero(inputArray);    
        System.out.println("Longgest Subarray with sum starts at [" + maxIndex.getStart() + " ] and ends at [" + maxIndex.getEnd() + "]");    
    }    
}

Finding duplicates in an unsorted array

2011-03-10T09:05:00.001-08:00

Q: You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Algorithm:

1. Read input from startPos
2. If input is within the maxRange or it's not in correct place then it's a candidate to be replaced else incrementStartPos
3. finalPosition for input is input[i]
4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange
5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance
6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array
7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element

Eg: if an array had
(2, 3, 4, 3, 2}
1. n=5 after step1 we'll get
{3, 7, 4, 3, 2}
2. now a[0] = 3 so again in loop we'll get
{4, 7, 8, 3, 2}
3. now a[0] = 4 so again in loop we'll get
{3, 7, 8, 9, 2}
4. a[0] = 3 so again in loop we'll get { , 7, 13, 9, 2}
5. since a[0] is empty move to a[1] and in loop we find it's at the right place so move to next, 8, 9 are also in place so we move to last element and have the final array as
{ , 12, 13, 9, }

Now to find how many are duplicates divide every element by 5 and take the mod => m = (a[i] mod n) -1 this gives you how many times an element is repeated.

 public static void main(String[] args) {        
          int[] inputArr1 = {0, 2, 3, 4, 3, 2};   
        findDuplicates(inputArr1, 5);    
        printDuplicatesAndMissingElements(inputArr1);    
    }
      private static void findDuplicates(int[] inputArr, int maxRange) {   
        // for simplicity reasons we will assume nothing is there in 0 index of array     
        // and start from 1    
        int i = 1;    
        int maxArrLength = inputArr.length;    
        
        while(true) {    
            if ( i > maxArrLength - 1)     
                break;    
            
            int finalPos = inputArr[i];    
            System.out.println(" Read :: " + inputArr[i]);    
            
            if (finalPos > maxRange) {    
                //this element is already in final position skip and move further looking for elements within maxRange    
                i++;    
                continue;    
            }    
            int finalPosElement = inputArr[inputArr[i]];    
            int startPos = i;    
            int startPosElement = inputArr[i];    
            
            // if startPos element isn't in place and it's within the maxRange..    
            // then candidate for swap or reaching final pos...    
            if (inputArr[startPos] != i ||     
                    inputArr[startPos] <= maxRange) {
                  if (finalPosElement > maxRange) {   
                    // if finalposElement > maxRange then no swapping required    
                    // just add maxRange to denote multiple entry    
                    inputArr[finalPos] += maxRange;    
                    //make startPosElement as 0    
                    inputArr[startPos] = 0;    
                    System.out.println("No swapping required incemented " + inputArr[finalPos] );    
                }    
                else {    
                    //swap    
                    int temp = startPosElement;    
                    inputArr[startPos] = finalPosElement;    
                    inputArr[finalPos] = temp + maxRange;    
                    System.out.println("Swapped : " + startPosElement + " with " +finalPosElement);    
                }    
            }    
            printArray(inputArr);    
            // if the element in current evaluated position isn't still correct repeat the above again    
            if (inputArr[startPos] == i ||    
                     
                    inputArr[startPos] > maxRange) {    
                System.out.println(" Read :: "+ inputArr[startPos] + " it's already in place");    
                inputArr[startPos] += maxRange;    
                i++;    
            }    
            else if (inputArr[startPos] == 0){    
                i++;    
                continue;    
            }    
            else {    
                continue;    
            }    
                
        }    
        
    }    
    
    private static void printArray(int[] inputArr) {    
        for (int i=1; i < inputArr.length; i++) {    
            System.out.print(inputArr[i] +",");    
        }    
        System.out.println("");    
    }    
    private static void printDuplicatesAndMissingElements(int[] inputArr) {    
        int maxRange = inputArr.length;    
        for (int i=1; i < inputArr.length; i++) {    
            if (inputArr[i] == 0) {    
                System.out.println(" Element [" + i + "] is missing");    
            }    
            int input = inputArr[i];    
            int mod = input / maxRange;    
            if ( mod > 1) {    
                System.out.println (" Element [" + i + "] is repeated + [" + mod + "] times");    
                
            }    
        }    
    }
  }

Ternary Search Tree implementation

2011-02-07T09:59:00.001-08:00

The ternary search tree contains three types of links. First, there are pointers that correspond to links in the corresponding trie, shown as dashed down-arrows. Traversing a down-link corresponds to “matching” the character from which the arrow starts. The left- and right- links are traversed when the current character does not match the desired character at the current position. We take the left-link if the character we are looking for is alphabetically before the character in the current node, and the right-link in the opposite case.

Ternary tree data structure solves the memory problem of tries which we discussed in the earlier post in a more clever way. To avoid the memory occupied by unnecessary pointers, each trie node is represented as a tree-within-a-tree rather than as an array. Each non-null pointer in the trie node gets its own node in a ternary search tree.

Each node in a Ternary search tree could be implemented like this in java:

class TNode
{
    char m_char;
    TNode left, center, right;
    boolean wordEnd;

    public TNode(char ch, boolean wordEnd)
    {
        m_char = ch;
        wordEnd = wordEnd;
    }
}

Here is a Ternary search tree that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Here is a simple Ternary search tree implementation in java:

    
public class TernarySearchTree {
      TNode root = null;   
    
    public TernarySearchTree()    
    {    
        this.root = null;    
    }
      private void insert(String key, int pos, TNode node)   
    {    
        char s[] = key.toCharArray();    
        if (node == null) { node = new TNode(s[pos], false); }
          if (s[pos] < node.m_char) {    
            insert(key, pos, node.left);     
            }    
        else if (s[pos] > node.m_char) {     
            insert(key, pos, node.right);     
            }    
        else    
        {    
            if (pos + 1 == key.length()) { node.wordEnd = true; }    
            else { insert(key, pos + 1, node.center); }    
        }    
    }
      public void insert(String s)   
    {    
        if (s == null || s == "") throw new IllegalArgumentException();
          insert(s, 0, this.root);   
    }
      public boolean containsKey(String key)   
    {    
        if (key == null || key == "") throw new IllegalArgumentException();
          int pos = 0;   
        TNode node = this.root;    
        char s[] = key.toCharArray();    
        while (node != null)    
        {
              if (s[pos] < node.m_char) { node = node.left; }   
            else if (s[pos] > node.m_char) { node = node.right; }    
            else    
            {    
                if (++pos == key.length()) return node.wordEnd;    
                node = node.center;    
            }    
        }
          return false;   
    }    
    
    public static void main(String[] args)    
    {    
        TernarySearchTree tree = new TernarySearchTree();    
        tree.insert("AB");    
        tree.insert("ABBA");    
        tree.insert("ABCD");    
        tree.insert("BCD");    
        
        boolean found = tree.containsKey("AB");    
        
        if(found)    
            System.out.println("AB is found in the tree");    
        else    
            System.out.println("AB is not found");    
        
        found = tree.containsKey("ABCD");    
        
        if(found)    
            System.out.println("ABCD is found in the tree");    
        else    
            System.out.println("ABCD is not found");
      }   
}
  class TNode   
{    
    char m_char;    
    TNode left, center, right;    
    boolean wordEnd;
      public TNode(char ch, boolean wordEnd)   
    {    
        m_char = ch;    
        wordEnd = wordEnd;    
    }    
}

Trie implementation

2011-02-07T09:00:00.000-08:00

A trie is a tree-like data structure in which each node contains an array of pointers, one pointer for each character in the alphabet. Starting at the root node, we can trace a word by following pointers corresponding to the letters in the target word.

Some of the uses of this Trie data structure is

1) Auto completion of the words or sentences like in Google Suggest.

2) Dictionary etc..

Each node in a trie could be implemented like this in java:

  class Node {   
    Node[] children;    
    boolean isKey;
      public Node() {   
        isKey = false;    
        children = new Node[26];    
    }
      public Node(boolean key) {   
        isKey = key;    
        children = new Node[26];    
    }
  }

Here is a trie that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Here is a simple Trie search tree implementation in java:

  public class Trie {
      Node root;
      public Trie() {   
        this.root = new Node();    
    }
      /**   
     * Method to insert a string to Node and its children    
     *     
     * @param key    
     *            the string to insert (the string is assumed to be uppercase)    
     * @return true if the node or one of its children is changed, false    
     *         otherwise    
     */    
    public boolean insert(String key) {    
        return root.insert(key.toUpperCase());    
    }
      /**   
     * Returns whether key is a valid prefix for certain key in this trie. For    
     * example: if key "hello" is in this trie, tests with all prefixes "hel",    
     * "hell", "hello" return true    
     *     
     * @param prefix    
     *            the prefix to check    
     * @return true if the prefix is valid, false otherwise    
     */    
    public boolean containPrefix(String prefix) {    
        return root.containPrefix(prefix.toUpperCase());    
    }
      /**   
     * Returns whether key is a valid key in this trie. For example: if key    
     * "hello" is in this trie, tests with all prefixes "hel", "hell" return    
     * false    
     *     
     * @param key    
     *            the key to check    
     * @return true if the key is valid, false otherwise    
     */    
    public boolean containKey(String key) {    
        return root.containKey(key.toUpperCase());    
    }    
    
    public static void main(String[] args)    
    {    
        
        Trie trie = new Trie();    
        trie.insert("AB");    
        trie.insert("ABBA");    
        trie.insert("ABCD");    
        trie.insert("BCD");    
        
        boolean found = trie.containKey("AB");    
        
        if(found)    
            System.out.println("AB is found in the trie");    
        else    
            System.out.println("AB is not found");    
        
        found = trie.containPrefix("ABC");    
        
        if(found)    
            System.out.println("ABC prefix is found in the trie");    
        else    
            System.out.println("ABC prefix is not found");
      }   
}
  class Node {   
    Node[] children;    
    boolean isKey;
      public Node() {   
        isKey = false;    
        children = new Node[26];    
    }
      public Node(boolean key) {   
        isKey = key;    
        children = new Node[26];    
    }
      /**   
     * Method to insert a string to Node and its children    
     *     
     * @param key    
     *            the string to insert (the string is assumed to be uppercase)    
     * @return true if the node or one of its children is changed, false    
     *         otherwise    
     */    
    public boolean insert(String key) {    
        // If the key is empty, this node is a key    
        if (key.length() == 0) {    
            if (isKey)    
                return false;    
            else {    
                isKey = true;    
                return true;    
            }    
        } else {// otherwise, insert in one of its child
              int childNodePosition = key.charAt(0) - 'A';   
            if (children[childNodePosition] == null) {    
                children[childNodePosition] = new Node();    
                children[childNodePosition].insert(key.substring(1));    
                return true;    
            } else {    
                return children[childNodePosition].insert(key.substring(1));    
            }    
        }    
    }
      /**   
     * Returns whether key is a valid prefix for certain key in this trie. For    
     * example: if key "hello" is in this trie, tests with all prefixes "hel",    
     * "hell", "hello" return true    
     *     
     * @param prefix    
     *            the prefix to check    
     * @return true if the prefix is valid, false otherwise    
     */    
    public boolean containPrefix(String prefix) {    
        // If the prefix is empty, return true    
        if (prefix.length() == 0) {    
            return true;    
        } else {// otherwise, check in one of its child    
            int childNodePosition = prefix.charAt(0) - 'A';    
            return children[childNodePosition] != null    
                    && children[childNodePosition].containPrefix(prefix    
                            .substring(1));    
        }    
    }
      /**   
     * Returns whether key is a valid key in this trie. For example: if key    
     * "hello" is in this trie, tests with all prefixes "hel", "hell" return    
     * false    
     *     
     * @param key    
     *            the key to check    
     * @return true if the key is valid, false otherwise    
     */    
    public boolean containKey(String key) {    
        // If the prefix is empty, return true    
        if (key.length() == 0) {    
            return isKey;    
        } else {// otherwise, check in one of its child    
            int childNodePosition = key.charAt(0) - 'A';    
            return children[childNodePosition] != null    
                    && children[childNodePosition].containKey(key.substring(1));    
        }    
    }
      public boolean isKey() {   
        return isKey;    
    }
      public void setKey(boolean key) {   
        isKey = key;    
    }    
}

360 degree Viewer

2010-02-17T10:56:00.001-08:00

Sample Application showing the 360 degree view of an image using paper vision 3d.

Demo here

Source code

 <?xml version="1.0" encoding="utf-8"?>   
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute"     
                xmlns:view="org.papervision3d.view.*" creationComplete="init();"     
                width="622" height="504"     
                backgroundGradientAlphas="[1.0, 1.0]" backgroundGradientColors="[#FFFFFF, #DEDEDE]">    
    <mx:Script>    
        <![CDATA[    
            import mx.events.ItemClickEvent;    
            import org.papervision3d.objects.primitives.Cylinder;    
            import org.papervision3d.materials.BitmapFileMaterial;    
            private var cylinder:Cylinder;    
            //Initialization function    
            private function init():void{    
                // BasicView added to the Stage    
                myUI.addChild( bv );    
                bv.cameraAsCamera3D.x = 0;    
                bv.cameraAsCamera3D.z = 0;    
                bv.cameraAsCamera3D.y = 0;    
                //Create object    
                var mat:BitmapFileMaterial = new BitmapFileMaterial("DSC00020.jpg",true);    
                mat.doubleSided = true;    
                mat.precise = true;    
                mat.smooth = true;    
                cylinder = new Cylinder( mat , 80 , 100 , 100 , 100 , 80 , false , false );    
                bv.scene.addChild( cylinder );    
                //Rendering bv.startRendering();    
                this.addEventListener(Event.ENTER_FRAME , onTimer );    
            }    
            //Rendering    
            private function onTimer( e:Event ):void{    
                bv.renderer.renderScene( bv.scene , bv.camera , bv.viewport );    
                cylinder.rotationY += (myUI.width - myUI.mouseX )/ 100;    
            }    
            private function onClick(e:ItemClickEvent):void{    
                cylinder.rotationY = e.item.angle;    
            }    
        ]]>    
    </mx:Script>    
    <view:BasicView id="bv"/>    
    <mx:UIComponent id="myUI" width="300" height="300"/>    
    <mx:LinkBar id="link" x="263.5" y="6" labelField="label" itemClick="onClick(event)">    
        <mx:Object label="a" angle="0"/>    
        <mx:Object label="b" angle="90"/>    
        <mx:Object label="c" angle="180"/>    
        <mx:Object label="d" angle="270"/>    
    </mx:LinkBar>    
    <mx:Label x="280.5" y="476" text="360 Video"/>    
</mx:Application>