Common pseudocode questions, puzzles and challenges

Question

Hi,

I am looking for examples of pseudocode problems that you may have been asked in an interview or been asked to represent as part of your job or education. I'm not looking for examples from any domain in particular, so it can be related to design patterns, algorithms, data structures, caching strategies, anything to do with Software Engineering and Development, simple or complex.

For example, some common ones I have found are mainly related to sorting and searching techniques:

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

Insertion sort:

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;

Binary search:

   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
   }

We may be able to build up a decent list of pseudocode algorithms and problems, if many people share their thoughts and experiences.

I'm looking to come up with the pseudocode representation myself, as practice. So even if you can't find a pseudocode example, but you think it would be an ideal concept to represent in this way, that would help too.

I also have a few questions related to the subject too:

• Which pseudocode have you been asked to write in an interview before?
• Do these questions tend to relate to short, simple algorithms that are one or two functions long?
• Should language specific constructs be avoided when writing pseudocode? As the representation is meant to be language agnostic, is it safer to not use terms like Dispose and foreach that don't exist in each language?

Thanks

---

Edit:

A few examples of some more I have found, I'll keep editing as I find more:

---

Write a function that takes a single string to reverse the order of words within a sentence, not reversing the words:

Input: "The cat sat on the mat, with another cat!"

Output: "cat! another with mat, the on sat cat The"

---

Write a function that takes a single string that will return the word that occurs most within that string, ignoring case and punctuation. If more than one word has the same number of occurences return the one that occurred first:

Input: "The cat sat on the mat, with another cat!"

Output: the

---

Write a function to find the character that has the highest number of occurences within a certain string, ignoring case. If there is more than one character with equal highest occurences, return the character that appeared first within the string.

Input: "Character"

Output: c

---

Write a function that reverses a string

Input: "reverse"

Output: "esrever"

Answer 1

I have not myself ever been asked to write pseudo-code in an interview (still a student), but a friend of mine who applied to Google for a summer job was asked to write a regexp parser that could deal with a subset of regexps (iirc, alphanumeric input only and using the *, + and {x,y} notation). I'm considering applying to them next year for a summer job myself and am terrified by the idea of trying to write something like that on the spot XD.

I believe he solved it using two functions that recursed off of one another. Not sure how.

Oh, he wasn't just asked to write pseudo-code for this, btw. He was asked to write actual C++ code, on the spot, that would compile. (In a Google Docs document, as well).

Answer 2

I haven't been asked it yet, but there is the classic FizzBuzz question.

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

as found at http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html

It is meant as a simple screening question, and not to pose any significant difficulty to even very new programmers.

Answer 3

I was asked to write a pseudo-code solution for this during an interview for an internship a few years ago:

Write an algorithm that, given a directory path, can count the total number of files that fall under that directory and all subdirectories.

Being able to solve this demonstrates an understanding of tree traversal.