[Adobe] Merge Sorted Array

Problem: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Approach: It's an simple implementatio problem. You can directly go to implementation to understand the approach.

Implementation in C#:

    public void Merge(int[] nums1, int m, int[] nums2, int n)

    {

        int writeIndex = m + n - 1;

        int num1Index = m - 1;

        int num2Index = n - 1;

        while(num1Index >= 0 && num2Index >= 0)

        {

            if (nums1[num1Index] > nums2[num2Index])

            {

                nums1[writeIndex--] = nums1[num1Index--];

            }

            else

            {

                nums1[writeIndex--] = nums2[num2Index--];

            }

        }

        while (num2Index >= 0)

        {

            nums1[writeIndex--] = nums2[num2Index--];

        }

    }

Complexity: O(m + n)

Adobe Question: Calculate square of a number without using arithmetic operators and inbuilt methods

Question: Calculate square of a number without using arithmetic operators like *, /, +, -. Obviously inbuilt methods like pow() can't be used.

Solution:

1: If the given number 'num' is even then:
    num = 2 * n
    so square(num) = square (2 * n) = 4 * square(n)

2: If num is odd then:
    num =  2 * n + 1
    so square(num) = square(2 * n +  1) = 4 * square(n) + 4 * n + 1

Implementation:

int square(int num)
{
if(num == 0 || abs(num) == 1)
return abs(num);

if(num < 0)
num = -num;

int half = num>>1;

if(num & 1)
return ((square(half)<<2) + (half<<2) + 1);
else
return (square(half)<<2);
}

Complexity: O(log(n))

Adobe Question: Url Encode a string

A buffer of infinite length is given. You need to change < to < and > to >

Solution:

void encode()
{
char str[2048] = "ab<bc>nn<";
int len = strlen(str);
int count = 0;
for(int i = 0; i < len; ++i)
{
(str[i] == '<' || str[i] == '>') && (++count);
}

int newLen = len + 3*count;
str[newLen] = '\0';
for(int i = newLen-1, j = len-1; j>=0; --j)
{
if(str[j] == '<' || str[j] == '>')
{
str[i--] = ';';
str[i--] = 't';
(str[j] == '<') && (str[i--] = 'l') || (str[i--] = 'g');
str[i--] = '&';
}
else
str[i--] = str[j];
}
cout<<'\n'<<str<<"\n\n";
}

[Adobe] Find median of infinite stream of numbers

Problem: The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [1, 2, 3], the median is 1.
• For example, for arr = [1, 2], the median is (1 + 2) / 2 = 1.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void AddNum(int num) adds the integer num from the data stream to the data structure.
• double FindMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Approach: Use one max heap and one min heap in following way:

• Max heap will be containing the numbers which are less than median.
• Min heap will be containing the numbers which are greater than or equals to median.
• Difference between the size of two heaps will never be greater than 1.

The numbers in max heap should be less than numbers in min heap so if the current number is less than or equal to the top of max heap then it will go to max heap otherwise it will go to min heap. 

We just need to take care of the violation of third condition after insertion.

When we try to find the median, we can just see if max heap has more elements than min heap (case of number of elements are odd) then we can return it's top otherwise its the case of even number so we can safely return (top of max heap + top of min heap) / 2.


Implementation in C#:

public class IntMaxCompare : IComparer<int>

{

    public int Compare(int x, int y) => y.CompareTo(x);

}

public class MedianFinder

{

    public MedianFinder()

    {

        this.maxHeap = new PriorityQueue<int, int>(new IntMaxCompare());

        this.minHeap = new PriorityQueue<int, int>();

    }

   

    public void AddNum(int num)

    {

        if (this.maxHeap.Count == 0 || this.maxHeap.Peek() >= num)

        {

            this.maxHeap.Enqueue(num, num);

        }

        else

        {

            this.minHeap.Enqueue(num, num);

        }

        if (this.maxHeap.Count > this.minHeap.Count + 1)

        {

            int elem = this.maxHeap.Dequeue();

            this.minHeap.Enqueue(elem, elem);

        }

        else if (this.maxHeap.Count < this.minHeap.Count)

        {

            int elem = this.minHeap.Dequeue();

            this.maxHeap.Enqueue(elem, elem);

        }

    }

   

    public double FindMedian()

