Thursday, June 16, 2016

GeeksForGeeks Challenges 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    //code
    auto t = 0;
    std::cin >> t;

    while (t--)
    {
        auto n = 0;
        std::cin >> n;

        std::vector<int> v;
        
        while (n--)
        {
            auto x = 0;
            
            std::cin >> x;

            v.push_back(x);
        }

        auto max1 = 0;
        auto max2 = 0;
        for (size_t index = 0; index < v.size(); ++index)
        {
            if (v[index] > max1)
            {
                max2 = max1;
                max1 = v[index];
            }
            else
            {
                max2 = std::max(max2, v[index]);
            }
        }

        std::cout << (long long) max1 * max2 << std::endl;
    }
    return 0;
}


Posted by at No comments:

Tuesday, June 14, 2016

SPOJ Challenges 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
      #include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    // your code goes here
    auto t = 0;
    std::cin >> t;
    
    for (auto c = 0; c < t; ++c)
    {
        auto s = 0, e = 0;
        std::cin >> s >> e;
 
        auto isprime = true;
        auto i = 0;
 
        for (i = s; i <= e; ++i)
        {
            if (i == 1) continue;
 
            isprime = true;
            int x = (int)std::sqrt(i);
 
            for (int f = 2; f <= x; ++f)
            {
                if (i % f == 0)
                {
                    isprime = false;
                    break;
                }
            }
 
            if (isprime)
            {
                std::cout << i << std::endl;
            }
        }
    }
    return 0;
} 
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
      #include <iostream>
using namespace std;
 
int main() {
 // your code goes here
 auto x = 0;
 while(std::cin >> x)
 {
  if(x == 42) break;
  std::cout << x << std::endl;
 }
 return 0;
}
Posted by at No comments:

Sunday, June 5, 2016

LeetCode Challenges 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        
        bool same = false;
        
        if((p != null) && (q != null))
        {
            bool leftTreeSame = IsSameTree(p.left, q.left);
            bool rightTreeSame = IsSameTree(p.right, q.right);
            same = leftTreeSame && rightTreeSame;            
            same = same && (p.val == q.val ? true : false);
        }

        return same;
    }
}

  • Invert Binary Tree
    • In-Place Recursive Solution (Huge improvement possible if a check for null is added before recursing root.left and root.right)
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private void PreOrder(TreeNode root)
    {
        if (root == null) return;            
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        PreOrder(root.left);
        PreOrder(root.right);
    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        PreOrder(root);
        return root;
    }
}
    • Not In Place (Has a very bad run time performance)
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
      /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode minvertedroot;
    
    private void PreOrder(TreeNode root, TreeNode invertedroot)
    {
            if (root == null || invertedroot == null) return;

            TreeNode left = null;
            if (root.left != null)
            {
                left = new TreeNode(root.left.val);
            }

            TreeNode right = null;
            if (root.right != null)
            {
                right = new TreeNode(root.right.val);
            }

            invertedroot.val = root.val;
            invertedroot.left = right;
            invertedroot.right = left;

            if (root.right != null)
            {
                PreOrder(root.right, invertedroot.left);
            }

            if (root.left != null)
            {
                PreOrder(root.left, invertedroot.right);
            }

    }

    public TreeNode InvertTree(TreeNode root)
    {
        if (root == null) return root;
        minvertedroot = new TreeNode(root.val);
        PreOrder(root, minvertedroot);
        return minvertedroot;
    }
}


       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
      class Solution {
private:
    void Transpose(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = row; col < cols; ++col)
            {
                std::swap(matrix[row][col], matrix[col][row]);
            }
        }
    }

    void SwapCols(vector<vector<int>>& matrix)
    {
        auto rows = matrix.size();
        auto cols = rows;

        for (auto row = 0UL; row < rows; ++row)
        {
            for (auto col = 0UL; col < cols / 2; ++col)
            {
                std::swap(matrix[row][col], matrix[row][cols - col - 1]);
            }
        }
    }

public:
    void rotate(vector<vector<int>>& matrix) {
        Transpose(matrix);
        SwapCols(matrix);
    }
};

