Programming Puzzles
  • Introduction
  • CTCI
    • Arrays and Strings
      • Is Unique
      • Check Permutation
      • URLify
      • Palindrome Permutation
      • One Away
      • String Compression
      • Rotate Matrix
      • Zero Matrix
      • String Rotation
    • Linked Lists
      • Remove Dups
      • Return Kth to Last
      • Delete Middle Node
      • Sum Lists
      • Palindrome
      • Intersection
    • Trees
      • Route Between Nodes
      • Minimal Tree
      • Check Balanced
      • Build Order
      • First Common Ancestor
      • BST Sequences
      • Check Subtree
      • Random Node
    • Stacks and Queues
      • Three in One
      • Stack Min
      • Stack of Plates
      • Queue via Stacks
      • Sort Stack
    • Sorting and Searching
      • Sorted Merge
      • Group Anagrams
      • Search in Rotated Array
      • Sorted Search, No Size
      • Sparse Search
      • Sort Big File
      • Missing Int
      • Find Duplicates
      • Sorted Matrix Search
    • Bit Manipulation
      • Insertion
    • Math and Puzzles
      • Two Ropes
      • Nine Balls
      • The Heavy Pill
      • Basketball
      • Dominos
    • Recursion and Dynamic Programming
      • Triple Step
      • Robot in a Grid
      • Magic Index
      • Power Set
      • Recursive Multiply
      • Towers of Hanoi
      • Permutations without Dups
      • Parens
      • Paint Fill
      • Coins
    • Object Oriented Design
      • Circular Array
    • Moderate
      • Number Swapper
      • Word Frequencies
      • Intersection
      • Tic Tac Win
      • Factorial Zeros
      • Smallest Difference
      • Number Max
      • Operations
      • Living People
      • Diving Board
      • Bisect Squares
      • Best Line
      • Sub Sort
      • Contiguous Sequence
      • Pattern Matching
      • Pond sizes
      • T9
      • Sum Swap
      • Pairs with Sum
    • Hard
      • Add Without Plus
      • Shuffle
      • Random Set
      • Count of 25
      • Baby Names
      • Majority Element
      • Word Distance
      • The Masseuse
      • Word Transformer
      • Sparse Similarity
  • EoPI
    • Arrays and Strings
  • LeetCode
    • 3 Longest Substring Without Repeating Characters
    • 4 Median of Two Sorted Arrays
    • 5 Longest Palindromic Substring
    • 6 ZigZag Conversion
    • 7 Reverse Integer
    • 8 String to Integer (atoi)
    • 9 Palindrome Number
    • 11 Container With Most Water
    • 14 Longest Common Prefix
    • 15 3Sum
    • 16 3Sum Closest
    • 17 Letter Combinations of a Phone Number
    • 19 Remove Nth Node From End of List
    • 20 Valid Parentheses
    • 21 Merge Two Sorted Lists
    • 22 Generate Parentheses
    • 23 Merge k Sorted Lists
    • 24 Swap Nodes in Pairs
    • 26 Remove Duplicates from Sorted Array
    • 27 Remove Element
    • 28 Implement strStr()
    • 29 Divide Two Integers
    • 30 Substring with Concatenation of All Words
    • 32 Longest Valid Parentheses
    • 33 Search in Rotated Sorted Array
    • 34 Search for a Range
    • 35 Search Insert Position
    • 36 Valid Sudoku
    • 37 Sudoku Solver
    • 38 Count and Say
    • 40 Combination Sum II
    • 41 First Missing Positive
    • 42 Trapping Rain Water
    • 43 Multiply Strings
    • 44 Wildcard Matching
    • 45 Jump Game II
    • 46 Permutations
    • 48 Rotate Image
    • 49 Group Anagrams
    • 53 Maximum Subarray
    • 54 Spiral Matrix
    • 59 Spiral Matrix II
    • 62 Unique Paths
    • 64 Minimum Path Sum
    • 66 Plus One
    • 67 Add Binary
    • 68 Text Justification
    • 69 Sqrt(x)
    • 70 Climbing Stairs
    • 71 Simplify Path
    • 73 Set Matrix Zeroes
    • 74 Search a 2D Matrix
    • 75 Sort Colors
    • 80 Remove Duplicates from Sorted Array II
    • 83 Remove Duplicates from Sorted List
    • 90 Subsets II
    • 91 Decode Ways
    • 99 Recover Binary Search Tree
    • 100 Same Tree
    • 103 Binary Tree Zigzag Level Order Traversal
    • 104 Maximum Depth of Binary Tree
    • 105 Construct Binary Tree from Preorder and Inorder Traversal
    • 112 Path Sum
    • 114 Flatten Binary Tree to Linked List
    • 119 Pascal's Triangle II
    • 120 Triangle
    • 128 Longest Consecutive Sequence
    • 129 Sum Root to Leaf Numbers
    • 133 Clone Graph
    • 136 Single Number
    • 137 Single Number II
    • 138 Copy List with Random Pointer
    • 144 Binary Tree Preorder Traversal
    • 146 LRU Cache
    • 148 Sort List
    • 150 Evaluate Reverse Polish Notation
    • 155 Min Stack
    • 157 Read N Characters Given Read4
    • 161 One Edit Distance
    • 162 Find Peak Element
    • 163 Missing Ranges
    • 167 Two Sum II - Input array is sorted
    • 168 Excel Sheet Column Title
    • 170 Two Sum III - Data structure design
    • 173 Binary Search Tree Iterator
    • 186 Reverse Words in a String II
    • 189 Rotate Array
    • 199 Binary Tree Right Side View
    • 200 Number of Islands
    • 202 Happy Number
    • 207 Course Schedule
    • 210 Course Schedule II
    • 214 Shortest Palindrome
    • 216 Combination Sum III
    • 217 Contains Duplicate
    • 221 Maximal Square
    • 226 Invert Binary Tree
    • 227 Basic Calculator II
    • 228 Summary Ranges
    • 229 Majority Element II
    • 230 Kth Smallest Element in a BST
    • 234 Palindrome Linked List
    • 236 Lowest Common Ancestor of a Binary Tree
    • 237 Delete Node in a Linked List
    • 239 Sliding Window Maximum
    • 240 Search a 2D Matrix II
    • 242 Valid Anagram
    • 243 Shortest Word Distance
    • 245 Shortest Word Distance III
    • 246 Strobogrammatic Number
    • 247 Strobogrammatic Number II
    • 253 Meeting Rooms II
    • 255 Verify Preorder Sequence in Binary Search Tree
    • 256 Paint House
    • 258 Add Digits
    • 260 Single Number III
    • 261 Graph Valid Tree
    • 263 Ugly Number
    • 264 Ugly Number II
    • 266 Palindromic Permutation
    • 270 Closest Binary Search Tree Value
    • 271 Encode and Decode Strings
    • 277 Find the Celebrity
    • 279 Perfect Squares
    • 280 Wiggle Sort
    • 281 Zigzag Iterator
    • 283 Move Zeroes
    • 284 Peeking Iterator
    • 285 Inorder Successor in BST
    • 286 Walls and Gates
    • 288 Unique Word Abbreviation
    • 290 Word Pattern
    • 292 Nim Game
    • 293 Flip Game
    • 296 Best Meeting Point
    • 297 Serialize and Deserialize Binary Tree
    • 298 Binary Tree Longest Consecutive Sequence
    • 301 Remove Invalid Parentheses
    • 304 Range Sum Query 2D - Immutable
    • 310 Minimum Height Trees
    • 311 Sparse Matrix Multiplication
    • 312 Burst Balloons
    • 313 Super Ugly Number
    • 315 Count of Smaller Numbers After Self
    • 316 Remove Duplicate Letters
    • 317 Shortest Distance from All Buildings
    • 319 Bulb Switcher
    • 322 Coin Change
    • 323 Number of Connected Components in an Undirected Graph
    • 326 Power of Three
    • 330 Patching Arrays
    • 333 Largest BST Subtree
    • 334 Increasing Triplet Subsequence
    • 335 Self Crossing
    • 338 Counting Bits
    • 340 Longest Substring with At Most K Distinct Characters
    • 344 Reverse String
    • 345 Reverse Vowels of a String
    • 346 Moving Average from Data Stream
    • 347 Top K Frequent Elements
    • 349 Intersection of Two Arrays
    • 356 Line Reflection
    • 357 Count Numbers with Unique Digits
    • 359 Logger Rate Limiter
    • 361 Bomb Enemy
    • 362 Design Hit Counter
    • 366 Find Leaves of Binary Tree
    • 367 Valid Perfect Square
    • 369 Plus One Linked List
    • 379 Design Phone Directory
    • 387 First Unique Character in a String
    • 389 Find the Difference
    • 394 Decode String
    • 395 Longest Substring with At Least K Repeating Characters
    • 396 Rotate Function
    • 399 Evaluate Division
    • 403 Frog Jump
    • 404 Sum of Left Leaves
    • 406 Queue Reconstruction by Height
    • 409 Longest Palindrome
    • 417 Pacific Atlantic Water Flow
    • 418 Sentence Screen Fitting
    • 422 Valid Word Square
    • 425 Word Squares
    • 434 Number of Segments in a String
    • 435 Non-overlapping Intervals
    • 438 Find All Anagrams in a String
    • 441 Arranging Coins
    • 445 Add Two Numbers II
    • 453 Minimum Moves to Equal Array Elements
    • 476 Number Complement
    • 482 License Key Formatting
    • 494 Target Sum
    • 496 Next Greater Element I
    • 500 Keyboard Row
    • 503 Next Greater Element II
    • 505 The Maze II
    • 506 Relative Ranks
    • 507 Perfect Number
    • 513 Find Bottom Left Tree Value
    • 514 Freedom Trail
    • 517 Super Washing Machines
    • 523 Continuous Subarray Sum
    • 530 Minimum Absolute Difference in BST
    • 531 Lonely Pixel I
    • 534 Design TinyURL
    • 545 Boundary of Binary Tree
    • 551 Student Attendance Record I
    • 554 Brick Wall
    • 563 Binary Tree Tilt
    • 567 Permutation in String
    • 572 Subtree of Another Tree
    • 604 Design Compressed String Iterator
    • 605 Can Place Flowers
    • 606 Construct String from Binary Tree
    • 624 Maximum Distance in Arrays
    • 630 Course Schedule III
    • 652 Find Duplicate Subtrees
    • 654 Maximum Binary Tree
    • 657 Judge Route Circle
    • 665 Non-decreasing Array
    • 669 Trim a Binary Search Tree
    • 672 Bulb Switcher II
    • 677 Map Sum Pairs
    • 681 Next Closest Time
    • 684 Redundant Connection
    • 686 Repeated String Match
    • 690 Employee Importance
    • 692 Top K Frequent Words
    • 212 Word Search II
    • 360 Sort Transformed Array
    • 616 Add Bold Tag in String
    • 318 Maximum Product of Word Lengths
    • 341 Flatten Nested List Iterator
    • 272 Closest Binary Search Tree Value II
    • 56 Merge Intervals
    • 215 Kth Largest Element in an Array
    • 98 Validate Binary Search Tree
    • 351 Android Unlock Patterns
    • 289 Game of Life
    • 575 Distribute Candies
    • 47 Permutations II
    • 267 Palindrome Permutation II
    • 308 Range Sum Query 2D - Mutable
    • 348 Design Tic-Tac-Toe
    • 68 Text Justification
    • 125 Valid Palindrome
    • 139 Word Break
    • 661 Image Smoother
    • 485 Max Consecutive Ones
    • 208 Implement Trie (Prefix Tree)
    • 140 Word Break II
    • 487 Max Consecutive Ones II
    • 61 Rotate List
    • 498 Diagonal Traverse
    • 231 Power of Two
    • 520 Detect Capital
    • 473 Matchsticks to Square
    • 127 Word Ladder
    • 251 Flatten 2D Vector
    • 244 Shortest Word Distance II
    • 245 Shortest Word Distance III
    • 423 Reconstruct Original Digits from English
    • 676 Implement Magic Dictionary
    • 332 Reconstruct Itinerary
    • 718 Maximum Length of Repeated Subarray
    • 172 Factorial Trailing Zeroes
    • 713 Subarray Product Less Than K
    • 36 Valid Sudoku
    • 752 Open the Lock
    • 65 Valid Number
    • 760 Find Anagram Mappings
    • 582 Kill Process
    • 594 Longest Harmonious Subsequence
    • 581 Shortest Unsorted Continuous Subarray
    • 599 Minimum Index Sum of Two Lists
    • 635 Design Log Storage System
    • 642 Design Search Autocomplete System
    • 379 Design Phone Directory
    • 295 Find Median from Data Stream
    • 232 Implement Queue using Stacks
    • 383 Ransom Note
    • 278 First Bad Version
    • 206 Reverse Linked List
    • 787 Cheapest Flights Within K Stops
    • 818 Race Car
    • Categorical
    • Array and Strings
      • Max Avg Number
      • Circular Array Cycle
      • Molecular Weight
      • Itoa
      • Average GPA
      • In Fibonacci Sequence
      • Shortest Rotated Distance
      • Sub-array Factor
      • Matrix Convolution
      • Add One to Array
      • Sum Two Arrays
      • Array Transformation
      • Unique Sub Arrays
      • Reverse and Simplify String
      • Reverse String
      • Information Masking
      • Minimum Array Reduction
      • Add Numbers in Unclean Data
      • Array Operations
      • Equilibrium Index
      • Visit All Places in Minimum Time
    • Linked List
      • Double Linked List Connected Components
    • Trees and Graphs
      • Directory Sum
      • Largest Subtree
      • Shortest Path DAG Source to Sink
      • HTML Parser
      • Infix to Postfix Expression Evaluater
      • Longest Path in Undirected Acyclic Graph
      • Decompress String
      • Pythagoras Tree
      • Kings
      • All Paths
      • Leaf Nodes
      • Proper Locking
      • Number of Cities at each Distance
      • Root Path as DLL
      • Binary Replacement
      • All Root to Leaf Paths
    • Recursion and Dynamic Programming
      • Recursive to_string
      • N Loop
      • Divisible by Set
      • Brute Force Seam Carving
      • Perimeter Island
      • Knight on a Phone
      • Coin Change Problem
      • Maximum Product in Matrix
      • Largest Sum of a Path in a Triangle
      • Linked List Tree
    • Sorting and Searching
      • Three Highest Numbers
      • Common Elements in Sorted Arrays
      • Inverse Spiral Matrix
      • Number Negatives in Sorted Matrix
      • Number of Bombs in Minesweeper
      • Two Sum Less Than
      • Frequency Compression
      • N Closest Points
      • Find Sum Pairs
      • Max with no Comparitor
      • Largest Subarray
      • Single Missing Number
      • Ternary Search
      • Fastest Frog Jump
    • Design
      • Random Hash DS
      • Road Trip
      • Load Balancer
      • Haircut Appointment Scheduler
      • Conway's Game of Life
      • Design Twitter
      • LogParser
      • Permission Management for a General Tree
      • Max Stack
      • Parking Lot
    • Probability
      • Simplified Blackjack
      • Rand7
      • Shuffle
    • Combinatorics
      • Binary Permutation
      • N Queens
      • Prefix Permutation
    • Mathematics
      • Angle Between Time
      • Line Segment Intersection
      • Maximum Points View Angle
      • Collatz Conjecture
      • Convex Hull
      • Swap In Place
      • Powers of 2
      • Monte Carlo Approximation of PI
      • Perfect Power
      • Derivative of a Polynomial
    • Bit Manipulation
      • Reverse Binary
    • Cryptography
      • Message Encyption and Decryption
      • Encryption
    • Other
      • Maximum Time Combination
      • Polish Notation String Calculator
  • Competition
    • CodeDavis
  • Project Eular
    • 1 Multiples of 3 and 5
    • 2 Even Fibonacci numbers
    • 3 Largest Prime Factor
    • 4 Largest Palindrome Product
    • 5 Smallest Multiple
    • 6 Sum Square Difference
    • 7 10001st Prime
    • 8 Largest Product in a Series
    • 9 Special Pythagorean Triplet
    • 10 Summation of Primes
    • 11 Largest Product in a Grid
    • 12 Highly Divisible Triangular Number
    • 13 Large Sum
    • 14 Longest Collatz Sequence
    • 15 Lattice Paths
    • 16 Power Digit Sum
    • 17 Number Letter Counts
    • 18 Maximum path sum I
    • 19 Counting Sundays
Powered by GitBook
On this page

Was this helpful?

  1. Competition

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));
}
PreviousCompetitionNextProject Eular

Last updated 5 years ago

Was this helpful?

[]()

https://www.wikiwand.com/en/T9_(predictive_text