CareerCup

Can you elaborate on the question:

Lets say we have two edges : (0, 0), (0, 3) and (0, 0), (0, 5). Since each edge will create a single square - the total number of squares will be 2.

Meaning the number of squares = number of edges.

Ofcourse we need to find the co-ordinates of the remaining square points. What else needs to be done ?

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

public class Facebook1 {

    Set<Integer> arraySet = new HashSet<>();

    public static void main(String[] args) {

        Facebook1 fb1 = new Facebook1();
        fb1.totalInterval( new int[][]{ {1, 4}, {6, 8}, {2, 4}, {7, 9}, {10, 15} } );
    }

    void totalInterval(int[][] input){

        int totalInter = 0;

        for (int[] inputPair : input) {

            int first = inputPair[0];
            int second = inputPair[1];

            for (int i = first; i < second; i++) {
                arraySet.add(i);
            }

        }

        System.out.println(arraySet);

//        for (int i = 0; i < arraySet.size(); i ++) {
//            if (arraySet.get(i) == 1)
//                totalInter = totalInter + 1;
//        }

        System.out.println(arraySet.size());
    }
}

String longestSubstring = "";

Create two collections:
Distinct characters collection
Duplicate characters collection

Create two pointers:
Start index
End index

Loop
	While end index does not reach the end of string( increment end index)
	
	if(distinct_collection.size() < k)
		
		Read character at end index
		
		If(char is in distinct)
			Remove char from distinct collection + Add to duplicate collection
		
		else if (char in duplicate )
			Do nothing

		// This means the char has come up the first time
		else 
			Add to distinct collection
	
	// This will happen when the number of distinct characters == k
	else
		
		If substring(startIndex, endIndex).length() > longestSubstring.length()
			longestSubstring = substring(startIndex, endIndex)
		
		Loop (distinct collection.size() == k)

			If character at startPtr in distinct collection
				startPtr++
				Remove character from distinct collection
			
			Else
				continue;
			
	}

Print longestSubstring

Algorithm:

String longestSubstring = "";

Create two collections:
Distinct characters collection
Duplicate characters collection

Create two pointers:
Start index
End index

Loop
While end index does not reach the end of string( increment end index)

if(distinct_collection.size() < k)

Read character at end index

If(char is in distinct)
Remove char from distinct collection + Add to duplicate collection

else if (char in duplicate )
Do nothing

// This means the char has come up the first time
else
Add to distinct collection

// This will happen when the number of distinct characters == k
else

If substring(startIndex, endIndex).length() > longestSubstring.length()
longestSubstring = substring(startIndex, endIndex)

Loop (distinct collection.size() == k)

If character at startPtr in distinct collection
startPtr++
Remove character from distinct collection

Else
continue;

}

Print longestSubstring

Approach from "Cracking the coding interview:

public static void main(String[] args) {

		List<String> list = printCombos(new Integer(1234).toString());
		System.out.println(list);
	}

	static List<String> printCombos(String num) {
		
		List<String> methodList = new ArrayList<>();
		
		if (num.length() == 1) {
			methodList.add(num);
			return methodList;
		}
		else{
			int lastIndex = num.length() -1;
			
			char lastIndexItem = num.charAt(lastIndex);
			String firstPart = num.substring(0, lastIndex);
			
			methodList = permutate(printCombos(firstPart), lastIndexItem);
			return methodList;
		}
	}
	
	static List<String> permutate(List<String> firstPart, char lastIndexItem){
		
		List<String> methodList = new ArrayList<>();
		
		for(String s : firstPart){
			
			for(int i = 0; i <= s.length(); i++){
				
				String tempString = new StringBuilder(s).insert(i, lastIndexItem).toString();
				methodList.add(tempString);
			}
		}
		
		return methodList;
	}

Factory pattern

Add the List to a HashSet.

It will remove duplicates and will NOT return in insertion order.

String s = "asdba()da(d))";
		Stack<Integer> stack = new Stack<>();
		StringBuilder builder = new StringBuilder();
		
		for(int i = 0; i < s.length(); i++){
			
			char c = s.charAt(i);
			
			switch (c) {
			case '(':
				
				stack.push(i);
				break;

			case ')':
				
				if (!stack.isEmpty()) {
					
					builder.insert(stack.pop(), "(");
					builder.append(')');
				}
				break;
				
			default:
				builder.append(c);
				break;
			}
		}
		
		System.out.println(builder.toString());

Don't quiet understand the implementation by @Anwar.

Concatenation should require adding the new string ASCII values to the existing array. If the array length is short. It will have to be re-sized.

Shortcomings:

a. Finding a consecutive block of memory to store array of a bigger size might be challenging when memory utilization is high.

b. Resizing takes O(n) time since each input is copied to the new array.

c. High number of abandoned arrays might need Garbage collection regularly. This might take CPU bandwidth and might slow the machine.

a. Sort c1, c2, c3 ... cn, descending order

b. Create array of size [M]

c. Loop over numbers
Store first M numbers in the array. ( first col will have the highest number )

d. int highestColumn = 0 ( since col 0 has the highest value )

e. Loop over columns in the array, from last to first i.e. in ascending order.
This is to ensure the lowest digit is added the next highest number, thus creating the lowest combo.
&&
Loop until c series numbers finish

if ( array[highestColumn] >= array[currentColumn] + c )
Add c in current column
else
Add c in current column
highestColumn = currentColumn

Print value of array[highestColumn]

static void lazyBartender(){
		
		Set<Character> topLevelDrinksSet;
		Set<Character> topLevelCustomerSet;
		
//		Loop on drinks
		while(true){
			
			Set<Character> loopLevelCustomerSet;
			
//			Loop on customers
			while(true){
				
//				Does current customer have the current drink as a fav.
//				Yes -> loopLevelCustomerSet.add(Customer)
			}
			
//			If topLevelCustomerSet does NOT have all the counted customers
			if(!topLevelCustomerSet.containsAll(loopLevelCustomerSet)){
				topLevelCustomerSet.addAll(loopLevelCustomerSet);
				topLevelDrinksSet.add(currentDrink);
			}
		}
		
		System.out.println(topLevelDrinksSet);
	}

This reminds me of how Amazon works i.e. filters and sorts

1. Keep a pair of test data. The first would be ranked lower that the second on only a SINGLE parameter e.g. rating, price or else.

From the resulting list find whether the comes after the second. This should tell us whether the sort works well.

Use StringBuffer.reverse()

Is the question too simple or have I not understood it ?

1. Sorting can be done by the OS itself and the result can be stored in an Array

2. As Fernando mentioned ... a Heap could be used. But the issue is ... that for 40,000,000. The value of nlogn would be very high.

3. We could use a hashmap with 'n' buckets, each bucket with increasing order of date.
Each bucket can then have a linked list, with items in sorted order.

Complexity should be n, considering a good hashing technique.