Interview Questions Design Patterns

Q: What design pattern is used to implement a Synchronized HashMap?

A: Decorator Pattern
Decorator pattern allows a user to add new functionality to an existing object without altering its structure. This type of design pattern comes under structural pattern as this pattern acts as a wrapper to existing class.

This pattern creates a decorator class which wraps the original class and provides additional functionality keeping class methods signature intact.

We are demonstrating the use of decorator pattern via following example in which we will decorate a shape with some color without alter shape class.

Synchronized HashMap Decorator Pattern Example

import java.util.Collections; 
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.Set;

public class HashMapSynchronizationDemo{

		    public static void main(String args[]) {

	        Map<String, String> currencies = new HashMap<String, String>();

				currencies.put("USA", "USD"); 
				currencies.put("England", "GBP"); 
				currencies.put("Canada", "CAD"); 
				currencies.put("HongKong", "HKD"); 
				currencies.put("Australia", "AUD");

	        currencies = Collections.synchronizedMap(currencies);
	        Set<String> keySet = currencies.keySet();  

	        synchronized(currencies) {  
				Iterator<String> itr = keySet.iterator();
	            while (itr.hasNext()){
						System.out.println(itr.next()); 
			} 
		} 
	} 
} 

Output
USA
Canada
HongKong
England
Australia

Another Decorator Pattern Example

import java.util.ArrayList;
import java.util.ListIterator;


public class ChaiDecorator extends Tea {
    private Tea teaToMakeChai;
    private ArrayList chaiIngredients = new ArrayList();
    
    public ChaiDecorator(Tea teaToMakeChai) {
        this.addTea(teaToMakeChai);
        chaiIngredients.add("bay leaf");
        chaiIngredients.add("cinnamon stick");
        chaiIngredients.add("ginger");
        chaiIngredients.add("honey");
        chaiIngredients.add("soy milk");
        chaiIngredients.add("vanilla bean");
    }


    private void addTea(Tea teaToMakeChaiIn) {
        this.teaToMakeChai = teaToMakeChaiIn;
    }
    
    public void steepTea() {
        this.steepChai();
    }


    public void steepChai() {
        teaToMakeChai.steepTea();
        this.steepChaiIngredients();
        System.out.println("tea is steeping with chai");
    }    
    
    public void steepChaiIngredients() {
        ListIterator listIterator = chaiIngredients.listIterator();
        while (listIterator.hasNext()) {
            System.out.println(((String)(listIterator.next())) + 
                                         " is steeping");
        }
        System.out.println("chai ingredients are steeping");
    }      
}

QUESTION 2

You are given an unsorted binary array.

Example [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]

And a letter K, which represents the number of swap operations allowed on this binary array.

You need to find out the maximum length continuous subarray that can be generated using K many swaps.

Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9.

QUESTION 3

You are given a binary matrix with each row sorted.
That means each row will have zeros at the front and ones at the back. You need to find out which row which contains a maximum number of ones.

Example:

[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]
[0 0 0 0 0 0 1 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]

Answer : Second row and Sixth with 8 ones.
You will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

QUESTION 4

Design a system to monitor services (like when they were down/ CPU time) etc.

QUESTION 5

Design a system for dashboard that effectively shows almost real time data.

QUESTION 6

Implement a stack that in addition to push and pop has a function that returns the min value of the stack.

I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.

QUESTION 7

Given a sorted array with “n” elements, distributed them into “k” nearly equally weighing buckets.

Space is not constraint.

Ex: [1,3,6,9,10]
bucket size: 3

output:[10],[9,1],[3,6]

QUESTION 8

Add two link list, can not modify the link list, can not reverse the link list first and second.

Link list 1 – 1->2->3->7
Link list 2 – 2->9
Output Sum – 1->2->6->6

Solution:
Iterate through the two lists twice. First time get the difference in length. Second time get the sum at every digit (allow a node to have 2 digits). And then iterate through the new result array once to deal with the carry.

