## unknown Interview Questions

- 0of 0 votes
You are given a tree and any of the leaf node which is given as input is set to fire. And in each unit time all the neighbouring nodes of the nodes which are already in fire also catch fire. Given a tree find the time taken for the whole tree to catch fire.

The whole catches fire meaning all nodes catches fire.

Example :

4

/ \

5 6

/ \ / \

7 8 9 10

\ \

13 11

\

12

Assume the source leaf node : 9

At 1 sec : 6 catches fire

At 2 sec : 10 and 4 catches fire

At 3 sec : 5 catches fire

At 4 sec : 7 and 8 catches fire

At 5 sec : 13 and 11 catches fire

At 6 sec : 12 catches fire

If we have access to parent pointers its easy just BFS and keeping track of visited we get the answer.

How to go about the problem if we do not have access to parent pointers ??

- 0of 0 votes
Given a array of integers there is one that is repeated several time. How would you compute the length of the sequence of repeated elements.

Assuming the initial array is sorted can you do better than O(n) both for spatial and temporal cost?

- 0of 0 votes
You are given 20 questions to solve in 20 minutes.

If you successfully solve the question, you would receive 2 marks.

If you failed to solve the question, and you do not try it ( let it untouched ) , you would receive 0 marks. If you solve it wrong ( i.e. not the correct answer ) - you would receive -1 ( negative) .

With the story, here are the problems:

1. Write an algorithm, which, given an input array ( set ) of questions, and varying probability ( 0 <= p <= 1 ) of can do and can not do per question, generates a strategy for solving the paper to generate maximum expected pay off.

