ranechabria
BAN USER- 0of 0 votes
AnswersUser inputs a series of numbers and terminates the series by a zero. Your program should find the first three maximum values in the series and exclude them from the series and compute the average of the remaining numbers. (excluding zero as well)
- ranechabria in United States
Ex - 3, 7, 12, 2, 25, 8, 9, 13, 10, 0
First three maximum numbers = 25, 13, 12
Average of the rest = (3 + 7 + 2 + 8 + 9 + 10) / 6 = 6.5| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Coding - 2of 2 votes
AnswersUser inputs a sequence of digits. Every digit is a keystroke, that is equivalent to some character out of a sequence of characters. Digit zero and five mean NULL. The table is given below
- ranechabria in United States
0 - NULL
1 - v, t, f, r, q
2 - f, t, k
3 - w, z, b, g
4 - r, s
5 - NULL
6 - f, i, r
7 - p
8 - l, o
9 - p
Generate all possible character sequence for a given sequence of digits.
Ex - If the user input 9801, your program should generate
{plv, plt, plf, plr, plq, pov, pot, pof, por, poq} (not necessarily in this order).
This problem is somewhat similar to the SMS problem. It basically boils down to generating a cartesian product of the character sets corresponding to keys.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Coding Data Structures
Here's my implementation in C.
Walking the string from left to right, you compute the length of the longest substring ending at each character. You then simply pick the substring ending at the character with the biggest substring length. Compiled and tested at interviewing.io
Sample output:
aacdbbeb, k = 2. Output = aacdbbeb
alblabljln, k = 1. Output = ablj
alblabljln, k = 2. Output = alblab
#include <stdio.h>
#include <string.h>
void LongestSubstringWorker (char *string, unsigned int factor,
unsigned int *maxlen,
unsigned int *maxindex,
unsigned int currindex) {
unsigned int count[256];
unsigned int len[strlen(string)];
unsigned int i,j;
for (i = 0; i < 256; i++) {
count[i] = 0;
}
for (i = 0; i < strlen(string); i++) {
len[i] = 1;
}
count[(unsigned char)string[0]] = 1;
for (i = 1; i < strlen(string); i++) {
count[(unsigned char)string[i]]++;
if (count[(unsigned char)string[i]] <= factor) {
len[i] = len[i - 1] + 1;
if (len[i] > *maxlen) {
*maxlen = len[i];
*maxindex = i + currindex;
}
} else {
for (j = 0; j < i; j++) {
if (string[j] == string[i]) {
LongestSubstringWorker (&string[j + 1], factor,
maxlen, maxindex, j + 1 + currindex);
return;
}
}
}
}
}
void LongestSubstring (char *string, unsigned int factor) {
unsigned int maxlen;
unsigned int maxindex;
unsigned int i;
if (string == NULL) {
return;
}
maxlen = 1;
maxindex = 0;
LongestSubstringWorker(string, factor, &maxlen, &maxindex, 0);
for (i = maxindex - (maxlen - 1); i <= maxindex; i++) {
printf("%c", string[i]);
}
printf("\n");
}
int main() {
LongestSubstring("alblabljln", 1);
return 0;
}
Thanks for this. I got an idea to get started with this problem because of this solution. Some improvement suggestions -
1. This code doesn't work for 24 = 12 * 1 * 2. This is because your seed stops looping at value 11. Just change it to seed <= (num * 0.5)
2. Doesn't work for 111 = 111 * 1 * 1 * 1. For this case to be handled, we'll have to expand the loop for seed to loop all the way until num, which is while (seed <= num). Seems inefficient. The other alternative is to somehow check if all digits are ones.
3. We can initially check if num < 10. If yes, then that itself is the seed. Hence we don't need to enter the while loop. This also gives us the flexibility to initialize seed to 10 and start with 10, rather than 1.
Just adding this point to assure those people who aren't sure about max heaps and such - Using a max heap to solve this is surely a good idea. If someone has the implementation details of max heap fresh in memory, then thats great. However, epic questions are such that almost all questions can be worked out without having any knowledge of such data structures. So, not having brushed up your data structures doesn't put you at a disadvantage.
- ranechabria July 15, 2012#include <iostream>
#include <vector>
using namespace std;
float FindMax (vector<int>& arr) {
/* convention is : max_1 < max_2 < max_3 */
int max_1, max_2, max_3, sum;
max_1 = max_2 = max_3 = sum = 0;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] > max_3) {
max_1 = max_2;
max_2 = max_3;
max_3 = arr[i];
}
else if (arr[i] > max_2) {
max_1 = max_2;
max_2 = arr[i];
}
else if (arr[i] > max_1) {
max_1 = arr[i];
}
}
if (max_1 == max_2 || max_2 == max_3) {
throw "No three unique maximum numbers.";
}
for (int i = 0; i < arr.size(); i++) {
if (arr[i] != max_1 && arr[i] != max_2 && arr[i] != max_3) {
sum += arr[i];
}
}
cout << "Max_1: " << max_1 << endl << "Max_2: "
<< max_2 << endl << "Max_3: " << max_3 << endl;
return static_cast<float> (sum) / (arr.size() - 3);
}
int main ( ) {
vector<int> arr;
int num;
cout << "Enter a sequence of numbers. Terminate with zero." << endl;
while (cin >> num && num != 0) {
arr.push_back(num);
}
try {
if (arr.size() < 3) {
throw "Not enough numbers were entered.";
}
cout << "Average excluding the maximum three is " << FindMax (arr) << endl;
}
catch (const char* ex) {
cout << ex << endl;
}
return 0;
}
Not very sure. Probably, the complexity should be the product of the cardinality of each keystroke, since that is the total number of outputs we are generating. To put it another way, that is number of times we're iterating the for loop. So for 9801, the number of times the for loop is iterating is |9| * |8| * |1| = 1 * 2 * 5 = 10.
For a keystroke (n1)(n2)(n3).., the runtime should be |n1| * |n2| * |n3| *.... (where only non empty keys are considered)
I failed to answer this at the time of the test. Below is the solution that I worked out later.
#include <iostream>
#include <string>
using namespace std;
string pattern[] = {"","vtfrq","ftk","wzbg","rs","","fir","p","lo","p"};
void Generate (const string& keystroke, int curr, int size) {
static string str; /* The output string */
if (str.length() == size) {
cout << str << endl;
return;
}
int digit = keystroke[curr] - '0';
/* This if-conditional passes when the key is
* zero or five, which are NULLs. In that case,
* proceed to the next digit. Hence curr + 1.
*/
if (pattern[digit].empty() == true) {
Generate (keystroke, curr + 1, size);
return;
}
/* Loop through the characters for the current keystroke.
* Add that character to the output string and proceed to
* the next key. When you return (i.e., backtrack), pop the
* last character.
*/
for (int i = 0; i < pattern[digit].length(); i++) {
str.push_back (pattern[digit][i]);
Generate (keystroke, curr + 1, size);
str.erase (str.end() - 1); /* Pop now, since you are backtracking */
}
}
int main ( ) {
string keystroke;
/* count is the number of characters in each output string */
int count = 0;
cout << "Enter your keystroke: ";
cin >> keystroke;
for (int i = 0; i < keystroke.length(); i++) {
int digit = keystroke[i] - '0';
if (digit < 0 || digit > 9) {
cout << "Only numericals allowed." << endl;
return 1;
}
if (pattern[digit].empty() == false) count++;
}
/* The function that generates the sequences. Is recursive.
* The second parameter is a count of how many characters
* have been generated so far. The third parameters gives
* the maximum number of characters each sequence contains.
*/
Generate (keystroke, 0, count);
return 0;
}
Works for not just 4 but for any other number of digits.
#include <iostream>
using namespace std;
void Generate (int& val, int curr, int dig, bool four) {
if (curr == dig) {
cout << val << "\t";
return;
}
if (four == true && (curr == dig - 1)) {
if (val % 10 != 4) cout << val * 10 + 4 << "\t";
return;
}
for (int i = 1; i <= 9; i++) {
if (val % 10 != i) {
val = val * 10 + i;
Generate (val, curr + 1, dig, four);
val = val / 10;
}
}
}
int main ( ) {
int dig, val;
cout << "Enter the number of digits: ";
cin >> dig;
for (int i = 1; i <= 9; i++) {
if (i == 4) Generate (i, 1, dig, true);
else Generate (i, 1, dig, false);
}
return 0;
}
Not the most efficient solution but does a pretty decent job.
#include <iostream>
using namespace std;
int days_in_month[] = { 0, 31, 28, 31, 30, 31, 30,
31, 31, 30, 31, 30, 31 };
class Date {
public:
int year;
int month;
int date;
Date () {}
Date (int y, int m, int d) {
year = y;
month = m;
date = d;
}
bool operator < (const Date& obj) {
if (year == obj.year && month == obj.month)
return date < obj.date ? true : false;
if (year == obj.year)
return month < obj.month ? true : false;
return year < obj.year ? true : false;
}
bool operator > (const Date& obj) {
return ! (*this < obj);
}
};
ostream& operator << (ostream& out, Date& obj) {
if (obj.month < 10) out << "0";
out << obj.month;
if (obj.date < 10) out << "0";
out << obj.date;
out << obj.year;
return out;
}
Date ProcessDate (string& start) {
int y, m, d;
y = m = d = 0;
for (int i = 0; i < 2; i++) {
m = m * 10 + (start[i] - '0');
}
if (m > 12) {
throw "Invalid month entered.";
}
for (int i = 2; i < 4; i++) {
d = d * 10 + (start[i] - '0');
}
if (d > days_in_month[m]) {
throw "Invalid date entered.";
}
for (int i = 4; i < 8; i++) {
y = y * 10 + (start[i] - '0');
}
return Date (y, m, d);
}
Date ProcessDate (int num) {
int y = num % 10000;
int m = num / 1000000;
int d = (num / 10000) % 100;
return Date (y, m, d);
}
int Reverse (int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
int main ( ) {
string start, end;
Date Dstart, Dend;
try {
cout << "Enter start date (mmddyyyy): ";
cin >> start;
Dstart = ProcessDate (start);
cout << "Enter end date (mmddyyyy):";
cin >> end;
Dend = ProcessDate (end);
}
catch (const char* ex) {
cout << ex << endl;
return 0;
}
while ((Dstart < Dend) == true) {
int rev_month = Reverse (Dstart.year % 100);
rev_month = Dstart.year % 100 < 10 ? rev_month * 10 : rev_month;
if (rev_month > 12) { /* No palindrome for this year */
Dstart.year++;
continue;
}
int rev_date = Reverse (Dstart.year / 100);
if (rev_date > days_in_month[rev_month]) {
Dstart.year++;
continue;
}
int palindrome_date = Reverse(Dstart.year) * 10000 + Dstart.year;
Date Palin_date = ProcessDate (palindrome_date);
if (Palin_date < Dend) {
cout << Palin_date << endl;
}
Dstart.year++;
}
return 0;
}
Wrong. 10022001 is a palindrome date. 2001 - 1002 is not zero. You have confused a palindrome with "similar sequence".
- ranechabria July 13, 2012This was very helpful. I spent a couple hours breaking my head trying to figure out what the code is doing. And it just blew me. This program is also careful not to print duplicates. Thanks!!
Just an improvement to save some unnecessary swap function calls. Call the swap function only if i is not equal to j. This holds for both the forward swap and the backtrack swap.
if ( i != j ) {
swap ( a + i , a + j ) ;
}
Brilliant! Thanks for the solution. #include <set> is not needed anyway :)
- ranechabria July 10, 2012Using a vector and no sentinels. Using sentinel initializers somehow puts me off.
#include <iostream>
#include <vector>
using namespace std;
int main ( ) {
int val, max_odd, min_even;
vector<int> arr;
cout << "Enter the elements. Terminate with zero." << endl;
while (cin >> val && val != 0)
arr.push_back(val);
max_odd = min_even = 0;
/* Initialize max_odd and min even to the first odd
* and even numbers encountered. I don't prefer
* initializing with random sentinels, feels like bad
* coding to me
*/
for (int i = 0; i < arr.size(); i++) {
if (arr[i] % 2 == 0)
min_even = arr[i];
else
max_odd = arr[i];
if (max_odd != 0 && min_even != 0)
break;
}
/* Loop through the entire vector and find
* the max_odd and min_even.
*/
for (int i = 0; i < arr.size(); i++) {
if (arr[i] % 2 == 0 && arr[i] < min_even)
min_even = arr[i];
else if (arr[i] % 2 != 0 && arr[i] > max_odd)
max_odd = arr[i];
}
cout << "Max odd: " << max_odd << endl
<< "Min even: " << min_even << endl;
return 0;
}
I've compiled and tested this C++ code. The input array doesn't need to be sorted. Also prints the elements that add up to the target sum.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main ( ) {
int val, target;
int index = 0; /* Current array index */
int minpick = 10000; /* Initialize to a high value */
vector<int> arr; /* The vector holding the elements */
/* Temporary vector and the vector holding the minimum set */
vector<int> temp, min;
cout << endl << "Enter the array elements. End with EOF (ctrl + D)" << endl;
while (cin >> val)
arr.push_back(val);
/* Clear the cin buffer */
cin.clear();
cout << endl << "Enter the target sum: ";
cin >> target;
/* Sort the array */
sort(arr.begin(), arr.end());
/* Assumption made that the target itself
* doesn't exist in the array. Would be better
* if that edge-case is added too. */
while (index < arr.size() && arr[index] < target) {
int sum = arr[index]; /* Sum of array elements */
int i = index + 1;
int count = 1; /* Count of elements that add up to target */
temp.push_back(arr[index]);
while (i < arr.size() && sum < target) {
sum = sum + arr[i];
temp.push_back(arr[i]);
count++;
if (sum >= target) {
if (sum == target) {
if (count < minpick) {
/* Least number of elements maintained
* in minpick variable */
minpick = count;
/* Copy the elements adding up to target
* from temp to the min vector */
min.assign (temp.begin(), temp.end());
}
}
/* Pop the last two elements from the temp
* vector and take them off from sum. This
* is needed to move on and try out other
* possible combinations. */
sum = sum - temp.back(); temp.pop_back();
sum = sum - temp.back(); temp.pop_back();
count = count - 2;
if (sum == 0) break;
}
else {
i++;
}
}
temp.clear();
index++;
}
if (minpick == 10000) {
cout << endl << "No combination exists." << endl << endl;
return 0;
}
cout << endl;
for (vector<int>::iterator it = min.begin(); it != min.end(); it++) {
cout << *it << " ";
}
cout << endl << "Minimum picks = " << minpick << endl << endl;
return 0;
}
The first answer by Mejbaol Sajib is wrong. Run it for the input {1, 2, 4, 5, 6} with the target of 15. The answer should be 3 (6 + 5 + 4). Your code returns 4.
- ranechabria July 10, 2012#include <iostream>
using namespace std;
/*
* This function generates all the well ordered
* combinations of passwords for a given length.
* Parameters -
* length : The length of the password to be generated.
* curr_length : The length generated so far.
* pswd - The password represented as an integer. This
* puts a constraint that the password can't begin with
* a zero.
*/
void Generate (int length, int curr_length, int pswd) {
/*
* If the below if clause is true, then we have
* generated the required number of digits. So
* now print that password and return.
*/
if (curr_length == length) {
cout << pswd << "\t";
return;
}
/*
* Get the least significant digit from the password
* generated so far. This helps us check if the next
* loop iteration will yield a well ordered password
* or not.
*/
int unit_digit = pswd % 10;
for (int i = 1; i < 10; i++) {
/*
* Only if 'i' is greater than 'unit_digit',
* then 'i' will become the new least significant
* digit. If not, then the well-ordered condition
* fails and we just continue looping.
*/
if (i > unit_digit) {
/*
* Make 'i' the least significant digit
* in the password now.
*/
pswd = pswd * 10 + i;
/*
* Recursively call the Generate function again
* to generate the next least significant digit.
* This will continue till curr_length will become
* equal to the desired length.
*/
Generate (length, curr_length + 1, pswd);
/*
* You are now done with one possible password.
* Now remove the least significant digit and
* proceed to the next possible combination.
*/
pswd = pswd / 10;
}
}
}
int main ( ) {
// Length of the password
int length;
cout << "Enter the length of the password: ";
cin >> length;
/*
* Password's most significant number ranges from
* 1 to 9. Hence looping 9 times. Remember, this
* looping is only for the most significant number.
* The lesser significant numbers are generated in
* the Generate function.
*/
for (int pswd = 1; pswd < 10; pswd++) {
Generate (length, 1, pswd);
}
cout << endl;
return 0;
}
Take a look at the second comment. The link to cs.duke.edu. Understand that code and thats all you need.
- ranechabria June 01, 2012
- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.
- ranechabria January 15, 2018