Create methods for Set implementation. (Getting unique values from user to create a Set, and methods to implement Intersection, Union... of 2 sets

You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say "foo" , output all the products which have names having 50% or more similarity with the given keyword ie "foo"

Write the most efficient algorithm for the same.

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

(I traversed the tree twice, but interviewer said there is a recursive way to solve this)

An array is given where each rows are sorted in ascending order and each columns are sorted in ascending order. Like {{1,2,4,6}, {3,5,7,8}}. Now one number "k" is given which can be inside the matrix. Or may not be too.
Need to find out what is the position (i,j) for k, if this is inside the matrix.

Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square

Implement a function
public long[] GetMultiples(int num)
eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn't contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}

How do you output the nodes from a binary search tree given a range

Phone screen: Asked a few Windows platform questions like how to create and manage a thread.

Given a char array with words in it, find all 'a' characters and replace with xyz. Modify the input array, do not create a copy of the array.

Given an array of n with each element being in the range of 1-50, print out how many time each number from 1-50 occurs.

Do in order traversal of tree.

Print a tree level by level.

Implement atoi in C.

Input Data : {[1,3],[2,4],[10,11],[4,6]}
Output: {[1,6],[10,11]}
We have to merge all the ranges that are overlapping. You can consider Input data as any Data structure.

A site wants to present lowest airfare for a return journey. Suggest the algorithm to calculate k least sum.
If i say show me 4 options then it should return 4 lowest fares. If 8 then 8 options.

Given a sorted array find two numbers whose sum is equal to the given sum.
E.g 1 2 3 4 5 Sum to find 9 then 4+5 (Just two numbers occurring first and fulfilling the criteria)

what is daemon thread in java

How do we validate that a given doc is a well formed xml? which DS and algorithm? Write the test cases as well

Given a list of strings say N, how would you write a perfect hash function and ensure 0 collissions?

Linked List with following structure..

struct node
{
    int data;
    struct node *next;
    struct node *next_larger;
}

i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5