2. Given the question paper is multiple choice, between 4 choices ( a,b,c,d ) do a bias analysis ( e.g. if more a's are coming than 'c's ), and decide if you would like to probabilistically take risk and mark some to increase pay off.

Obviously, you can get a maximum 40, and a minimum -20.

3. Now, put yourself in the position of the examiner, and try to ensure it is almost impossible to increase payoff by random selection over the questions. Try to negate the bias. That is question 3.

In all 3 cases write an algorithm. Face to face interview, time allocated was 60 minutes. Panel Interview.

- 0of 0 votes
Consider a string A containing exactly X characters. A variant of A, A(k), can be obtained by doing a cyclic shift of A starting from position k (0 <= k < X). The number of characters after the shift in A(k) will remain the same as they were in A. Every j-th character (0 <= j <= X-1) of A(k) is equal to (k+j)%X character of A. We will call A a classic word if there are exactly M positions k such that A(k) = A

You are given array Q containing exactly R strings. For each permutation s = (s[0], s[1], ..., s[R-1]) of integers between 0 and R-1, inclusive, we can define a string generated by this permutation as a concatenation Q[s[0]] + Q[s[1]] + ... + Q[s[R-1]]. Find the number of permutations that generate classic words. All indices in this problem are 0-based

Constraints

Set Q will contain between 1 and 8 elements, inclusive. Each element will have 1 to 20 characters, inclusive

M will be between 1 and 200, inclusive

Input Format

Line 1: comma separated strings representing set Q

Line 2: Integer M

Output Format

Number of permutations that generate classic words

Sample Input

CD,QCCD,QC

2

Sample Output

3

Explanation

The classic words are "CDQCCDQC" and "QCCDQCCD". Permutation 0, 1, 2 generates the first, and 1, 2, 0 and 2, 0, 1 generate the second

- 0of 0 votes
Your friend has invented a new compound consisting of N elements. However, he has forgotten the amount of each element that goes into the recipe.

For N-1 pairs of elements, he remembers the proportion in which the elements within each pair should be added to the compound. Fortunately, these N-1 proportions are sufficient to restore the recipe of the entire compound.

You are given N-1 proportions as String. Each String is formatted "#<a> and #<b> as <p>:<q>" (quotes for clarity), which means that the mass of element <a> divided by the mass of element <b> in the cocktail must be equal to <p>/<q> (all elements are 0-indexed). Print exactly N elements, where the first line is the mass of element 0 and second line is the mass of element 1 and so on... such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0.

Input

Line 1: N

Line 2 .. N: proportion_i

Output

N lines of masses, as stated in the problem statement

Input Explanation

Line 1: N, the number of elements

Line 2 to line N: N-1 proportions, format described in the problem statement

Output Explanation

Output will contain exactly N lines, each line is the mass of the element such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0.

Sample Input

3

#0 and #1 as 9:8

#1 and #2 as 9:8

Sample Output

81

72

64

- 0of 0 votes
Consider a social website SocialX, where friends connect to each other, just as they do on Facebook

Friendship on SocialX is symmetric (if X is a friend of Z, then Z is also a friend of X) however not transient (if X and Z are friends and Z and Y are friends, then X and Y are not necessarily friends)

The term "k-joined" is defined as follows. If two people are friends, they are called 1-joined. For k >= 1, two people X and Z are called (k+1)-joined if X and Z are k-joined, or if there exists a person Y such that X and Y are k-joined and Y and Z are friends.

"Approachable Score" is defined as follows. If two people X and Z are not friends, then their Approachable Score is the fewest number of people (other than themselves) who must be removed from the network in order for X and Z to not be 3-joined. The higher the Approachable Score, the more likely it is that X and Z know each other.

Given a set of friends containing exactly K elements, where K is the number of people in the network. People are numbered from 0 to K-1. The j-th character of the i-th element of friends is '1' if i and j are friends, and '0' otherwise. Return the Approachable Score for personX and personZ

Constraints

Set of friends will contain exactly K (1 < K < 41) elements, where each element will contain exactly K characters. Each character will either be '0' or '1'

friends[i][j] will always be equal to friends[j][i] and friends[i][i] will always be equal to 0

friend[personX][personZ] will be equal to 0 and personX will never be equal to personZ

Input Format

Line 1: comma separated K elements representing friends

Line 2: Integer representing personX

Line 3: Integer representing personZ

Output Format

Integer representing Approachable Score

Sample Input

0100,1010,0101,0010

0

3

Sample Output

1

Explanation

Either remove person 1 or person 2 to get an Approachable Score of 1 for person 0 and 3

- 1of 1 vote
You are given a list of tasks as an integer array, task_costs. Every i-th element of task_costs represents a task and requires task_costs[i] seconds to complete. All tasks listed in the array are independent of other tasks.

It is required to finish all the tasks independently and as soon as possible. You are given a single worker robot to start taking the tasks and finish them one at a time. However if you like, you can divide the worker robot in two. Each resulting robot can then be further divided into two and so on. There is a cost, in seconds, of dividing a robot in two, represented by robot_divide_cost.

You can assign an independent task to any available robot, however you can't interrupt or divide a robot while it is working on the assigned task. At the same time you can't assign a task to any robot while its in the process of getting divided.

To keep things simple you can't allow multiple robots to work on the same task. At any given time only one robot can work on a task and finish it. Once any particular robot finishes a task it can't be assigned any further tasks.

Given a list of tasks and cost of dividing a robot, find the least amount of time to finish all tasks.

Input:

3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,360,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600,3600

3600

Expected Output: 25200

Input:

1113,773,824,822,1458,1257,908,1320,780,1016,1066,861,1150,718,1405,738,718,980,1037,946,1121,1349,805,1378,1308,1272,1532,779,875,1392,982,1282,744,723,1033,1067,1158,1071,742,683,678,762,686,1143,862,1231,765,1472,1560,1085

3147

Expected Output: 20040

- 0of 0 votes
You are given a string X and integer k (0 <= k < length of X). For each value of k you can look at a sub-string of X starting from index 0 to index k and choose to reverse it. As an example, let X = LMNAP and k = 2. If you reverse the sub-string of X between 0 and 2 you will get NMLAP. Subsequently if choose k = 3 and reverse you will end up with ALMNP.

Given the string X as an input find lexicographically earliest possible string. In the example above, lexicographically ALMNP comes earlier than NMLAP.

Input:

AACAACAABBABACAACBCACCCAAABACABACACCBCCAAABABACBCC

Expected Output: AAAAAAAAAAAAAAAAAAAAAAACCBBBCCBCCCCBCBCCCBCCBBCBCC

Input:

BACBCBCACAACBCBBCCBACCCCAACCBCCAABACAABCAAAABBAABC

Expected Output: AAAAAAAAAAAAAAAAAABCBCBCCCBCBBCCBCCCCCCBCCBCBCBBBC

- 0of 0 votes
How to print from 3rd column to till last columns using awk command in unix, if there are 'n' columns in a file.

- 0of 0 votes
Given a matrix of ‘O’ and ‘X’, find the largest sub rectangle surrounded by ‘X’

Example :

XXXXX

X0X0X

XXXXX

XXXXX

Output : largest rectangle size is 4 x 5

- 0of 0 votes
`interface RangeContainerFactory { /** * builds an immutable container optimized for range queries. * Data is expected to be 32k items or less. * The position in the “data” array represents the “id” for that instance * in question. For the “PayrollResult” example before, the “id” might be * the worker’s employee number, the data value is the corresponding * net pay. E.g, data[5]=2000 means that employee #6 has net pay of 2000. */ RangeContainer createContainer(long[] data) } /** * a specialized container of records optimized for efficient range queries * on an attribute of the data. */ interface RangeContainer { /** * @return the Ids of all instances found in the container that * have data value between fromValue and toValue with optional * inclusivity. The ids should be returned in ascending order when retrieved * using nextId(). */ Ids findIdsInRange(longfromValue, long toValue, boolean fromInclusive, boolean toInclusive) } /** * an iterator of Ids */ interface Ids { /** * return the next id in sequence, -1 if at end of data. * The ids should be in sorted order (from lower to higher) to facilitate * the query distribution into multiple containers. */ static final shortEND_OF_IDS = -1 short nextId() } Validation: Your implementation should pass the following simple JUnit test before you start tuning for performance with volume data: public class RangeQueryBasicTest { private RangeContainer rc @Before public void setUp(){ RangeContainerFactory rf = new YourRangeContainerFactory() rc = rf.createContainer(new long[]{10,12,17,21,2,15,16}) } @Test public void runARangeQuery(){ Ids ids = rc.findIdsInRange(14, 17, true, true) assertEquals(2, ids.nextId()) assertEquals(5, ids.nextId()) assertEquals(6, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) ids = rc.findIdsInRange(14, 17, true, false) assertEquals(5, ids.nextId()) assertEquals(6, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) ids = rc.findIdsInRange(20, Long.MAX_VALUE, false, true) assertEquals(3, ids.nextId()) assertEquals(Ids.END_OF_IDS, ids.nextId()) } } FAQ Can't we just use a B-Tree/ NavigableMap/HashTable/BinarySearch/Lucene... Sure, if you want. But there are a number of things we'd like to achieve: ● The container will be in memory and will need to hold lots of data, so we'd like it to be as space efficient as possible, but not to the extent where speed is significantly compromised. Speed is king, memory/disk can be purchased. ● Since we hate collecting garbage, we need to be careful about memory allocation during a query, as my grandmother told me, "allocate not, gc not". ● Code should be clear and understandable. ● The rough order of trade off to consider for this case is: search performance, efficient usage of memory, simplicity and maintainability of the code These objectives are often at odds - we'd like to explore what's possible.`

- 2of 2 votes
How to find middle element in a linked list without knowing the length of the linked list

- 2of 2 votes
You know result of a soccer match, print all the possible ways that this game ends up with this result.

Example: final score 1 - 1:

0 - 0

0 - 1

1 - 1

0 - 0

1 - 0

1 - 1

Another example if the final score is 2 - 3 there are many possibilities for reaching to that score:

2 - 3

0 - 0

1 - 0

2 - 0

2 - 1

2 - 2

2 - 3

0 - 0

1 - 0

1 - 1

1 - 2

2 - 2

2 - 3

0 - 0

0 - 1

0 - 2

0 - 3

...

- 0of 0 votes
Find the largest substring in s1, such that all characters in the substring are present somewhere in s2

- 0of 0 votes
Asked me to write an API. Then ask:

Consider how the API could support 3rd party applications which need to perform some logic based on the structure and content of a filter in a type-safe manner.

- 0of 0 votes
It is part of a programming exercise.

Input is a combination of arbitrary complex filters. For example:

name = "smith" AND age > 9 OR Not(city = "New York")

It asks for a string representation, including the ability to generate and parse filters from the string representation. (you are not required to implement the string parsing logic since this could take too long)

Hint: give an example of a tree data structure.

- 0of 0 votes
Given an array of integers of unknown size, how to reverse the order of the positive integers?

Ex [4 3 8 9 -2 6 10 13 -1 2 3 .. ] =>

[ 9 8 3 4 -2 13 10 6 -1 3 2]

- 0of 2 votes
The "Island Count" Problem

Given a 2D matrix M, filled with either 0s or 1s, count the number of islands of 1s in M.

An island is a group of adjacent values that are all 1s. Every cell in M can be adjacent to the 4 cells that are next to it on the same row or column.

Explain and code the most efficient solution possible and analyze its runtime complexity.

Example: the matrix below has 6 islands:

0 1 0 1 0

0 0 1 1 1

1 0 0 1 0

0 1 1 0 0

1 0 1 0 1

- 0of 0 votes
Find the nth Fibonacci Prime, in the shortest code

- 0of 0 votes
Given a list of nodes, each with a left child and a right child (they can be null), determine if all nodes belong in a single valid binary tree. The root is not given.

- 0of 0 votes
A paper consists of a series of consecutive numbers from 1 up to 2^n values. For example,

For case 2^1, content of the paper is,

1 2

For case 2^2, content of the paper is,

1 2 3 4

For case 2^3, content of the paper is,

1 2 3 4 5 6 7 8

There will be n number of commands for 2^n case. Below are the commands,

L – Fold the paper from Left edge to Right edge

R – Fold the paper from Right edge to Left edge

After performing the n number of commands, there will be a single number in all layer of paper, you need to write down the numbers in all layers when you see the paper from upside of it.

Please provide an efficient algorithm.

Example:

Content of the paper (2^3):

1 2 3 4 5 6 7 8

Commands: LRL

Output:

5 4 1 8 7 2 3 6

- 0of 0 votes
How will you test an application like Google Analytics ?

- 0of 0 votes
What are the basic features you will add into your own test framework ?

- 0of 0 votes
Which structure can be used to return the lastly added node and remove it from the collection and also will allow to peek the highest valued node without removing it from the collection. What is the time and space complexity for Push, Pop and Peek actions

- 0of 0 votes
Suppose you have a huge data of students. This data is in RAM (around 48 GB). Student has following attributes:

1) RollNo

