## Recent Interview Questions

- 0of 0 votes
Chinese chess has 8*8=64 cells.And the point is (1,1),（1，2）,..............(8,8）.And the horse walks by diagonal line of two cells from where point it is.Calculate the shortest step(s) between two points for the horse to walk. Eg. (1,1) to (4,4). Horse go like this (1,1)>(2,3)>(4,4)

- 0of 0 votes
Chinese chess has 8*8=64 cells.And the point is (1,1),（1，2）,..............(8,8）.And the horse walks by diagonal line of two cells.Calculate the shortest step(s) between two points for the horse to walk. Eg. (1,1) to (4,4). Horse go like this (1,1)>(2,3)>(4,4)

- 0of 0 votes
`Jumper Game: A NxN grid which contains either of 0-empty, 1 - player 1, 2 - player 2. Given a position in the grid, find the longest jump path. For jump path, you can jump only diagonally, you can jump on opponent cell and also the landing cell should be empty. No opponent cell can be jumped more than once. Write a function which takes grid and a specific position in the grid, and returns the longest possible number of jumps in the grid. For Example: if grid = { { 0,0,0,0,0,0 }, { 0,1,0,0,0,0 }, { 2,0,2,0,2,0 }, { 0,0,0,0,0,0 }, { 0,0,0,0,0,0 }, { 0,0,0,0,0,0 }, }; Answer should be 2 - (1,1) -> (3,3) -> (1,5)`

- 0of 0 votes
Given an array of integers.

Move all non-zero elements to the left of all zero elements.

- 0of 0 votes
There's a new language which uses the latin alphabet. However, you don't know the order among letters.

It could be:

a b c d ...

as it could also be:

b e z a m i ...

You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.

- 0of 0 votes
There are different buildings standing close to each other. These are of same width but different height.

Suppose if rainfall happens, what will be the volume of water that get trapped on top of all these buildings together. ?

INPUT (Example)

No: of buildings : 4

heights of the buildings(in any units): 3 4 3 4

- 0of 0 votes
Design Maps: You have set of [lat, long] for all famous locations. Given your position [lat, long] return all famous locations within r radius of your position.

- 0of 0 votes
You have set of [lat, long] of all famous locations. Given your position [lat, long] return all famous locations within radius r of your position

- 0of 0 votes
-How to mitigate that your software is the real one and not the stolen one.

- 0of 0 votes
How to steal a password when i have both public key and know the algorithm?

- 0of 0 votes
If i record the traffic when i write the username and password and redirect my page?

- 0of 0 votes
Given a number,print it in words.

19621 -> One lakh ninety six thousand and twenty one.

- 0of 0 votes
Given a array of positive integers, find all possible triangle triplets that can be formed from this array.

eg: 9 8 10 7

ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10

Note : array not sorted, there is no limit on the array length

- 0of 0 votes
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.

A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 = P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q], and in addition A[P] ? A[Q].

For example, in array A such that:

A[0] = 0

A[1] = 3

A[2] = 3

A[3] = 7

A[4] = 5

A[5] = 3

A[6] = 11

A[7] = 1

the following pairs of indices have adjacent values:

(0, 7), (1, 4), (1, 7),

(2, 4), (2, 7), (3, 4),

(3, 6), (4, 5), (5, 7).

For example, indices 4 and 5 have adjacent values because the values A[4] = 5 and A[5] = 3 are different, and there is no value in array A that lies strictly between them - the only such value could be the number 4, which is not present in the array.

Given two indices P and Q, their distance is defined as abs(P-Q), where abs(X) = X for X = 0, and abs(X) = -X for X < 0. For example, the distance between indices 4 and 5 is 1 because abs(4 - 5) = (5 - 4) = 1.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the maximum distance between indices of this array that have adjacent values. The function should return -1 if no adjacent indices exist.

For example, given array A such that:

A[0] = 1

A[1] = 4

A[2] = 7

A[3] = 3

A[4] = 3

A[5] = 5

the function should return 4 because:

indices 0 and 4 are adjacent because A[0] ? A[4] and the array does not contain any value that lies strictly between A[0] = 1 and A[4] = 3;

the distance between these indices is abs(0 - 4) = 4;

no other pair of adjacent indices that has a larger distance exists.

Assume that:

N is an integer within the range [1..40,000];

each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

- 1of 1 vote
Given an array of type:-

1. Increasing

2. Decreasing.

3. Increase-Decrease

4. Decrease-Increase

Find:- 1. Type of array in minimum steps ?

2. Maximum element from array in min steps?

- 2of 2 votes
Question was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.

Examples:

1) Pattern : "abba", input: "redbluebluered" should return 1.

2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.

3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.

- 0of 0 votes
Given an array of integers when the difference between every two neighbored elements is either -1 or +1 or 0.

Write an efficient search algorithm to find a given number of x in the array.

- 0of 0 votes
Implement algo for ls command in unix. You have n ordered file names with you. You have to print file names in column then in rows.

e.g. I have 5 files

F1 F3 F5

F2 F4

Minimize on number of rows

Maximize on number of columns

Max Page Width possible P

Page width of any row = max width of all files in first column + max width of all files in second column + ... +max width of all files in last column

- 0of 0 votes
`You are given an mxn grid, where (0,0) refers top most left position and (m-1,n-1) the bottom most right. The grid is filled with ones. All positions in the grid that are blocked are filled with zeros. You are given this grid and are assured that there exists atleast one path from (0,0) to (m-1, n-1). Find the minimum distance of the path from (0,0) to (m-1, n-1) given that you are allowed to move only vertically, horizontally and diagonally`

