Goldman Sachs CoderPad Interview || US position

Location
US
Posted
15 Jul 2025
303 reads

Summary

I experienced a CoderPad interview at Goldman Sachs for a US position, where I was presented with a unique string encoding problem involving a 'repeat from beginning' instruction.

How it went

You are given a sequence of characters, representing a series of steps. You need to find the minimum number of characters required to encode this sequence using a special "repeat from the beginning" instruction, denoted by '*'.

The '' instruction means that the currently encoded prefix should be repeated from its beginning. For example, if you have encoded "AB", then "AB" would expand to "ABAB". If you have encoded "ABC", then "ABC*" would expand to "ABCABC". This repeat instruction can be applied multiple times implicitly (e.g., 'A*' for 'AAA').

Your task is to write a function that takes the un-encoded sequence as input and returns the minimum number of characters required to encode it.

Example:

Consider the sequence "A, B, A, B, C, A, B, A, B, C, D". This can be encoded as "ABCD" which has a length of 6 characters.

We can name the problem as: MINIMUM ENCODING LENGTH

Test Cases:

print(f"'AA': {findMinChars('AA')}") # Expected: 2 (A + A) or (A* implies A repeated multiple times) print(f"'AAA': {findMinChars('AAA')}") # Expected: 2 (A*) print(f"'ABAB': {findMinChars('ABAB')}") # Expected: 3 (AB*) print(f"'ABABA': {findMinChars('ABABA')}") # Expected: 4 (ABA) print(f"'AAAAA': {findMinChars('AAAAA')}") # Expected: 2 (A) print(f"'ABCABCABC': {findMinChars('ABCABCABC')}") # Expected: 4 (ABC*) print(f"'ABABCABABCD': {findMinChars('ABABCABABCD')}") # Expected: 6 (ABCD)

Questions asked (1)

  1. 01

    Minimum Encoding Length with Repeat Instruction

    Data Structures & Algorithms

    You are given a sequence of characters, representing a series of steps. You need to find the minimum number of characters required to encode this sequence using a special "repeat from the beginning" instruction, denoted by '*'.

    The '' instruction means that the currently encoded prefix should be repeated from its beginning. For example, if you have encoded "AB", then "AB" would expand to "ABAB". If you have encoded "ABC", then "ABC*" would expand to "ABCABC". This repeat instruction can be applied multiple times implicitly (e.g., 'A*' for 'AAA').

    Your task is to write a function that takes the un-encoded sequence as input and returns the minimum number of characters required to encode it.

    Example:

    Consider the sequence "A, B, A, B, C, A, B, A, B, C, D". This can be encoded as "ABCD" which has a length of 6 characters.

    We can name the problem as: MINIMUM ENCODING LENGTH

    Test Cases:

    print(f"'AA': {findMinChars('AA')}") # Expected: 2 (A + A) or (A* implies A repeated multiple times) print(f"'AAA': {findMinChars('AAA')}") # Expected: 2 (A*) print(f"'ABAB': {findMinChars('ABAB')}") # Expected: 3 (AB*) print(f"'ABABA': {findMinChars('ABABA')}") # Expected: 4 (ABA) print(f"'AAAAA': {findMinChars('AAAAA')}") # Expected: 2 (A) print(f"'ABCABCABC': {findMinChars('ABCABCABC')}") # Expected: 4 (ABC*) print(f"'ABABCABABCD': {findMinChars('ABABCABABCD')}") # Expected: 6 (ABCD)

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Goldman Sachs recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!