Encrypted Words

Today is Friday. The current temperature is about 40 F which is not bad for this time of the year. Tomorrow is my youngest sister birthday. I believe she is still in China. I will send her a message wishing her a nice day.

I have a few problems solve from a Facebook coding practice questions site. I should post them over the weekend if something else does not come up. My wife and I are planning on getting groceries done at the end of the day so we can remain at home over the weekend. Grocery stores tend to have much more activity on weekends.

This problem is named Encrypted Words but there is no encryption. It is a hashing problem.

You've devised a simple encryption method for alphabetic strings 
that shuffles the characters in such a way that the resulting string 
is hard to quickly read, but is easy to convert back into the original string.

When you encrypt a string S, you start with an initially-empty resulting string R 
and append characters to it as follows:

o Append the middle character of S (if S has even length, then we define the middle character 
  as the left-most of the two central characters)
o Append the encrypted version of the substring of S that's to the left of the middle character (if non-empty)
o Append the encrypted version of the substring of S that's to the right of the middle character (if non-empty)

For example, to encrypt the string "abc", we first take "b", 
and then append the encrypted version of "a" (which is just "a") 
and the encrypted version of "c" (which is just "c") to get "bac".

If we encrypt "abcxcba" we'll get "xbacbca". 
That is, we take "x" and then append the encrypted version "abc" 
and then append the encrypted version of "cba".

Input
S contains only lower-case alphabetic characters
1 <= |S| <= 10,000

Output
Return string R, the encrypted version of S.

The idea is to process an input string named S and build and return the encrypted string in R. The steps are then described.

As with any other problem you encounter, make sure you read the problem and understand the wording. Most problems tend to be obscure to understand. I do not see the value of that since it is a very well established practice to get answered questions before you start coding. That said; there are Agile methodologies that can be used to start with some code with the assumption that it will be required later in the project. In this case, there is not much time you may spend (or waste) coding things that may or may not be required in the solution.

I will attempt to solve the problem using the Java programming language on a Windows 10 computer using the VSCode IDE. The site requests that you solve the problem using the provided IDE. If you are planning on applying to Facebook, you might be better off developing the code in the provided IDE which does not feature support for features that are readily available in most modern and current IDEs.

I will be solving this problem in my machine so I need to write a test scaffolding.

abc
main <<< s ==>abc<==
main <<< r ==>bac<==


abcd
main <<< s ==>abcd<==
main <<< r ==>bacd<==


abcxcba
main <<< s ==>abcxcba<==
main <<< r ==>xbacbca<==


facebook
main <<< s ==>facebook<==
main <<< r ==>eafcobok<==

Shows the input string which we need to encrypt. Our code reads the string and displays it. This was done for us to see that all is well so far.

The next line seems to contain the result string.

The four test cases are provided by Facebook. They all seem to return the expected results.

String findEncryptedWord(String s) {
// Write your code here
}

The signature of the function to be developed makes sense. We have the input string passed as an argument. We need to return the associated encrypted string.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // **** read string ****
        String s = reader.readLine().trim();

        // **** close buffered reader ****
        reader.close();

        // ???? ????
        System.out.println("main <<< s ==>" + s + "<==");

        // **** encrypt string and display result ****
        System.out.println("main <<< r ==>" + findEncryptedWord(s) + "<==");
    }

Our test scaffolding is simple. We open a buffered reader, read in the input string, close the buffered reader, and display the input string. We then call the function that encrypts the word and display the result.

    /**
     * Recursive call.
     */
    static String findEncryptedWord(String s) {

        // **** initialization ****
        String r    = "";
        int mid     = 0;

        // **** [0] compute the position of of middle character in S ****
        mid = s.length() / 2;
        if (s.length() % 2 == 0)
            mid -= 1;

        // **** [1] append the middle character of S ****
        r += s.substring(mid, mid + 1);

        // **** [2] append the encrypted version of the substring of S 
        //      that's to the LEFT of the middle character (if non-empty) ****
        if (mid > 0) {

            // **** generate left sub string ****
            String ls = s.substring(0, mid);
    
            // **** encrypt and append ***
            r += findEncryptedWord(ls);
        }

        // **** [3] append the encrypted version of the substring of S 
        //      that's to the RIGHT of the middle character (if non-empty) ****
        if (mid < s.length() - 1) {

            // **** generate right sub string ****
            String rs = s.substring(mid + 1, s.length());

            // **** encrypt and append ****
            r += findEncryptedWord(rs);;
        }

        // **** return encrypted string ****
        return r;
    }

The problem seems to call for a recursive approach. Note that I have labeled the steps with numbers.

We first initialize a couple variables. One is used to build the encrypted string. The other is used to compute the mid index for the input string.

We then move to calculate the mid index of the input string. If the string contains an odd number of characters, the mid index is obtained by dividing the string length by 2. Note that if the string length is even, we should use the index of the character to the left of the midpoint. Note that in the test cases we have two even and two odd numbered input strings.

Now that we have the mid index, we can start by appending the mid character to the output string.

We now have to generate the left side string which should not be empty. If possible, we encrypt the string and append the returned string to the result.

The last step is to check if we have a non-empty right side string. If so we encrypt and append the returned value to the encrypted string.

When all is set and done, we returned the encrypted string.

The code returned the expected results for all four cases and the two test cases executed after compiling and running the code at the Facebook site. Given this, I might have not developed a bug free solution. When you experiment with HackerRank or LeetCode, your code is tested against dozens of scenarios. If you find a problem, please let me know. I will address it promptly.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 4,811 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

john.canessa@gmail.com

2 thoughts on “Encrypted Words”

    1. Hi Nicky,

      Sorry about that.
      I tend to forget to mention such info most of the time.
      Will make a note to always include it in future posts.

      Thanks;

      John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.