2) Name

3) Address

Now I need to implement three method:

getStudentByRollNo(int rollno)

getStudentsByName(String name)

getStudentsByAddress(String address)

In what data structure I can keep these students so that these methods can return the results really fast.

- 2of 2 votes
The problem gives you a sample input data file containing the all the employee-employer relationship information of a company. For example "Peter, John, 2013, software developer--John, NULL, 2012, CEO--David, Peter, 2014, technician..." means there are 3 people int this company (segmented by '--' ), the first 1 is Peter, his boss is John, he entered the company in 2013 as a software developer. The second is John as CEO, with no boss, the third is David as technician, his boss is Peter. The problem is asking to output information in hierarchy style

- 0of 0 votes
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (prisoners, who also have danger ranks). The guard has a list of prisoners with their corresponding danger ranks and he also has a list of the friends of each of the prisoners in the prison.

The danger rank is computed as follows: Prisoner 1 has a danger value of 5, his friends are Prisoner 2 and Prisoner 5, who have danger values of 3 and 4 respectively. So the danger value of Prisoner 1 is 5+3+4 = 12.

There could be any number of prisoners. Whichever prisoner has the highest value is the most dangerous(computed using the above method).

Friendship can be assumed to be symmetric.

Come up with an efficient algorithm to find the most dangerous prisoner?

