查找查找给定索引值的步骤

I am new to SO - I have a question which I was asked in interview and which for life of me I am not able to wrap my head around. I can solve it with while/for loop but interviewer specifically asked not to use them I even discussed with few friends of mine but unable to solve it. If someone can provide pointers.

我是第一次这么做——我有一个问题，我在面试中被问到过，而我的生活中，我却无法完全理解。我可以用while/for循环来解决它，但面试官特别要求不要使用它们，我甚至与我的几个朋友讨论过，但却无法解决。如果有人能提供指针。

Question is: for given array

问题是:对于给定的数组

s[] = {5,1,0,4,2,3}

1. length of array is not given.
2. 不给出数组的长度。
3. If length of array is 5 content is guaranteed to be between 0 to 5.
4. 如果数组的长度是5，那么内容保证在0到5之间。
5. There is no repetition of numbers.
6. 没有重复的数字。

Sample example length(s, 3) - a[3] = 4 , a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3 returns length of 4 .

样本长度(s, 3) - a[3] = 4, a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3，返回长度为4。

For given condition write subroutine int length (s, 3) - to find the number of steps it takes to find given value -

对于给定条件，编写子例程int长度(s, 3)，以找到找到给定值所需的步骤数。

Additional conditions

附加条件

1. You cannot use any loop statements like for, while and so on -
2. 您不能使用任何循环语句，如for, while等。
3. You cannot use any global or static variables.
4. 不能使用任何全局变量或静态变量。
5. You cannot call other routines inside this routine
6. 不能调用这个例程中的其他例程
7. You cannot modify given function parameters - it stays length (s, n) only
8. 不能修改给定的函数参数——它只保持长度(s, n)
9. You cannot change original array too
10. 你也不能改变原来的数组

4 个解决方案

#1

Alternative solution that does not modify the array at all, but hides an extra parameter inside top 16 bits of x:

完全不修改数组的替代解决方案，而是在x的前16位中隐藏一个额外的参数:

int length(int *s, int x){
    int start = (x >> 16) - 1;
    if (start < 0)
        start = x;
    if (s[x] == start)
       return 0;
    return 1 + length(s, ((start + 1) << 16) + s[x]);   
}

This will fail if there are too many elements in the array, but I suspect any other recursive solution is likely to hit a stack overflow by that point in any case.

如果数组中有太多的元素，这将失败，但是我怀疑任何其他递归解决方案在任何情况下都有可能导致堆栈溢出。

#2

I think I found the answer eventually no I didnt crack it but found it online :) .. Here is the solution

我想我最终找到了答案，没有，我没有破解它，但是在网上找到了。这是解决方案

int length(int * s, int x){
    if(s[x] < 0){
        return -1;
    }
    else{
        s[x] = -s[x];
        int len = length(s, -s[x]);
        s[x] = -s[x];
        return len + 1;
    }
}

#3

