Ahmed.Ebaid
BAN USERpublic static long generateNDigitRandomNumber(int n) {
long result = 0;
List<Integer> randomDigits = new ArrayList<>();
Random r = new Random();
int digit = 0;
for (int i = 0; i < n; i++) {
if (i == 0) {
while ((digit = r.nextInt(10)) == 0)
;
randomDigits.add(digit);
continue;
}
if (i != n - 1) {
while ((digit = r.nextInt(10)) == randomDigits.get(i - 1))
;
randomDigits.add(digit);
} else {
while (((digit = r.nextInt(10)) % 2) == 1
|| digit == randomDigits.get(i - 1))
;
randomDigits.add(digit);
}
}
for (int i = 0; i < randomDigits.size(); i++) {
result += randomDigits.get(i) * Math.pow(10, n - 1 - i);
}
return result;
}
- Ahmed.Ebaid August 18, 2017We can do an inorder traversal twice, first to find the count. Second to get the median based on that count using an array with single element.
- Ahmed.Ebaid August 18, 2017This should be a basic BFS, or DFS. One corner case to look at here would be a loop if a manager is an employee in the chain.
- Ahmed.Ebaid August 08, 2017public static Node reverseWords(Node root) {
Node dummy = new Node('0');
Node curr = root, temp = null, spaceCharDummy = null;
dummy.next = curr;
while (curr != null && curr.next != null) {
while (curr.value == ' ') {
//if there are multiple spaces, make the final space marks the sublist header of the new word
spaceCharDummy = curr;
temp = spaceCharDummy;
curr = spaceCharDummy.next;
}
if (curr == null) {
//No more words can be found.
break;
}
temp = curr.next;
if (temp.value != ' ') {
curr.next = temp.next;
temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
if (spaceCharDummy != null) {
spaceCharDummy.next = temp;
} else {
dummy.next = temp;
}
} else {
spaceCharDummy = temp;
curr = spaceCharDummy.next;
}
}
return dummy.next;
}
- Ahmed.Ebaid August 04, 2017public static Node reverseWords(Node root) {
Node dummy = new Node('0');
Node curr = root, temp = null, spaceCharDummy = null;
dummy.next = curr;
while (curr != null && curr.next != null) {
while (curr.value == ' ') {
//if there are multiple spaces, make the final space marks the sublist header of the new word
spaceCharDummy = curr;
temp = spaceCharDummy;
curr = spaceCharDummy.next;
}
if (curr == null) {
//No more words can be found.
break;
}
temp = curr.next;
if (temp.value != ' ') {
curr.next = temp.next;
temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
if (spaceCharDummy != null) {
spaceCharDummy.next = temp;
} else {
dummy.next = temp;
}
} else {
spaceCharDummy = temp;
curr = spaceCharDummy.next;
}
}
return dummy.next;
}
- Ahmed.Ebaid August 04, 2017public static Node reverseWords(Node root) {
Node dummy = new Node('0');
Node curr = root, temp = null, spaceCharDummy = null;
dummy.next = curr;
while (curr != null && curr.next != null) {
while (curr.value == ' ') {
//if there are multiple spaces, make the final space marks the sublist header of the new word
spaceCharDummy = curr;
temp = spaceCharDummy;
curr = spaceCharDummy.next;
}
if (curr == null) {
//No more words can be found.
break;
}
temp = curr.next;
if (temp.value != ' ') {
curr.next = temp.next;
temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
if (spaceCharDummy != null) {
spaceCharDummy.next = temp;
} else {
dummy.next = temp;
}
} else {
spaceCharDummy = temp;
curr = spaceCharDummy.next;
}
}
return dummy.next;
}
Actually, since the question is about multiplying the three maximum numbers we can still achieve a O(n) for whatever numbers beings used by using additional data structure such as hash map which contains a maximum numbers as a key and frequency of that number as a value. Basically, the idea would be to insert maximums in a hash map with their frequency. if that frequency is greater than or equal 3, then we are done. If it is 2, we are missing the third maximum, if only 1, that means we are missing the other 2 maximums. So, the idea here is to iterate over the array 3 times which is O(3n).
- Ahmed.Ebaid July 04, 2017import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.google.common.collect.Lists;
public class CareerCup {
private static Map<String, Integer> managerSpaceMap = new HashMap<>();
public static void printStructure(
Map<String, List<String>> managerEmployeeMap) {
for (Map.Entry<String, List<String>> entry : managerEmployeeMap
.entrySet()) {
String manager = entry.getKey();
if (!managerSpaceMap.containsKey(manager)) {
if (managerSpaceMap.isEmpty()
|| !managerSpaceMap.containsKey(manager)) {
managerSpaceMap.put(manager, 0);
}
printHierarchy(manager, managerSpaceMap.get(manager));
for (String employee : entry.getValue()) {
printHierarchy(employee, managerSpaceMap.get(manager) + 1);
if (isManager(managerEmployeeMap, employee)) {
managerSpaceMap.put(employee,
managerSpaceMap.get(manager) + 1);
handleManager(managerEmployeeMap, employee);
}
}
}
}
}
private static void handleManager(
Map<String, List<String>> managerEmployeeMap, String manager) {
for (String emp : managerEmployeeMap.get(manager)) {
printHierarchy(emp, managerSpaceMap.get(manager) + 1);
if (isManager(managerEmployeeMap, emp)) {
managerSpaceMap.put(emp, managerSpaceMap.get(manager) + 1);
handleManager(managerEmployeeMap, emp);
}
}
}
private static boolean isManager(
Map<String, List<String>> managerEmployeeMap, String employee) {
return managerEmployeeMap.containsKey(employee);
}
private static void printHierarchy(String employee, int spacing) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < spacing; i++) {
sb.append(" ");
}
sb.append("-");
System.out.println(sb.toString() + employee);
}
public static void main(String[] args) {
Map<String, List<String>> map = new HashMap<>();
map.put("AAA", Lists.newArrayList("BBB", "CCC", "EEE"));
map.put("CCC", Lists.newArrayList("DDD"));
map.put("XXX", Lists.newArrayList("YYY", "ZZZ"));
map.put("DDD", Lists.newArrayList("TTT", "OOO"));
map.put("TTT", Lists.newArrayList("MMM", "NNN", "XXX"));
map.put("FFF", Lists.newArrayList("JJJ", "KKK"));
printStructure(map);
}
}
public static int findPivotIndex(List<Integer> ints) {
int left = 0, right = ints.size() - 1, sumLeft = 0, sumRight = 0;
sumLeft = ints.get(left);
sumRight = ints.get(right);
while (left < right) {
if (sumLeft < sumRight) {
sumLeft += ints.get(++left);
} else if (sumLeft > sumRight) {
sumRight += ints.get(++right);
} else {
left++;
right--;
}
}
return sumLeft == sumRight ? right : -1;
}
Another Solution that depends on bit manipulation could be as follows:
i)Invert bits in every single row -> O(n) with the assumption that the bit mask operation takes constant time with fast processor.
ii)Return the least significant one in every row -> Should be another O(n)
iii) Number of zeros in every row = N - output of step # ii -> O(n)
iv) Add numbers
iv)
Can a caching policy with LRU be of any help here. You can use LinkedHashMap and implement the removeEldestEntry when size is more than capacity(i.e., n). Assuming those records are unique.
- Ahmed.Ebaid August 18, 2017For duplicate records, you can use a map with key equal to song name and an integer value representing the frequency of how many times the song was listened for. You can then output the first n songs with maximum frequency.