×

Loading...
Ad by
Ad by

微软面试题求解, 多谢。

1. Suppose you have an integer array a of size n that is ordered but has duplicates. For example a = [ 0, 0, 0, 2, 3, 3, 5, 5, 5, 7, 9, 9] (n = 12). Write a function that removes the duplicates, and then returns the new size. In above example, a becomes [ 0, 2, 3, 5, 7, 9 ] and the function returns 6. Do it in-place, meaning no extra memory space should be allocated to store intermediate or final results.

2. Write a function that will accept an array of integers and the length of the array, find the two largest even integers in the array, multiply them together, and return the result.
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 微软面试题求解, 多谢。
    1. Suppose you have an integer array a of size n that is ordered but has duplicates. For example a = [ 0, 0, 0, 2, 3, 3, 5, 5, 5, 7, 9, 9] (n = 12). Write a function that removes the duplicates, and then returns the new size. In above example, a becomes [ 0, 2, 3, 5, 7, 9 ] and the function returns 6. Do it in-place, meaning no extra memory space should be allocated to store intermediate or final results.

    2. Write a function that will accept an array of integers and the length of the array, find the two largest even integers in the array, multiply them together, and return the result.
    • C语言的大侠都跑哪去了?
    • Your question 1 remove((char*)myints+*(unique( myints, myints+sizeof(myints)/sizeof(int) ))+2);
      • remove((char*)myints+*(unique( myints, myints+sizeof(myints)/sizeof(int) ))+2);
      • 没看懂, 能写成程序吗?
        • by using STL functions, you dont see a interim value in your code. I think this is the purpose of the test. Do you really believe no interim value will be used to swap values?
          • sorry, swap value does not need intermediate variable.
          • 微软都是让用C语言写, 不能用STL
    • 要求用标准C语言写。
    • Q1:
      int UniqueArray(int *arr, int size)
      {
      int i, j = 1;

      for (i = 1; i < size; i++)
      {
      if (arr[j-1] != arr[i])
      {
      arr[j] = arr[i];
      j++;
      }
      }
      return j;
      }
      • what if size==0? and if there is no duplication, all elements are unnecessarily assigned, so arr[j] = arr[i]; is needed only when i!=j
    • 第一道题的答案(程序)见内,供参考。
      本文发表在 rolia.net 枫下论坛#include <stdio.h>

      int print_array(int *input, int number)
      {
      int i;

      printf("number = %d [", number);
      for(i=0; i<number; i++)
      {
      printf("%d ", *input);
      input++;
      }
      printf("]\n");
      }

      int re_order(int *input, int number)
      {
      int i;
      int final_number = 0;
      int available_position = 0;
      int offset = 0;

      if (number <= 1)
      return number;

      final_number = 1;
      available_position++;
      offset++;

      for(i=1; i<number; i++)
      {
      if (*(input+offset) == *(input+available_position-1))
      {
      *(input+offset) = 0;
      offset++;
      }
      else
      {
      final_number++;
      *(input+available_position) = *(input+offset);
      available_position++;
      offset++;
      }

      }

      return final_number;
      }

      int main()
      {
      // int int_array[]={};
      // int int_array[]={0};
      // int int_array[]={0, 0};
      // int int_array[]={0, 0, 2};
      int int_array[]={0, 0, 0, 2, 3, 3, 5, 5, 5, 7, 9, 9};
      int new_number;

      print_array(&int_array[0], sizeof(int_array)/sizeof(int));
      new_number = re_order(&int_array[0], sizeof(int_array)/sizeof(int));
      print_array(&int_array[0], new_number);
      }更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 第13行如果改为printf("]\n ");输出会更清楚些。
      • I prefer input[offset] over *(input+offset) for better readability. If I'd like to increase performance, I'd replace *(input+offset) with *next (of type int*) and ++offset with ++next.
        • good point!
    • 第二道题答案(程序),供参考。
      本文发表在 rolia.net 枫下论坛#include <stdio.h>

      int print_array(int *input, int number)
      {
      int i;

      printf("number = %d [", number);
      for(i=0; i<number; i++)
      {
      printf("%d ", *input);
      input++;
      }
      printf("]\n");
      }

      //return:
      // -1 - empty array;
      // 1 - no even inetegers found in the array;
      // even - the multiplied value;

      int seek_array(int *input, int number)
      {
      int i;
      int largest_even = 9999;
      int the_less_even = 9997;

      if (number <= 0 )
      return -1;

      for(i=0; i<number; i++, input++)
      {
      if (((*input)/2)*2 != *input) continue;

      if (largest_even == 9999 && the_less_even == 9997)
      largest_even = *input;
      else if (the_less_even == 9997)
      {
      if (*input <= largest_even)
      the_less_even = *input;
      else
      {
      the_less_even = largest_even;
      largest_even = *input;
      }
      }
      else
      {
      if (*input < the_less_even)
      ;
      else if (*input == the_less_even)
      ;
      else if (*input > largest_even)
      {
      the_less_even = largest_even;
      largest_even = *input;
      }
      else if (*input == largest_even)
      the_less_even = largest_even;
      else //in case that *input less than the_less_even;
      the_less_even = *input;
      }
      }

      printf("largest_even = %d, the_less_even=%d\n", largest_even, the_less_even);


      if (largest_even == 9999 && the_less_even == 9997)
      return 1;
      else if (the_less_even == 9997)
      return largest_even;
      else
      return largest_even*the_less_even;
      }

      int main()
      {
      // int int_array[]={};
      // int int_array[]={3};
      // int int_array[]={4};
      // int int_array[]={0, 0};
      // int int_array[]={12, 10};
      // int int_array[]={0, 0, 2};
      // int int_array[]={135, 51, 92147};
      // int int_array[]={1, 2, 3, 5, -4, 9, -8};
      int int_array[]={0, 1, 0, 2, 3, 4, 5, 10, 5, 20, -2, 9};
      int return_value=0;

      print_array(&int_array[0], sizeof(int_array)/sizeof(int));
      return_value = seek_array(&int_array[0], sizeof(int_array)/sizeof(int));
      printf("seek_array() returned: %d\n", return_value);
      }更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 2个int的最大偶数,相乘后不是int了吧, 该用long吧
        • good point!!
      • 2 minor concerns: 1. operator % can be used. 2. sequence of conditions can be reordered to ommit no action conditions like if (*input < the_less_even) ;
        • good point!