Sunday, October 16, 2016

Wednesday, October 12, 2016

Group Shifted Strings

Given an array of strings (all lowercase letters), the task is to group them in such a way that all strings in a group are shifted versions of each other. Two string S and T are called shifted if,

S.length = T.length
S[i] = T[i] + K for
1 <= i <= S.length  for a constant integer K
For example strings {acd, dfg, wyz, yab, mop} are shifted versions of each other.

Count maximum points on same line

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.


Input : points[] = {-1, 1}, {0, 0}, {1, 1},
                    {2, 2}, {3, 3}, {3, 4}
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}

Assembly Line Scheduling

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Thursday, October 6, 2016

Happy Numbers

What is an happy number can be shown in the following example:

19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Caterpillars and Uneaten Leaves

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has as associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon.

Given a set A of K elements K<-15, N<=10^9, we need to determine the number of uneaten leaves.


N= No of uneaten leaves.

K= No. of caterpillars

A = Array of integer jump numbers

Output: The integer nu. Of uneaten leaves.

Sample Input:10, 3, 2, 4, 5

Output: 4


[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

Wednesday, September 14, 2016

Active and Inactive cells after k Days

Given a binary array of size n where n > 3. A true (or 1) value in the array means active and false (or 0) means inactive. Given a number k, the task is to find count of active and inactive cells after k days. After every day, status of i’th cell becomes inactive if its left and right cells have same value, i.e., either both are 0 or both are 1.
Since there are no cells before leftmost and after rightmost cells, the value cells before leftmost and after rightmost cells is always considered as 0 (or inactive).

Maximize value of (arr[i] – i) – (arr[j] – j) in an array

Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. Where i and j vary from 0 to n-1 and n is size of input array arr[].

Tuesday, September 13, 2016

Behavioural Questions

Behavioral Questions
  1. Things u learn in 3 years of experience which makes u different from fresher guy?
  2. Project description

Miscellaneous Interview Questions

1. Draw the recursion stack of any program and find in what order one function is called and stored in the stack and in what order it is returned back to its callee function. And to prove what is the space complexity through that recursion stack.