You are given an old touch sma

Samsung Interview Question for Software Engineers

3

of 3 votes

5
Answers
You are given an old touch smartphone numbers having dial pad and calculator app.

Aim: The goal is to type a number on dialpad.

But as phone is old, some of the numbers and some operations can't be touched.
For eg. 2,3,5,9 keys are not responding , i.e you cannot use them
But you can always make a number using other numbers and operations in Calculator. There could be multiple ways of making a number

.Calculator have 1-9 and +,-,*,/,= as operations. Once you have made the number in Calculator you can copy the number and use it.

You have to find minimum number to touches required to obtain a number.

#Input:#
There will be multiple Test cases .Each test case will consist of 4 lines
1) First line will consist of N,M,O
N: no of keys working in Dialpad (out of 0,1,2,3,4,5,6,7,8,9)
M:types of operations supported (+,-,*,/)
O: Max no of touches allowed

2) second line of input contains the digits that are working e.g 0,2,3,4,6.
3) Third line contains the valued describing operations, 1(+),2(-),3(*),4(/)

4) fourth line contains the number that we want to make .

#Output:#
Output contains 1 line printing the number of touches required to make the number

#Sample Test Case:#
1 // No of test cases
5 3 5 // N ,M, O
1 2 4 6 0 // digits that are working (total number of digits = N),
1 2 3 // describing operations allowed (1--> '+', 2--> '-', 3--> '*' , 4--> '/' )(total number is equals to M)
5 // number we want to make

Answer 3
How 4? 1+4= , "=" is also counted as a touch

2nd Sample Case
3 // No of Test cases
6 4 5 // N ,M, O
1 2 4 6 9 8 // digits that are working (total number of digits = N),
1 2 3 4 // describing operations allowed (1--> +, 2--> -, 3--> , 4-->/)
91 // number we want to make
6 2 4 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28
5 2 10
1 2 6 7 8
2 3 // -, allowed
981

#Output:#
2 // 91 can be made by directly entering 91 as 1,9 digits are working, so only 2 operations
5// 35-7=, other ways are 1+3*7=
9//62*16-11=

Order for computation will be followed as symbols entered, if + comes, it will be computed first

One more example: lets say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn't work.
If you have to type 18-> 2 operations. (Each touch is considered an operation),br> If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.
- neovivek14 July 23, 2017 in United States | Report Duplicate | Flag | PURGE
Samsung Software Engineer Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: United States

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 1 vote

I got this question today at Samsung's NCR test : I was able to figure out the approach using backtracking but there were so many constraints and i felt emergy lost. My approach was to simple create a 1d array of Numers|operators as input. Then for each set recur after checking constraints .

Before recurring use the lastOperator if present or simply append current digit to current number formed
After recurring reset current number formed

Keep updating click count in base condition

- Anonymous October 28, 2018 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Can you please check if this code works on the given constraint or not?
Thanks!!

#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
	int t;   cin>>t;
	while(t--)
	{
		int n,m,lim;   cin>>n>>m>>lim;
		vector<int> v,o;
		queue<pair<int,int> > q;
		for(int i=0;i<n;++i)
		{
			int x;  cin>>x;
			v.push_back(x);
			q.push(make_pair(x,1));
		}
		for(int i=0;i<m;++i)
		{
			int x;   cin>>x;
			o.push_back(x);
		}
		int y;   cin>>y;
		pair<int,int> re;
		while(!q.empty())
		{
			int x = q.front().first;
			int l = q.front().second;
			
			if(x==y)
			{
				re.first = y;
				re.second = l;
				break;
			}
			q.pop();
			
			if(!vis[x])
			{
			
			for(int i=0;i<n;++i)
			{
				q.push(make_pair(x*10 + v[i],l+1));
			}
			
			for(int i=0;i<m;++i)
			{
				for(int j=0;j<n;++j)
				{
					if(o[i]==1)
					{
						q.push(make_pair(x+v[j],l+3));
					}
					else if(o[i]==2)
					{
						q.push(make_pair(x-v[j],l+3));						
					}
					else if(o[i]==3)
					{
						q.push(make_pair(x*v[j],l+3));						
					}
					else if(o[i]==4)
					{
						q.push(make_pair(x/v[j],l+3));						
					}					
				}
			}
			
			vis[x] = true;			
		    }
		}		
		cout<<re.second<<endl;		
	}
}

