CodeDavis
SUBSTRING
Determine if a word when split in the middle, results in two substrings that are similar to each other.
Note
- All inputs are case insensitive.
- Output should be either YES or NO.
- Words are similar, if the two halves contain the same characters
ex.
hippie NO
tUTu YES
MadAm YES
ooooOOOO YES
- Approach:
- Split in middle, detect odd and even
- Check matching character using unordered_multiset
bool isMiddleSame(string &str) {
std::transform(str.begin(), str.end(), str.begin(), ::tolower);
int middle = str.length() / 2;
string half1 = str.substr(0, middle);
string half2;
if (str.length() % 2 != 0) {
half2 = str.substr(middle + 1, str.length());
}
else {
half2 = str.substr(middle, str.length());
}
unordered_multiset<char> all;
for (auto i : half1) {
all.insert(i);
}
for (auto i : half2) {
if (all.find(i) == all.end()) {
return false;
}
else {
// iter to avoid removing all elements
auto iter = all.find(i);
all.erase(iter);
}
}
return true;
}
int main()
{
string str;
while (1) {
cin >> str;
bool ok = isMiddleSame(str);
if (ok) cout << "YES";
else cout << "NO";
cout << endl;
}
}
FLASH
The Flash, Barry Allen is put in a crucial situation and he has to travel back in time to save his parents from getting murdered. The Flash travels 15 years back in time (i.e. 2001). He intercepts a text message from the murderer. He then realizes that people had used T9 style text messaging in the early 2000’s. Your mission, should you choose to accept it (Please tell me, you got that Mission Impossible reference), is to help The Flash encipher his “text” messages into T9 text style format and send it to his comrades in the present.
Google "T9 Style Keyboard" to find out what it is. I'm sure most of you have used it when you were younger.
ex.
The Flash -> 8443303335552777744
- Approach:
- Create a map that models t9 predictive text
- Search for character, and return the corresponding number n amount of times.
string t9KeyBoard(string &text) {
// character that maps to its corresponding button, and amount required to press
unordered_map<char, pair<unsigned short, char>> amount = {
{{ 'a' },{ make_pair(1,'2') }}, {{ 'b' },{ make_pair(2,'2') }}, {{ 'c' },{ make_pair(3, '2') }}, {{ 'd' },{ make_pair(1,'3') }}, { { 'e' },{ make_pair(2, '3') }}, { { 'f' },{ make_pair(3, '3') }},
{{ 'g' },{ make_pair(1,'4') }}, {{ 'h' },{ make_pair(2,'4') }}, {{ 'i' },{ make_pair(3, '4') }}, {{ 'j' },{ make_pair(1,'5') }}, { { 'k' },{ make_pair(2, '5') }}, { { 'l' },{ make_pair(3, '5') }},
{{ 'm' },{ make_pair(1,'6') }}, {{ 'n' },{ make_pair(2,'6') }}, {{ 'o' },{ make_pair(3, '6') }}, {{ 'p' },{ make_pair(1,'7') }}, { { 'q' },{ make_pair(2, '7') }}, { { 'r' },{ make_pair(3, '7') }},
{{ 's' },{ make_pair(4,'7') }}, {{ 't' },{ make_pair(1,'8') }}, {{ 'u' },{ make_pair(2, '8') }}, {{ 'v' },{ make_pair(3,'8') }}, { { 'w' },{ make_pair(1, '9') }}, { { 'x' },{ make_pair(2, '9') }},
{{ 'y' },{ make_pair(3,'9') }}, {{ 'z' },{ make_pair(4,'9') }}, {{ ' ' },{ make_pair(1, '0') }}
};
string final_str = "";
for (auto i : text) {
char c = tolower(i);
for (int i = 0; i < amount.find(c)->second.first; i++) {
final_str += amount.find(c)->second.second;
}
}
return final_str;
}
int main() {
string test = "The Flash";
cout << t9KeyBoard(test);
pause();
}
ENIGMA
The Germans dominated the second world war for majority of the war. The reason they were able to do this was because they encrypted their messages using “ENIGMA”, The ultimate machine. Enigma was not only difficult, but was nearly impossible to crack. This problem asks you to vaguely simulate the Enigma encryptor. This Enigma machine will take in the Key for a particular string/word and use alternate up and down shifts to change the original word into something that seems like garbage to the naked eye!
The first line is going to be the word and the second line is going to be the key. The input is case insensitive and the output must be lowercase only.
Note:
- Input is case insensitive.
- Output should be lowercase letters only.
- You are to assume a circular range of letters here. For this problem, you will only be dealing with lowercase alphabets.
- If you shift the letter “b” up by “y”, the resulting answer would be “a”.
- You may assume that the Key is always going to be less than or equal to the length of the given word.
- Once all shifts of the key are done once, start from the beginning again.
ex.
SAMPLE INPUT
cats
dog
SAMPLE OUTPUT
gnao
Explanation
- The first letter of the word, “c” is shifted up by “d” letters. “c” shifted up by “d” is “g”
- The second letter of the word, “a” is shifted down by “o” letters”. “a” shifted down by “o” is “n”
- The third letter of the word, “t” is shifted up by “g” letters. “t” shifted up by “g” is “a”
- The fourth letter of the word, “s” is shifted down by “d” letters. “s” shifted down by “d” is “o”
- Approach:
- Model a bi-directional map of alpha characters and their cooresponding value.
- Then, alternative between shifting up and shifting down by preforming the math between char1->num and char2-> num, either adding or subtracting. We mod this by 26 to ensure it remains within the cycle of alpha characters.
string enigma(string one, string two) {
unordered_map<char, int> alpha = {
{ { 'a' },{ 1 } },{ { 'b' },{ 2 } },{ { 'c' },{ 3 } },{ { 'd' },{ 4 } },{ { 'e' },{ 5 } },{ { 'f' },{ 6 } },
{ { 'g' },{ 7 } },{ { 'h' },{ 8 } },{ { 'i' },{ 9 } },{ { 'j' },{ 10 } },{ { 'k' },{ 11 } },{ { 'l' },{ 12 } },
{ { 'm' },{ 13 } },{ { 'n' },{ 14 } },{ { 'o' },{ 15 } },{ { 'p' },{ 16 } },{ { 'q' },{ 17 } },{ { 'r' },{ 18 } },
{ { 's' },{ 19 } },{ { 't' },{ 20 } },{ { 'u' },{ 21 } },{ { 'v' },{ 22 } },{ { 'w' },{ 23 } },{ { 'x' },{ 24 } },
{ { 'y' },{ 25 } },{ { 'z' },{ 26 } }
};
unordered_map<char, int> nums = {
{ { 1 },{ 'a' } },{ { 2 },{ 'b' } },{ { 3 },{ 'c' } },{ { 4 },{ 'd' } },{ { 5 },{ 'e' } },{ { 6 },{ 'f' } },
{ { 7 },{ 'g' } },{ { 8 },{ 'h' } },{ { 9 },{ 'i' } },{ { 10 },{ 'j' } },{ { 11 },{ 'k' } },{ { 12 },{ 'l' } },
{ { 13 },{ 'm' } },{ { 14 },{ 'n' } },{ { 15 },{ 'o' } },{ { 16 },{ 'p' } },{ { 17 },{ 'q' } },{ { 18 },{ 'r' } },
{ { 19 },{ 's' } },{ { 20 },{ 't' } },{ { 21 },{ 'u' } },{ { 22 },{ 'v' } },{ { 23 },{ 'w' } },{ { 24 },{ 'x' } },
{ { 25 },{ 'y' } },{ { 26 },{ 'z' } }
};
int length2 = two.length() - 1;
bool shift_up = true;
int wrap;
string final_str = "";
for (int i = 0; i < one.length(); i++) {
if (i == 0) wrap = 0;
else wrap = i % length2;
char one_str = one.at(i);
int increment_by = alpha.find(two.at(wrap))->second;
if (shift_up) {
int new_num = (alpha.find(one_str)->second + increment_by) % 26;
final_str += nums.find(new_num)->second;
shift_up = false;
}
else {
int new_num = abs((alpha.find(one_str)->second - increment_by)) % 26;
final_str += nums.find(new_num)->second;
shift_up = true;
}
}
return final_str;
}
int main() {
cout << enigma("cats", "dog");
pause();
}
JURRASIC PARK
Jurassic Park is opening again! This time there will be bigger and better attractions and yes, of course there are going to be dinosaurs. But the scientists at InGen need your help to create these monstrous beings. Help them by merging the DNA of a lizard (Array 1) and the DNA collected from the fossil of a Tyrannosaurus Rex (Array 2) in order to create a super dinosaur. But wait, the process isn’t just that simple. In order to merge the DNA we need to make sure that each element in the resulting array has only one digit.
Note
- Input contains only positive numbers.
ex.
SAMPLE INPUT
9 2 8 4
7 3 5 2
SAMPLE OUTPUT
1 6 5 1 3 6
Explanation:
- Adding the individual elements (starting from left), we get 9 + 7 = 16 which is split as 1 and 6 in the output array. Similarly, 2 + 3 = 5, 8 + 5 = 13 which is 1 and 3 and so on
- Approach:
- Parse both strings
- Add together number per number -> convert back to string, and then add spaced inbetween.
string JURRASICpark(string &one, string &two) {
string final_str = "";
string cur_num = "";
vector<int> nums1;
vector<int> nums2;
for (int i = 0; i < one.length(); i++) {
if (one.at(i) == ' ') continue;
else {
while (i < one.length() && one.at(i) != ' ') {
cur_num += one.at(i);
i++;
}
nums1.push_back(atoi(cur_num.c_str()));
}
cur_num = "";
}
cur_num = "";
for (int i = 0; i < two.length(); i++) {
if (two.at(i) == ' ') continue;
else {
while (i < two.length() && two.at(i) != ' ') {
cur_num += two.at(i);
i++;
}
nums2.push_back(atoi(cur_num.c_str()));
}
cur_num = "";
}
for (int i = 0; i < nums1.size(); i++) {
final_str += to_string(nums1.at(i) + nums2.at(i));
}
int orginal = final_str.length();
for (int i = 1; i < orginal * 2 - 1; i+=2) {
final_str.insert(i, " ");
}
return final_str;
}
int main()
{
string one;
string two;
getline(cin, one);
getline(cin, two);
cout << JURRASICpark(one, two);
}
FINDING DORY
You are in the world dominated by fishes, whales and sharks. Your best friend - dory, is suddenly gone missing. Your goal is to find Dory who is somewhere in the ocean.
The first line of the input is the word to be found. After it is the 4x4 char matrix.
Note
- Input contains only lowercase letters. All inputs are 4x4 char matrices.
- The Ocean is assumed to be a 2 dimensional array.
- As you traverse through this “Ocean”, you will find many creatures (or you might just find nothing, who knows.)
- Each element in the 2D array is a character.
ex.
SAMPLE INPUT
dory
d a g k
o o r t
r z r v
k q l y
SAMPLE OUTPUT
YES
Explanation
- If you look at the diagonal of the char matrix you can see that it spells "dory".
- Approach:
- If we find either starting char or ending char of the word, and it exists up, down, diagonally, etc... then return true. We also make sure to follow up with our orientation.
- Otherwise, if the entire scan fails, return false;
Test1->true
R Z L Y R G U R G W F A O A R
B N J J R B S H F W I S L V V
K Y A K F O D Z H T D D L L A
E P J J B K D W E P X F Y I F
I V H M Z L Q D J P U H K G L
K Z D N J T Z K O X R M L K A
W C G K M I I A I V Y A Y O M
J C N G H B T O U Q J G L R E
F R A I I U K G R U R V T B L
A H P R G B C W R A V F F R F
B V A I I I R B D H X E Q N K
I O B C Q X E G X A K I T N Z
O F Z P F J N A T N X N O K O
B S Q B D A O Z K J G S A K T
R Z F P V T K P I E P U N O X
Test2->false
R Z L Y R G U R G W F A O A R
B N J J E B S H F W I S L V V
K Y A K F O D Z H T D D L L A
E P J J B K D W E P X F Y I F
I V H M Z L Q D J P U H K G L
K Z D N J T Z K O X R M L K A
W C G K M I I A I V Y A Y O M
J C N G H B T O U Q J G L R E
F R A I I U K G R U R V T B L
A H P R G B C W R A V F F R F
B V A I I I R B D H X E Q N K
I O B C Q X E G X A K I T N Z
O F Z P F J N A T N X N O K O
B S Q B D A O Z K J G S A K T
R Z F P V T K P I E P U N O X
Test3->true
R Z L Y R G U R G W F A O A R
B N J J E B S H F W I S L V D
K Y A K F O D Z H T D D L L O
E P J J B K D W E P X F Y I R
I V H M Z L Q D J P U H K G Y
K Z D N J T Z K O X R M L K A
W C G K M I I A I V Y A Y O M
J C N G H B T O U Q J G L R E
F R A I I U K G R U R V T B L
A H P R G B C W R A V F F R F
B V A I I I R B D H X E Q N K
I O B C Q X E G X A K I T N Z
O F Z P F J N A T N X N O K O
B S Q B D A O Z K J G S A K T
R Z F P V T K P I E P U N O X
Test4->false
R Z L Y R G U R G W F A O A R
D O R J E B S H F W I S L V V
O Y O K F O D Z H T D D L L A
R P Y J B K D W E P X F Y I F
I V H M Z L Q D J P U H K G L
K Z D N J T Z K O X R M L K A
W C D K M I I A I V Y A Y O M
J C N O H B T O U Q J G L R E
F R A I R U K G R U R V T B L
A H P R G B C W R A V F F R F
B V A I I I Y B D H X E Q N K
I O B C Q X E G X A K I T N Z
O F Z P F J N A T N X N O K O
B S Q B D A O Z K J G S A K T
R Z F P V T K P I E P U N O X
class WordSearch {
public:
WordSearch(char *infile, string word) {
processFile(infile);
find = word;
find_length = find.length();
// for quick finding
for (auto i : word) {
word_chars.insert(i);
}
}
bool word_exists() {
row_size = wordmap.size();
col_size = wordmap.at(0).size();
for (int row = 0; row < row_size; row++) {
for (int col = 0; col < col_size; col++) {
char cur = wordmap.at(row).at(col);
if (word_chars.find(cur) == word_chars.end()) {
continue;
}
else {
if (search_up(cur, row, col) || search_up_right(cur, row, col) ||
search_right(cur, row, col) || search_right_down(cur, row, col) ||
search_down(cur, row, col) || search_down_left(cur, row, col) ||
search_left(cur, row, col) || search_left_up(cur, row, col)) {
return true;
}
}
}
}
return false;
}
private:
vector<vector<char>> wordmap;
unordered_set<char> word_chars;
int row_size, col_size;
string find;
unsigned short find_length;
void processFile(char *file) {
fstream infile(file);
string line;
vector<char> temp;
while (std::getline(infile, line)) {
for (auto i : line) {
if (i != ' ')
temp.push_back(tolower(i));
}
wordmap.push_back(temp);
temp.clear();
}
}
bool isValid(int row, int col, const int row_size, const int col_size) {
return (row < row_size && col < col_size &&
col >= 0 && row >= 0);
}
bool search_up(char start, int row, int col) {
// select orientation -> forward d -> o -> r -> y
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
row++;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
row++;
}
else return false;
}
return true;
}
}
bool search_up_right(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
row++;
col++;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
row++;
col++;
}
else return false;
}
return true;
}
}
bool search_right(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
col++;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
col++;
}
else return false;
}
return true;
}
}
bool search_right_down(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
col++;
row--;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
col++;
row--;
}
else return false;
}
return true;
}
}
bool search_down(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
row--;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
row--;
}
else return false;
}
return true;
}
}
bool search_down_left(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
row--;
col--;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
row--;
col--;
}
else return false;
}
return true;
}
}
bool search_left(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
col--;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
col--;
}
else return false;
}
return true;
}
}
bool search_left_up(char start, int row, int col) {
if (start == find.at(0)) {
for (int str_forward = 0; str_forward < find_length; str_forward++) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_forward)) {
col--;
row++;
}
else return false;
}
return true;
}
else {
for (int str_backward = find_length - 1; str_backward >= 0; str_backward--) {
if (isValid(row, col, row_size, col_size) && wordmap.at(row).at(col) == find.at(str_backward)) {
col--;
row++;
}
else return false;
}
return true;
}
}
};
int main(int argv, char **argc)
{
string find = "dory";
WordSearch map(argc[1], find);
cout << boolalpha << map.word_exists();
pause();
}
KIDNAPPER
A kidnapper wrote a ransom note but is worried it will be traced back to him. He found a magazine and wants to know if he can cut out letters from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive. Given the words in the magazine and the words in the ransom note, print YES if he can replicate his ransom note exactly using letters from the magazine; otherwise, print NO.
The first line of the input is the sentence in the magazine from which he wants to create an untraceable replica. The second line of the input is the sentence he wants to write in his ransom note.
ex.
SAMPLE INPUT
Do not step on the broken glass
then do not
SAMPLE OUTPUT
NO
Explanation
- We can find all the letters in "then do not" in the first sentence except for the letter "d". Remember it is case sensitive!
NEXT HIGHEST NUMBER
For every number in the array, output a new array that such that for every number in the input array, it finds the first next higher number. If no higher number exists, output its own number in the original index.
Ex.
input: 2 3 8 5 6 -1 7 8 -2 9
output: 3 8 9 6 7 7 8 9 9 9
Explanation: 3 is the first next higher number after 2, 9 is the next higher number after 8.
- Approach:
- O(n^2) solution seems trivial.
- O(nlogn)
- Use a priority queue.
- If the first element you encounter is greater than itself, fill in the solution vector right there and there.
- Otherwise, store it in the priority queue. We can think of this as a kind of todo list for the queue remember to go back to. Our queue will be sorted in ascending order. It will store a pair, in which the first element will contain the number it will be looking for that exceeds it, and the next number the position it needs to store it in. It will be sorted in ascending order by its first element, that way we would know to stop and not check all the elements in the queue every time. Rather, the only time we go in the while loop is when we make some progress and add the next element in the queue. Logn insertions for the q, with n maximum iterations.
struct Comparitor {
bool operator()(pair<int, int> &one, pair<int, int> &two) {
return one.first > two.first;
}
};
vector<int> next_higher_number(vector<int> &ar)
{
vector<int> sol(ar.size());
priority_queue<pair<int, int>, vector<pair<int, int>>, Comparitor> q;
for (int i = 1; i < ar.size(); i++)
{
if (ar[i] > ar[i-1])
sol[i - 1] = ar[i];
else {
// looking for > ar[i] at position sol[i - 1]
q.push(make_pair(ar[i - 1], i - 1));
}
while (!q.empty() && ar[i] > q.top().first) {
sol[q.top().second] = ar[i];
q.pop();
}
}
sol[ar.size() - 1] = ar[ar.size() - 1];
return sol;
}
int main()
{
vector<int> in = { 2, 3, 8, 5, 6, -1, 7, 8, -2, 9 };
print(next_higher_number(in));
}
Last modified 4yr ago