inucoder
BAN USERI hope my Java solution is easy to read and understand:
String binarySum(String n1, String n2){
if (n2.length() > n1.length()){
String tmp = n1;
n1 = n2;
n2 = tmp;
}
StringBuilder sum = new StringBuilder();
int carry = 0;
for (int i = 0; i < n1.length(); i++){
int idx1 = n1.length() - 1 - i;
int bit1 = n1.charAt(idx1) - '0';
int bit2 = 0;
int idx2 = n2.length() - 1 - i;
if (idx2 >= 0){
bit2 = n2.charAt(idx2) - '0';
}
int bitSum = bit1 + bit2 + carry;
if (bitSum >= 2){
carry = 1;
}
else {
carry = 0;
}
bitSum %= 2;
sum.append((char)(bitSum + '0'));
}
if (carry == 1){
sum.append('1');
}
return sum.reverse().toString();
}
function removeDuplicates(S, i, set, solution){
if (i === S.length){
return solution;
}
else {
c = S[i];
if (!set[c]){
set[c] = true;
return removeDuplicates(S, i + 1, set, solution + c);
}
else {
return removeDuplicates(S, i + 1, set, solution);
}
}
}
removeDuplicates("xxxxxyyyyzz", 0, {}, "")
I hope my Java solution helps:
static void permutate(String[] words, int depth, String permutation){
if (depth == words.length){
System.out.println(permutation);
}
else {
String w = words[depth];
for (int i = 0; i < w.length(); i++){
permutate(words, depth + 1, permutation + w.charAt(i));
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
String[] words = {"red", "fox", "super"};
permutate(words, 0, "");
}
One way of doing it is to traverse the nodes in any order (preorder for example), and for every node, traverse it's left subtree and right subtree, for every node in left subtree such that it's value is greater than the current node value, we output a pair, same for right subtree when we find values lesser than the current node value.
class Node {
int value;
Node left;
Node right;
}
int ans = 0;
void traverseLeft(Node node, int value){
if (node == null){
return;
}
if (node.value > value){
ans++;
}
traverseLeft(node.left, value);
traverseLeft(node.right, value);
}
void traverseRight(Node node, int value){
if (node == null){
return;
}
if (node.value < value){
ans++;
}
traverseRight(node.left, value);
traverseRight(node.right, value);
}
void traverse(Node node){
if (node == null){
return;
}
traverseLeft(node.left, node.value);
traverseRight(node.right, node.value);
traverse(node.left);
traverse(node.right);
}
traverse(root);
Build a tree from the input:
class Node {
Employee employee;
ArrayList<Node> manages = new ArrayList<>();
Node(Employee e){
employee = e;
}
}
Node root = null;
HashMap<Integer, Node> byId;
for(Employee e: employees){
Node node = new Node(e);
byId.put(e.id, node);
if(e.managerId == null){
root = node;
}
}
for(Employee e: employees){
Node node = byId.get(e.id);
if(node == root){
continue;
}
Node managerNode = byId.get(node.employee.managerId);
managerNode.manages.add(node);
}
Part 1:
Node node = byId.get(id);
for (Node n: node.manages){
Employee e = n.employee;
System.out.println(e.id);
}
Part 2:
void traverseAndPrint(Node node, Node root){
if(node != root){
System.out.println(node.employee.id);
}
for(Node child: node.manages){
traverse(child, root);
}
}
traverseAndPrint(byId.get(id), root);
Consider the following code:
public class DateUtils {
static final int IDX_YEAR = 0;
static final int IDX_MONTH = 1;
static final int IDX_DAY = 2;
static int[] daysCount = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
private static boolean isLeapYear(int year){
return year % 4 == 0 && (year % 100 != 0 && year % 400 != 0);
}
public static int getDayOfYear(String date){
String[] parts = date.split("-");
int year = Integer.parseInt(parts[IDX_YEAR]);
int month = Integer.parseInt(parts[IDX_MONTH]) - 1;
int day = Integer.parseInt(parts[IDX_DAY]);
boolean leapYear = isLeapYear(year);
int dayOfYear = 0;
for (int m = 0; m < month; m++){
dayOfYear += daysCount[m];
//february
if (m == 1 && leapYear){
dayOfYear++;
}
}
dayOfYear += day;
return dayOfYear;
}
}
Getting an O(n) time/space solution is not hard. First find the max value in A, then, iterate it again and store in a list M all the positions where it appears. Generate a random integer x between 0 and |M| (exclusive) and return M[x].
For a O(1) space solution, use the idea for getting a random element from a stream of unknown length:
It's works as follows:
1) First find the max value in A
2) Let maxSeenSoFar = 0 and maxIndex = -1
3) For each element of A, at position i, if it's the max value:
3.1) increase maxSeenSoFar by one
3.2) do maxIndex = i with probability 1 / maxSeenSoFar
4) Return maxIndex
- inucoder May 22, 2017