C语言 面试问题:包含两个整数的最长前缀

j0pj023g  于 2023-06-21  发布在  其他
关注(0)|答案(7)|浏览(118)

我试图在技术面试的在线评估中解决以下问题,但失败了。我一直在思考这个问题有一段时间了,似乎找不到一个令我满意的答案:
您正在查找数组A的最长前导片段(前缀),其中X和Y的出现次数相等,其中X和Y是整数。
例如,在X=7且Y=42的情况下,其中A=[6,42,11,7,1,42]的最长前缀将是4,因为A[0]-A[4]包含相同数目的X和Y。
另一示例,X=6并且Y=13。A=[13,13,1,6]。函数应该返回-1,因为没有前缀。
X=100,Y=63,A=[100,63,1,6,2,13]应该返回5。
我尝试用C语言回答:

int solution(int X, int Y, int A[], int N){
  int result=-1;
  int nX=0; //number of occurrences of X
  int nY=0; //number of occurrences of Y
  int i;
  for(i=0;i<N;i++){//loop through the input array
    if(A[i]==X)//occurrence of X
      nX += 1;

    /*
    EDGE CASE BELOW: this should have been an if 
    statement, because X and Y could be the same 
    number.  I know I missed this in the assessment, 
    but believe there is another issue, because I 
    failed almost all the test cases generated by the 
    assessment. 
    */
    else if(A[i]==Y)//occurrence of Y 
      nY += 1;
    if((nX!=0)&& (nX==nY))//same number of X and Y 
    //and there is at least one occurence of each
      result=i;//longest prefix is the index
    }
    return result;
}

不幸的是,我自己无法生成失败的测试用例,并且失败的测试用例隐藏在评估中。因此,我不能提供太多有用的信息。
我知道,每次我失败,我的程序返回一个-1而不是正确的答案。
如果你们中的任何一个人能通过思考看到一些错误,我很想看看我错过了什么。谢谢!

x7yiwoj4

x7yiwoj41#

如果您已经准确地描述了需求,那么它们不会指定 XY 出现的相等 * 正 * 次数。零有效。
所以这个:

if((nX!=0)&& (nX==nY))//same number of X and Y 
    //and there is at least one occurence of each
      result=i;//longest prefix is the index
    }

应该是这样的:

if(nX==nY)//same number of X and Y 
      result=i;//longest prefix is the index
    }

不检查nX!=0。因此,如果 X 没有出现在数组中和/或 Y 没有出现在数组中,您的代码将不必要地返回-1。
此外,这些要求似乎并不能保证 XY 是不同的;如果不是,那么代码返回-1,但是根据需求的字面阅读,答案应该是 N-1。

6uxekuva

6uxekuva2#

在看到你的要求和答案之后,还有一个需要对你的代码进行修改的地方@约书亚。
来自@ruakh的答案也是正确的,但需要再做一个更改来处理其他测试用例。
你必须将“else if”条件替换为“if”条件,以获得Y的出现,如下面的代码所示:

for(i=0;i<N;i++){
    if(A[i]==X)
      nX += 1;
    if(A[i]==Y)  //occurrence of Y 
      nY += 1;

因为,如果“X”和“Y”具有相同的值,则仅“nX”将被计数,并且“nY”将通过“else if”条件被忽略。要解决这种情况,您必须将“else if”条件替换为“if”条件。
样本:X=42,Y=42,A=[42,63,42,6,2,13]
那么以我的情况,上面的样品处理得很好。
我希望我的回答能解决或增加你的答案的准确性。

monwx1rj

monwx1rj3#

首先,不要在面试中做任何任务。面试不是考试。这是两个平等参与者的对话。忽略所有试图以这种方式操纵你和你的时间的公司。
其次,这个函数声明

int solution(int X, int Y, int A[], int N);

这是一个初学者的宣言。
首先,不要使用大写字母来命名参数。
第二,数组的大小应具有size_t as类型和函数的返回类型。
第三,数组应该是函数的第一个参数,并且应该有限定符const。
第四,在使用变量的最小范围内声明变量。
该函数可以像演示程序中所示的那样声明。如果没有这样的前缀,则函数返回0。如果没有前缀ot到(size_t)-1,可以将返回值更改为数组的大小。

#include <stdio.h>

size_t largest_balanced_seq( const int a[], size_t n, int x, int y )
{
    size_t last_index = 0;

    for ( size_t i = 0, x_count = 0, y_count = 0; i < n; i++ )
    {
        x_count += a[i] == x;
        y_count += a[i] == y;

        if ( x_count != 0 && x_count == y_count )
        {
            last_index = i;
        }
    }

    return last_index;
}

int main(void) 
{
    int a[] = { 6, 42, 11, 7, 1, 42 };

    printf( "%zu\n", largest_balanced_seq( a, sizeof( a ) / sizeof( *a ), 7, 42 ) );

    int b[] = { 100, 63, 1, 6, 2, 13 };

    printf( "%zu\n", largest_balanced_seq( b, sizeof( b ) / sizeof( *b ), 100, 63 ) );

    return 0;
}

程序输出为

4
5

考虑到当函数返回子序列的长度时,也就是当它指定一个像[0, N)这样的范围时,效果要好得多。例如,这种方法在整个C++中使用。所以给你这个任务的人不是很高的资格。:)

