Microsoft Written Test Questions

Microsoft visited our campus for recruitment. Here are the 3 questions asked for us in written round. Unfortunately, i couldn't clear the written round. Anyone, please post the answers if you know them.

  1. There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). Full points are given for the solution bearing efficiency O(log n). Partial points for the efficiency O(n).


  2. Given a string *Str of ASCII characters, write the pseudo code to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed) . Extend your algorithm to remove duplicates in the string which consisted of UNICODE characters.


  3. Given that, there are 2 linked lists L1 and L2. The algorithm finds the intersection of the two linked lists. i.e' "L1 intersection L2 " ( similar to intersection of 2 sets ). Write all the possible test cases involved in the above given problem.

Please, post the answer if you know them.

26 comments:

  1. The median can be obtained recursively as follows. Pick the median
    of the sorted array A. This is just O(1) time as median is the n/2th
    element in the sorted array. Now compare the median of A, call is
    a with median of B, b. We have two cases.
    • a < b : In this case, the elements in B[n
    2 · · · n] are also
    greater than a. So the median cannot lie in either A[1 · · · n
    2 ]
    or B[n
    2 · · · n]. So we can just throw these away and recursively
    solve a subproblem with A[n
    2 · · · n] and B[1 · · · n
    2 ].
    • a > b : In this case, we can still throw away B[1 · · · n
    2 ] and
    also A[n
    2 · · · n] and solve a smaller subproblem recursively.
    In either case, our subproblem size reduces by a factor of half and
    we spend only constant time to compare the medians of A and B.
    So the recurrence relation would be T(n) = T(n/2) + O(1) which
    has a solution T(n) = O(log n).

    ReplyDelete
    Replies
    1. Computer ScientistSeptember 14, 2012 6:53 PM

      Anantharam: "Now compare the median of A, call is
      a with median of B, b . We have two cases."

      There are 3 cases, not 2 -
      1. a < b
      2. a > b
      3. a = b

      Delete
    2. case a = b:
      a is the median of the 2 lists.

      Delete
  2. 2.
    main()
    {
    char *str = "Potato";
    char *temp,*cur,*loop;
    temp = str;
    cur = temp;
    int flag;
    while (*cur !='\0')
    {
    loop = str;
    flag =0;
    while(loop<=temp)
    {
    if(*loop == *cur)
    {
    flag = 1;
    break;
    }
    loop++;
    }
    if (flag ==0)
    {
    temp++;
    str[temp-str]=*cur;
    }
    cur++;
    }
    temp++;
    str[temp-str]='\0';
    printf("\n\n %s",str);
    }

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. int mergeStep(int * & a, int * aEnd, int * & b, int * bEnd) {
    if (a == aEnd) {
    return *b++;
    }
    if (b == bEnd) {
    return *a++;
    }
    if (a < aEnd && b < bEnd) {
    return (*a < *b) ? *(a++) : *(b++);
    }
    throw runtime_error("can't progress merge");
    }

    /*
    * O(size) solution.
    */
    double findMedianLinear(int * a, int * b, int size) {
    int * aEnd = a + size, * bEnd = b + size;
    for (int i = 0; i < size - 1; i++ ) {
    mergeStep(a, aEnd, b, bEnd);
    }
    return (mergeStep(a, aEnd, b, bEnd) + mergeStep(a, aEnd, b, bEnd)) / 2.0;
    }

    ReplyDelete
  5. anantharam,
    could you explain how your algorithm of finding. will work on the following input:
    a = {1, 3};
    b = {2, 2);

    ReplyDelete
    Replies
    1. I forgot the case a (median of list 1) = b (median of list 2), in that case median is-> (max(a[n/2],b[n/2]) + min(a[n/2+1],b[n/2+1])/2

      Hence in this problem-> median of list a = 2 = median of list b = 2.
      (max(1,2) + min(3,2))/2 = (2+2)/2 = 2

      Delete
  6. double findMedianLog(int * a, int * b, int size) {
    int m1 = a[size / 2];
    int m2 = b[size / 2];

    if (size == 2) {
    return (max(a[0], b[0]) + min(a[1], b[1])) / 2;
    }
    if (m1 < m2) {
    return findMedianLog(a + size / 2, b, size - size / 2);
    }
    return findMedianLog(b + size / 2, a, size - size / 2);
    }

    ReplyDelete
  7. For 1st qns think on these lines for a logn algorithm:
    compare the medians of both arrays (in O(1) since it is sorted). The problem size will be reduced to n elements by this single comparison. Then continue

    ReplyDelete
  8. main()
    {
    char *str = "abababababcdefefefefefegyuiopl";
    char *p = str;
    char *q = p + 1;
    char *check = str;

    while (*p != '\0')
    {
    if (*q == '\0')
    {
    p++;
    q = p + 1;
    }
    while (( *q != *p ) && (*q != '\0'))
    q++;

    if (*p == *q)
    {
    check = q + 1;
    if (*check == '\0')
    *q ='\0';
    strcpy(q,check);
    q = p + 1;
    }
    }

    printf ("\n%s",str);
    }

    ReplyDelete
  9. For Question 2:



    * Arrays
    * Articles
    * Bit Magic
    * C/C++ Puzzles
    * GFacts
    * Linked Lists
    * MCQ
    * Misc
    * Output
    * Strings
    * Trees

    Print all the duplicates in the input string.
    March 22, 2009

    Write an efficient C program to print all the duplicates and their counts in the input string

    Algorithm: Let input string be “geeksforgeeks”
    1: Construct character count array from the input string.

    count['e'] = 4
    count['g'] = 2
    count['k'] = 2
    ……

    2: Print all the indexes from the constructed array which have value greater than 0.

    Solution
    view source
    print?
    # include
    # include
    # define NO_OF_CHARS 256

    /* Returns an array of size 256 containg count
    of characters in the passed char array */
    int *getCharCountArray(char *str)
    {
    int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
    int i;

    for (i = 0; *(str+i); i++)
    count[*(str+i)]++;

    return count;
    }

    /* Print duplicates present in the passed string */
    void printDups(char *str)
    {
    int *count = getCharCountArray(str);
    int i;
    char temp;

    for (i = 0; i < NO_OF_CHARS; i++)
    if(count[i] > 1)
    printf("%c, count = %d \n", i, count[i]);
    }

    /* Driver program to test to pront printDups*/
    int main()
    {
    char str[] = "test string";
    printDups(str);
    getchar();
    return 0;

    }
    NOTE: Copied from geeksforgeeks.org site....

    ReplyDelete
  10. char *remove_duplicates(char *str)
    {
    char *str1, *str2;

    if(!str)
    return str;

    str1 = str2 = str;

    while(*str2)
    {
    if(strchr(str, *str2)<str2)
    {
    str2++;
    continue;
    }

    *str1++ = *str2++;
    }
    *str1 = '\0';

    return str;
    }

    ReplyDelete
  11. Can anyone please give the solution for the last problem.

    ReplyDelete
  12. char * remove_dup_chars(char *str)
    {
    int len=strlen(str);
    char *tmp=str,*tmp2=str;
    int hole=0;
    while(tmp && *tmp!='\0') {
    hole=0;
    tmp2=(tmp+1);
    while(tmp2 && *tmp2!='\0') {
    if(!hole && *tmp2==*tmp) {
    hole=1;
    }
    if(hole) {
    while(*(tmp2+hole) == *tmp) {
    hole++;
    }
    *tmp2=*(tmp2+hole);
    }
    tmp2++;
    }
    tmp++;
    }
    return str;
    }


    int main()
    {
    char a[]="abcdabedaaabcf";
    printf("orig:%s\n",a);
    printf("after rem dup:%s\n",remove_dup_chars(a));
    memcpy(a,"Potato",strlen("Potato")+1);
    printf("orig:%s\n",a);
    printf("after rem dup:%s\n",remove_dup_chars(a));

    return 0;
    }

    ReplyDelete
  13. int main()

    {

    char str[]="ababdfdfhjiab";
    char *ptr;
    int i;
    printf("\n %s ",str);
    for(i=0;i<strlen(str)-1;i++)
    {
    for(ptr=&str[i+1];*ptr!='\0';ptr++)
    {
    if(*ptr==str[i])
    strcpy(ptr,ptr+1);
    }
    }
    printf("\n %s ",str);
    }

    ReplyDelete
  14. for the first question the method is very easy actually:

    we can do it using a recursive function:
    find the median of both the arrays:
    suppose m1 is the median of the first array
    m2 is the median of the second array

    then if m1 > m2 then again call that recursive function in the right part of the second array and in the left part of the first array.

    continue this step until the number of elements in the array is not two

    when the number of elements in both the arrays are two then do the following:

    suppose in the first array the elements are :

    f1 f2

    and in the second the elements are

    s1 s2

    then if

    f1 < s2
    return (f2+s1)/2

    else
    return (f1+s2)/2

    ReplyDelete
  15. #include
    #include
    #include
    main(){
    char s[100] = "aabcdeefgghijjkllllmnooo";
    int l = strlen(s);
    int i;
    int count[226] = {0};
    for(i=0;i1){
    count[s[i]] = -1;
    i++;
    }
    else if(count[s[i]]==-1){
    int j;
    for(j=i+1;j<l;j++){
    s[j-1] = s[j];
    }
    l--;
    }
    else
    i++;
    }
    s[l] = '\0';
    printf("%s\n",s);
    system("pause");
    }

    ReplyDelete
  16. visit geeks for geeks.org

    ReplyDelete
  17. abe yaad kaise nahi rehta be gadhe aadhe question post kerta hai........... bhak

    ReplyDelete
  18. sorry be faaltu me maarli....galat samjha tha tujhe tu bahut achha insaan haibe....

    ReplyDelete
  19. IN 2nd question it is given no extra data structure should be used (IN place).so can we use extra 256 size array as hash table

    ReplyDelete
  20. // code for question 1 : median.c

    // Prem Raj... IITJ

    #include
    #include

    void median(int* p1,int* p2,int* p3,int* p4);

    int a[5] = {1,2,3,5,6};
    int b[5] = {6,7,8,9,10};

    int main()
    {


    int i=0,j=4,k=0,l=4;

    median(&i,&j,&k,&l);

    printf("Median is %d and %d\n",a[i],b[k]);

    return 0;

    }

    void median(int* i,int* j,int* k,int* l){

    int n1,n2,x;

    if(*i > *j || *k > *l)
    {
    printf("Invalid array\n");
    exit(0);
    }

    if(*i == *j)
    {
    return;
    }

    if(*i == *j-1)
    {
    if(a[*i]>b[*k])
    {
    if(a[*j]b[*l])
    a[*j] = b[*l];
    *i = *j;
    *l = *k;
    }
    }

    n1 = (*i+*j)/2;
    n2 = (*k+*l)/2;
    x = (*j-*i+1)%2;

    if(a[n1] > b[n2])
    {

    if(x==0)
    {*j = n1+1;
    *k = n2;}
    else
    {*j = n1;
    *k=n2;}
    }

    else
    {

    if(x==0)
    {*l=n2+1;
    *i=n1;}
    else
    {*l=n2;
    *i=n1;}
    }

    median(i,j,k,l);
    }

    ReplyDelete