• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Count Possible Decodings of a given Digit Sequence

February 10, 2015 by Dhaval Dave

Find number of ways a string can be decoded into, if A=1, B=2, C=3 … Z=25 and encoding number is 123 ways decoding can be done is
1 2 3 = A B C
1 23  = A X
12 3  = L C

How to find total number of decodings possible.
this is DP problem.
Start thinking in pattern.if
1 2 3 is String/Array input.

– 1 can be decoded in 1 way.
– 2 cab be decoded in 1 way.
– 1 2 (along with previous one < 26) so 2 can be decoded in (old number of way + 1) = 2 ways
– 3 can be decoded in 1 way
– 2 3 ( can be decoded also as < 26) so total = 3 ways.

Total ways = 3

Algo

input 
string A[N] 
NoOfWay[0]=1
NoOfWay[1]=2

for (i=1 to N){
   if (A[i] <= 26) NoOfWay [ i+1 ] = NoOfWay [ i ];
   if ( A[i] + (A[i-1]*10) <= 26 )  NoOfWay [ i+1 ] = NoOfWay [ i+1 ] + NoOfWay [ i – 1 ];
}
return NoOfWay [ N ]

Its very easy to code.
You can try ur self.
PS : We have assumed that number will be in range of 1-9.
You can edit algo/code to ensure numbers like 103 also. (0-9)
You can working code : http://ideone.com/2QA9Cq

 

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Dynamic Programming, Mathematical

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Add Sub Multiply very large number stored as string

Generic Object Oriented Stack with Template

Maximum difference between two elements s.t larger element appears after the smaller number

Stock Buy Sell to Maximize Profit

Printing Longest Common Subsequence

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

K’th Largest Element in BST when modification to BST is not allowed

Handle duplicates in Binary Search Tree

Find Pythagorean Triplets in an array in O(N)

Print Power Set of a Set

Flipkart SDET Interview Experience

Wrong Directions given find minimum moves so that he can reach to the destination

Word Break Problem

SAP Hiring Off-Campus General Aptitude

Search element in a matrix with all rows and columns in sorted order

Maximum occurred Smallest integer in n ranges

Subset Sum Problem Dynamic programming

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Client Server C program

Spanning Tree

Singly linked list

Serialise Deserialise N-ary Tree

Find next greater number with same set of digits

Diagonal Traversal of Binary Tree

Max Sum in circularly situated Values

C++ OOPs Part2

Check Binary Tree is Binary Search Tree or not

Connect n ropes with minimum cost

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Maximum path sum between two leaves

Copyright © 2025 · Genesis Framework · WordPress · Log in