sqougxex

sqougxex4#

int solution(int X, int Y, int A[], int N){
  int result=-1;
  int nX=0; //number of occurrences of X
  int nY=0; //number of occurrences of Y
  int i;
  for(i=0;i<N;i++){//loop through the input array
    if(A[i]==X)//occurrence of X
      nX += 1;

    /*
    EDGE CASE BELOW: this should have been an if 
    statement, because X and Y could be the same 
    number.  I know I missed this in the assessment, 
    but believe there is another issue, because I 
    failed almost all the test cases generated by the 
    assessment. 
    */
    else if(A[i]==Y)//occurrence of Y 
      nY += 1;
    if((nX!=0)&& (nX==nY))//same number of X and Y 
    //and there is at least one occurence of each
      result=i;//longest prefix is the index
    if (X==Y)
      result =i;
    }---this two lines of code is needed for the code correction
    
    return result;
}
cclgggtu

cclgggtu5#

def solution(X, Y, A):

    N = len(A)
    result = -1
    nX = 0
    nY = 0

    for i in range(N):
        if A[i] == X:
            nX += 1
        if A[i] == Y:
            nY += 1
        if nX == nY:
            result = i
            if (X == Y and nX != 0):
                break

    return result

print( solution(7, 42, [6, 42, 11, 7, 1, 42]) )
print( solution(6, 13, [13, 13, 1, 6]) )
print( solution(100, 63, [100, 63, 1, 6, 2, 13]) )
print( solution(1, 1, [1]) )
print( solution(1, 1, [1, 1, 1]) )
print( solution(1, 1, [1, 2, 1]) )
print( solution(1, 1, [2, 2, 1]) )
print( solution(1, 1, [2, 1, 2]) )
bq8i3lrv

bq8i3lrv6#

def solution(X, Y, A):

    N = len(A)
    result = -1
    nX = 0
    nY = 0

    for i in range(N):
        if X==Y:
            if A[i]==X:
                nX += 1
            if nX%2==0:
                result=i
        else:
            if A[i] == X:
                nX += 1
            elif A[i] == Y:
                nY += 1
            if nX == nY:
                result = i
    return result

print( solution(7, 42, [6, 42, 11, 7, 1, 42]))

print( solution(6, 13, [13, 13, 1, 6]) )

print( solution(100, 63, [100, 63, 1, 6, 2, 13]) )

print( solution(1, 1, [1]) )

print( solution(1, 1, [1, 1, 1]) )

输出:

4
-1
5
-1
1
q1qsirdb

q1qsirdb7#

int solution(int X, int Y, int[] A) {
    int N = A.length;
    int result = -1;
    int nX = 0;
    int nY = 0;

    if (X != Y) {
        for (int i = 0; i < N; i++) {
            if (A[i] == X)
                nX += 1;
            else if (A[i] == Y)
                nY += 1;
            if (nX == nY)
                result = i;
        }
    } else {
        for (int i = 0; i < N; i++) {
            if (A[i] == X){
                nX += 1;
                if(nX % 2 == 1 && nX > 1)
                    result = i - 1;
            }
        }
        if (nX % 2 == 0)
            result = N - 1;
    }

    return result;
}

相关问题