Hackerrank

Contacts

We're going to make our own Contacts application! The application must perform two types of operations:

1. add name, where  is a string denoting a contact name. This must store  as a new contact in the application.
2. find partial, where  is a string denoting a partial name to search the application for. It must count the number of contacts starting with  and print the count on a new line.

Given  sequential add and find operations, perform each operation in order.

Input Format

The first line contains a single integer, , denoting the number of operations to perform.
Each line  of the  subsequent lines contains an operation in one of the two forms defined above.

Constraints

• It is guaranteed that  and  contain lowercase English letters only.
• The input doesn't have any duplicate  for the  operation.

Output Format

For each find partial operation, print the number of contact names starting with  on a new line.

Sample Input

4
add hack
add hackerrank
find hac
find hak

Sample Output

2
0

Explanation

We perform the following sequence of operations:

1. Add a contact named hack.
2. Add a contact named hackerrank.
3. Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we print  on a new line.
4. Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print  on a new line.

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

class trieNode {

    public:

    int val;

    trieNode *next[26];

    trieNode() {

        val = 0;

    }

};

class Trie {

    private:

        trieNode *root;

  public:

    Trie() {

        for (int i = 0; i < 26; i++) {

            root = new trieNode();

            root -> next[i] = NULL;

        }

    }

    void insert(string input) {

        if (input.size() == 0) {

            return;

        }

        trieNode *trav = root;

        for (int i = 0; i < input.size();i++) {

            int index = input[i] - 'a';

            if (trav -> next[index] == NULL) {

                trav -> next[index] = new trieNode();

            }

            trav -> next[index] -> val++;

            trav = trav -> next[index];

        }

    }

    

    int search(string input) {

        if (input.size() == 0) {

            return 0;

        }

        trieNode *trav = root;

        for (int i = 0; i < input.size();i++) {

            int index = input[i] - 'a';

            if (trav -> next[index] == NULL) {

                return 0;

            }

            trav = trav -> next[index];

        }

        return trav -> val;

    }

    

    ~Trie() {

       deleteTrie(root);

    }

    void static deleteTrie(trieNode *rot) {

        if (rot == NULL) {

            return;

        }

        for (int i = 0; i < 26; i++) {

            if (rot -> next[i] != NULL) {

                deleteTrie(rot -> next[i]);

            }

        }

        delete rot;

    }

};

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

    int n;

    cin >> n;

    Trie* trie = new Trie();

    string input, op;

    for (int i = 0; i < n; i++) {

        cin >> op >> input;

        if (op == "add") {

           trie->insert(input); 

        } else if (op == "find") {

            cout << trie->search(input) << endl;

        }

    }

    delete trie;

    return 0;

}

======== 

Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then:

• If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set ,  is the median.
• If your set contains an even number of elements, the median is the average of the two middle elements of the sorted sample. In the sorted set ,  is the median.

Given an input stream of  integers, you must perform the following task for each  integer:

1. Add the  integer to a running list of integers.
2. Find the median of the updated list (i.e., for the first element through the  element).
3. Print the list's updated median on a new line. The printed value must be a double-precision number scaled to decimal place (i.e.,  format).

Input Format

The first line contains a single integer, , denoting the number of integers in the data stream.
Each line  of the  subsequent lines contains an integer, , to be added to your list.

Constraints

Output Format

After each new integer is added to the list, print the list's updated median on a new line as a single double-precision number scaled to  decimal place (i.e.,  format).

Sample Input

6
12
4
5
3
8
7

Sample Output

12.0
8.0
5.0
4.5
5.0
6.0

Explanation

There are  integers, so we must print the new median on a new line as each integer is added to the list:

// Efficient one using heap: https://www.youtube.com/watch?v=VmogG01IjYc

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <stack>

#include <string>

#include <bitset>

#include <cstdio>

#include <limits>

#include <vector>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <fstream>

#include <numeric>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

void insert(list<int>& lst, int num) {

    list<int>::iterator it;

    it = lst.begin();

    while (it != lst.end()) {

        if (*it < num) {

            it++;

        } else {

            lst.insert(it, num);

            return;

        }

    }

    lst.push_back(num);

    return;

}

double median(list<int>& lst) {

    double ans;

    int size = lst.size();

    if (size == 0) {

        return ans;

    }

    list<int>::iterator it = lst.begin();

    if (size % 2 != 0) {

        advance(it, size/2);

        return double(*it);

    } else {

        advance(it, size/2);

        ans = double(*it);

        it--;

        ans += double(*it);

        return ans/2;

    }

}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    int n;

    cin >> n;

    

    list<int> list;

    

    while (n-- > 0) {

        int num;

        cin >> num;

        insert(list, num);

        cout << median(list) << endl;

    }

    return 0;

}

============

Swap Nodes [Algo]

by abhiranjan

• Problem
• Submissions
• Leaderboard
• Discussions
• Editorial 

A binary tree is a tree which is characterized by any one of the following properties:

• It can be an empty (null).
• It contains a root node and two subtrees, left subtree and right subtree. These subtrees are also binary tree.

Inorder traversal is performed as

1. Traverse the left subtree.
2. Visit root (print it).
3. Traverse the right subtree.