- 0of 0 votes
You have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.

Tower:

{

(height, 100), (weight, 50),

(xposition, 25), (yposition, 36)

}

Tree:

{

(area, 100), (noofleaves, 500),

(height, 25), (yposition, 36)

}

Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different.

Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match.

For example, if you have the above two objects, then the answer for the following queries is

Query:

{ (height, 100), (yposition, 36) }

Answer:

1 // matches Tower, but not Tree

Query:

{ (yposition, 36) }

Answer:

2 // matches both Tower and Tree

Query:

{ (height, 100), (noofleaves, 500) }

Answer:

0 // neither Tower, not Tree satisfy both properties

Input

The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings - the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above).

This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification.

One test file will contain only one test case. A single test case may contain several queries.

Output

Print M lines. Each line must be the answer of the respective query.

Constraints

1 ≤ N ≤ 10000

1 ≤ M ≤ 100000

1 ≤ k ≤ 4

Sample Input

2 3

4

height 100a

weight 50b

xposition 25a

yposition 36b

4

area 100a

noofleaves 500

height 25

yposition 36b

3

weight 80

xposition 25a

yposition 36b

1

yposition 36b

2

xposition 25a

yposition 36b

Sample Output

0

2

1

- 0of 0 votes
You are given a rectangular grid with 2 rows and N columns. The top row is labeled 1 and the bottom row is labeled 2. The columns are labeled from 1 to N in increasing order. Each cell in the grid contains a single character.

Consider a hamiltonian walk in this grid. Meaning, pick a starting cell, say (i,j), and consider a path that starts from (i,j) and goes through every cell in the grid exactly once. Note that you can only walk to adjacent cells, or cells that you share a common edge with. There may be several such paths. Let us concatenate the characters in the order in which the cells are visited during a walk. The string formed can be called the string for the walk.

Among all the possible walks, and their respective strings, find out the lexicographically smallest string. We know that the length of the strings are all the same - to be precise, 2N. Thus, the lexicographically smallest string is simply the alphabetically smallest string if you compare the characters from left to right.

Input

The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 3 lines. The first line contains the number N, the number of columns in the grid. It is well known of course that the grid contains 2 rows. The next two lines contain the description of the grid in the form of two strings; the string of N characters in row 1 from left to right and the string of N characters in row 2 from left to right, respectively. Each character will be a lowercase engish letter.

Output

Output a single line for each test case. The line must contain a string with 2N characters. This string should be the lexicographically smallest string for some hamiltonian walk in the grid.

Constraints

1 = T = 100

1 = N = 10

Sample Input

2

3

abc

def

10

ababaaabab

bababababa

Sample Output

abcfed

aaababababababababab

Explanation

In the first test the possible strings are { abcfed, adebcf, adefcb, badefc, bcfeda, cbadef, cfedab, cfebad, dabcfe, dabefc, defcba, edabcf, efcbad, fedabc, fcbade, fcbeda }. The smallest string is abcfed.

- 1of 1 vote
You have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?

(Use Dynamic Programming)

- 0of 0 votes
`There are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.`

- 2of 2 votes
Given a large array of unsigned ints, quickly find two who's sum is 10

Then the interviewer asked me to write test cases.

Followed by how to implement this on a distributed system, where multiple systems can read/write simultaneously on a shared cache (HINT: It is ok if you do not return the first instance)

- 0of 0 votes
A seller sells lot of products in his store and people place orders,just like any other store. Each item has a different weight and price.

And each order can be a combination of different number of items with random quantity. Now each of these orders areto be put into different packages and sent to the courier company for delivery.

But there are certain rules while splitting items into packages, they are as below:

1. If the cost of all the items in an order is more than $1000, split those items into multiple

packages, otherwise one package would be enough.

2. If the items in the same order are split into multiple packages, then the weight of the

packages should be equally distributed over the packages with consideration of optimum

courier charges.

3. While splitting, NO PACKAGE can have a total price above $1000

- 0of 0 votes
In a city year of birth/death of people who where born and died between year 1900 to 2000 are given. Write an algorithm to find the year in which max people were alive.

- 2of 2 votes
What is the maximum number of edges you could add to n vertexes to make a acyclic undirected graph?

Follow up:

What is the maximum number of edges you could add to n vertexes to make a acyclic directed graph?

- 1of 1 vote
There is a string whose characters can only be either ‘a’, ‘b’ or ‘_’ (there can be only one ‘_’ in the string). At each step, we can modify the string as follows:

1. ‘_’ can be swapped with its adjacent character, example “a_ba” can be changed to either “_aba” or “ab_a”.

2. Two characters adjacent to ‘_’ (both on the same side of ‘_’) can be reversed along with the ‘_’ if both characters are different, example, “aa_ba” can be changed to “aaab_” but not to “_aaba” because both characters are ‘a’.

You are given two strings, the initial state and the final state (lengths will be same), you have to output the minimum number of steps required to change the string in initial state to the string in the final state.

example:

input: a_b ab_

output: 1

input: abaa_a b_aaaa

output: 4

reason for example 2:- abaa_a -> aba_aa -> ab_aaa -> _baaaa -> b_aaaa

- -1of 1 vote
Implement a vector-like data structure from scratch.

This question was to be done in C or C++.

Discussion topics:

1. Dealing with out of bounds accesses.

2. What happens when you need to increase the vector's size?

3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back

- 0of 0 votes
You have a sorted array containing the age of every person on Earth.

[0, 0, 0, 0, ..., 1, 1, ..., 28, 28, ..., 110, ...]

Find out how many people have each age.