Md Omar Faroque
BAN USERI am good for nothing..
- 0of 0 votes
AnswersFind the label with max width of a tree.
- Md Omar Faroque in United States for Amazon Business
// 0 A
// /|\
// 1 B C D
// /| | \
// 2 E F G H
Answer is 2 here.| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer
Let's assume
1. The distance between two poles is 1 unit.
2. The tallest pole is 10unit height.
3. The shortest one is 1 unit, clear from the problem.
Now,
If two tallest pole are neighbor (10 10), then you need only 1 unit of wire to connect.
But if one pole is 10 and another pole is 1, now you need a diagonal distance (sqrt(10*10+1))
Happy case: All the pole is same height
Worst case: One pole is max height, 10 and the next one is 1. It will look like a triangular wave.
Just need to sum up all the non horizontal(diagonal) line of the wave.
Heap is also possible.
distance: list of available seats with
Always pick the max distance, pick the first available seat. If there is no seat available with that distance, drop it.
Update and find next available would O(logn). Straight segment tree.
- Md Omar Faroque June 10, 2022Here is my full java solution:
public class MinRangeInKSortedList {
/**
* Problem Statement:
* You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
* <p>
* For example,
* List 1: [4, 10, 15, 24, 26]
* List 2: [0, 9, 12, 20]
* List 3: [5, 18, 22, 30]
* <p>
* The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
*/
MinRangeInKSortedList minRangeInKSortedList;
@BeforeEach
public void init() {
minRangeInKSortedList = new MinRangeInKSortedList();
}
@Test
public void firstTest(){
int res= minRangeInKSortedList.findRange(
List.of(List.of(4, 10, 15, 24, 26),
List.of(0, 9, 12, 20),
List.of(5, 18, 22, 30)));
Assertions.assertEquals(res,4);
}
@Test
public void secondTest(){
int res= minRangeInKSortedList.findRange(
List.of(List.of(1,2),
List.of(2,3,4,5),
List.of(4,5,6)));
Assertions.assertEquals(res,2);
}
int findRange(List<List<Integer>> input) {
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
int[] max=new int[3];
max[0]=Integer.MIN_VALUE;
for(int i=0;i<input.size();i++){
int data=input.get(i).get(0);
if(data>max[0]){
max=new int[]{data,i,0}; // data, list, position
}
pq.add(new int[]{data,i,0});
}
int minRange=Integer.MAX_VALUE;
while (!pq.isEmpty()){
int[] min=pq.poll();
minRange=Math.min(minRange,max[0]-min[0]);
int listLoc=min[1];
int pos=min[2];
if(pos+1>=input.get(listLoc).size()) break;
int num=input.get(listLoc).get(pos+1);
if(num>max[0]){
max[0]=input.get(listLoc).get(pos+1);
max[1]=listLoc;
max[2]=pos+1;
}
pq.add(new int[]{input.get(listLoc).get(pos+1),listLoc,pos+1});
}
return minRange;
}
}
This is not a BT. Each node might be n numbers of node. I forgot to add that.
- Md Omar Faroque May 12, 2017import java.util.ArrayList;
import java.util.HashSet;
public class TVHourProblem {
public static void main(String[] args) {
HashSet<Integer> set=new HashSet<>();
ArrayList<int[]> list=new ArrayList<>();
list.add(new int[] {1,4});
for(int i=0;i<list.size();i++){
int[] obj=list.get(i);
int in=obj[0];
int out=obj[1];
for(int j=in+1;j<=out;j++){
if(!set.contains(j)){
set.add(j);
}
}
}
System.out.println("TV ON: "+set.size());
}
}
import java.util.ArrayList;
import java.util.HashSet;
public class TVHourProblem {
public static void main(String[] args) {
HashSet<Integer> set=new HashSet<>();
ArrayList<int[]> list=new ArrayList<>();
list.add(new int[] {1,4});
for(int i=0;i<list.size();i++){
int[] obj=list.get(i);
int in=obj[0];
int out=obj[1];
for(int j=in+1;j<=out;j++){
if(!set.contains(j)){
set.add(j);
}
}
}
System.out.println("TV ON: "+set.size());
}
}
Here is my Solution:
- Md Omar Faroque September 15, 2022```
public void random(int a, int b) {
int num = 1<<31;
int min=num|a;
int max=num|b;
StringBuilder sb=new StringBuilder("");
String minStr=Integer.toBinaryString(min);
String maxStr=Integer.toBinaryString(max);
int idx=1;
while (idx< maxStr.length()){
if(minStr.charAt(idx)!=maxStr.charAt(idx)) break;
sb.append(minStr.charAt(idx));
idx++;
}
int temp=idx;
while (true){
while (idx<maxStr.length()){
String r=rand();
sb.append(r);
idx++;
}
if((Integer.parseInt(sb.toString(),2) >=a &&
Integer.parseInt(sb.toString(),2)<=b)){
System.out.println(Integer.parseInt(sb.toString(),2));
break;
}
sb.delete(temp-1,sb.length());
idx=temp;
}
}
private String rand() {
Random rd = new Random(); // creating Random object
return !rd.nextBoolean() ? "0" : "1";
}
```