Interview Problems 23

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).

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

22 Responses to Interview Problems 23

  1. snehal says:

    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)

    • Avi Dullu says:

      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.

      • Amar says:

        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.

  2. snehal says:

    8. isnt it Fisher–Yates_shuffle card shuffling algorithm?
    plz correct me if i m wrong.

  3. duke87 says:

    can u give me the algo of 10th question?

  4. amit says:

    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)?

  5. Amar says:

    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?

    • Avi Dullu says:

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

      • vikas says:

        “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.

  6. Amar says:

    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.

  7. ilovealgo says:

    @avi

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

    • Avi Dullu says:

      @ilovealgo

      If my not answering the 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 are only interested 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.

  8. CyberS1ren says:

    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. CyberS1ren says:
    
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node
    {
      int num;
      struct node *left, *right;
    } node;
    
    node *Initialize()
    {
      node *root = (node *)malloc(sizeof(node));
      root->num = -1;
      root->left = root->right = NULL;
    
      return root;
    }
    
    int main()
    {
      node *root = Initialize();
    
      int m, n;
      scanf("%d%d",&m, &n);
    
      int i, j, temp;
    
      int a[m][n];
    
      for (i=0; i < m; i++)
        for (j=0; j < n; j++)
          scanf("%d", &a[i][j]);
    
      for (i=0; i < m; i++)
      {
        int flag = 0;
        node *ptr = root;
        for (j=0; jleft == NULL)  // Avi: Some problem here ?
        {
          root->left = (node *)malloc(sizeof(node));
          root->left->num = 0;
          root->left->left = root->left->right = NULL;
          flag = 1;
        }
        root = root->left;
      }
      else // Assuming only 0 and 1s; can add error handling
      {
        if (root->right == NULL)
        {
          root->right = (node *)malloc(sizeof(node));
          root->right->num = 0;
          root->right->left = root->right->right = NULL;
          flag = 1;
        }
    
        root = root->right;
      }
    }
    
    if (flag == 1) // We encountered it for the first time
    {
      for (j=0; j<n; j++)
        printf("%d ", a[i][j]);
      printf("\n");
    }
    
    root = ptr;
    }
    
    return 0;
    }
    
    
  10. vikas says:

    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.

  11. vikas says:

    9.Anything better than O(nlgn) possible ?
    n log n is simple to achieve. If anyone wants we can discuss it.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: