我试图在技术面试的在线评估中解决以下问题,但失败了。我一直在思考这个问题有一段时间了,似乎找不到一个令我满意的答案:
您正在查找数组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而不是正确的答案。
如果你们中的任何一个人能通过思考看到一些错误,我很想看看我错过了什么。谢谢!
7条答案
按热度按时间x7yiwoj41#
如果您已经准确地描述了需求,那么它们不会指定 X 和 Y 出现的相等 * 正 * 次数。零有效。
所以这个:
应该是这样的:
不检查
nX!=0
。因此,如果 X 没有出现在数组中和/或 Y 没有出现在数组中,您的代码将不必要地返回-1。此外,这些要求似乎并不能保证 X 和 Y 是不同的;如果不是,那么代码返回-1,但是根据需求的字面阅读,答案应该是 N-1。
6uxekuva2#
在看到你的要求和答案之后,还有一个需要对你的代码进行修改的地方@约书亚。
来自@ruakh的答案也是正确的,但需要再做一个更改来处理其他测试用例。
你必须将“else if”条件替换为“if”条件,以获得Y的出现,如下面的代码所示:
因为,如果“X”和“Y”具有相同的值,则仅“nX”将被计数,并且“nY”将通过“else if”条件被忽略。要解决这种情况,您必须将“else if”条件替换为“if”条件。
样本:X=42,Y=42,A=[42,63,42,6,2,13]
那么以我的情况,上面的样品处理得很好。
我希望我的回答能解决或增加你的答案的准确性。
monwx1rj3#
首先,不要在面试中做任何任务。面试不是考试。这是两个平等参与者的对话。忽略所有试图以这种方式操纵你和你的时间的公司。
其次,这个函数声明
这是一个初学者的宣言。
首先,不要使用大写字母来命名参数。
第二,数组的大小应具有size_t as类型和函数的返回类型。
第三,数组应该是函数的第一个参数,并且应该有限定符const。
第四,在使用变量的最小范围内声明变量。
该函数可以像演示程序中所示的那样声明。如果没有这样的前缀,则函数返回0。如果没有前缀ot到(size_t)-1,可以将返回值更改为数组的大小。
程序输出为
考虑到当函数返回子序列的长度时,也就是当它指定一个像
[0, N)
这样的范围时,效果要好得多。例如,这种方法在整个C++中使用。所以给你这个任务的人不是很高的资格。:)sqougxex4#
cclgggtu5#
bq8i3lrv6#
输出:
q1qsirdb7#