CareerCup

Give me real time application of BST.....

Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.

Examples:
abc -> ac
ac->''
react->rt

Two numbers are represented as linked lists. Both lists are of same length. Add them without manipulating the lists and without a second traversal.

Add a number to array and if there is carry increase array size.
----------------------------------------------------------------------
For example input = {7,3,5,3,9} convert this to number 73539, add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form of in-built number format. So you have to do this summation in-place. Also, how would you increase array size in-case input = {9,9,9} so output = (1,0,0,0}

Assume, all elements of arrays are between 0 and 9.

Data-structure and algorithm used in Load Balancer??

Explaining algorithm write code for it

Consider a city with 50 locations each numbered from 0 to 49. Mr. XYZ runs a taxi service in a city. He has 25 Taxi’s to service the passengers. When passenger needs a taxi he makes a call to Mr. XYZ and give details like his current location as a source, and where he is willing to travel as a destination. He also tells max time he can wait for a taxi. In return Mr. XYZ either allocate a taxi to the passenger or tell him request can’t be satisfied within the given max_waiting time. Allocated taxi travels from its current location to the passengers pick-up point i.e. the source. This travel is termed as non revenue travel. Mr. XYZ charge passenger only for the distance from source to the destination. After dropping passenger to the destination taxi waits for call from Mr. XYZ to serve next passenger.
Let’s assume we know all TaxiHireRequests in advance. We also know the distance and time to travel between any two locations in the city.


Write a program which will choose the taxi’s such that sum of non_revenue distance travelled by all the Taxi’s is minimum and the number of unsatisfied requests are minimized. Also print the total non_revenew distance and number of unsatisfied requests.


pseudo helper structures.
struct TaxiHireRequest{
int Time Of Request;//Number of seconds from 12AM
int Source; // an int from 0 to 49
int Destination;// an int from 0 to 49
int Maximum waiting time // in seconds;
}[200]


struct Taxi{
int location;//an int from 0 to 49
bool isHired//true or false
}[25]


int Distance[50][50];
int Time[50][50];
// Extend the structure whenever required.

Given N dices.Each dice has A faces.That means each dice has numbers from 1 to A.Given Sum S,Find the number of ways to make the sum S if dices are rolled together.

How do you find the greatest 1000 elements in a list of a million elements? No other information given. What would be the runtime? Hint: You can do better than O(n log n). I didn't realize but it could be possible with Tree or Heaps.

Flatten a List<List<Integer>> in Java and implement the hasNext() and next() methods.
e.g. [[6,8],4] should return true when at 6, 8 and false at 4.

Implementation of Advanced set which have the functionality as "Set" in c++ along with extra functionality-Random number generator.Returns the random number from the set.

Given a directed acyclic graph.How to represent it in the relational database for efficient retrieval of all the children nodes and all the parents of any node.(ex a->b here b is child of a and a is parent of b)

Given a string.Find the longest substring in it such that the substring contains only 2 unique characters.Ex- aabbcbbbadef Ans-bbcbbb

In a party there are n different-flavored cakes of volume V1, V2, V3 ... Vn each. Need to divide them into K people present in the party such that
- Each member of party gets equal volume of cake (say V, which is the solution we are looking for)
- A given member should get a cake of single flavour only i.e. You cannot distribute parts of different flavored cakes to same member.
- Minimum volume of cake gets wasted after distribution so that means a maximum distribution policy

Write a C program to search for a given pattern from various files in a directory without using grep or any other inbuilt command

I Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:

Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.

Example distribution:
w = 1, 2, 3, 2, 1

Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9

Example results:
n = 0, 1, 2, 3, 4

Documentation:

Class java.util.Random

public int nextInt(int n)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive

Find the most frequently occurring element in a BST. In this BST we can have leftnode<=rootnode<=rightnode.

Write a function which returns kth element from the tail in a linked list.

Implement Iterator class with peek() functionality in Java.

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

What is the difference between a computers heap and it's stack?

Blacklist all the nodes in a B-tree, when viewed from all 4 directions.

Sort a singly-linked list of unknown size using constant space.

You are trying to to daemonize an unknown, black-box binary executable. The binary executable returns no output to STDOUT or STDERR. Assume that the mystery binary return code is non-zero. What troubleshooting steps might you take to learn more about what the binary is supposed to do, and why it is failing?

During boot, after the BIOS performs a successful power-on-self-test, describe everything that occurs until the console is presented to the user.

How do you make sure an API does not leak memory?

You are given a dictionary, in the form of a file that contains one word per line. E.g.,
abacus
deltoid
gaff
giraffe
microphone
reef
qar
You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}.
The task is to find the longest word in the dictionary that can be spelled with the collection of
letters. For example, the correct answer for the example values above is “giraffe”. (Note that
“reef” is not a possible answer, because the set of letters contains only one “e”.)

Input is a number of words. Construct a listing of valid 6-letter words. You have access to bool IsValid(const string& word); Implement Insert() and Get() for this listing.

Escape strings. Convert special ASCII characters to form of ‘\ooo’, where ‘ooo’ is oct digit of the corresponding special character.
The ascii characters that smaller than space are regarded as special characters.

Return a shortest prefix of <code>word</code> that is <em>not</em> a prefix of any word in the <code>list</code>

e.g.
word: cat, it has 4 prefixes: “”, “c”, “ca”, “cat”
list: alpha, beta, cotton, delta, camera
Result is “cat”

Suppose we use binary search tree to implement set, design an algorithm that we can get an random element from the set, while maintain all the other set operations have same complexities.