CareerCup

Clazz is heavier to lock. You can check the result with below code.
To put the mutex on it would take more time.

import java.util.Date;

public class Try {
public static void main(String[] args) throws InterruptedException {
Date d = new Date();
final Try2 t2 = new Try2();
for (int i = 0; i < 100000; i++) {
Thread t = new Thread() {
public void run() {
t2.test();
}
};
t.start();
t.join();
}
Date d2 = new Date();
System.out.println(d2.getTime() - d.getTime());


d = new Date();
for (int i = 0; i < 100000; i++) {
Thread t = new Thread() {
public void run() {
Try1.test();
}
};
t.start();
t.join();
}
d2 = new Date();

System.out.println(d2.getTime() - d.getTime());
}
}

class Try1 {
public static synchronized void test() {

}
}

class Try2 {
public synchronized void test() {

}
}

public void swapNode(Node node, int k){
		this.k = k;
	
		if(k < 0){
			System.out.println("Provide valid value for k");
			return;
		}

		if(node == null){
			System.out.println("Linked list is empty");
			return;
		}
			
		swapNode(node);
		
		if(first == null || last == null){
			System.out.println("K should be less than N");
			return;
		}
		
		int temp = first.data;
		first.data = last.data;
		last.data = temp;
	}
	
	private void swapNode(Node node) {
		if(node.next != null){
			firstN++;
			if(firstN == k)
				first = node;
			
			swapNode(node.next);
		}
		
		lastN++;
		if(lastN == k)
			last = node;
	}

public void swapNode(Node node, int k){
this.k = k;

if(k < 0){
System.out.println("Provide valid value for k");
return;
}

if(node == null){
System.out.println("Linked list is empty");
return;
}

swapNode(node);

if(first == null || last == null){
System.out.println("K should be less than N");
return;
}

int temp = first.data;
first.data = last.data;
last.data = temp;
}

private void swapNode(Node node) {
if(node.next != null){
firstN++;
if(firstN == k)
first = node;

swapNode(node.next);
}

lastN++;
if(lastN == k)
last = node;
}

There is something called, Composite design pattern, I think interview would expecting that word from you.

public class ReturnDuplicate {
	public static void main(String[] args) {
		int array[] = new int[]{2,1,2,4,3,1,5,1};
		int[] duplicates = getDuplicates(array);
		for(int i=0; i<duplicates.length;i++)
			System.out.println(duplicates[i]);
	}

	private static int[] getDuplicates(int[] array) {
		HashSet<Integer> uniqueSet = new HashSet<Integer>();
		ArrayList<Integer> duplicates = new ArrayList<Integer>();
		
		for(int i=0 ; i< array.length; i++){
			Integer item = array[i];
			if(uniqueSet.remove(item))
				duplicates.add(item);
			else
				uniqueSet.add(item);
		}
		
		int[] dupArray = new int[duplicates.size()];
		for(int i=0; i< duplicates.size(); i++)
			dupArray[i] = duplicates.get(i);
		
		return dupArray;
	}
}

public class LongestSubStringWith2Char {
	
	public String findString(String str){
		int firstFreq, nextFreq, totalCount, end = 0;
		Character firstChar, secondChar;
		
		//Initially make the characters and frequencies to numm
		firstChar = secondChar = null;
		firstFreq = nextFreq = totalCount=0;
		
		for(int i=0; i<str.length(); i++){
			char ch = str.charAt(i);
			
			//Increase the frequecy based on the character found
			if(firstChar == null){
				firstChar = ch;
				firstFreq++;
			}
			else if(ch == firstChar)
				firstFreq++;
			else if(secondChar == null){
				secondChar = ch;
				nextFreq++;
			}
			else if(ch == secondChar)
				nextFreq++;
			
			// If character is not in the last two list, start new sequence
			if(ch != firstChar && ch != secondChar){
				firstChar = secondChar;
				firstFreq = nextFreq;
				secondChar = ch;
				nextFreq = 1;
			}
			
			//If the sequece is bigger than previous found, make this a bigger
			if(totalCount < nextFreq + firstFreq){
				end = i+1;
				totalCount = firstFreq + nextFreq;
			}
		}
		
		return str.substring(end - totalCount, end);
	}
	
