Leetcode: Strobogrammatic Number

 This question is asked at Facebook, Google, Cisco, and Microsoft. Given a string num which represents an integer, return true if num is a strobogrammatic number. A strobogrammatic number is number that looks the same when rotated 180 degrees. 

Example 1: true for "69"

Example 2: true for "88"

Example 3: false for "962" 

Example 4: true for "1"

First we want to rotate the integer by 180 degrees, so we write some numbers down some paper and rotate the paper. 

Before

After

0 - rotatable [0]. 1- rotatable(maybe). 2- rotatable (maybe) [2]. 3 - not rotatable. 4 - not rotatable. 5 - rotatable [5] 6 - rotatable [9]. 7 - not rotatable. 8 - rotatable (maybe) [8]. 9 - rotatable [6]

For interview, you should state your assumptions and ask clarifying questions to anything you're unsure about. Here, we'll assume 3 4 and 7 are not rotatable. 

The first thing that we can do is reverse the string and see if the rotated copies are equal to each other. 

We have subsequently, the following pseudocode: 

rotated_string = empty string

for each character in reverse string:

    if character is 0 1 or 8 append to rotated string

    else if character is 6 append 9

    else if character is 0 append 6

    else if character is invalid return false

    return true if the rotated_string is same as string else return false.  

We can also see if rotated digits contains a key and append the corresponding value to the HashMap. 

We can also measure using 2 pointers and seeing if the corresponding rotated value. 

define function isStrobogrammatic(num): 

   rotations = a new hash map 

   add to rotations: '0' -> '0', '1' -> '1', '8' -> '8', '6' -> '9' and '9' -> '6'

   left = 0

   right = num.length - 1

   while left <= right:

            if left not in rotations return false

            get expected rotation, compare right to expected rotation if not equal return false

            left ++ 

            right --

    return true 

Here's the Java code: 

class Solution {

    public boolean isStrobogrammatic(String num) {

        //map each character to its inverse

        Map<Character, Character> rotatedDigits = new HashMap<>(Map.of('0', '0', '1', '1', '6', '9', '8', '8' '9', '6' ));

        //2 iterations from left to right, all in one loop 

        for(int left = 0; right = num.length() - 1; left <= right; left++, right--) {

            //get the characters on the left and on the right

            char leftChar = num.charAt(left); 

            char rightChar = num.charAt(right); 

            //see if rotated digits has the key to see if the key is rotatable and length - n same as n

            if(!rotatedDigits.containsKey(leftChar) || !rotatedDigits.get(leftChar) != rightChar) {

                return false;

            }

        }

return true; 

}

    }

}