CareerCup

Design Bing search.

How Solr/Lucene or Elasticsearch work? For what purpose are they used?

What's Hbase, Pig, used for? Why do we need Hbase if we can use Hive to query Hadoop?

What are different phases of Map reduce operation - I think they were looking for split, combiners, partitioners, sorting phases of whole map reduce stage.

My interview was for big data position for their Search team. They were looking for person with good Hadoop skill set :-

1. Can you describe Hadoop Architecture? What are various components of it (Primary/Secondary namednodes, data node etc)? Explain working of each.

Is there a difference between the terms "sibling" and "cousin" of a specified node in a Binary Tree/ Binary Search Tree? If yes, then what?

Implement Priority Queue

Implement Least Recently Used Cache for IPAddress lookup. Assume max cache size is 1000 but it should scale well with larger number
Key of the cache is server name and value is IPAddress.

Given a string left rotate it by given number of times with O(n) solution

Given a array where each element is maximum +-k index away from it's sorted position, find an algorithm to sort such array.

In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players trn.

In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. In the question here, we are concerned with the following, related problem: First n straws are dumped on the table. Next, for every pair of straws, we want to determine if the straws are connected by a path of touching straws. In other words, given a list of the endpoints for n > 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws. Give an algorithm to compute all the pairs of straws that are connected.
Here is some additional information that you can use:

As a basic step you need to determine whether two straws directly touch (intersect), i.e., whether straw ab with end points a and b intersects with straw cd (with end points c and d).
To get full credit also explain how the elementary step i) can be done. If you cannot find an algorithm for this step, assume an O(n 2 ) algorithm and explain how to find all pairs of straws that are connected.
Analyse and explain the worst-case computational complexity of your algorithm in terms of n.

Your job is to build a data structure to maintain a set of photographs. Your photograph database should allow you to insert and search for photographs, as well as to designate some of the photographs as favourites by marking them. In more detail, your data structure should support the following operations:

Insert(x, t, m): inserts photograph x that was taken at time t. If m = 1, then the photograph is marked as a favourite; if m = 0, then it is not a favourite.

Search(t): find the next photograph taken after time t.

NextFavorite(t): find the next photograph taken after time t that is a favourite.

Give a data structure for solving this problem, and explain how it works. For more efficiency, your data structure should be both time and space efficient: more points will be given for more efficient solutions. (Remember that the photographs themselves may be quite large.) Give the performance (i.e., running time) of each operation and the space usage of the data structure. You may assume that at any given time t, your camera has taken at most one photograph x. Describe your solution in words, or very high-level pseudocode. You do not need to provide complete details. You must provide enough detail, however, that your solution is clear.

Given an array of integer nos. All numbers are distinct.
WAP to find the two longest non-intersecting continuous subarrays
of equal size s.t. *all* elements of one of them are smaller than that of the other subarray:

a[i..i + k - 1] and a[j..j+k-1] where i + k <= j
s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1]
and k is maximal

Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8}
a = {6, 5, 4, 1, 3, 7} then we have:
{6, 5} and {4, 1} or
{6, 5} and {1, 3} or
{5, 4} and {1, 3} ...

You are given a bag with N balls (where the value of N is unknown). Each ball in the bag is uniquely numbered with a value between 1 to N (inclusive) i.e. for each number between 1 and N, there is only one ball with that number. Now you pick a ball from the bag and see its number. You repeat this experiment K times. What is the best possible estimate of the value of N (the number of balls in the bag) you can make from the above experiment (of taking out a ball from the bag K times) in the following cases
a) With replacement
b) Without replacement.

Given a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot

Find the number of bits set in a given character array.

After giving him a bit wise operation that was O(n) where n is the number of bits set, he wanted a more optimum solution

Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.
2.) Length of array should not be 0.
3.) Array itself should not be null.
4.) Given number, arrayLength can be represented by 32bits or 64 bits.
5.) number should not be negative.
6.) Input does not has pair, It should return false
7.) Input has pair, It should return true
8.) Input has all negative values and pair exists, then function should return true
9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

How do you traverse a binary tree and output the nodes in-order? Do it in O(1) space.

Hint: You can modify the tree.

Insert a value into a sorted linked list.

Using C/C++ write a small function (around 5 lines in the body) to insert a value in a sorted linked list. Take into consideration that the list might be empty at first, and the function should cover the cases of insertion at the head and tail...

PS what the interviewer is looking for is the ability to write a small C/C++ code that solves the question and not the algorithm per se which is trivial

Given array of marks and array of time taken to finish the question, and a passing mark P maximize on marks which will get you P but minimizing the time t.