- Anonymous November 08, 2018 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Can you please check if this code work on given constraints or not ?
Thanks!!

#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
	int t;   cin>>t;
	while(t--)
	{
		int n,m,lim;   cin>>n>>m>>lim;
		vector<int> v,o;
		queue<pair<int,int> > q;
		for(int i=0;i<n;++i)
		{
			int x;  cin>>x;
			v.push_back(x);
			q.push(make_pair(x,1));
		}
		for(int i=0;i<m;++i)
		{
			int x;   cin>>x;
			o.push_back(x);
		}
		int y;   cin>>y;
		pair<int,int> re;
		while(!q.empty())
		{
			int x = q.front().first;
			int l = q.front().second;
			
			if(x==y)
			{
				re.first = y;
				re.second = l;
				break;
			}
			q.pop();
			
			if(!vis[x])
			{
			
			for(int i=0;i<n;++i)
			{
				q.push(make_pair(x*10 + v[i],l+1));
			}
			
			for(int i=0;i<m;++i)
			{
				for(int j=0;j<n;++j)
				{
					if(o[i]==1)
					{
						q.push(make_pair(x+v[j],l+3));
					}
					else if(o[i]==2)
					{
						q.push(make_pair(x-v[j],l+3));						
					}
					else if(o[i]==3)
					{
						q.push(make_pair(x*v[j],l+3));						
					}
					else if(o[i]==4)
					{
						q.push(make_pair(x/v[j],l+3));						
					}					
				}
			}
			
			vis[x] = true;			
		    }
		}		
		cout<<re.second<<endl;		
	}
}

- Anonymous November 08, 2018 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Nhi chl rha 2nd sample case 2nd test case koi ans nhi arhaa

- Anonymous July 07, 2019 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Can you please provide us with a psuedo code or something like that ?
Thanks

- Tarun August 14, 2019 | Flag

Comment hidden because of low score. Click to expand.

of 1 vote

I feel for the Test Case :
5 2 10
1 2 6 7 8
2 3 // -, allowed
981

Answer should be 17-8=9 then 81 5+2 =7 operation..why the answer is 9?

- sohag December 09, 2023 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Samsung is the chutiyamost company I have ever seen till date. In IOI 3problem given for 5hour and great samsung gives 1ques for 4hour......What do samsung actually want???

- anonymous July 24, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

5 2 10
1 2 6 7 8
2 3 // -, allowed
981

Why 9//62*16-11= when we can do 7+2= & 81

- Anonymous September 20, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

abe chutiye kis calculator ka output tune is tarah se(7+2=&81) 981 dekha hai. it will show 81 only in this case

- Anonymous October 27, 2018 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Only 2,3 - (- , *) are allowed, you cannot do 7+2 , since '+' is not allowed.

- t May 06, 2022 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

{
make a combinations of all numbers possible along with their touch count . for all these numbers using the available operands check if we can reach the answer again using recursive backtracking.
}

- Daljit Singh March 22, 2018 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Can anyone provide a correct approach to solve this question?

- Ashish Musani April 17, 2018 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Second Test Case for problem in wrong..
Correction
6 2 4 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28

Here it should be
6 3 5 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28

Try Solving it now...

If you are struck and need solution mail me on namit.pasrija@gmail.com

- Namit August 21, 2018 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

happ

- Anonymous July 07, 2019 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

Namit is not providing solution dont waste time in requesting solution from him.

- Naman September 06, 2018 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

You're right. He's not sending the solution.

- Naina April 12, 2019 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

can somebody provide me the solution for this

- sonu March 26, 2019 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

I feel for the Test Case :
5 2 10
1 2 6 7 8
2 3 // -, allowed
981

Answer should be 8 (82*12-3=)

- Mahesh Kasana July 26, 2019 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

3 is not allowed only digits available are: 1 2 6 7 8

- anonymous February 09, 2020 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

bkl

- Samsung ka choda June 22, 2023 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

koi btao bhai iska soln

- mai he chutiya hun jo samsung me intern krne aya July 01, 2023 | Flag Reply

Comment hidden because of low score. Click to expand.

-1

of 1 vote

rfvb ae

- Anonymous September 20, 2017 | Flag Reply

CareerCup

Samsung Interview Question for Software Engineers

Books

Videos

Resume Review

Mock Interviews