The solution I came up with runs in quadratic time.

A hash table which has the Prisoner as Key and list of his friends as value

Compute the sum of danger rank of all friends one key at a Time. (n * N)

Maintain a max count and update it as necessary.

I believe there is a solution for this problem having better time complexity than O(N^2).

- 0of 0 votes
Operation :Deleting element in the binary search tree(Without linked list) I'm trying to implement a pseudo-code but operation not implemented.can cause?(If you want I can write a pseudo-code.)So,delete operation is not happening for BST.can cause?-1 is null element in array. Linked list is not be for this code.

void deleting(int *Tree,int element){

int temp=0;

while((Tree[temp]!=element) && (Tree[temp]!=-1)){

/*loop until the element is found*/

if(element<Tree[temp])

temp=2*temp+1;

else

temp=2*temp+2;

}

if(Tree[temp]!=1)/* if the element is found*/

/*case1 - Delete leaf node*/

if((Tree[2*temp+1]==-1) && (Tree[2*temp+2]==-1))

Tree[temp]=-1

/*case 2- delete node with one child*/

else if((Tree[2*temp+1]==-1)|| (Tree[2*temp+2]==-1)){

if(Tree[2*temp+1]!=-1) /* is the child in the left of temp*/

preOrder((2*temp+1),Tree);

else

preOrder((2*temp+2),Tree);

}

/*case 3-delete node with 2 children*/

else if {

int inOrder_N=2*temp+2 /* inorder successor is surely in the right sub tree*/

while(Tree[2*inOrder_N]!=-1)

inOrder_N=2*inOrder_N;

Tree[temp]=Tree[inOrder_N]; /* replace with inorder successor*/

if(Tree[2*inOrder_N+2]==-1);/* inorder successor has no child*/

Tree[inOrder_N]=-1;

else /* inorder successor has no child*/

preOrder(((2*inOrder_N)+1),Tree)

}

else

printf("element not found");

}

void preOrder(int node, int *bst,int n){

if(node<n){

printf("Node : %d - Value : %d \n",node,bst[node]);

preOrder(2*node+1,bst,N);

preOrder(2*node+2,bst,N);

}

return;

}

- 0of 0 votes
You have two anagram strings S and P. You can do an operation swap(), which swaps two adjacent characters in a string, or swaps the last character and the first character in a string. What is the minimum number of operations you have to perform to change S to P.

E.g. S = "abcd", P = "bdca", the output should be 2, as "abcd" -> "dbca" -> "bdca".

- 0of 0 votes
I have an unordered array of nodes. Each node has an id and parent_id. I want to pretty print out the nodes in an expanded format.

Assumptions:

There is only one root node in the array.

Don't worry about the white space.

Node has a toString() method.

All the ids are arbitrary and unique.

This is a tree and not a graph.

For example:

Sample input:

[{parentId: F, id:G}, {parentId: E, id: F}, {parentId: A, id: B}...]`A (parent_id = null) B (parent_id = A) C (parent_id = B) D (parent_id = C) H (parent_id = B) E (parent_id = A) F (parent_id = E) G (parent_id = F)`

Sample output:

ABCDHEFG

Please write a more optimized solution and tell me the complexity.