Raminder
BAN USERAssumptions: time is in minutes, 0 means "in position" and 1 means "out position". Therefore direction Array has either 0 or 1 indicating that person is either going in or out.
Note: the code is not tested.
int [] getSequence(int [] timeList, int [] directionList){
if(timeList.length == 0 || directionList.length != timeList.length)return null;
HashMap<int,List<Integer>> map = new HashMap<>();
int [] result = new int [timeList.length];
int door = 0;
int minTime = getMinTime(timeList);
int maxTime = getMaxTime(timeList);
for(int i = 0; i < timeList.length; i++){
map.putIfAbsent(timeList[i],new ArrayList<Integer>());
map.get(timeList[i]).add(directionList[i]);
}
int j = 0;
for(int i = minTime; i <= maxTime; i++){
if(map.containsKey(i)){
List<Integer> list = map.get(i);
if(list.size() == 1){
result[++j] = list.get(0);
door = reslut[j];
}else if(list.size() >= 2){
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
if(iterator.next() == door){
iterator.remove();
result[++j] = door;
}
}
for(int value : list){
door = value;
result[++j] = value;
}
}
}
}
return result;
}
private int getMaxTime(int [] timeList){
int maxTime = -1;
for(int time : timeList)
maxTime = time > maxTime? time : maxTime;
return maxTime;
}
private int getMinTime(int [] timeList){
int minTime = Integer.MaxVal;
for(int time : timeList)
minTime = time < minTime? time : minTime;
return minTime;
}
int getNumberOfGoodStrings(int N){
char [] charArray = new char [N];
return getNumberOfGoodStrings(N,0,0,charArray);
}
private int getNumberOfGoodStrings(int N, int index, int Ccount, char [] charArray){
if(index == N)return 1;
int count = 0;
if(index - 2 < 0 || charArray[index - 2] != 'A'){
charArray[index] = 'A';
count += getNumberOfGoodStrings(N,index + 1, Ccount, charArray);
}
if((index - 2 >= 0 && charArray[index - 2] != 'B' && harArray[index - 1] != 'B') ||
(index == 1 && charArray[0] != 'B') ||
index == 0){
charArray[index] = 'B';
count += getNumberOfGoodStrings(N,index + 1, Ccount, charArray);
}
if(Ccount < 4){
charArray[index] = 'C';
count += getNumberOfGoodStrings(N,index + 1, Ccount + 1, charArray);
}
return count;
}
I am using trieNode that takes strings instead of char. The upper bound is m*(!n) where n is the length of rule.
class TrieNode{
public HashMap<String, TrieNode> childrenMap;
public String value;
public TrieNode(HashMap<String,TrieNode> map, String value){
this.childrenMap = map;
this.value = value;
}
}
boolean hasAmibiguouty(String [][] rules, TrieNode root){
HashSet<String> [] rulesSet = new HashSet[rules[0].length - 1];
for(int i = 0;i < rules[0].length - 1; i++){
rulesSet[i] = new HashSet<String>();
for(int j = 0; j < rules.length;j++){
if(rules[j][i] != "*" && !rulesSet[i].contains(rules[j][i]))
rulesSet[i].add(rules[j][i]);
}
}
boolean duplicate = false;
for(int i = 0; i < rules.length; i++){
duplicate = addRule(rules[i], rulesSet, root,0);
if(duplicate)return true;
}
return false;
}
boolean addRule(String [] rule, HashSet [] ruleSet, TrieNode root, int index){
if(index == rule.length - 1){
if(root.value != null)return true;
root.value = rule[index];
return false;
}
if(rule[index].equals("*")){
Iterator<String> it = ruleSet[index].iterator();
while(it.hasNext()){
String ruleName = it.next();
root = addRuleToNode(root,ruleName);
boolean duplicate = addRule(rule,ruleSet,root.childrenMap.get(ruleName),index + 1);
if(duplicate)return true;
}
}else{
root = addRuleToNode(root,rule[index]);
return addRule(rule,ruleSet,root.childrenMap.get(rule[index]),index + 1);
}
return false;
}
TrieNode addRuleToNode(TrieNode root, String ruleName){
if(root.childrenMap.containsKey(ruleName)){
return root;
}else{
TrieNode node = new TrieNode(new HashMap<String, TrieNode>(),null);
root.childrenMap.put(ruleName, node);
return root;
}
}
You can not do better than N^2 but some quick optimizations can be done which are also practical during the interview. Like one I am doing below is that list of points is sorted based on their point.x values and comparing each point to the other points from left to right, if point2.x - point1.x > k that there is no need to compare any other values in rest of the list as all the other values will have x values equal to, or bigger than point2.x value. Note: The code below is not tested
List<List<Point>> getSets(Point [] points, int k){
List<List<Point>> listOfLists = new ArrayList<List<Point>>();
int [] set = new int[points.length];
Arrays.fill(set, -1);
Arrays.sort(points, (a,b)-> a.x - b.x);
HashMap<Integer, List<Point>> map = new HashMap<>();
for(int i = 0; i < points.length; i++){
for(int j = i + 1; j < points.length; j++){
if(points[j].x - points[i].x > k)break;
int distance = getDistance(points[i], points[j]);
if(distance > k)break;
int rootOfI = find(set, i);
int rootOfJ = find(set, j);
union(set,rootOfI,rootOfJ);
}
}
for(int i = 0; i < set.length; i++){
int root = find(set, i);
map.putIfAbsent(root, new ArrayList<Point>());
map.get(root).add(points[i]);
}
for(Map.Entry<Integer, List<Point>> entry: map.entrySet()){
if(entry.getValue().size() > 1)
listOfLists.add(entry.getValue());
}
return listOfLists;
}
int getDistance(Point i, Point j){
double xVal = Math.pow(Math.abs(i.x - j.x), 2);
double yVal = Math.pow(Math.abs(i.y - j.y), 2);
double distance = Math.sqrt(xVal + yVal);
return (int)distance;
}
int find(int [] set, int i){
if(set[i] < 0)return i;
return set[i] = find(set,set[i]);
}
void union(int [] set, int root1, int root2){
if(set[root1] < set[root2]){
set[root2] = root1;
set[root1]--;
}else{
if(set[root1] == set[root2])set[root2]--;
set[root1] = root2;
}
}
Rotate every string to start from 'a' and map keys to value as list of strings. if list has more than one string than add that to resulting set.
public List<List<String>> similarStrings(List<String> stringList){
if(stringList.size() == 0)return null;
List<List<String>> sameStrings = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for(String str : stringList){
if(str.length() > 0){
String rotatedString = rotateString(str);
map.putIfAbsent(rotatedString, new ArrayList<String>());
map.get(rotatedString).add(str);
}
}
for(Map.Entry<String, List<String>> e : map.entrySet()){
if(e.getValue().size() > 1){
sameStrings.add(e.getValue());
}
}
return sameStrings;
}
private String rotateString(String str){
if(str.length() == 0)return str;
StringBuilder sb = new StringBuilder();
str = str.toLowerCase();
char lastChar = 'a';
sb.append('a');
for(int i = 1; i < str.length();i++){
char curr = str.charAt(i);
char prev = str.charAt(i - 1);
char rotatedChar = 0;
if(curr > prev){
int delta = curr - prev;
rotatedChar = (char) (lastChar + delta);
}else if(curr == prev){
rotatedChar = lastChar;
}else if(curr < prev){
int delta = prev - curr;
if(lastChar - delta >= 'a'){
rotatedChar = (char) (lastChar - delta);
}else{
delta = 'a' - delta;
rotatedChar = (char) (('z' - delta) + 1);
}
}
sb.append(rotatedChar);
lastChar = rotatedChar;
}
return sb.toString();
}
This question has some ambiguity so I am assume that set is compared against all the unique characters in super set.
The following code returns either a set that has no common element with other sets or a set that has minimum common elements with superset containing all the unique characters of all the sets.
public char[] getMostUniqueSet(char [][] allSets){
int minimum = Integer.MAX_VALUE;
char [] minArray = new char[0];
Map<Character,Integer> charMap = new HashMap<>();
for(char [] setArray: allSets){
for(char c : setArray)
charMap.put(c, charMap.getOrDefault(c, 0) + 1);
}
for(char [] setArray: allSets){
int tempMin = 0;
for(char c : setArray)
if(charMap.get(c) > 1)tempMin++;
if(tempMin == 0){
return setArray;
}else if(tempMin < minimum){
minArray = setArray;
minimum = tempMin;
}
}
return minArray;
}
boolean isBloodRelated(int id1, int d2){
if(id1 == id2) return true;
HashSet<Integer> idSet = new HashSet<>();
Deque<Integer> queue = new ArrayDeque<>();
idSet.add(id1);
idSet.add(id2);
queue.add(id1);
queue.add(id2);
while(!queue.isEmpty()){
int id = queue.poll();
Card card = getCard(id);
int momId = card.getMomId();
int dadId = card.getDadId();
if(idSet.contains(momId) || idSet.contains(dadId))return true;
if(momId != -1){
queue.add(momId);
idSet.add(momId);
}
if(dadId != -1){
queue.add(dadId);
idSet.add(dadId);
}
}
return false;
}
public static boolean palindromeOfTwoStrings(String [] list){
HashSet<String> setOfStrings = new HashSet<>();
for(String str : list){
setOfStrings.add(str);
}
for(String str: list){
//check for the reverse of the suffix by removing first character
if(str.length() > 1 && setOfStrings.contains(reverseString(str.substring(1))))
return true;
int len = str.length();
char ch = str.charAt(str.length() - 1);
//if last n characters of the string are same then we
//will have to check the reverse of each prefix by removing
//each of last characters one by one
while(len > 0 && ch == str.charAt(str.length() - 1)){
String prefix = reverseString(str.substring(0, len));
if(setOfStrings.contains(prefix))return true;
len--;
ch = str.charAt(len);
}
}
return false;
}
public static String reverseString(String str){
if(str.length() <= 1)return str;
StringBuilder sb = new StringBuilder();
sb.append(str);
sb.reverse();
return sb.toString();
}
space is O(n), runtime is order O(n*s) where s is the length of largest string
- Raminder April 22, 2019Actually, problem is simpler than it looks. Can be done in O(n) with using any recursion or stack. For every pair 'a' has to come before 'b'. So if we start with counter = 0, and increment the count every time we see an 'a' and decrement it every time we see 'b'. So if the counter goes below 0 during the scan or end up not being zero, we know the input is not valid.
- Raminder June 22, 2018Assumptions: matrix is a proper rectangle i.e. each sub-array has equal length. We need to check all possible rectangular plots from each plot unless cost is already more than budget. Algo starts from [0,0]. No rectangular plot is recomputed. Worst case is O(M^2.N^2)
public static int findMaxArea(int [] [] matrix, int B){
int rows = matrix.length;
int columns = matrix[0].length;
int count = 0,sum = 0,tempCount =0;
for(int c = 0; c < columns; c++){
for(int r = 0; r < rows; r++){
for(int i = c; i < columns; i++){
sum = 0;
tempCount = 0;
for(int j = r; j < rows; j++){
for(int y = c; y <= i; y++){
sum += matrix[j][y];
tempCount++;
}
if(sum <= B && tempCount > count){
count = tempCount;
}else if(sum > B){
break;
}
}
}
}
}
return count;
}
public static void rotTrans(String [] list){
HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();
String key;
int len = 0,i = 0, j = 0;
for(String s: list){
key = keyGen(s);
if(map.containsKey(key)){
map.get(key).add(s);
}else{
map.put(key, new ArrayList<String>());
map.get(key).add(s);
}
}
for(String k : map.keySet())
len += map.get(k).size() - 1;
String [][] result = new String [len][2];
for(Map.Entry<String,ArrayList<String>> entry : map.entrySet()){
if(entry.getValue().size() > 1){
for(j = 1; j < entry.getValue().size(); j++){
result[i][0] = entry.getValue().get(0);
result[i][1] = entry.getValue().get(j);
i++;
}
}
}
System.out.println(Arrays.deepToString(result));
}
public static String keyGen(String str){
if(str.length() <= 1) return "1";
StringBuilder sb = new StringBuilder();
char ch1,ch2;
ch1 = str.charAt(0);
sb.append(1);
for(int i = 1; i < str.length(); i++){
ch2 = str.charAt(i);
if(ch2 >= ch1){
sb.append((ch2 - ch1) + 1);
}else{
sb.append((ch1 - 'Z' + 1) + (('A' - ch2) + 1));
}
ch1 = ch2;
}
return sb.toString();
}
- Raminder July 12, 2020