    {

        if (this.maxHeap.Count > this.minHeap.Count)

        {

            return (double) this.maxHeap.Peek();

        }

        return (this.maxHeap.Peek() + this.minHeap.Peek()) / 2.0;

    }

    PriorityQueue<int, int> maxHeap;

    PriorityQueue<int, int> minHeap;

}

Complexity: AddNum - O(logn), FindMedian - O(1)

Adobe Question: Multiply two numbers using bitwise operators

Solution:

A =            101
B =              10
                  -------
                    000
                  101x             x here denotes a left shift by 1 bit.
                  -------
Result =      1010

The magic is to check for the last bit of B. If the last bit is 1, then add ‘A’ to result else do nothing. And after every check right shift ‘B’ by 1 bit and left shift ‘A’ by 1 bit.

To add two numbers using bitwise, you need to implement the full adder where you calculate sum and carry as below:
Sum = A xor B (A ^ B)
Carry = A and B (A & B)


Source:
int bitwiseMultiply(int a, int b)
{
int result = 0;
while ( b != 0)
{
if ( b & 1)
{
result = sum( a, result);
}
a = a << 1; b = b >> 1;
}
return result;
}

int sum (int a, int b)
{
int sum = 0;
int carry = 0;
while ( a )
{
carry = a & b;
sum = a ^ b;
carry = carry << 1;
a = carry;
}
return sum;
}

Adobe Question: Implement doubly link list with only one address field

Instead of storing next and previous pointer, store xor of next and previous pointers. Implementation is given below -

struct Node
{
    int data;
    int xor;
    Node(int d=0, int x=0):data(d), xor(x){}
};

class DList
{
public:
    DList(Node* h=0, Node* t=0):head(h){}
    void insert(int val); //insert at last position
    void traverse();
private:
    Node* head;
};

void DList::insert(int val)
{
    if(!head)
    {
        head = new Node(val);
    }
    else
    {
        Node* prev = head, *temp = (Node*)(head->xor);
        while(temp)
        {
            Node* temp1 = temp;
            temp = (Node*)((int)prev ^ temp->xor);
            prev = temp1;
        }
        temp = new Node(val, (int)prev);
        prev->xor ^= (int)temp;
    }
}

void DList::traverse()
{
    if(!head)
        return;
    Node* prev = head, *temp = (Node*)(head->xor);
    while(temp)
    {
        cout<<prev->data<<'\t';
        Node* temp1 = temp;
        temp = (Node*)((int)prev ^ temp->xor);
        prev = temp1;
    }
    cout<<prev->data<<'\n';
}

* Limitation of this approach is, we can traverse list only from head or tail (if given).

Adobe Question: Print paths from root to all leaves in a Binary Tree

Solution:

Do a preorder traversal and insert elements in vector, While returning from node, remove it from vetcor.
if a leaf is found print all the elements in Vector.


//Public interface
void BSTree::printAllpath()
{
    cout<<"\nAll paths from root to leaves::";
    vect.clear();  // vect is private vector<Node*> of BSTree class
    printAllpath(root);
}


//Actual working, Private member of BSTree class
void BSTree::printAllpath(Node* node)
{
    if(node)
    {
        vect.push_back(node->data);
        if(!(node->left) && !(node->right))
        {
            cout<<'\n';
            for(int i=0; i<vect.size(); ++i)
                cout<<vect[i]<<'\t';
            vect.pop_back();
            return;
        }
        printAllpath(node->left);
        printAllpath(node->right);
        vect.pop_back();
    }
}

Adobe Question: Generic Swap in C

void Swap(void* var1, void* var2, int size)
{
    void *temp = malloc(size);
    memcpy(temp,var1,size);
    memcpy(var1, var2, size);
    memcpy(var2, temp, size);
    free (temp);
}

Adobe Question: Implement Binary Search using one comparison per iteration.

Solution: 

// Search value in array a of length size
int binarySearch( int* a, int value, int low, int high, int size) 
{
    while (low < high)
    {
        int mid = low + ((high - low) / 2); // Avoid overflow (low + high)
           if (a[mid] < value)
               low = mid + 1;
           else
                //can't be high = mid-1: as a[mid] >= value,
                //so high can't be < mid as a[mid] can be = value
                high = mid;
    }
       // high == low
       if ((low < size) && (a[low] = = value))
           return low; // found
       else
           return -1; // not found
}