CareerCup

There are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money).

Company strategy is that, they want at least 'K' advertisement should be there among M consecutive advertising boards. But at the same time Company want to pay minimum for its advertisement.

Now, what is the total number of ways, different ways Company can advertise meeting its minimum cost strategy.

As for Example: N= 3, M = 2, K=1 ==> there is only one way for minimum cost, ie. 0C0 , where '0' denotes No company advertisement, and 'C' denotes company advertisement board.

Similarly, for N =4, M =2, K =1 ==> there is 3 possible ways, ie. C0C0, 0C0C, 0CC0.

Problem: you are given 2 words with equal number of characters. Find an algorithm to go from first word to second word, changing one character at each step, in such a way that each intermediate word exist in a given dictionary.
Example:
Words are pit, map. A possible solution:
pit, pot, pet, met, mat, map

How would you test each of the 3 layers in a 3-tier web app?

How would you test amazon search functionality on the home page?

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

You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.

Ex: Input [1, 3, 3, 2, 1]
Output [1, 1, 2, 3, 3]

But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.

You are only permitted to swap elements.

If you are going to debug a program with about 5000 lines of codes (written in C), given that some of its features are working fine while other are not, how are you going to fix it?

Given an array with different numbers and a number of C,so how to find all the combinations which the sum is C..like..array={1,2,3,4},C=3,,return is 2,which contains two combinations{{1,2},{3}}.

You visit a website and it is slow today (it is not slow everyday). What could be the cause(s) of the slowness?

which data structure should be used to implement thread pool ? How to assign particular thread from thread pool ?

Given a list of n points in 2D space. Lets call them (X1,Y1), (X2,Y2) .... (Xn,Yn). Find the optimal way to retrieve the result of following query.

SELECT min(X) FROM (2D Points) WHERE Y between Ymin and Ymax.

Suppose there is a directory XYZ having too many files (100 to 10000). Each file contain the format like first line having company name and second line some data values. We need to read each files in directory and create the new directories at some path with company names and move that file (1.txt ) to that directory.
what should be design.
My suggestion was to Create a function ScanDir() which will read the count of files and will make loop to read the file and will create a thread for that file and move to next file and process the all files.

Two numbers are missing from the first hundred numbers. They are NOT sorted. How to find them?
You can't sort.. and can't iterate one by one.. has to be less than O(N)? Can't use stack , set or any collection interface or in fact any other data structure or array!

An array contains N numbers where N is huge. There are only k distinct numbers. Sort those k numbers.

I tld him to use a hashmap for this. He was fine with the solution. But he wanted me to optimise it for a multicore machine. I couldn't come up with an answer. :(

You are given a long list of integers, so long that you can not fit the entire list into memory, implement an algorithm to get the max 100 elements in the list.

Given these 4 commands :

INCREMENT: 
    READ V
    WRITE V + 1

ZERO
    WRITE 0


ASSIGN : =

LOOP : FOR <integer> = <start> to <finish> do
	 	...
	     END FOR

Define these 4 functions: Decrement, Divide, test If equal (pseudo code).

You have an array of binary numbers as "00001101000001010100000..."... We need to find the First occurrence of 1 in this series.. using binary search.

we need to design an algorithm of complexity less than O(n).. and we need to use binary search strictly..

Using these 3 functions:

INCREMENT:
    READ N1
    WRITE N1 + 1

MINUS:
    READ N1, N2
    WRITE N1 - N2

MULTIPLY:
    READ N1,N2
    WRITE N1*N2

Define these four functions: Greater than, Equality, Nonequality, Divide.

How can you implement multiplication operator using increment operator (No arithmetic operation is allowed)?

Write a function to evaluate a string that has only integers, and operators '+' & '*'. The evaluation should be done in a single pass. For example passing "3*2+5*6" should result in this function returning 36.

Write a function fix a loop in the linked list based on the assumption that the linked list is sorted.

How would you find if a linked list has a loop? How would you do it without using additional memory, if the linked list is sorted.

Write a function to find a key in Hash map if the value associated to that key is given as input. As a followup, swap key & value assuming that value is not equal to any of the existing keys.

Write a function to perform string replace without using any inbuilt functions.

// Given two lists of strings build a new list that has all strings that appear in both the original lists. If the same string appears more than once output it as many times as it appears in both lists
//
// Example:
// "dog", "bird", "elephant", "dog", "dog", "cat"
// "cat", "dog", "dog", "cat", "cat", "fish"
// Result (order doesn't matter)
// "dog", "dog", "cat"

//Given an array of NxN, print its diagonals from top-right to bottom-left.

//Sample Input:
// [[1, 2, 3],
// [4, 5, 6],
// [7, 8, 9]]

//Sample Output:
//1,
//2, 4,
//3, 5, 7,
//6, 8,
//9

Given an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other? k indices and within plus or minus l (value) of each other? Do all, even the latter, in O(n) running time and O(k) space.

Give three Hash tables has some values.you need compare three hash tables and store the common values in fourth hash table?

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

The bin packing problem is an example of a wide set of problems. The task is to find how many set sized bins are required to hold a number of differently sized boxes. How many bins (10 units high) are required to contain the following boxes (1,3,4 and 5 units high)?