Goldman Sachs CoderPad Interview || US position
- Location
- US
- Posted
- 15 Jul 2025
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)
- 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)