i don't think it contradicts with any of your conditions. i just didn't use the array as a parameter (that isn't a problem actually, you can modify it yourself)

我认为这与你的任何条件都不矛盾。我只是没有使用数组作为参数(实际上这不是问题，您可以自己修改它)

int s[] = {5,1,0,4,2,3};
bool col[100]; ///to check cycle

int rec(int n)
{
    if(col[n])return 0;
    col[n]=true;
    int sum=0;
    sum = 1+rec(s[n]);
    return sum;
}

#4

The interviewer is probing your understanding of algorithms and programming paradigms, trying to understand your training, background, and depth. The interviewer has a challenging task; identifying capable developers with minimal evidence. Thus the interviewer presents a constructed problem that (they hope) elicits the desired knowledge (does candidate X know how to solve problem Y, or understand concept Z) perhaps because the interviewer believes the desired answer indicates the candidate knows the expected body of knowledge.

面试官正在探索你对算法和编程范例的理解，试图了解你的训练、背景和深度。面试官的任务很有挑战性;用最少的证据来识别有能力的开发人员。因此，面试官提出了一个构建好的问题(他们希望)能引出所需的知识(应试者X是否知道如何解决问题Y，或理解概念Z)，可能是因为面试官认为所需要的答案表明应试者知道预期的知识体系。

Modern languages provide several repetition structures (commands, statements), some which pre-test (check condition before entering statement-block), and some which post-test (check condition after performing statement block at least once). Here are examples,

现代语言提供了几种重复结构(命令、语句)，有些是预测试(在输入语句块之前检查条件)，有些是测试之后(至少执行语句块一次后检查条件)。下面是例子,

Pre-test

检测前

while(condition) statement-block
for(initializer;condition;step) statement-block

Post-test

测试后

do statement-block while(condition)
repeat statement-block until(condition)
do statement-block until(condition)

These can all be written as conditional (choice) structures with branching (goto),

这些都可以写成条件(选择)结构和分支(去)，

Pre-test

检测前

label:
if(condition)
    statement-block;
    goto label;
else
    nil;
endif

Post-test

测试后

label:
statement-block;
if(condition)
    goto label;
endif

You can also use recursion, where you call the same function as long as condition holds (or until condition met, depending upon positive or negative logic),

您还可以使用递归，在这种情况下，您调用相同的函数，只要条件保持不变(或者直到条件满足，取决于正或负逻辑)，

Pre-test

检测前

function recurse(args)
    if(condition)
        statement-block
        recurse(revised args);
    endif
    return
end #function

Post-test

测试后

function recurse(args)
    statement-block
    if(condition)
        recurse(revised args);
    endif
    return;
end

You would learn about recursion in an algorithms, or perhaps a computability course. You would learn about conditional branching in a compiler, high performance computing, or systems class. Your compiler course might examine techniques for detecting 'tail-recursion', and how to rewrite the function call into a loop.

你会学习算法中的递归，或者可能是可计算性的课程。您将了解编译器、高性能计算或系统类中的条件分支。编译器课程可能会研究检测“尾部递归”的技术，以及如何将函数调用重写为循环。

Here is the problem, restated,

问题是，

given array, s[] = {5,1,0,4,2,3}
array length unknown
content between [0 .. length], not repeated, no duplicates
write subroutine which provides the number of steps to find given value

That is,

也就是说,

int length( array s, int member ) --> position

Examine the conditions (constraints) on the problem,

检查问题的条件(约束)，

• Array length unknown - Solution must work for variable range of inputs
• 数组长度未知-解决方案必须适用于可变范围的输入。
• Cannot use loop statements (for, while, etc) - This suggests either the interviewer wants conditional branch or recursion.
• 不能使用循环语句(for, while, etc)——这表明面试官想要条件分支或递归。
• Cannot use global or static variables - Does this suggest interviewer wants a recursive/functional-programming solution? Conditional-branch also provides this.
• 不能使用全局变量或静态变量——这是否表明面试官想要递归/函数式编程解决方案?条件分支也提供这个。
• Cannot call other routines inside this routine - Does interviewer mean functions other than same function, or call any function (what does interviewer mean by 'other').
• 不能调用这个例程中的其他例程——面试官是指除了相同功能之外的功能，还是调用任何功能(面试官所说的“其他”是什么意思)。
• Cannot modify function parameters, stays length(s,n) - Declaring local (stack) variables is allowed. This could mean pass by value, make a local copy, etc. But not destructive modifications.
• 不能修改函数参数，保持长度(s,n)——允许声明局部(堆栈)变量。这可能意味着通过值传递、生成本地副本等，但不是破坏性的修改。
• Cannot change original array - Definitely no destructive modifications. Possible 'hint' (ok to make local copy?), or further indication that you should use conditional-branch?
• 无法更改原始数组——绝对没有破坏性修改。可能的“提示”(可以进行本地复制吗?)，或者进一步指示您应该使用条件分支?

Here are two solutions, and a test driver (note, I have named them lengthi, iterative, and lengthr, recursive).

这里有两个解决方案和一个测试驱动程序(注意，我将它们命名为lengthi、迭代和lengthr、recursive.com)。

#include <stdio.h>

/* conditional branch */
int lengthi( int s[], int member )
{
    int position=0;
    AGAIN:
    if( s[position] == member ) return(position);
    ++position;
    goto AGAIN;
    return(-1);
}

/* recursive */
int lengthr( int s[], int member )
{
    if( s[0] == member ) return(0);
    return( 1+length(s+1,member) );
}

int
main(int argc,char* argv[])
{
    int s1[] = {0,1,2,3,4,5,6,7,8,9};
    int s2[] = {1,2,3,4,9,8,7,6,0,5};
    int s3[] = {2,4,6,8,0,1,3,5,7,9};

    printf("%d at %d\n",3,lengthr(s1,3));
    printf("%d at %d\n",3,lengthr(s2,3));
    printf("%d at %d\n",3,lengthr(s3,3));
    printf("%d at %d\n",3,lengthi(s1,3));
    printf("%d at %d\n",3,lengthi(s2,3));
    printf("%d at %d\n",3,lengthi(s3,3));
}

Since we are supposed to find the number of steps (iterations, function calls), that is asking for the ordinal position in the list, not the C index (zero based) position.

因为我们应该找到步骤的数量(迭代，函数调用)，这是要求列表中的序号位置，而不是C索引(基于零的)位置。

This is an interview question, and not a programming problem (per se), so probably better suited for the Programmers.stackexchange site. I might give the interviewer an entertaining answer, or their desired answer.

这是一个面试问题，而不是编程问题(本质上)，因此可能更适合程序员。课件网站。我可能会给面试官一个有趣的回答，或者他们想要的答案。