I tried to solve this by dividing the marks by time which will give factor of utilization of a particular question, and then partition the marks on P, and choose only marks less than P, try to sort the selected marks, time pair in small subset, and minimize on t. Is this a right approach.

You are writing a simulation for a print server. This print server can accept jobs from 3 places - network, USB, or operator. It can dispatch only one job at a time. Each input job should contain an integer t which is the time in seconds it will take to process the job. Write a multi-threaded program to simulate the server and provide some simulated load with jobs. Think, of some interesting statistics your program should emit and code them in.

Find and fix the bugs in the following function that is supposed to remove the head element from a singly linked list.


void RemoveHead (node * head)
{
free(head);
head = head - > next;
}

Write a function that takes a string as an input and outputs an integer, e.g. turning "1234" into 1234.

Find whether a number (which is less than 10000) is a perfect square or not. If it is perfect square, calculate square root in O(1) without using sqrt function.
Example : 1024 => 32
1025=> not perfect square.

Given a dictionary that contains mapping of employee and his/her manager like this

Dictionary<string, string> employees = new Dictionary<string, string>()
{
{ "A","C" },
{ "B","C" },
{ "C","F" },
{ "D","E" },
{ "E","F" },
{ "F","F" }
};

Write a function to get no of employees under each manager in the hierarchy not just their direct reports.
In the above dictionary the root node/ceo is listed as reporting to himself.

Output should be a Dictionary<string,int> that contains this

A - 0
B - 0
C - 2
D - 0
E - 1
F - 5

Point errors (if any) in the following pointer code and explain what it does...

char* cp(char *a)
{
char *f;
f=(char*)malloc(strlen(a)*sizeof(char));
while(*a != 0)
{
*f=*a;
f++;
a++;
}
cout<< f;
return f;

}

You are tasked with implementing a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. The method signature should look like:

public static string GenerateLowestNumber(string number, int n)

Where the number parameter is a string that contains a number (e.g. “4205123”), and the n parameter represents the number of characters to remove from the string. The goal of this method is to return the lowest number that can be generated by removing n characters from the number provided while keeping the positions of the remaining characters relative to each other the same (i.e. the method should remove n characters from the string, but it cannot re-order the characters).
For example, if number is “4205123” and n is 4, the lowest possible number that can be generated after removing any 4 characters is “012”. If number is “216504” and n is 3, the lowest possible number that can be generated after removing 3 characters is “104”.

Identify the flaws / limitations in the following ConvertToNumber method:

public static bool ConvertToNumber(string str)
        {
            bool canConvert = false;
            try
            {
                int n = Int16.Parse(str);
 
                if (n != 0)
                {
                    canConvert = true;
                }
            }
            catch (Exception ex)
            {
                
            }
            bool retval = false;
            if (canConvert == true)
            {
                retval = true;
            }
            return retval;
        }

You are tasked with migrating data between two systems that store movie metadata. The first system, which you are to use as input, keeps their movie metadata in the following structure:
MovieName ContributorType ContributorName
Pulp Fiction Director Quentin Tarantino
Pulp Fiction Actor John Travolta
Pulp Fiction Actor Samuel L. Jackson
Titanic Director James Cameron

The second system, which you are to output to, uses the following object for movie information:

class MovieInformation
        {
            public string Name { get; set; }
            public string Director { get; set; }
            public List<string> Actors { get; set; }
        }

The first system provides an IDataReader that lets you access their data. Their data is always sorted on MovieName. You can call Read on the IDataReader to move the cursor to the next entry, and you can call GetString on the IDataReader to get the movie name, contributor type, and contributor name. For example, with the above data, if you were to call:

MovieDataReader dataReader = new MovieDataReader();
            int movieNameOrdinal = dataReader.GetOrdinal( "MovieName" );
            int contributorTypeOrdinal = dataReader.GetOrdinal( "ContributorType" );
            int contributorNameOrdinal = dataReader.GetOrdinal( "ContributorName" );
 
            while ( dataReader.Read() )
            {
                string movieName = dataReader.GetString( movieNameOrdinal );
                string contributorType = dataReader.GetString( contributorTypeOrdinal );
                string contributorName = dataReader.GetString( contributorNameOrdinal );
            }

Then at the end of the first iteration of this while loop, movieName would be “Pulp Fiction”, contributorType would be “Director” and contributorName would be “Quentin Tarantino”.
The second system provides a single method for posting movie information to their DB. This method should only ever be called once per movie:

class MovieInformationDatabase
        {
            public void SaveMovieInformation( MovieInformation information )
            {
            }
        }

Implement a method that migrates all of the data from the first system to the second system