	public static void main(String[] args) {
		LongestSubStringWith2Char demo = new LongestSubStringWith2Char();
		System.out.println(demo.findString("aabbcbbbadef"));
		System.out.println(demo.findString("aabbaacdef"));
		System.out.println(demo.findString("abbbbbbaddeeffff"));
		System.out.println(demo.findString("ffeeeeeeeeeeedddddddddddbbbbbbbbbaaaaaa"));
	}
}

It will print :

4565676,4565678,4567654,4567656,4567676,4567678,4567876,4567878,4567898,5432101,5432121,5432123,5432321,5432323,5432343,5432345,5434321,5434323,5434343,5434345,5434543,5434545,5434565,5434567,5454321,5454323,5454343,5454345,5454543,5454545,5454565,5454567,5456543,5456545,5456565,5456567,5456765,5456767,5456787,5456789,5654321,5654323,5654343,5654345,5654543,5654545,5654565,5654567,5656543,5656545,5656565,5656567,5656765,5656767,5656787,5656789,5676543,5676545,5676565,5676567,5676765,5676767,5676787,5676789,5678765,5678767,5678787,5678789,5678987,5678989,6543210,6543212,6543232,6543234,6543432,6543434,6543454,6543456,6545432,6545434,6545454,6545456,6545654,6545656,6545676,6545678,6565432,6565434,6565454,6565456,6565654,6565656,6565676,6565678,6567654,6567656,6567676,6567678,6567876,6567878,6567898,6765432,6765434,6765454,6765456,6765654,6765656,6765676,6765678,6767654,6767656,6767676,6767678,6767876,6767878,6767898,6787654,6787656,6787676,6787678,6787876,6787878,6787898,6789876,6789878,6789898,7654321,7654323,7654343,7654345,7654543,7654545,7654565,7654567,7656543,7656545,7656565,7656567,7656765,7656767,7656787,7656789,7676543,7676545,7676565,7676567,7676765,7676767,7676787,7676789,7678765,7678767,7678787,7678789,7678987,7678989,7876543,7876545,7876565,7876567,7876765,7876767,7876787,7876789,7878765,7878767,7878787,7878789,7878987,7878989,7898765,7898767,7898787,7898789,7898987,7898989,8765432,8765434,8765454,8765456,8765654,8765656,8765676,8765678,8767654,8767656,8767676,8767678,8767876,8767878,8767898,8787654,8787656,8787676,8787678,8787876,8787878,8787898,8789876,8789878,8789898,8987654,8987656

package com.trails;

public class NumberGenerator {
	static int start = 4565676;
	static int end = 8987656;
	
	static int sDigit;
	static int eDigit;
	
	public static int getDigit(int number){
	    int counter = 0;
	    while(number != 0){
	       counter++;
		number = number / 10;
	     }
		return counter;
	}
	
	public static int getFirstDigit(int number){
		while(getDigit(number) != 1){
			number = number / 10;
		}
		
		return number;
	}
	
	public static void main(String[] args) {
		sDigit = getDigit(start); // Find total number of Digit
		eDigit = getDigit(end); // Find total number of Digit
		
		int firstNode = getFirstDigit(start); // Get first digit of end
		int lastNode = getFirstDigit(end); // Get first digit of end

		// Till first digit <= last digit
		while(firstNode <= lastNode){
			generateNumbers(firstNode, firstNode, 1);
			firstNode++;
		}
	}

      private static void generateNumbers(int number, int currentNode, int digit) {
	      // if current number of digits are more than start digits and number is in range
	     if(digit >= sDigit && number >= start && number <= end){
			System.out.print(number+ ",");
			return;
		}
		
		// If number contains more digits than the end stop immediately
		if(digit > eDigit)
			return;

	//If current digit for processing is 0, stop this branch
	if(currentNode != 0)
	     generateNumbers(10 * number + (currentNode-1), currentNode - 1, digit + 1);
		
	//If current digit for processing is 9, stop this branch
	if(currentNode != 9)
	    generateNumbers(10 * number + (currentNode + 1), currentNode + 1, digit + 1);
    }
}

