omid095
BAN USER/**
* Complexity is O(n)
* @author Omid Ghiasi Tarzi
*/
static int arrowCount(List<Integer> list){
int arrow=list.get(0);
int arrows=1;
int pararelArrows=0;
int max=0;
for(int i=0; i<list.size();i++){
int diff=list.get(i)-arrow;
if(diff==0){
arrow--;
pararelArrows=0;
continue;
}
else if(diff==1){
pararelArrows++;
if(max<pararelArrows){
max=pararelArrows;
arrows++;
}
}
else {
max=0;
arrows++;
}
arrow=list.get(i)-1;
}
return arrows;
}
/**
* @author Omid Ghiasi Tarzi
*/
public static List<String> chainList(List<String> list){
Set<Character> starts=new HashSet<>();
Set<Character> ends=new HashSet<>();
Map<Character,String> map=new HashMap<>();
for(String str:list){
starts.add(str.charAt(0));
ends.add(str.charAt(str.length()-1));
map.put(str.charAt(0),str);
}
starts.removeAll(ends);
char c=starts.toArray(new Character[0])[0];
List<String> result=new ArrayList<>();
while(map.get(c)!=null){
String str=map.get(c);
result.add(str);
c=str.charAt(str.length()-1);
}
return result;
}
/**
* @author Omid Ghiasi Tarzi
*/
static List<Integer> intersect(List<Integer> first, List<Integer> second) {
Set<OrderedInt> firstSet = toOrderedIntSet(first);
Set<OrderedInt> secondSet = toOrderedIntSet(second);
firstSet.retainAll(secondSet);
return firstSet.stream().map(i -> i.value).collect(Collectors.toList());
}
private static Set<OrderedInt> toOrderedIntSet(List<Integer> list) {
Set<OrderedInt> resultSet = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i : list) {
map.put(i, map.getOrDefault(i, 0) + 1);
resultSet.add(new OrderedInt(i, map.get(i)));
}
return resultSet;
}
static class OrderedInt {
int value;
int order;
OrderedInt(int value, int order) {
this.value = value;
this.order = order;
}
@Override
public boolean equals(Object o) {
OrderedInt other = (OrderedInt) o;
return value == other.value && order == other.order;
}
@Override
public int hashCode() {
return 31 * (31 * value + order);
}
}
/**
* @author Omid Ghiasi Tarzi
*/
static List<Integer> intersect(List<Integer> list1,List<Integer> list2){
list1=new ArrayList<>(list1);
list2=new ArrayList<>(list2);
Collections.sort(list1);
Collections.sort(list2);
int i=0;
int j=0;
List<Integer> result=new ArrayList<>();
while(i<list1.size()&&j<list2.size()){
if(list1.get(i)<list2.get(j)){
i++;
}else if(list1.get(i)>list2.get(j)){
j++;
}else{
result.add(list1.get(i));
i++;
j++;
}
}
return result;
}
/**
* Complexity: O(n^2) where n reservations and n hotel
* @author Omid Ghiasi Tarzi
*/
static Set<String> getAvailableHotels(
Map<String, Integer> hotelSizes,
List<String> reservations,
String fromDate,
String toDate
) {
Set<String> result = new HashSet<>();
Map<String, List<String>> map = reservations.stream().collect(Collectors.groupingBy(check -> check.split(" ")[0]));
for (String hotel : map.keySet()) {
List<String> list = map.get(hotel);
if (isHotelAvailable(list, hotelSizes.get(hotel), fromDate, toDate)) {
result.add(hotel);
}
}
return result;
}
static boolean isHotelAvailable(List<String> reservations, int size, String fromDate, String toDate) {
List<String> ins = new ArrayList<>();
List<String> outs = new ArrayList<>();
for (String reservation : reservations) {
ins.add(reservation.split(" ")[1]);
outs.add(reservation.split(" ")[2]);
}
int space = size;
int i = 0;
int j = 0;
while (i < ins.size()) {
if (ins.get(i).compareTo(outs.get(j)) < 0) {
space--;
if (space <= 0 && ins.get(i).compareTo(toDate) <= 0 && ins.get(i).compareTo(fromDate) >= 0) {
return false;
}
i++;
} else {
space++;
j++;
}
}
return true;
}
/**
* @author Omid Ghiasi Tarzi
*/
static int getMaxDay(List<List<Integer>> checks) {
List<Integer> ins = new ArrayList<>();
List<Integer> outs = new ArrayList<>();
for (List<Integer> check : checks) {
ins.add(check.get(0));
outs.add(check.get(1));
Collections.sort(ins);
Collections.sort(outs);
}
int i = 1;
int j = 0;
int count = 1;
int maxPeople = count;
int maxDay = ins.get(0);
while (i < ins.size()) {
if (ins.get(i) <= outs.get(j)) {
count++;
if (count > maxPeople) {
maxPeople = count;
maxDay = ins.get(i);
}
i++;
} else {
count--;
j++;
}
}
return maxDay;
}
/**
* @author Omid Ghiasi Tarzi
*/
static int getMaxDay(List<List<Integer>> checks) {
List<Integer> ins = new ArrayList<>();
List<Integer> outs = new ArrayList<>();
for (List<Integer> check : checks) {
ins.add(check.get(0));
outs.add(check.get(1));
Collections.sort(ins);
Collections.sort(outs);
}
int i = 1;
int j = 0;
int count = ins.get(i);
int maxPeople = count;
int maxDay = 0;
while (i < ins.size()) {
if (ins.get(i) <= outs.get(j)) {
count++;
if (count > maxPeople) {
maxPeople = count;
maxDay = ins.get(i);
}
i++;
} else {
count--;
j++;
}
}
return maxDay;
}
/**
* @author Omid Ghiasi Tarzi
*/
List<Integer> getPopulars(Map<Integer,Set<String>> reviews, Set<String> keyWords){
Map<Integer,Integer> scores=new HashMap<>();
for(int hotel:reviews.keySet()){
Set<String> review=new HashSet<>(reviews.get(hotel));
review.retainAll(keyWords);
scores.put(hotel,review.size());
}
return scores.entrySet().stream()
.sorted(Comparator.comparing(Map.Entry::getKey))
.sorted((e1,e2)->e2.getValue()-e1.getValue())
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}
/**
* complexity is O(n) while n is total count of numbers
*
* @author Omid Ghiasi Tarzi
*/
static Set<Integer> getCommons(Set<Set<Integer>> sets) {
Set<Integer> result = new HashSet<>();
result.addAll(sets.iterator().next());
for (Set<Integer> set : sets) {
result.retainAll(set);
}
return result;
}
/**
* @author Omid Ghiasi Tarzi
*/
static boolean isCaptured(int x,int y){
Set<String> indexes=new HashSet<>();
String currentState=getState(x,y);
return isCaptured(x,y,currentState,indexes);
}
static boolean isCaptured(int x, int y, String desired, Set<String> indexes){
String current=getState(x,y);
if(current.equals("empty")){
return false;
}
if(!current.equals(desired)){
return true;
}
String index=x+","+y;
if(indexes.contains(index)){
return true;
}
indexes.add(index);
return isCaptured(x-1,y,desired,indexes)&&
isCaptured(x+1,y,desired,indexes)&&
isCaptured(x,y-1,desired,indexes)&&
isCaptured(x,y+1,desired,indexes);
}
/**
* The idea is for each list of numbers is
* retained = intersect(list, board) ; result += retained ; board += list
*
*
* @author Omid Ghiasi Tarzi
*/
public static List<Integer> getDuplication(List<List<Integer>> lists) {
Set<Set<Integer>> board = new HashSet<>();
Set<Set<Integer>> resultSet = new HashSet<>();
List<Integer> resultList = new ArrayList<>();
for (List<Integer> list : lists) {
Map<Integer, Integer> localMap = new HashMap<>();
Set<Set<Integer>> localSet = new HashSet<>();
for (int i : list) {
localMap.put(i, localMap.getOrDefault(i, 0) + 1);
localSet.add(new LinkedHashSet<>(Arrays.asList(i, localMap.get(i))));
}
Set<Set<Integer>> retainedSet = new HashSet<>(localSet);
retainedSet.retainAll(board);
resultSet.addAll(retainedSet);
board.addAll(localSet);
}
for (Set<Integer> set : resultSet) {
resultList.add(set.iterator().next());
}
return resultList;
}
- omid095 October 12, 2019