The "Single-Row Keyboard" interview question is a straightforward but insightful problem that simulates typing on a custom keyboard layout. You are given a string keyboard of length 26 representing the layout of the keys in a single row, and a string word. You start with your finger at index 0. To type each character of the word, you must move your finger from its current position to the position of the character you want to type. The "Single-Row Keyboard coding problem" asks you to calculate the total time taken, which is the sum of the absolute distances between consecutive characters' indices.
Google frequently uses this question for entry-level or internship roles. It tests basic array indexing, string manipulation, and the ability to map characters to their positions efficiently. While it's an "EASY" problem, it evaluates whether a candidate can optimize the character-to-index lookup using a hash table or a fixed-size array instead of repeatedly searching the keyboard string.
This problem follows the "Hash Table and String interview pattern". To avoid an O(N*26) solution (where N is the length of the word), you should pre-calculate the index of each character in the keyboard. A small array of size 26 or a hash map can store the mapping from character to its index. This allows you to find any character's position in O(1) time. The algorithm then iterates through the word, calculates the distance from the current finger position to the next character's index, updates the total time, and moves the finger position.
Keyboard: pqrstuvwxyzabcdefghijklmno
Word: cat
|13 - 0| = 13. Total time: 13. Current index: 13.|11 - 13| = 2. Total time: 13 + 2 = 15. Current index: 11.|4 - 11| = 7. Total time: 15 + 7 = 22. Current index: 4.
Total time to type "cat" is 22.A common mistake is forgetting to update the "current position" after typing a character. Another error is not using an absolute value for the distance calculation, which can lead to negative time if the finger moves to the left. Finally, failing to pre-index the keyboard can lead to a less efficient solution, which, although it might pass for small inputs, shows a lack of attention to performance.
Always look for ways to trade a little bit of space (like an array of size 26) for significantly better time complexity. Mapping characters to their positions is a very common sub-task in string-related "Single-Row Keyboard interview question" scenarios. Practice this until it becomes second nature.