Informatica Question: Given a transaction log in which each line contains a transaction detail (Customer Id, Customer name, Price), Find out the average price given by a customer.

Solution:

1. Read each line, extract customer id and price.

2. Maintain a hash in which key is customer id and value is pointer to struct defined as below -
    struct details
    {
       long totalPrice;
       int count;
     };

3. For each transaction do
    i.  hash[customerId]->totalPrice += extractedPrice;
    ii. hash[customerId]->count++;

4. Now for given customer, average price = hash[customerId]->totalPrice / hash[customerId]->count;

Range Minimum Query

You can find the description and implementation using c++ of Range Minimum Query(RMQ) in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#RMQ

Knuth-Morris-Pratt Algorithm: String Matching in Linear time

You can find the description and implementation using c++ of Knuth Morris Pratt ( KMP)  in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#Knuth

Count Sort: Sorting in linear time

You can find the description and implementation using c++ of Count Sort in the following link -

http://algods-cracker.blogspot.com/p/algorithms.html#Count

[Amazon] Find Least Common Ancestor of two nodes in a Binary Tree

Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Input: root = [1,2], p = 1, q = 2
Output: 1

Approach: Its an straight forward solution which can be understood by just looking at the code. Please note that we are using Post order traversal approach here.

Implementation in C#:

       public TreeNode LowestCommonAncestor(TreeNode root,

                                         TreeNode p,

                                         TreeNode q)

    {

        if (root == null)

        {

            return null;

        }

        if (root == p || root == q)

        {

            return root;

        }

        TreeNode leftLCA = this.LowestCommonAncestor(root.left, p, q);

        TreeNode rightLCA = this.LowestCommonAncestor(root.right, p, q);

        if (leftLCA != null && rightLCA != null)

        {

            return root;

        }

        else if (leftLCA != null)

        {

            return leftLCA;

        }

        else if (rightLCA != null)

        {

            return rightLCA;

        }

        return null;

    }

Complexity: O(n)

Amazon Question: Set inorder successor of each node of Binary Tree

Solution:
1. Do reverse inorder traversal.
2. Set inorder successor to the previous node.

Source Code:
// Given node structure -

struct Node
{
int data;
Node* left;
Node* right;
Node* inorderSuccessor;
};


void BSTree::fillInorderSuccessor(Node* node, Node*& prev)
{
if(node)
{
fillInorderSuccessor(node->right, prev);
node->inorderSuccessor = prev;
prev = node;
fillInorderSuccessor(node->left, prev);
}
}

Amazon Question: Find number of vertical lines that can cover whole nodes of Binary Tree

Solution:

1. Do a preorder traversal.
2. Initialize count to 0.
3. Whenever encounter a left node increase count by 1.
4. Whenever encounter a right node decrease count by 1.
5. Return maxCount - minCount + 1.

Source Code:

int BTree::findVerticalLinesToCut(Node* node, int count)
{
static int max = 0, min = 0;
if(node)
{
max = max < count? count : max;
min = min > count ? count : min;

if(node->left)
{
findVerticalLinesToCut(node->left, count+1);
}
if(node->right)
{
findVerticalLinesToCut(node->right, count-1);
}
}
return max - min + 1;
}

Find the maximum sum of sub array within an array.

Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Approach: This is simple Kadane's Algorithm. Just look at the implementation to understand the approach.

Implementation in C#:

    public int MaxSubArray(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return int.MinValue;

        }

        int max = int.MinValue;

        int currSum = 0;

        int maxSum = int.MinValue;

        for (int i = 0; i < length; ++i)

        {

            if (max < nums[i])

            {

                max = nums[i];

            }

            currSum += nums[i];

            if (currSum < 0)

            {

                currSum = 0;

            }

            else

            {

                maxSum = Math.Max(currSum, maxSum);

            }

        }

        return max < 0 ? max : maxSum;

    }

Complexity: O(n)

[GFG][Amazon] Find the missing and repeating number

Problem: You are given an array of n+2 elements. All elements in the array are in range 1 to n and all elements occur once except two numbers which occur twice. Find the two repeating numbers.

Example:

Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 2 is missing and 3 occurs twice 

Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1

Approach: We are going to use xor here.

Implementation in C++:

vector<int> findTwoElement(vector<int> arr, int n)

{

        // code here

        int xor1 = arr[0];

        for (int i = 1; i < n; ++i)

        {

            xor1 ^= arr[i];

        }

        

        for (int i = 1; i <= n; ++i)

        {

            xor1 ^= i;

        }

        

        int setBit = xor1 & ~(xor1 - 1);

        int x = 0, y = 0;

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

        {

            if (arr[i] & setBit != 0)

            {

                x ^= arr[i];

            }

            else

            {

                y ^= arr[i];

            }

        }

        for (int i = 1; i <= n; ++i)

        {

            if (i & setBit != 0)

            {

                x ^= i;

            }

            else

            {

                y ^= i;

            }   

        }

        vector<int> result;

        result.push_back(x);

        result.push_back(y);

        return result;

    }

Complexity: O(n)

[Amazon] Sort array which contains only 0, 1 or 2 in O(n)

Problem: Sort an array which contains only 0, 1 or 2. The time complexity should not be more than O(n).

Example:

Input: arr = [0, 1, 2, 0, 1, 1, 2]
Output: [0, 0, 1, 1, 1, 2, 2]

Approach: We will use three pointer approach here.

Implementation in C#:

    public void SortColors(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return;

        }

        int low = 0;

        int high = length - 1;

        for (int mid = 0; mid <= high;)

        {

            Console.WriteLine($"{mid}: {nums[mid]}");

            switch(nums[mid])

            {

                case 0: this.Swap(nums, low++, mid++);

                    break;

                case 1: mid++;

                    break;

                case 2: this.Swap(nums, mid, high--);

                    break;

            }

        }

    }

    private void Swap(int[] nums, int i, int j)

    {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

Complexity: O(n)