Samsung Interview Question
NonesCountry: India
Interview Type: Written Test
#include <bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int A[1000];
int mini,ans,tot;
int ABS(int x)
{
if(x<0)
x=-1*x;
return x;
}
int MAX(int a,int b)
{
if(a>b)
return a;
return b;
}
int solve(int i,int curr,int n)
{
if(i==n)
{
int x=ABS(tot-2*curr);
if(x<mini)
{
mini=x;
ans=MAX(curr,tot-curr);
}
return 1;
}
if(dp[i][curr]!=-1)
return dp[i][curr];
return dp[i][curr]=solve(i+1,curr+A[i],n)+solve(i+1,curr,n);
}
int main()
{
int n;
cin>>n;
mini=INT_MAX;
ans=tot=0;
for(int i=0;i<n;i++){
cin>>A[i];
tot+=A[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
dp[i][j]=-1;
}
solve(0,0,n);
cout<<ans;
}
Maybe This will help
#include "stdafx.h"
#include "stdio.h"
static int bar_data[50];
static int max_length;
static int num_of_bars;
static int total_length;
int FindSum(int length, char* IsUsed)
{
int i;
printf("\n FindSum: [%d] ", length);
for (i = 0; i < num_of_bars; i++)
{
printf("%d ", IsUsed[i]);
}
printf("\n");
#if 0
for (i = num_of_bars - 1; i >= 0; i--)
{
if ((IsUsed[i] == 0) && ((length - bar_data[i]) == 0))
{
IsUsed[i] = 1;
return 1;
}
}
#endif
for (i = num_of_bars - 1; i >= 0; i--)
{
if ((IsUsed[i] == 0) && ((length - bar_data[i]) >= 0))
{
IsUsed[i] = 1;
length -= bar_data[i];
if (length == 0)
{
return 1;
}
if (FindSum(length, IsUsed) == 0)
{
IsUsed[i] = 0;
}
else
{
return 1;
}
}
}
return 0;
}
int CalculateHeight()
{
int i = 0, j = 0, h1 = 0, h2 = 0;
int max_height = 0;
char IsUsed[51];
for (i = num_of_bars - 1; i > 0; i--)
{
if (bar_data[i] > total_length)
{
j++;
total_length -= bar_data[i];
}
}
max_height = total_length / 2;
num_of_bars -= j;
j = 0;
for (i = max_height; i > 1; i--)
{
memset(IsUsed, '\0', sizeof(IsUsed));
h1 = FindSum(i, IsUsed);
if (h1)
h2 = FindSum(i, IsUsed);
if (h1 & h2)
{
j = i;
break;
}
}
return j;
}
int main()
{
int i;
printf("\n Enter Number of Bars: ");
scanf_s("%d", &num_of_bars);
printf("\n Enter Bar Code Length's: ");
total_length = 0;
for (i = 0; i < num_of_bars; i++)
{
scanf_s("%d", &bar_data[i]);
total_length += bar_data[i];
}
printf("\n Max Height: %d", CalculateHeight());
getchar();
return 0;
}
O(S^2 * N) time, where S is sum of the input pipes' lengths, and N is number of the pipes.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void LargestPipes(vector<int> const &a, vector<int> &p1, vector<int> &p2, vector<int> &p1_out,
vector<int> &p2_out, int16_t &len_out, unordered_set<uint64_t> &memo,
int16_t len1 = 0, int16_t len2 = 0, int idx = 0)
{
if (idx < 0 ||
idx > a.size())
{
return;
}
if (len1 == len2 &&
len1 > len_out)
{
len_out = len1;
p1_out = p1;
p2_out = p2;
}
if (idx == a.size()) {
return;
}
uint64_t memo_key = (static_cast<uint64_t>(len1) << 48) | (static_cast<uint64_t>(len2) << 32) | idx;
if (memo.find(memo_key) != memo.end()) {
return;
}
memo.insert(memo_key);
p1.push_back(a[idx]);
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1 + a[idx], len2, idx + 1);
p1.pop_back();
p2.push_back(a[idx]);
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2 + a[idx], idx + 1);
p2.pop_back();
LargestPipes(a, p1, p2, p1_out, p2_out, len_out, memo, len1, len2, idx + 1);
}
int main()
{
vector<int> p1, p2, p1_out, p2_out;
int16_t len_out;
unordered_set<uint64_t> memo;
LargestPipes({1, 2, 3, 4, 6}, p1, p2, p1_out, p2_out, len_out, memo);
for (int n : p1_out) {
cout << n << ", ";
}
cout << "\n";
for (int n : p2_out) {
cout << n << ", ";
}
cout << "\n";
}
#include <bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int A[1000];
int mini,ans,tot;
int ABS(int x)
{
if(x<0)
x=-1*x;
return x;
}
int MAX(int a,int b)
{
if(a>b)
return a;
return b;
}
int solve(int i,int curr,int n)
{
if(i==n)
{
int x=ABS(tot-2*curr);
if(x<mini)
{
mini=x;
ans=MAX(curr,tot-curr);
}
return 1;
}
if(dp[i][curr]!=-1)
return dp[i][curr];
return dp[i][curr]=solve(i+1,curr+A[i],n)+solve(i+1,curr,n);
}
int main()
{
int n;
cin>>n;
mini=INT_MAX;
ans=tot=0;
for(int i=0;i<n;i++){
cin>>A[i];
tot+=A[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
dp[i][j]=-1;
}
solve(0,0,n);
cout<<ans;
}
Maybe this will help.
Time Complexity:- O(N*S)
- utkarshh14 July 24, 2019