Nice :-)

Krish, I am not traversing in n elements rather, I am traversing in possible sulution. For an example if i need to find a number between 100 to 200, then possible tree would be

1
0 1
-1 1 0 2

Now you need to check
10-1 (This will not be checked as it reached to 0 )
101
110
112

This means you don't have to traverse 100 to 200 elements (99 elements ). Please correct if I am wrong.

you can do using hashing. Lets assume you have only a...z characters.
Generate 26 prime numbers and keep in an array.

char[ ] nonDuplicateArray;

for(every character C in string ){
if(hash % prime[C-'a'] == 0){
// This means character's prime already multiplied earlier
continue;
}

hash <- hash * prime[C-'a'] ; // This will keep multiplying prime numbers
Add this character to non duplicate array.
}

This exactly O(n) time complexity.

There are lots of string search algorithms.

1. Brute force ( Moving by 1 till end )
2. Rabin Karp ( Use rollover hashing )
3. Horspool ( Shifting to last matched item )
4. KMP ( Create DFA and use it for searching )

You can use any of the above four. I feel KMP is faster then others when string contains repeated characters.

private static void findEvenOddSum(Node node) {
		// Add the root node
		List<Node> list = new ArrayList<Node>();
		list.add(node);
		// Pass the arguments, 
		//list : Nodes to process at current level, isOdd : level is odd or even 3. difference : difference between odd and even
		findSum(list, true, 0);
	}

	private static void findSum(List<Node> list, boolean isOdd , int difference) {
		final int elementSize = list.size();
		//If no more elements to process
		if(elementSize == 0){
			System.out.println("Difference between odd and even is : " + difference);
			return;
		}
		
		int sumAtLevel = 0;
		//Find the nodes for processing
		for(int i=0; i< elementSize; i++){
			//Take from the list and remove. We can use queue instead
			Node n = list.get(0);
			list.remove(0);
			
			//Add to sum at current level
			sumAtLevel += n.data; 
			
			// Find the left node for further processing
			if(n.left != null)
				list.add(n.left);
			
			//Find the right node for further processing
			if(n.right != null)
				list.add(n.right);
		}
		
		// Operate on difference based on the level
		if(isOdd)
			difference += sumAtLevel;
		else
			difference -= sumAtLevel;
		
		// Switch the level and pass the other items
		findSum(list, !isOdd, difference);
			
	}

package com.trails;

import java.util.Arrays;
import java.util.HashSet;

public class Try {

	public static void main(String[] args) {
		Try t = new Try();
		Integer[] items = new Integer[]{-5,6,7,1,0,12,5,-6,100};
		HashSet<Integer> values = new HashSet<Integer>(Arrays.asList(items));
		t.findSubset(values, 13);
			
	}

	private void findSubset(HashSet<Integer> values, int target) {
		int count = 0;
		for(Integer value : values){
			if(values.contains(target - value)){
				count++;
				System.out.println("Value 1 : " + value + " Value 2 : " + (target-value) + " Target : " + target);
			}
		}
		
		if(count == 0)
			System.out.println("Value not found to make target : " + target);
	}
}

It is very simple problem. For every start to end first digit, we need to create a tree. For example 500000 to 600000 is given range that we need to create a binary tree where left child is one less than the parent digit and right child is 1 greater the parent digit.

After the tree constructed, take root and do all traversal to all possible leaf at level count ( decimal points of start ) and generate a number for such branch.

Check is this number is in limit, if yes print it. Like this keep doing till the first digit <= last. No need to do traverse like this for(int i=start;i<end+1;i++).

If first array will be size of 99999 records and second will have 3 records, you have to do much operations. You should use binary search logic to find the next array rather than linear approach.

Semaphore is for signaling and mutex is for lock.
When you want a lock on a object and you want to keep other threads waiting, you can use synchronized keyword. The object under synchronized block will be locked and no other thread can use it.

While wait(), notify() and notifyAll() are signaling system, means when two threads want to communicate using an object you can use these methods. these are works as semaphore do.