INTERVIEW QUESTIONS Archives - Page 3 of 3

Classic interview question :

Print all possible words from phone number digits.

This question is asked by companies like microsoft, google, facebook. Lets see example input/output to understand this problem.

This is the cellphone keypad

Where pressing ‘2’ you can type letters -> ‘a’,’b’,’c’

using 3 -> ‘d’,’e’,’f’ etc.

So given the number 23 what are the possible words ??

ad,ae,af

bd,be,bf

ce,ce,cf

To make it clear in your head you can imagine, what happens when you press 2,3 keys while typing a text, if you press 2 first and then 3 what different words can you type ? (Answer is list of words written above) since you pressed two keys all the words will be of length 2.

Lets write a function that given the key as input returns list of characters it represents, so for instance if key is ‘2’ function returns a char[] {‘a’,’b’,’c’}.

 private char[] GetCharacters(char x)
        {
            //You should perform validation for x here.
            char[] arr;
            switch (x)
            {
                case '0': arr = new char[1] { '0' };
                    return arr;
                case '1': arr = new char[1] { '1' };
                    return arr;
                case '2': arr = new char[3] { 'a', 'b', 'c' };
                    return arr;
                case '3': arr = new char[3] { 'd', 'e', 'f' };
                    return arr;
                case '4': arr = new char[3] { 'g', 'h', 'i' };
                    return arr;
                case '5': arr = new char[3] { 'j', 'k', 'l' };
                    return arr;
                case '6': arr = new char[3] { 'm', 'n', 'o' };
                    return arr;
                case '7': arr = new char[4] { 'p', 'q', 'r', 's' };
                    return arr;
                case '8': arr = new char[3] { 't', 'u', 'v' };
                    return arr;
                case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };
                    return arr;
                default: return null; 
            }
        }

private char[] GetCharacters(char x)

{

//You should perform validation for x here.

char[] arr;

switch (x)

{

case '0': arr = new char[1] { '0' };

return arr;

case '1': arr = new char[1] { '1' };

return arr;

case '2': arr = new char[3] { 'a', 'b', 'c' };

return arr;

case '3': arr = new char[3] { 'd', 'e', 'f' };

return arr;

case '4': arr = new char[3] { 'g', 'h', 'i' };

return arr;

case '5': arr = new char[3] { 'j', 'k', 'l' };

return arr;

case '6': arr = new char[3] { 'm', 'n', 'o' };

return arr;

case '7': arr = new char[4] { 'p', 'q', 'r', 's' };

return arr;

case '8': arr = new char[3] { 't', 'u', 'v' };

return arr;

case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };

return arr;

default: return null;

}

Now lets write a recursive function that will use the above function to print all possible words.

 private List<string> strs = new List<string>();
        private int depth = 0;
        char[] numbersArray;
        private void PrintLetters(string numbers)
        {

            this.numbersArray = numbers.ToCharArray();
            this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty);
        }

        private void PrintAllCombinations(char[] letters, string output)
        {
            depth++;
            for (int i = 0; i < letters.Length; i++)
            {

                if (this.depth != 3)
                {
                    output += letters[i];
                    this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output);
                }
                else
                {
                    this.strs.Add(output + letters[i]);
                }
            }
        }

private List<string> strs = new List<string>();

private int depth = 0;

char[] numbersArray;

private void PrintLetters(string numbers)

{

this.numbersArray = numbers.ToCharArray();

this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty);

}

private void PrintAllCombinations(char[] letters, string output)

{

depth++;

for (int i = 0; i < letters.Length; i++)

{

if (this.depth != 3)

{

output += letters[i];

this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output);

}

else

{

this.strs.Add(output + letters[i]);

}

I am using a variable depth, to stop the recursion. And using Console.Writeline() to print the strings.

Interesting application of this problem can be, to convert given phone number to a readable word.

for example : 27753 -> APPLE.

Leave a comment if you like the post. 🙂

This is an interesting problem, and a good interview question.

Count the number of comments in Code file

Lets define the comments :

1) Single line comments start with //

2) Multi line comments start with /* and end with */

What are the different possible comments in the code ?

// at the start of the line,

some code here and then // some code

“C://somepath” this is not a comment !! (Our code should be able to ignore this)

‘//’ Even this is not a comment we should ignore (//) here.

/* some line */

/* /**/*/

These are some of the possible combinations that form comments in source code.

Now we can solve this using traditional approach of checking first character and second character and deciding based on that, but i dont like it,

it will involve lot of if’s and hard to keep track of all the conditions. Also the code will not be readable.

How about creating a state machine like the following :

So we start with initial state “Normal Content” if we get a / there then we go to state -> Single Line Comment start , here if we get another /

we go to state -> single line comment end. Similarly for the rest conditions.

