# Interview Problems 23

February 19, 2011 22 Comments

1. A question set is given to you and you have to generate (question numbers are in an array) generate different set of question paper for k students.

2. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k “abcababceced” (2 ‘c’ are removed)

After removing repeated substring of length 2: “abcababceced” –> “abcabceced” (substring “ab” is removed) and so on.

3. You are given a 1D array of integers, such as:

int[] array = [3,4,7,2,2,6,0,9];

Suppose you need to treat this array as a 2D table with a given number of rows.

You want to sum the columns of the table.

One value of numRows is 4..in that case the resultant array would look like

what if numRows==4?

3 4

7 2

2 6

0 9

—-

12 21

4. Given an unsorted array, find the longest consecutive elements sequence.

Ex: 5 7 3 4 9 10 1 15 12

Ans: 3 4 5

5. You have to create a graph in most efficient way from relationship of nodes read from txt file.

text file contains information like:

node_id weight node_id

node_id weight node_id

…..

// which means two nodes are connected with some weight. (undirected)

There are around 600K such information for about 65000 nodes.

Aim is to create a a subgraph for a given node_id. i.e for that node_id find ALL successor nodes with level mentioned i.e form a subgraph for that node.

6. Given ‘n’ no of sets and each set is of a variable size. Find out the cross product of these ‘n’ of sets.

For eg. {1,2} , {3,4} , {5,6,7} these are the three sets.The cross product of these sets would be as below.

{1,3,5},{1,3,6},{1,3,7},{1,4,5},{1,4,6},{1,4,7},{2,3,5},{2,3,6},{2,3,7},{2,4,5},{2,4,6},{2,4,7}.

7. Given an array of integers, find out number of ways in which you can select increasing subsequences of length k(k<=n).

eg array is 1 4 6 2 5 & k=3

Output: 3

Sequences: 1 4 6, 1 4 5, 1 2 5

8. Sorry posted this question as a repetition of question 1.

9. Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays

eg:

0 1 0 0 1

1 0 1 1 0

0 1 0 0 1

1 1 1 0 0

ans:

0 1 0 0 1

1 0 1 1 0

1 1 1 0 0

10. Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1).

10.

Step1: Find the point after which the decrease starts let us call it P1. O(logn)

Step2: From P1 reverse the array. O(n)

Step3: Mark the beginning of the array as P2.

Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)

If you notice, there are multiple points in the array which has the mentioned property. So the algorithm you suggest will not work in given constraints.

If you can do this problem in O(n), you can sort in O(n) which isn’t possible. Isn’t every possible combination a sequence of increasing and decreasing sequence?

May be the interviewer was looking for the candidate to prove that it can’t be done.

8. isnt it Fisher–Yates_shuffle card shuffling algorithm?

plz correct me if i m wrong.

No. This is not a shuffling problem. Please think over it as minimizing the number of question repetitions across students.

can u give me the algo of 10th question?

You can post approaches and I might help you out. Do not prefer to vomit out answers 🙂

10.

isnt it similar to k way merging…and isnt a very complex algorithm (which i am not sure what it should be) involved to do inplace merging in o(n)?

1. Let me rephrase this question. From a total of n questions you have to give m questions to each of the k students such that each question is repeated equal number of times. Am I right?

No. Both the number of repeated questions and the number of repetitions of each repeated question are minimized.

“Both the number of repeated questions and the number of repetitions of each repeated question are minimized.”

Both should be minimized means?

it will be good if you explain with some sample input/output

Suppose there are 7 questions, 5 students, 2 should be given to each student.

(1,2) (3,4)(5,6)(7,1)(1,2)

repeated questions : 1–> 3 times and 2 ->2 times

if we divide:

(m*k)/n gives minimum number of times each question must be repeated.

remainder questions (m*k)%n times some more questions should be repeated again.

9. The example that you gave isn’t a N X N array.

Assuming N X N array, O(nlogn) solution is evident if N < 64. Basically the problem can be reduced to finding unique elements in an array. Quick Sort is one way to do it. Hashing can give a O(n) solution. For larger N, count sort can be used to sort the array and then find the duplicates.

@avi

if can’t help person..do u think u are very smart or wisest person in the world .then 🙂

@ilovealgo

If my not

answeringthe questions is your frustration then please forget this URL and go to some other site. I am not interested in sharing knowledge with people who areonlyinterested in answers. This place is for discussions, not giving out answers and putting adds to earn money.As far as my answering goes, I reply on the comments only when I am free. I work for a company who pays me to work for them, this blog gives me just leisure when I am free. So I will reply to the comments as per my wimps and fancies. And if I am not replying that directly implies that I am busy at work and will get back later.

10. There should be an additional factor k in the complexity, where k is the number of such monotones; otherwise every random array is your array with k = n – 1 in worst case.

9. Apparently, we can’t directly post code in comments in wordpress. Here is the link http://pastebin.com/XNHfw0h1

U can post code by

open_square_brace sourcecode language=”C” closed_square_brace

…. code ….

open_square_brace backslash closed_square_brace

updated your code with sytanx highlighting using the below mentioned tags. Not checked.

10. I don’t think it is possible to sort the array in O(n) , with any comparison sort. And any other method will probably take space O(n).

As we can easily observe that any sequence of number can be divided into monotonically increasing and monotonically decreasing sets.

Ex: lets say: 1,3,2,5,7,6

(1,3) decreasing (2,5,7) decreasing 6.

please reply if you disagree.

9.Anything better than O(nlgn) possible ?

n log n is simple to achieve. If anyone wants we can discuss it.

@vikas can u provide the code & algo for 9th question 🙂 reply asap