Popeye
BAN USERWhy it is not scalable ?. We can segregate the dictionary by word length.
Map<Integer, HashSet<String>> map; //key - length & value - set of words
and this would also be helpful in decreasing the lookup time in the set.
However, I believe the most efficient way is to use Trie.
The main assumption here is that the character is mistyped not and not left over.
private void printLettersInColors(String sentence, String[] colors) {
if(sentence == null || sentence.length() == 0 || colors == null || colors.length == 0) // validation
return;
int no = colors.length; // length can't be more than Integer.MAX_VALUE
int index = 0;
for(char c : sentence.toCharArray()) {
if(c != ' ') {
System.out.println(c+ " - " + colors[index++%no]);
} else {
System.out.println(" ");
}
}
}
public class MyClass {
public static void main(String args[]) {
//call getNoOfTeams method
}
private int getNoOfTeams(Country[] countries, int teamLength) {
int result = 0;
if(countries == null || countries.length ==0 || teamLength < 1)
return result;
List<Country> list = new ArrayList<>();
PriorityQueue<Country> queue = new PriorityQueue<>(new Comparator<Country>(){
public int compare(Country c1, Country c2) {
return c2.no - c1.no;
}
});
for(Country c : countries) {
queue.offer(c);
}
while (teamLength > queue.size()) {
for(int i=0; i<teamLength; ++i) {
Country temp = queue.poll();
temp.no = temp.no-1;
if(temp.no > 0) {
list.add(temp);
}
}
++result;
for(Country item : list)
queue.offer(item);
list.clear();
}
return result;
}
}
class Country {
String name;
int no;
public Country(String name, int no) {
this.name = name;
this.no = no;
}
}
private LinkedList<Integer> sumList(LinkedList<Integer> l1, LinkedList<Integer> l2) {
LinkedList<Integer> result = new LinkedList<>();
Stack<Integer> stack1 = new Stack<>();
Iterator<Integer> i1 = l1.iterator();
while(i1.hasNext()) {
stack1.push(i1.next());
}
Stack<Integer> stack2 = new Stack<>();
Iterator<Integer> i2 = l2.iterator();
while(i2.hasNext()) {
stack2.push(i2.next());
}
int number = 0;
while(!stack1.isEmpty() || !stack2.isEmpty()) {
number += stack1.isEmpty() ? 0 : stack1.pop();
number += stack2.isEmpty() ? 0 : stack2.pop();
result.addFirst(number%10);
number /= 10;
}
if(number != 0)
result.addFirst(number);
return result;
}
private List<int[]> mergeIntervals(List<List<int[]>> list) {
List<int[]> result = new ArrayList<>();
List<int[]> intervals = new ArrayList<>();
for(List<int[]> item : list) {
for(int[] i : item) {
intervals.add(i);
}
}
Collections.sort(intervals, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
int[] period = new int[]{intervals.get(0)[0], intervals.get(0)[1]};
for(int i=1; i<intervals.size(); ++i) {
if(period[1] >= intervals.get(i)[0]) {
if (intervals.get(i)[1] > period[1])
period[1] = intervals.get(i)[1];
} else {
result.add(period);
period = new int[]{intervals.get(i)[0], intervals.get(i)[1]};
}
}
result.add(period);
return result;
}
class Element {
int val;
List<Element> list;
boolean isList;
}
private long getValue(Element e, int factor) {
long sum = 0;
if(e == null)
return sum;
if(!e.isList)
return factor * e.val;
for(Element item : e.list) {
sum += getValue(item, factor + 1);
}
return sum;
}
1. sort all the toffee packets based on the number of toffees.
2. initialize 5 boxes with the last values (top 5 max values)
3. Insert the boxes into the min heap (size 5) based on the no of toffees
4. Iterate from (1 to n-5 packets) --> pop top element, add packet and insert again.
5. pop all top 4 boxes. 5th box or final popped box's toffees from the heap is the answer to the question.
Objects
--------
Person {
int name;
int id
}
CheckPoint {
DoublyLinkedList first;
DoublyLinkedList last;
Map<String, DoublyLinkedList> personToDLL; // person id to node
public CheckPoint() {
personToDLL = new HashMap<>();
}
}
DoublyLinkedList {
Person person;
DoublyLinkedList prev;
DoublyLinkedList next;
}
Variables
-----------
Map<String, CheckPoint> map; // checkPoint name to Object map
String HighestCheckPointReported; // to store the highest checkPoint that is reported;
Logic :
Everytime a person crosses the checkPoint(CP2)
1. Go to previous check point(CP1) if exists, get the node and delete from the list and map;
update the first and last node in checkPoint accordingly;
add the node to the current checkPoint based on the last node;
add to the map as well;
else
if previous check point doesnt exists, create the person the insert into the list; add this to the map; in current checkPoint
finally
Everytime update the HighestCheckPointReported if it is higher
To get the rank
Iterate from the HighestCheckPointReported to the lowestCheckPoint[first node in each CheckPoint object would help to find the order]
My Approach
1. find the difference value i.e) cost to NY - cost to SF [200, -60, 50, 250]
2. choose the top 50 lowest values and assign to NY location [2rd, 3rd person]
3. Rest 50 candidates to SF location [1st and 4th person]
1. use 2D array to store index as key and difference as value
2. use priority queue to get top 50 lowest value from the array
int max =0;
private static int[] maximumEvenSum(TreeNode node){
if(node == null)
return new int[]{0, 0};
if(node.left == null && node.right == null){
if(node.val % 2 == 0){
max = Math.max(max, node.val);
return new int[]{0, node.val};
} else{
return new int[]{node.val, 0};
}
}
int[] left = maximumEvenSum(node.left);
int[] right = maximumEvenSum(node.right);
int even = 0;
int odd = 0;
if(node.val % 2 == 0){
even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[0]) % 2 == 0)
max = Math.max(left[0] + node.val + right[0], max);
if((left[1] + node.val + right[1]) % 2 == 0)
max = Math.max(left[1] + node.val + right[1], max);
} else{
even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0);
odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[1]) % 2 == 0)
max = Math.max(left[0] + node.val + right[1], max);
if((left[1] + node.val + right[0]) % 2 == 0)
max = Math.max(left[1] + node.val + right[0], max);
}
left[1] = even;
left[0] = odd;
return left;
}
int max =0;
private static int[] maximumEvenSum(TreeNode node){
if(node == null)
return new int[]{0, 0};
if(node.left == null && node.right == null){
if(node.val % 2 == 0){
max = Math.max(max, node.val);
return new int[]{0, node.val};
} else{
return new int[]{node.val, 0};
}
}
int[] left = maximumEvenSum(node.left);
int[] right = maximumEvenSum(node.right);
int even = 0;
int odd = 0;
if(node.val % 2 == 0){
even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[0]) % 2 == 0)
max = Math.max(left[0] + node.val + right[0], max);
if((left[1] + node.val + right[1]) % 2 == 0)
max = Math.max(left[1] + node.val + right[1], max);
} else{
even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0);
odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[1]) % 2 == 0)
max = Math.max(left[0] + node.val + right[1], max);
if((left[1] + node.val + right[0]) % 2 == 0)
max = Math.max(left[1] + node.val + right[0], max);
}
left[1] = even;
left[0] = odd;
return left;
}
The Goal is to find the value of n here
private void isS2SubstringOfS3(String s1, String s2){
int n = (int)Math.ceil(((double)s2.length() -1) % s1.length()) + 1;
String s3 = formString(s1, n);
return s3.contains(s2); // use KMP String match here
}
private String formString(String s1, int n){
StringBuilder sb = new StringBuilder();
while(n > 0){
sb.append(s1);
--n;
}
return sb.toString();
}
This would take n^2 time. Let me know if you have any other best methods to do
private static boolean isValidGeneration(String str1, String str2){
if(str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0 || str1.length() % str2.length() != 0)
return false;
int prevLen = str1.length();
while(str1.length() > 0){
str1 = str1.replace(str2, "");
if(prevLen == str1.length()){
return false;
}
prevLen = str1.length();
}
return true;
}
public Node firstAncestor(Node leftNode, Node rightNode){
Node root1 = null;
Node root2 = null;
Stack<Node> stackLeft = new Stack<Node>();
while(leftNode.parent != null){
stackLeft.push(leftNode.parent);
}
Stack<Node> stackRight = new Stack<Node>();
while(rightNode.parent != null){
stackLeft.push(rightNode.parent);
}
int size = Math.min(stackLeft.size(), stackRight.size());
Node temp = null;
while(size-- >0){
if(stackLeft.peek() != stackRight.peek())
break;
temp = stackLeft.pop();
stackRight.pop();
}
return temp;
}
- Popeye May 12, 2018
My thoughts
- Popeye June 06, 20191. Use min heap
2. neglect the item if it is to be avoided
3. pop till the sum reached k