Home » Interview coding problems/challenges

Number following the pattern

In this article, we are going to see how to generate a sequence following a specific pattern? This problem has been featured in coding round of Amazon.
Submitted by Radib Kar, on February 10, 2019

Problem statement:

Given a pattern containing only I's and D's. 'I' stands for increasing and 'D' for decreasing. Devise an algorithm to print the minimum number following that pattern. Digits are from 1-9 and digits can't repeat.

Example:

    Input:
    IIDDIDD  

    Output:
    12543876

Solution

The pattern & number to be generated

  1. Length of minimum number = string length+1
    Hence, maximum string length possible is 8, since we can construct only with different digits (1-9)
  2. 'I' means the next digit will be 1 greater than the current & 'D' means the next digit will be 1 less than the current digit
    "II" → 123
    "DD" → 321

The problem can be used with help of stack. The concept is to create stack with consecutive number same as depth of a local contiguous sequence of 'D'.

Prerequisite:

  1. Input pattern, string s
  2. Stack st to store the digits
    Function findMinFromPattern(string s)
    1.  Declare a stack st; 
    2.  FOR i=0 : pattern length
            EnQueue (st, i+1); //push i+1 at first, i+1 becuase i is 0-indexed 
            IF (entire pattern is processed || s[i] =='I')
                While(stack is not empty){  
                    Pop and print
                End While
            END IF
        END FOR
    END FUNCTION

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void findMinFromPattern(string s){
	stack<int> st; //stack declared using STL
	for(int i=0;i<=s.length();i++){
		//push i+1 at first, i+1 becuase i is 0-indexed 
		st.push(i+1); 
		//when string length is processed or pattern in I
		if(s.length()==i || s[i]=='I' ){ 
			//pop and print until stack is empty
			while(!st.empty()){ 
				cout<<st.top();
				st.pop();
			}
		}
	}
	cout<<endl;
}

int main(){
	cout<<"enter pattern\n";    
	string s;
	cin>>s;
	
	if(s.length()>8){
		cout<<"Not possible,length>8\n";
	}
	else{
		cout<<"The minimum number generated is:\n";
		findMinFromPattern(s);//function to print
	}
	
	return 0;
}

Output

First run:
enter pattern
IIDDIDD
The minimum number generated is:
12543876

Second run:
enter pattern
IIIIIIIIDDDDIII
Not possible,length>8

Example with explanation:

Pattern string:
IIDDIDD

0 th iteration
i=0
EnQueue(st,i+1)
Stack status:
1
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
1
Output up to now:
1
Stack status;
Empty stack
-------------------------------------------------------------

1st iteration
i=1
EnQueue(st,i+1)
Stack status:
2
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
2
Output up to now:
12
Stack status;
Empty stack
-------------------------------------------------------------

2nd iteration
i=2
EnQueue(st,i+1)
Stack status:
3
S[i]=='D'
Nothing to do
Output up to now:
12
Stack status;
3
-------------------------------------------------------------

3rd iteration
i=3
EnQueue(st,i+1)
Stack status:
3
4(top)
S[i]=='D'
Nothing to do
Output up to now:
12
Stack status;
3
4(top)
-------------------------------------------------------------

4th iteration
i=4
EnQueue(st,i+1)
Stack status:
3
4
5(top)
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
5, then 4,then 3
Output up to now:
12543
Stack status;
Empty stack
-------------------------------------------------------------

5th iteration
i=5
EnQueue(st,i+1)
Stack status:
6
S[i]=='D'
Nothing to do
Output up to now:
12543
Stack status;
6
-------------------------------------------------------------

6th iteration
i=6
EnQueue(st,i+1)
Stack status:
6
7(top)
S[i]=='D'
Nothing to do
Output up to now:
12543
-------------------------------------------------------------

7th iteration
i=7
EnQueue(st,i+1)
Stack status:
6
7
8(top)
Entire string is processed
Pop and print until stack becomes empty
Print:
8, then 7, then 6
Output up to now:
12543876
Exit:
Minimum no is:
12543876





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.