Common pseudocode questions, puzzles and challenges [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 5 years ago.

Improve this question

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:

In开发者_开发百科put: "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"

---

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.

---

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.

---

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).

---

It took me a long time to figure it out, but here's my Excel VBA solution to the sentence reversing problem.

Public Sub SentenceReverse()

Dim InSentence As String 'Input sentence string
Dim OutSentence As String 'Output sentence string
Dim p As Integer 'Word Start
Dim q As Integer 'Word length

p = 1

InSentence = ActiveSheet.Range("A1").Value 'Assign the sentence to a string

For i = 2 To Len(InSentence) + 1 'Loop through all the characters of the input sentence
    If (Mid(InSentence, i, 1) = " " Or i = Len(InSentence) + 1) Then 'This character is a space or this is the the end of the sentence
        q = i - p 'Set the word length to the number of this position minus the position of the start of this word
        OutSentence = Mid(InSentence, p, q) & " " & OutSentence 'Add this word to the start of the output string
        p = i + 1 'Set the start of the next word as the position of this space + 1
    End If
Next i

MsgBox (OutSentence)

End Sub

---

I don't know if this is the most elegant approach, but here's a solution to find the word that occurs most often. Here's how I approached it.

1. Find the number of words by looping through the sentence and increment a word count variable if you find a space or you reach the end of the sentence. Create a word array of this length.
2. Using one variable for the start of each word and another variable for the length of each word, loop through the sentence again and assign the preceding characters to an element of the word array.
3. For each word array element, loop through each element of the word array, and compare it (nested loop). If there's a match, increment the value for that position of a count array that shows how many times each word appears.

4. Loop through the count array and compare the value in each field to the maximum value found so far. This gives the maximum number and therefore the most common word. Output that word.

   Public Sub FindCommonWord()

   Dim Insentence As String Dim WordArray() As String Dim CountArray() As Integer Dim p As Integer 'Word Start Dim q As Integer 'Word length Dim w As Integer 'Word Count Dim tw As String 'This Word Dim R As Integer 'Position of most common word

   p = 1 w = 1

   Insentence = ActiveSheet.Range("A1").Value 'Assign the sentence to a string

   'loop through all characters and count the number of words For h = 2 To Len(Insentence) + 1 'Loop through all the characters of the input sentence If (Mid(Insentence, h, 1) = " " Or h = Len(Insentence) + 1) Then 'This character is a space or this is the the end of the sentence w = w + 1 End If Next h

   w = w - 1

   ReDim WordArray(w) ReDim CountArray(w)

   w = 1 'loop through all characters and assign words to elements of an array For i = 2 To Len(Insentence) + 1 'Loop through all the characters of the input sentence If (Mid(Insentence, i, 1) = " " Or i = Len(Insentence) + 1) Then 'This character is a space or this is the the end of the sentence q = i - p 'Set the word length to the number of this position minus the position of the start of this word WordArray(w) = Mid(Insentence, p, q) p = i + 1 'Position of the next word w = w + 1 'Next word End If Next i w = w - 1 'Last word reached

   'loop through the array to work on each word For j = 1 To w 'loop through the array and count the number of times this word appears For k = 1 To w If UCase(WordArray(k)) = UCase(WordArray(j)) Then CountArray(j) = CountArray(j) + 1 Next k Next j

   R = 1

   'Find the maximum value in the count array For n = 1 To w If CountArray(n) > R Then R = n Next n MsgBox ("The most common word is " & WordArray(R) & " in position " & R & ".")

   End Sub