(For an Inorder traversal, start from the root and keep visiting the left subtree recursively until you reach the leaf,then you print the node at which you are and then you visit the right subtree.)

We define depth of a node as follow:

• Root node is at depth 1.
• If the depth of parent node is d, then the depth of current node will be d+1.

Swapping: Swapping subtrees of a node means that if initially node has left subtree L and right subtree R, then after swapping left subtree will be R and right subtree L.

Eg. In the following tree, we swap children of node 1.

                                Depth
    1               1            [1]
   / \             / \
  2   3     ->    3   2          [2]
   \   \           \   \
    4   5           5   4        [3]

Inorder traversal of left tree is 2 4 1 3 5 and of right tree is 3 5 1 2 4.

Swap operation: Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].

You are given a tree of N nodes where nodes are indexed from [1..N] and it is rooted at 1. You have to perform T swap operations on it, and after each swap operation print the inorder traversal of the current state of the tree.

Input Format
First line of input contains N, number of nodes in tree. Then N lines follow. Here each of ith line (1 <= i <= N) contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node. -1 is used to represent null node.
Next line contain an integer, T. Then again T lines follows. Each of these line contains an integer K.

Output Format
For each K, perform swap operation as mentioned above and print the inorder traversal of the current state of tree.

Constraints
1 <= N <= 1024
1 <= T <= 100
1 <= K <= N
Either a = -1 or 2 <= a <= N
Either b = -1 or 2 <= b <= N
Index of (non-null) child will always be greater than that of parent.

Sample Input #00

3
2 3
-1 -1
-1 -1
2
1
1

Sample Output #00

3 1 2
2 1 3

Sample Input #01

5
2 3
-1 4
-1 5
-1 -1
-1 -1
1
2

Sample Output #01

4 2 1 5 3

Sample Input #02

11
2 3
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4

Sample Output #02

2 9 6 4 1 3 7 5 11 8 10
2 6 9 4 1 3 7 5 10 8 11

Explanation

**[s] represents swap operation is done at this depth.

Test Case #00: As node 2 and 3 has no child, swapping will not have any effect on it. We only have to swap the child nodes of root node.

    1   [s]       1    [s]       1   
   / \      ->   / \        ->  / \  
  2   3 [s]     3   2  [s]     2   3

Test Case #01: Swapping child nodes of node 2 and 3 we get

    1                  1  
   / \                / \ 
  2   3   [s]  ->    2   3
   \   \            /   / 
    4   5          4   5  

Test Case #02: Here we perform swap operations at the nodes whose depth is either 2 and 4 and then at nodes whose depth is 4.

         1                     1                          1             
        / \                   / \                        / \            
       /   \                 /   \                      /   \           
      2     3    [s]        2     3                    2     3          
     /      /                \     \                    \     \         
    /      /                  \     \                    \     \        
   4      5          ->        4     5          ->        4     5       
  /      / \                  /     / \                  /     / \      
 /      /   \                /     /   \                /     /   \     
6      7     8   [s]        6     7     8   [s]        6     7     8
 \          / \            /           / \              \         / \   
  \        /   \          /           /   \              \       /   \  
   9      10   11        9           11   10              9     10   11 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class treeNode {
    int val;
    treeNode *left;
    treeNode *right;
    treeNode(int val) {
        val = val;
        left = NULL;
        right = NULL;
    }
};

void swap_level(treeNode *root, int level) {
    if (root == NULL) {
        return;
    }
    if (level == 1) {
        treeNode *temp = root -> left;
        root -> left = root -> right;
        root -> right = temp;
    } else {
        swap_level(root -> left, level - 1);
        swap_level(root -> right, level - 1);
    }
    return;
}

bool check(int tree_level, int k, int height) {
    while (k < height) {
        if (tree_level == k) {
            return true;
        }
        k += k;
    }
    return false;
}
void swap(treeNode *root, int k) {
    int ht = height(root);
    queue<pair<treeNode *, int> > q;
    q.push(make_pair(root, 1));
    
    while (!q.empty()) {
        pair<treeNode*, int> poped = q.front();q.pop();
        if (check(poped.second, k, ht)) {
            swap(poped.first);
            if (poped.first -> left != NULL) {
                q.push(make_pair(poped.first -> left, poped.second + 1));
            }
            if (poped.first -> right != NULL) {
                q.push(make_pair(poped.first -> right, poped.second + 1));
            }
        }
    }
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n, t;
    
    cin >> n;
    vector<pair<int, int> > treeDep;
    while (n-- > 0) {
        int a, b;
        cin >> a >> b;
        treeDep.push_back(make_pair(a, b));
    }
    treeNode *root = NULL;
    make_tree(treeDep, root);
    
    cin >> t;
    while (t-- > 0) {
        int k;
        cin >> k;
        treeNode *temp = NULL;
        copy(root, temp);
        swap(temp, k);
        cout << inorder(root) << endl;
        delete(temp);
    }
    delete(root);
    return 0;
}




Not optimized but good way to calculate height (no need to calculate height: just use queue with null, to track height.

https://github.com/ShrikantJadhav/HackerRank-Solutions/blob/master/SwapNodes.cpp