Test your knowledge with Algorithems Data structure scenario

  1. How do you sort the following array? What is the algorithm used for this?

arr ab = {8,7,9,6,3,5,2,0,4}

  1. depth DFS vs bredth BFS
  2. central blr, north blr sales man problem
  3. 1000000 records need to process and having less memory, how do you process effectively?

5.Time efficiency of quick sort algorithms

  1. Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips.

It s a divide and conquer problem.

Take 500 of the bottles and put one drop from each of them into an empty bottle.

Taste the juice in that bottle. If it’s bitter, we know the poison is in one of them;

if not, it’s in one of the other 500.

Now, take 250 of the bottles we’ve chosen and put one drop from each into another empty bottle and taste it.

Now, you’ve narrowed it down to 250 bottles.

Repeat, and narrow it down to 125… then 63… then 32… 16…8… 4… 2… and finally 1.

And you only had to taste the juice 10 times, instead of possibly 999.

  1. Question: There are N houses in a row. Each house can be painted in either Red, Green or Blue color.

The cost of coloring each house in each of the colors is different.

Find the color of each house such that no two adjacent house have the same color and the total cost of coloring all the houses is minimum.

Its dynamic programming problem.

We have  to maintain 3 minimums

cost(i,b)=min(cost(i-1,g),cost(i-1,r))+cost of painting i as b;

cost(i,g)=min(cost(i-1,b),cost(i-1,r))+cost of painting i as g;

cost(i,r)=min(cost(i-1,g),cost(i-1,b))+cost of painting i as r;

 

finally min(cost(N,b),cost(N,g),cost(N,r)) is the ans

7.Question -write a prototype and algo for a function for deleting a node in a linked list, but with following constraints:

1) You accept pointer to the start node as first parameter and item to be deleted as second parameter. start node is not global

2) You WILL NOT be returning pointer to the start node.

3) You WILL NOT be accepting a pointer to pointer to start node.

Hint:

Considering the constraints, the restriction is – only single dimension indirection is allowed, something like

void deleteNode(Node *pStart, Node* pDelete);

The problem is, modifications to the list will not be retained as it is passed as Node *. We need pass “Node **” or return the modified list pointer (which is also not allowed).

The idea is simple, add one more level of abstraction.

typedef struct List_tag

{

Node *pHead;

Node *pEnd;

} List;

Now the delete function declaration looks like,

void deleteNode(List *pList, Node *pNode);

8.Have you used HashMap before or  What is HashMap? Why do you use it

9.Do you Know how HashMap works in Java or How does get () method of HashMap works in Java

10.What will happen if two different objects have same hashcode?

11.How will you retrieve Value object  if two Keys will have same hashcode?

12.What happens On HashMap in Java if the size of the HashMap  exceeds a given threshold defined by load factor ?

  1. Do you see any problem with resizing of HashMap in Java??
  2. Question – There are n people on a day who came to be interviewed by Joe.

Joe rates every candidate from 0 to 10. He has to output the total ratings of all the people who came in a day.But, here’s the problem: Joe gets extremely frustrated when someone ends up scoring a 0 in the interview.So in frustration he ends up removing the candidate who scored that 0, and also removes the candidate who came before him.

If there is no candidate before the one who scores a 0, he does nothing.

You’ve to find the summation of all the ratings in a day bby Joe.

Input constraints:

The first line of input will contain an integer — n. The next n lines will contain an integer, where the ith integer represents the rating of the ith person.

Output constraints:

Print the required sum.

Constraints:

1 ≤ n ≤5 * 10^3

0 ≤ Value of ratings ≤10

15.algorithms classification

http://www.scriptol.com/programming/algorithms-classification.php
http://bigocheatsheet.com/

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s