常见的伪代码问题,难题和挑战

Question

我正在寻找您可能在面试中被问到或被要求代表您的工作或教育的伪代码问题的示例.我不是特别寻找来自任何领域的示例,因此它可能与设计模式,算法,数据结构,缓存策略,与软件工程和开发有关,简单或复杂.

例如,我发现的一些常见的主要与排序和搜索技术有关:

Bubblesort:

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 2 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

插入排序:

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        done := false;
        repeat
            if A[j] > value then
            begin
                A[j + 1] := A[j];
                j := j - 1;
                if j < 0 then
                    done := true;
            end
            else
                done := true;
        until done;
        A[j + 1] := value;
    end;
end;

二进制搜索:

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

我们也许可以建立的伪代码的算法和问题一个体面的列表,如果许多人分享他们的想法和经验.

我正在寻找自己的伪代码表示,作为练习.所以,即使你不能找到一个伪代码示例,但您认为这将是用这种方式来表现一个理想的概念,这将有助于太.

我也有一些与这个问题有关的问题:

• 你之前曾经被邀请写过哪个伪代码？
• 这些问题是否与一个或两个函数的简短算法有关？
• 在编写伪代码时是否应该避免语言特定的结构？由于表示意味着语言不可知,不使用每种语言中不存在的Dispose和foreach等术语更安全吗？

谢谢

---

编辑:

我发现的一些例子,我会继续编辑,因为我发现更多:

---

编写一个函数,它接受一个字符串来反转句子中单词的顺序,而不是反转单词:

输入:"猫坐在垫子上,还有另一只猫!"

输出:"猫!另一个带垫,就坐猫"

---

编写一个函数,该函数接受一个字符串,该字符串将返回该字符串中最常出现的单词,忽略大小写和标点符号.如果多个单词具有相同数量的出现次数,则返回首先出现的单词:

输入:"猫坐在垫子上,还有另一只猫!"

输出:

---

编写一个函数来查找某个字符串中出现次数最多的字符,忽略大小写.如果存在多个具有相同最高出现次数的字符,则返回字符串中首先出现的字符.

输入:"字符"

输出:c

---

编写一个反转字符串的函数

输入:"反向"

输出:"esrever"

Answer 1

我自己从未被要求在面试中编写伪代码（仍然是学生），但我的一个朋友向 Google 申请暑期工作，被要求编写一个可以处理正则表达式子集的正则表达式解析器（ iirc，仅输入字母数字并使用 *、+ 和 {x,y} 表示法）。我正在考虑明年自己向他们申请一份暑期工作，并且对尝试当场写出类似内容的想法感到害怕 XD。

我相信他使用两个相互递归的函数解决了这个问题。不知道怎么办。

哦，顺便说一句，他不仅仅是被要求为此编写伪代码。他被要求当场编写可以编译的实际 C++ 代码。（也在 Google 文档中）。