All school recruit pen test

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

All school recruit pen test

                                             ---9 month 22 days, all school recruit pen test

1,Given an ordered array a, length len, and a number of X, determine the A array. The existence of the number two, and their X, bool judge (int *a, int len, int x), return true, did not return false

2,Given the number of array n a, more than half the number for a fixed value, without order, do not open the extra array of circumstances, the most efficient algorithm to find the numbers: int find(int *a, int n)

 


Note: (reprint please contact blogger, personal opinion, is for reference only!)

1,Given an ordered array a, length len, and a number of X, determine the A array. The existence of the number two, and their X, bool judge (int *a, int len, int x), return true, did not return false

Solution:   pay attention to carefully study the conditions, such as key words, ordered arrays of a, which is an ordered array, the one ten!

Method of 1: traversal, the time complexity is O (N2), obviously, this method does not have any practical significance, but also the title says that an orderly array, the traversal method is the worst choice you can't think of any other method.!

Thought of 2: according to the characteristics of the ordered array, either increasing or decreasing, this time we do not imagined, took out some paper and a pen, give an example to analysis is the best approach,


  With the idea of the algorithm can be clearly demonstrated, this simple description: apply a with the original array a[N] the same as the length of the memory space with the given values of arr[N], X minus the original elements in the array, the memory space corresponds to arr[N] into the application, set two pointer in P and Q, the first element the last element and arr[N] respectively refers to the original array a[N], the pointer moves to meet the conditions:

The pointer must satisfy the condition: the P and Q pointer not cross-border, cross-border jump out of it

  If the pointer to the value and I is not equal to J (add conditions: I does not equal J, avoid 8 = 4 + 4 case), true is returned,

  If the array is the ascending , larger pointer value to each mobile,

  If the array is the descending , smaller pointer value to each mobile,

The mobile end, out of moving the pointer loop, that does not exist, return false

  In the (  Tyler_cao, bubble Teng ) have more concise comments, ideas are basically the same, reference!

code:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int Judge(int *a, int len, int x)
{
    int Ascending = 0;//1 indicates ascending or descending,
    Ascending = a[1] > a[0] ? 1 : 0;
    int *CopyA = (int *)malloc(sizeof(int) * len);
    memset(CopyA, 0, sizeof(int) * len);
    //Construct another array
    int icount = 0;
    for(icount = 0; icount <len; icount++)
    {
        CopyA[icount] = x - a[icount];
    }
    //Comparison of the two pointer value, this index instead of pointers
    int i = len - 1, j = 0;
    while(i >= 0 && j < len)
    {
        if(a[i] > CopyA[j])
        {
            switch(Ascending)
            {
                case 0: j++; break;//Descending
                case 1: i--; break;//Ascending
                default:break;
            }
        }
        else if(a[i] == CopyA[j] && i != j)
        {
            return 1;
        }
        else
        {
            switch(Ascending)
            {
                case 0: i--; break;//Descending
                case 1: j++; break;//Ascending
                default:break;
            }
        }
    }
    return 0;
}
int main()
{
    int a[] = {1, 2, 3, 4};
    int len = 4;
    int x = 8;
    switch(Judge(a, len, x))
    {
        case 0: printf("%d isn't exist!", x);break;
        case 1: printf("%d is exist!", x);break;
        default : break;
    }
    return 0;
}

 2,Given the number of array n a, more than half the number for a fixed value, without order, do not open the extra array of circumstances, the most efficient algorithm to find the numbers: int find(int *a, int n)

Solution: I found pretty much, requirement: don't sort, not to offer additional array. this question but I do not think very effective method, key reference programming of the United States 2.3 for post “ water king”.

The idea of the algorithm is: since the array in a fixed value appears more than half, then every deleted from an array of two different digital , until the elements in the array are the same, the last remaining the same array element must be the fixed value, here the use of a counter cnt, count a number of VeryNum array, the counter addition and subtraction to find the fixed value.

Flow chart of the algorithm:


code:

#include <stdio.h>
#include <stdlib.h>
int find(int *a, int n)
{
    int VeryNum = 0;
    int cnt = 0;
    int i = 0;
    for(i = 0; i <n; i++)
    {
        if(cnt == 0)
        {
            VeryNum = a[i];
            cnt = 1;
        }
        else
        {
            if(a[i] == VeryNum)
            {
                cnt++;
            }
            else
            {
                cnt--;
            }
        }
    }
    return VeryNum;
}
int main(void)
{
    int a[] = {15, 15, 5, 15, 5, 15, 1};
    int n = 7;
    printf("%d\n", find(a, n));
    return 0;
}



Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Wright at November 19, 2013 - 12:20 PM