Print all possible words from phone number digits. This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem. For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi … Read More →
String Decode Problem
Problem: If a=1, b=2, c=3,….z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings. For example: Input: “1123″. You need to general all valid alphabet codes from this string. Output List aabc //a = 1, a = 1, b = 2, c = 3 … Read More →
Word Ladder Problem
Problem: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary For example, Given: start = “hit” end = “cog” dict = ["hot","dot","dog","lot","log"] As one shortest … Read More →
Edit Distance – DP Problem
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Input: str1 = “cat”, str2 = “cut” Output: … Read More →
Decode Ways Leetcode Java
Problem: A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ – 1 ‘B’ – 2 ‘Z’ – 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12″, it could be decoded as “AB” (1 2) or … Read More →
Break String into Dictionary Words
Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string. e.g. input: “programmerit” output: {{pro, gram, merit}, {program, merit}, {programmer, it}} output: Solution: Recursive implementation: The idea is simple, we consider each prefix and … Read More →
Check if Any Anagram of a String is Palindrome or Not
Examples: Input: str = “aaaad” Output: 1 // “aaaad” is a anagram of a palindrome “aadaa” Input: str = “abcd” Output: 0 // “abcd” is not a anagram of any palindrome. A Simple Solution is to take the input string, try every possible rotation of it and return true if a anagram is a palindrome. … Read More →
Replace all spaces in a string with “%20″
Problem: Write a C program that will replace all spaces with ‘%20′ Solution: The algorithm is as follows: 1. Count the number of spaces during the first scan of the string. 2. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as … Read More →
Group all Words in Set of Anagrams of Each Other in Dictionary
Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets. For example – Input: “bat”, “tar”, “xyz” , “tab”, “tar” Output:[["bat", tab"], ["tar", rat"],”xyz” ] Thi sproblem was asked in amazon interview. Steps: 1)Use some sort of a hash … Read More →
Check if One String is a Rotation of Other String
Problem: Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ? If s1 = “crazyforcode” then the following are some of its rotated versions: “forcodecrazy” “codecrazyfor” Solution: Steps: First need to check if s1 and s2 are of the same length. Then check, if s2 is … Read More →
Find Anagrams in array of Strings
Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this … Read More →
Move the Spaces to Front of the String
Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place. string = “move these spaces to beginning” output =” movethesepacestobeginning” Solution: 1) Maintain two indices i and … Read More →
What’s going on ?