Goldman Sachs CoderPad Interview || US position
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.
Full Experience
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)
Interview Questions (1)
Minimum Encoding Length with Repeat Instruction
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)