public ListNode add(ListNode head1, ListNode head2) {


        if(head1 == null || head2 == null) {
            return head1 == null? head2: head1;
        }

        int diff = 0; //get the difference in lengths of the two lists

        ListNode p1 = head1, p2 = head2;
        while(p1 != null && p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        ListNode longer = p1 == null? head2: head1;
        ListNode shorter = p1 == null? head1: head2;

        while(p1 != null) {
            p1 = p1.next;
            diff++;
        }

        while(p2 != null) {
            p2 = p2.next;
            diff++;
        }

        ListNode dump = new ListNode(0);  //create a dummy head for the result list
        ListNode curr= dump;

        while(diff > 0) {   //create the longer part of the longer list
            diff--;
            curr.next = new ListNode(longer.val);
            longer = longer.next;
            curr = curr.next;
        }

        while(longer != null) { //add the two lists
            curr.next = new ListNode(longer.val + shorter.val);
            curr = curr.next;
            longer = longer.next;
            shorter = shorter.next;
        }

        curr = dump;
        ListNode carry = dump;
        while(curr != null) {       //carry always points at the number smaller than 9
            if(curr.val < 9) {      //when a carry is found at current node, add 1 to carry and change anything after carry and before curr to 0
                carry = curr;
            } else if(curr.val > 9){
                carry.val++;
                carry = carry.next;
                while(carry != curr) {
                    carry.val = 0;
                    carry = carry.next;
                }
                curr.val %= 10;
            }
            curr = curr.next;
        }

        return dump.val == 0 ? dump.next: dump;

    }

ANOTHER SOLUTION:

public class AddTwoLinkedList {

	
	public static void main(String[] args) {
		LL l2_4 = new LL(7, null);
		LL l2_3 = new LL(3, l2_4);
		LL l2_2 = new LL(2, l2_3);
		LL l2_1 = new LL(1, l2_2);
		
		LL l1_2 = new LL(9, null);
		LL l1_1 = new LL(2, l1_2);
		
		
		
		int s1 = 0;
		LL l1 = l1_1;
		while(l1 != null){
			l1 = l1.next;
			s1++;
		}
		int s2 = 0;
		LL l2 = l2_1;
		while(l2 != null){
			l2 = l2.next;
			s2++;
		}
		int c = s2-s1-1;
		LL prev = new LL(0, null);
		LL h = prev;
		while(c > 0){
			LL l = new LL(0, null);
			prev.next = l;
			prev = l;
			c--;
		}
		prev.next = l1_1;
		
		int carry = addLinkedList(l2_1, h, 0);
		LL lh = l2_1;
		if(carry > 0){
			lh = new LL(carry, l2_1);
		}
		
		while(lh != null){
			System.out.print(lh.val + " ");
			lh = lh.next;
		}
	}
	
	static int addLinkedList(LL l1, LL l2, int carry){
		if(l1 == null && l2 == null) return carry;
		
		carry = addLinkedList(l1.next, l2.next, carry);
		
		if(l1 != null && l2 != null){
			int sum = l1.val + l2.val + carry;
			if(sum > 9){
				String str = String.valueOf(sum);
				int toAdd = Integer.parseInt(str.substring(1,str.length()));
				carry = Integer.parseInt(str.substring(0,1));
				l1.val = toAdd;
			}else{
				l1.val = sum;
				carry = 0;
			}
		}
		return carry;
	}
	
}
class LL{
	int val;
	LL next;
	public LL(int val, LL next){
		this.val = val;
		this.next = next;
	}

ANOTHER SOLUTION

We must traverse both lists from their ends toward their beginnings. We can traverse one of the lists starting from the end via a recursive function, but it is a challenge to coordinate two different length lists that way. So we can traverse the other list first, pushing its elements into a stack. Then, as we unwind the recursion of the one list, we pop the elements of the converted list. In case the recursed list is shorter than the “stacked” list, we pop the rest of the elements, creating prefixing the “sum” with the elements of the stack that hadn’t been “added”. No counting necessary, O(m+n) time

In raw JavaScript, with a little NodeJS-ism for output:

// A Linked-list class
function LL(data, next) {
	// console.log("insert "+data)
	this.data = data;
	this.next = next;
}
LL.prototype.print = function () {
	process.stdout.write(this.data.toString())
	if (this.next) {
		process.stdout.write('-> ')
		this.next.print()
	}
	else
		process.stdout.write('\n')
}

// Recursive function to add a "stack" to a Linked-list
function _add(stack, list) {
	let sum;
	if (! list.next ) {
		sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data, null)
	}
	else {
		sum = _add(stack, list.next)
		sum = new LL((stack.length == 0 ? 0 : stack.pop()) + list.data,
							  sum)
		if (sum.next.data > 9) {
		  sum.next.data -= 10
		  sum.data += 1
		}
	}
	return sum
} // _add()

// This is the function solution to the exercise:
function addLists( L1, L2 ) {
	let stack=[];						// Tempoary data struct
	for (let i=L1; i; i=i.next)	// Fill the stack w/one list
		stack.push(i.data)

	let sum = _add(stack, L2)		// Add the revised list to the other list
	let carry = ( sum.data > 9 )
	if (carry) sum.data -= 10;		// If most signifant element overflowed...

	while (stack.length)	{			// While there are list elements left
		sum = new LL(stack.pop(), sum)
		if (carry) {					// Make sure handle the carry-over
			sum.data += 1;				// is added to the next digit
			carry = false;				// This only needs to be done once
		}
	}
	if (carry) {						// Make sure carry-over was handled
		sum = new LL(1, sum)			// adding a node, since no stack elements
	}										// were able to absorb it

	return sum;							// Return final list
} // addLists()

// Create test Linked-lists
var first	= new LL( 1, new LL( 2, new LL( 3, new LL(7))))
var second	= new LL( 2, new LL (9, null))

// Make sure they're constructed correctly
process.stdout.write("First list:  ")
first.print()
process.stdout.write("Second list: ")
second.print()
process.stdout.write("Sum:         ")
addLists(first,second).print()

ANOTHER SOLUTION

The challenge here is to do it using constant memory.
The time complexity is theta of n+m so we cant do anything there.
All the solutions you guys posted are garbage.

1. Iterate over lists to get their length.
2. Add each corresponding digit from left to right disregarding the carry. Lets call this S.
3. Add each digit and only consider the carry. 1 if it produces a carry 0 if not. Call this C.
4. Return S+C*10

1 2 3 7
2 9

Produces S=1256 and C=1.

O(n+m) time O(1) space.


ANOTHER SOLUTION
C# – O(N) time and O(1) space

public void Adding2LinkedList(LinkedListNode<int> one = null, LinkedListNode<int> sec = null)
        {
            int sum = 0;
            int carry = 0;
            var wholeSize = Math.Max(LengthOfLinkedList(one), LengthOfLinkedList(sec));
            var result = new LinkedList<int>();
            for (int i = 0; i < wholeSize; i++)
            {
                count = 0;
                var elemOne = FindTheKthLastElement(one, i);
                count = 0;
                var elemSec = FindTheKthLastElement(sec, i);
                sum = (elemOne + elemSec + carry) % 10;
                carry = (elemOne + elemSec + carry) / 10;
                result.AddFirst(sum);
            }


        }

        public int FindTheKthLastElement(LinkedListNode<int> list, int k)
        {
            int num = 0;
            if (list == null) return num;

            num = FindTheKthLastElement(list.Next, k);
            if (count++ == k)
                return list.Value;
            return num;
        }

        public int LengthOfLinkedList(LinkedListNode<int> list)
        {
            if (list == null) return 0;
            return 1 + LengthOfLinkedList(list.Next);
        }

LATEST SOLUTION

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
Node *tf = reverse(l1);
Node *ts = reverse(l2);
Node dummy;
Node *result = &dummy;
int carry =0,sum=0;

while (tf || ts || carry) {
sum = carry;
if (tf) {
sum += tf->data;
tf = tf->next;
}
if (ts) {
sum += ts->data;
ts = ts->next;
}
result->next = new Node(sum % 10);
carry = sum/10;
result = result->next;
}
return (reverse(dummy.next));
}


ListNode *reverse(ListNode *head) {
Node *curr = head;
Node *temp, *result;
temp = result = NULL;

while (curr) {
temp = curr->next;
curr->next = result;
result = curr;
curr = temp;
}

return result;
}

QUESTION 9


ANOTHER SOLUTION


ANOTHER SOLUTION


QUESTION 10


QUESTION 11


QUESTION 12


QUESTION 12


QUESTION 12


QUESTION 12


QUESTION 12


ANOTHER SOLUTION


ANOTHER SOLUTION


ANOTHER SOLUTION