And here is the code for above state machine :

 public enum ParserState
        {
            NormalContent,

            SingleQuote,

            DoubleQuote,

            MultipleCommentStart,

            MultipleCommentEnd,

            SingleLineCommentEnd,

            SingleLineCommentStart,

            StartObserved
        }

        private async Task<int> CommentCounter(string fileName)
        {

            var file = await KnownFolders.PicturesLibrary.GetFileAsync("codefile.txt");

            IList<string> fileContent = await FileIO.ReadLinesAsync(file);

            ParserState currentState = ParserState.NormalContent;

            int singleLineComments = 0;
            int multiLineComments = 0;

            foreach (string line in fileContent)
            {
                for (int i = 0; i < line.Length; i++)
                {
                    switch (currentState)
                    {
                        case ParserState.NormalContent: switch (line[i])
                            {
                                case '/': currentState = ParserState.SingleLineCommentStart; break;
                                case '\'': currentState = ParserState.SingleQuote; break;
                                case '\"': currentState = ParserState.DoubleQuote; break;
                                default: break;
                            }
                            break;

                        case ParserState.SingleLineCommentStart: switch (line[i])
                            {
                                case '/': currentState = ParserState.SingleLineCommentEnd; break;
                                case '*': currentState = ParserState.MultipleCommentStart; break;
                                default: currentState = ParserState.NormalContent; break;
                            }
                            break;

                        case ParserState.MultipleCommentStart: switch (line[i])
                            {
                                case '*': currentState = ParserState.StartObserved; break;
                                default: break;
                            }
                            break;

                        case ParserState.StartObserved: switch (line[i])
                            {
                                case '/': currentState = ParserState.MultipleCommentEnd; break;
                                case '*': currentState = ParserState.StartObserved; break;
                                default: currentState = ParserState.MultipleCommentStart; break;
                            }
                            break;

                        case ParserState.DoubleQuote: switch (line[i])
                            {
                                case '\"': currentState = ParserState.NormalContent; break;
                                default: break;
                            }
                            break;

                        case ParserState.SingleQuote: switch (line[i])
                            {
                                case '\'': currentState = ParserState.NormalContent; break;
                                default: break;
                            }
                            break;
                    }

                    switch (currentState)
                    {
                        case ParserState.SingleLineCommentEnd: singleLineComments++; break;

                        case ParserState.MultipleCommentEnd: multiLineComments++; break;
                    }

                    if (currentState == ParserState.SingleLineCommentEnd || currentState == ParserState.MultipleCommentEnd)
                    {
                        currentState = ParserState.NormalContent;
                        break;
                    }
                }
            }

            return multiLineComments + singleLineComments;
        }

100

101

public enum ParserState

{

NormalContent,

SingleQuote,

DoubleQuote,

MultipleCommentStart,

MultipleCommentEnd,

SingleLineCommentEnd,

SingleLineCommentStart,

StartObserved

}

private async Task<int> CommentCounter(string fileName)

{

var file = await KnownFolders.PicturesLibrary.GetFileAsync("codefile.txt");

IList<string> fileContent = await FileIO.ReadLinesAsync(file);

ParserState currentState = ParserState.NormalContent;

int singleLineComments = 0;

int multiLineComments = 0;

foreach (string line in fileContent)

{

for (int i = 0; i < line.Length; i++)

{

switch (currentState)

{

case ParserState.NormalContent: switch (line[i])

{

case '/': currentState = ParserState.SingleLineCommentStart; break;

case '\'': currentState = ParserState.SingleQuote; break;

case '\"': currentState = ParserState.DoubleQuote; break;

default: break;

}

break;

case ParserState.SingleLineCommentStart: switch (line[i])

{

case '/': currentState = ParserState.SingleLineCommentEnd; break;

case '*': currentState = ParserState.MultipleCommentStart; break;

default: currentState = ParserState.NormalContent; break;

}

break;

case ParserState.MultipleCommentStart: switch (line[i])

{

case '*': currentState = ParserState.StartObserved; break;

default: break;

}

break;

case ParserState.StartObserved: switch (line[i])

{

case '/': currentState = ParserState.MultipleCommentEnd; break;

case '*': currentState = ParserState.StartObserved; break;

default: currentState = ParserState.MultipleCommentStart; break;

}

break;

case ParserState.DoubleQuote: switch (line[i])

{

case '\"': currentState = ParserState.NormalContent; break;

default: break;

}

break;

case ParserState.SingleQuote: switch (line[i])

{

case '\'': currentState = ParserState.NormalContent; break;

default: break;

}

break;

}

switch (currentState)

{

case ParserState.SingleLineCommentEnd: singleLineComments++; break;

case ParserState.MultipleCommentEnd: multiLineComments++; break;

}

if (currentState == ParserState.SingleLineCommentEnd || currentState == ParserState.MultipleCommentEnd)

{

currentState = ParserState.NormalContent;

break;

}

return multiLineComments + singleLineComments;

}

Leave a comment if you like the post 🙂

INTERVIEW QUESTIONS

Print all possible words from phone number digits

Program to count number of comments in code

Fizz Buzz Problem

Recent Posts

Algotutor