int main()
{
    int n = 3;

    vector<vector<int>> v(n, std::vector<int>{});

    int start = 1;
    for (auto index = 0; index < n; ++index)
    {
        std::vector<int> row(n, 0);
        for (int v = 0; v < n; ++v)
        {
            row[v] = start++;
        }
        v[index].swap(row);
    }

    Solution s;
    s.rotate(v);

    for (auto const &e : v)
    {
        for (auto const &i : e)
        {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
}

Posted by at No comments:

Tuesday, May 31, 2016

HackerEarth Challenges

Posted by at No comments:

GenomicRangeQuery (Codility)

Problem Statement: GenomicRangeQuery

C++ Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++11 (g++ 4.8.2)
    std::vector<int> A(S.size(), 0);
    std::vector<int> C(S.size(), 0);
    std::vector<int> G(S.size(), 0);
    std::vector<int> T(S.size(), 0);

    auto index = 0;

    for (auto const &e : S)
    {
        if (e == 'A')
        {
            A[index]++;
        }
        else if (e == 'C')
        {
            C[index]++;
        }
        else if (e == 'G')
        {
            G[index]++;
        }
        else if (e == 'T')
        {
            T[index]++;
        }

        if (index > 0)
        {
            A[index] += A[index - 1];
            C[index] += C[index - 1];
            G[index] += G[index - 1];
            T[index] += T[index - 1];
        }
        ++index;
    }

    // At this time, A[i] is the total number of times A 
    // has been seen in the input string S until index i
    // So on with C, G and T vectors

    // Now we will check A, C, G and T arrays in that order
    // as this is the impact order as well (low to high)
    std::vector<int> retVal(P.size(), 0);

    for (auto index = 0; index < P.size(); ++index)
    {
        auto begin = P[index];
        auto end = Q[index];
        
        auto value = 1;
        
        do 
        {
            value = 1;
            bool bASeen = (begin == 0 && A[end] > 0) || (begin > 0) && A[end] > A[begin - 1];
            if (bASeen) break;

            value = 2;
            bool bCSeen = (begin == 0 && C[end] > 0) || (begin > 0) && C[end] > C[begin - 1];
            if (bCSeen) break;

            value = 3;
            bool bGSeen = (begin == 0 && G[end] > 0) || (begin > 0) && G[end] > G[begin - 1];
            if (bGSeen) break;

            value = 4;
            bool bTSeen = (begin == 0 && T[end] > 0) || (begin > 0) && T[end] > T[begin - 1];
            if (bTSeen) break;
        } while (0);

        retVal[index] = value;
    }
    return retVal;
}

C# Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int[] solution(string S, int[] P, int[] Q) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] A = new int[S.Length];
        int[] C = new int[S.Length];
        int[] G = new int[S.Length];
        int[] T = new int[S.Length];

        for (var i = 0; i < S.Length; ++i)
        {
            A[i] = 0;
            C[i] = 0;
            G[i] = 0;
            T[i] = 0;
        }

        var index = 0;

        foreach (var e in S)
        {
            if (e == 'A')
            {
                A[index]++;
            }
            else if (e == 'C')
            {
                C[index]++;
            }
            else if (e == 'G')
            {
                G[index]++;
            }
            else if (e == 'T')
            {
                T[index]++;
            }

            if (index > 0)
            {
                A[index] += A[index - 1];
                C[index] += C[index - 1];
                G[index] += G[index - 1];
                T[index] += T[index - 1];
            }
            ++index;
        }

        // At this time, A[i] is the total number of times A 
        // has been seen in the input string S until index i
        // So on with C, G and T vectors

        // Now we will check A, C, G and T arrays in that order
        // as this is the impact order as well (low to high)
        int[] retVal = new int[P.Length];
        for (var j = 0; j < P.Length; ++j)
        {
            retVal[j] = 0;
        }

        for (var k = 0; k < P.Length; ++k)
        {
            var begin = P[k];
            var end = Q[k];

            var value = 1;

            do
            {
                value = 1;
                bool bASeen = (begin == 0 && A[end] > 0) || (begin > 0) && A[end] > A[begin - 1];
                if (bASeen) break;

                value = 2;
                bool bCSeen = (begin == 0 && C[end] > 0) || (begin > 0) && C[end] > C[begin - 1];
                if (bCSeen) break;

                value = 3;
                bool bGSeen = (begin == 0 && G[end] > 0) || (begin > 0) && G[end] > G[begin - 1];
                if (bGSeen) break;

                value = 4;
                bool bTSeen = (begin == 0 && T[end] > 0) || (begin > 0) && T[end] > T[begin - 1];
                if (bTSeen) break;
            } while (false);

            retVal[k] = value;
        }
        return retVal;
    }
}

Learnings

  • This website helped me a lot to understand the concept of prefix sum applied to this problem.
Posted by at No comments:

Monday, May 30, 2016

CountDiv (Codility)

Problem Statement: CountDiv

C++ Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int A, int B, int K) {
    // write your code in C++11 (g++ 4.8.2)
    auto count = 0;

    auto start = A % K;
    if (start != 0)
    {
        start = (A + K) / K * K;
    }
    else
    {
        count++;
        start = A;
    }

    if (start > B) return 0;

    auto end = B % K;
    if (end != 0)
    {
        end = (B / K) * K;
    }
    else
    {
        count++;
        end = B;
    }

    count = (end - start) / K + 1;
    return count;
    
}

Learnings

  • Diff between B and A is not the right approach
For the input (11, 34, 17), the range i.e. B - A is 23 and dividing this by 17 gives 1. However, this is incorrect as the number 17 and 34 are divisible by 17 making the answer as 2.
Posted by at No comments:

Sunday, May 29, 2016

Passing Cars (Codility)

Problem Statement: PassingCars

C++ Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// you can use includes, for example:
 #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    auto goingEast = 0;
    auto pairsPassing = 0;

    for (auto &e : A)
    {
        if (e == 0)
        {
            goingEast++;
        }
        else if (e == 1)
        {
            pairsPassing += goingEast;
            if (pairsPassing > 1000000000) return -1;
        }
    }

    return pairsPassing;
}

C# Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        var eastBound = 0;
        var pairsCrossing = 0;
        
        foreach(var car in A)
        {
            if(car == 0)
            {
                eastBound++;
            }
            else if(car == 1)
            {
                pairsCrossing += eastBound;
                if(pairsCrossing > 1000000000) return -1;
            }
        }
        return pairsCrossing;
    }
}

Learnings

  • counting number of 1s or west bound cars
My initial idea was to go through the entire array and then count number of west bound cars. Then, traverse the array again and each time a 0 i.e. east bound car is encountered, update the west bound car count. Each time a 1 i.e. west bound car is encountered, simply decrement the count of west bound cars. This approach has one failed test case. I still need to analyze why. After this, however I figured out that it is possible to have a solution without doing an initial pass to find number of west bound cars.
Posted by at No comments:
Subscribe to: Posts (Atom)