thelineofcode
BAN USEROk, here is my extended version:
public static String addBinaryNumbers(String number1, String number2) {
char[] num1 = number1.toCharArray();
char[] num2 = number2.toCharArray();
int i = num1.length - 1;
int j = num2.length - 1;
int c = 0;
int sum = 0;
String result = "";
while (i >= 0 && j >= 0) {
sum = (int) (num1[i--] - '0') + (int) (num2[j--] - '0') + c;
result = addResult(sum, result);
c = sum > 1 ? 1 : 0;
}
while (i >= 0) {
sum = (int) (num1[i--] - '0') + c;
result = addResult(sum, result);
c = sum > 1 ? 1 : 0;
}
while (j >= 0) {
sum = (int) (num2[j--] - '0') + c;
result = addResult(sum, result);
c = sum > 1 ? 1 : 0;
}
if (c == 1) {
result = "1" + result;
}
return result;
}
private static String addResult(int sum, String result) {
switch (sum) {
case 0:
result = "0" + result;
break;
case 1:
result = "1" + result;
break;
case 2:
result = "0" + result;
break;
case 3:
result = "1" + result;
break;
}
return result;
}
@glebstepanov1992 I changed the tree construction part to match your example:
Node l2leftright = new Node(null, null, 7);
Node l2leftleft = new Node(null, null, 1);
// level 1
Node l1right = new Node(null, null, 6);
Node l1left = new Node(l2leftleft, l2leftright, 2);
// level 0 - root
Node root = new Node(l1left, l1right, 3);
Ans is 7.
- thelineofcode December 17, 2013In Java:
public String (String num1, String num2) {
// Use as radix 2 to convert binary num
return Integer.toBinaryString(Integer.parseInt(num1, 2)+ Integer.parseInt(num2, 2));
}
Its in Java but I think that C# is similar.
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<Integer>(Arrays.asList(new Integer[] { 1, 1, 2, 2, 4 }));
List<Integer> result = new ArrayList<Integer>();
printSumCombinations(numbers, 4, result, 0);
}
public static void printSumCombinations(List<Integer> numbers, int sum, List<Integer> result, int currentIndex) {
if (sum == 0) {
System.out.println(result);
return;
}
if (currentIndex > numbers.size() - 1) {
return;
}
if (numbers.get(currentIndex) != 0) {
result.add(currentIndex);
printSumCombinations(numbers, sum - numbers.get(currentIndex), result, currentIndex + 1);
result.remove(result.size() - 1);
}
printSumCombinations(numbers, sum, result, currentIndex + 1);
}
The question clearly states substring, not subsequence. As far as substrings are concerned this algo is correct. We have to count all of them.
- thelineofcode December 16, 2013Here is reasonable approach without suffix array and trie though.
stevekrenzel.com/articles/longest-palnidrome
You have to modify algorithm slightly to count all intermediate palindromes.
- thelineofcode December 16, 2013public static void main(String[] args) {
int n = 100;
int z = 39;
int k = 7;
int indexToRemove = 2;
Integer[] arr = new Integer[n];
for (int i = 1; i <= n; i++) {
arr[i - 1] = i;
}
Queue<Integer> q = new LinkedList<Integer>(Arrays.asList(arr));
for (int i = 0; i < k - 1 && !q.isEmpty(); i++) {
int counter = 0;
int initialSize = q.size();
while (counter < initialSize) {
for (int j = 0; j < indexToRemove - 1 && counter < initialSize; j++, counter++) {
q.offer(q.poll());
}
if (counter < initialSize) {
q.poll();
counter++;
}
}
indexToRemove++;
}
System.out.println("Element exists: " + q.contains(z));
}
Good point. I'll update my response when I came up with a better idea
- thelineofcode December 16, 2013This should work:
public static double calculatePayout(Member member) {
double payout = member.getMonthlySales() * 0.1;
double sumForRecruits = 0;
Collection<Member> recruitedMembers = member.getRecruitedMembers();
Collection<Member> newRecruits = new ArrayList<Member>();
while (!recruitedMembers.isEmpty()) {
for (Member recruit : recruitedMembers) {
sumForRecruits += recruit.getMonthlySales();
newRecruits.addAll(recruit.getRecruitedMembers());
}
recruitedMembers.clear();
recruitedMembers.addAll(newRecruits);
newRecruits.clear();
}
return payout + sumForRecruits * 0.04;
}
Create HashMap<String, Integer> where key is palindrome and value is the number of occurrences. Iterate over file and check if given word:
if(map.contains(word)) {
map.put(word, map.get(word)+1);
} else if(isPalindrome(word)) {
map.put(word,1);
}
You can also create a Set<String> 'noPalindromes' to avoid checking multiple times words which are not palindromes.
- thelineofcode December 15, 2013Do BFS search of the binary tree till the level of the target node.
Keep track of nodes for particular level so that you know when nodes for particular level start and end.
At the end you should have all nodes which are at the same level as target node.
Now it's very simple to find target node and return its sibling which is on the right or left.
Code:
package microsoft;
import java.util.ArrayList;
import java.util.List;
public class FindSibling {
static class Node {
Node left;
Node right;
int value;
public Node(Node left, Node right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
public String toString() {
return String.valueOf(value);
}
}
public static void main(String[] args) {
// level 3 - leaves
Node node1 = new Node(null, null, 10);
Node node2 = new Node(null, null, 11);
Node node3 = new Node(null, null, 12);
Node node4 = new Node(null, null, 13);
Node node5 = new Node(null, null, 14);
Node node6 = new Node(null, null, 15);
Node node7 = new Node(null, null, 16);
Node node8 = new Node(null, null, 17);
// level 2
Node l2rightright = new Node(node7, node8, 8);
Node l2rightleft = new Node(node5, node6, 7);
Node l2leftright = new Node(node3, node4, 6);
Node l2leftleft = new Node(node1, node2, 5);
// level 1
Node l1right = new Node(l2rightleft, l2rightright, 4);
Node l1left = new Node(l2leftleft, l2leftright, 3);
// level 0 - root
Node root = new Node(l1left, l1right, 2);
System.out.println(findSibling(root, node7));
}
private static Node findSibling(Node root, Node target) {
// there is no siblings
if (target == root) {
return null;
}
List<Node> currentLevel = new ArrayList<Node>();
List<Node> nextLevel = new ArrayList<Node>();
currentLevel.add(root);
boolean foundTarget = false;
int i = 0;
while (i < currentLevel.size()) {
Node node = currentLevel.get(i);
i++;
if (node.left != null) {
nextLevel.add(node.left);
}
if (node.right != null) {
nextLevel.add(node.right);
}
if (target == node.left || target == node.right) {
foundTarget = true;
}
if (i == currentLevel.size()) {
// don't go to next level
if (foundTarget) {
break;
} else {
currentLevel.clear();
currentLevel.addAll(nextLevel);
nextLevel.clear();
i = 0;
}
}
}
if (foundTarget) {
// there is no siblings
if (nextLevel.size() == 1) {
return null;
}
for (i = 0; i < nextLevel.size(); i++) {
if (nextLevel.get(i) == target) {
return i == 0 ? nextLevel.get(i + 1) : nextLevel.get(i - 1);
}
}
}
return null;
}
}
Do elements in the column have to be sorted or just adjusted so that elements in rows are sorted?
- thelineofcode December 15, 2013I assume that you can traverse the matrix in up, down, left and right direction.
Say that starting point A has coordinates A(r, c)
Check if any of neighboring points is equal 1
- up A(r-1, c)
- down A(r+1, c)
- left A(r, c -1)
- right A(r, c +1)
If any of this points is equal 1 invoke the method recursively with new coordinates eg new starting point is (r-1, c).
Repeat the process till you reach destination point or matrix's borders.
Simple code:
package interview;
public class FindPath {
public static void main(String[] args) {
int[][] m = { { 1, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 } };
System.out.println("Found path: " + findPath(0, 0, m.length - 1, m[0].length - 1, m));
}
private static boolean findPath(int startRow, int startCol, int endRow, int endCol, int[][] m) {
if (startRow < 0 || startCol < 0 || endRow < 0 || endCol < 0 || startRow > m.length - 1
|| startCol > m[0].length - 1 || endRow > m.length - 1 || endCol > m[0].length - 1) {
return false;
}
if (startRow == endRow && startCol == endCol) {
return true;
}
m[startRow][startCol] = -1;
// go up
boolean up = false;
if (startRow - 1 >= 0 && m[startRow - 1][startCol] == 1) {
up = findPath(startRow - 1, startCol, endRow, endCol, m);
}
// go down
boolean down = false;
if (startRow + 1 <= m.length - 1 && m[startRow + 1][startCol] == 1) {
down = findPath(startRow + 1, startCol, endRow, endCol, m);
}
// go left
boolean left = false;
if (startCol - 1 >= 0 && m[startRow][startCol - 1] == 1) {
left = findPath(startRow, startCol - 1, endRow, endCol, m);
}
// go right
boolean right = false;
if (startCol + 1 <= m[0].length - 1 && m[startRow][startCol + 1] == 1) {
right = findPath(startRow, startCol + 1, endRow, endCol, m);
}
return up || down || right || left;
}
}
You can also read about flood fill algorithm.
- thelineofcode December 15, 2013@Karthik Vvs you are right. I didn't take into account an offset for hour's hand.
Simple proportion 360 deg of minutes hand == 30 deg of hours hand. So
360/30 = 300/x => 36x = 900 => x = 25. 120 - 25 = 95 deg.
My mistake.
You can try this:
1) Create a graph between two people and their friends. If two people know each other (they are present in contacts list) make a vertex.
2) Find the shortest path between person A and B. Number of nodes in the path is the separation degree.
I think your answer is wrong. The angle between 0(midnight) - 6 and then 6 and 12 is 180 degrees.
50 minutes is when minutes hand is pointing 10. As you wrote an hour hand elapses 30 degrees for every hour.
So the angle is 180 - 60 = 120 degrees.
Here is how I see it:
6.00 - 180 degrees (hour hand points 6 and minutes hand points 12)
6.55 - 150 degrees
6.50 - 120 degrees
6.45 - 90 degrees
6.40 - 60 degrees
6.35 - 30 degrees
6.30 - 0 degrees (both hands points to 6 hour)
1) Iterate over array from the end.
2) Maintain two pointers
a) positivePtr - points to the latest positive element in array
b) negativePtr - points to the latest negative element in array
3) Make sure that positivePtr >negativePtr so that when you swap elements negative value go to the right and positive to the left side
4) After the swap decrements both pointers
Time O(n), space O(1)
Code:
public static void main(String[] args) {
int[] arr = { 3, -1, -2, 2, 2, 3, 2, -6, 2, 3, -8, 0, 2 };
int positivePtr = arr.length - 1;
int negativePtr = arr.length - 1;
System.out.println(Arrays.toString(arr));
while (positivePtr >= 0 && negativePtr >= 0) {
if (arr[positivePtr] < 0) {
positivePtr--;
} else {
if (negativePtr >= positivePtr || arr[negativePtr] >= 0) {
negativePtr--;
} else {
int tmp = arr[positivePtr];
arr[positivePtr] = arr[negativePtr];
arr[negativePtr] = tmp;
negativePtr--;
positivePtr--;
}
}
}
System.out.println(Arrays.toString(arr));
}
1) Generate the biggest possible number for 'n' eg. for n = 2 => 99, n=3 => 999...
2) Starting from that number check if 'o' factors exist which multiplied by each other are equal the biggestNumber.
a) If not decrements number and repeat point 2
Code:
package directi;
import java.util.ArrayList;
import java.util.List;
public class FindBiggestNumberForOMultiplications {
public static void main(String[] args) {
int n = 5;
int o = 5;
List<Integer> factors = new ArrayList<Integer>();
System.out.println(checkNum(generateBiggestNum(n), o, factors));
System.out.println(factors);
}
private static int generateBiggestNum(int n) {
int num = 9;
for (int i = 0; i < n - 1; i++) {
num *= 10;
num += 9;
}
return num;
}
private static int checkNum(int startNum, int o, List<Integer> factors) {
int num = 0;
for (num = startNum; num >= 2 * o; num--) {
if (findMultiplications(num, o, 0, 0, factors)) {
return num;
}
}
return -1;
}
private static boolean findMultiplications(int num, int o, int noOfFactors, int prevFactor, List<Integer> factors) {
if (noOfFactors > o) {
return false;
}
for (int i = 2; i <= 9; i++) {
if (num % i != 0 || i < prevFactor) {
continue;
}
noOfFactors++;
if (noOfFactors == o) {
factors.add(num);
return true;
}
if (findMultiplications(num / i, o, noOfFactors, i, factors)) {
factors.add(i);
return true;
}
}
return false;
}
}
balanced partitioning problem
- thelineofcode December 05, 2013Doesn't the priority queue implicitly sort elements?
- thelineofcode November 28, 2013Once you computed cumulative sum:
for(int i=1; i < W.length; i++){
W[i] = W[i-1]+W[i];
}
your algo has become O(n) solution since A.length = W.length.
- thelineofcode November 25, 2013Use simple recursion. There are two cases:
1) Include the given number in the sum
2) Exclude the number from the sum and proceed to next number
Code:
public static void main(String[] args) {
int n = 4;
List<Integer> result = new ArrayList<Integer>();
findNum(1, n, result);
}
public static void findNum(int numToAdd, int n, List<Integer> result) {
if (n == 0) {
System.out.println(result);
return;
}
if (n < 0 || numToAdd > n) {
return;
}
result.add(numToAdd);
findNum(numToAdd, n - numToAdd, result);
result.remove(result.size() - 1);
findNum(numToAdd + 1, n, result);
}
Good sol but you can just keep Hash<char, char> for each string. If the mapping already exists and is different then the old one return false.
- thelineofcode November 19, 2013He can still compare references.
- thelineofcode October 27, 2013@Miguel, your answer is incorrect. On my machine it takes 0.007s to generate all numbers. :)
- thelineofcode October 15, 2013Use DP approach:
1) Create auxiliary array say 'l' which has the same size as the original array.
2) In array 'l[i][j]' store max length of snake sequence which starts at point (i,j)
3) Perform flood fill algo on the original array to populate 'l' array like that:
- go [i][j+1] or/and [i+1][j] if the difference between point (i,j) and its neighbors is +-1
4) Find max element in array 'l' (there may be many points with the same value) and starting from that points print the sequences.
Code:
package adobe;
public class SnakeSeq {
public static void main(String[] args) {
int[][] arr = { { 1, 3, 2, 6, 8 }, { -9, 7, 1, -1, 2 }, { 1, 5, 0, 1, 9 } };
findSnakeSeq(arr);
}
public static void findSnakeSeq(int[][] m) {
int[][] l = new int[m.length][m[0].length];
int maxLength = 0;
for (int i = 0; i < l.length; i++) {
for (int j = 0; j < l[0].length; j++) {
if (l[i][j] == 0) {
int res = fillSeqLength(i, j, m, l);
if (res > maxLength) {
maxLength = res;
}
}
}
}
printMatrix(l);
printSequences(m, l, maxLength);
}
public static int fillSeqLength(int i, int j, int[][] m, int[][] l) {
if (i < 0 || j < 0 || i >= m.length || j >= m[0].length) {
return 0;
}
if (l[i][j] != 0) {
return l[i][j];
}
int right = 0;
int down = 0;
if (j + 1 < m[0].length && (m[i][j + 1] == m[i][j] + 1 || m[i][j + 1] == m[i][j] - 1)) {
right = fillSeqLength(i, j + 1, m, l);
}
if (i + 1 < m.length && (m[i + 1][j] == m[i][j] + 1 || m[i + 1][j] == m[i][j] - 1)) {
down = fillSeqLength(i + 1, j, m, l);
}
l[i][j] = Math.max(right, down) + 1;
return l[i][j];
}
public static void printSequences(int[][] m, int[][] l, int maxLength) {
for (int i = 0; i < l.length; i++) {
for (int j = 0; j < l[0].length; j++) {
if (l[i][j] == maxLength) {
printSequences(m, l, i, j, maxLength);
}
}
}
}
public static void printSequences(int[][] m, int[][] l, int i, int j, int maxLength) {
while (maxLength > 0) {
System.out.print(m[i][j] + " ");
maxLength -= 1;
if (j + 1 < m[0].length && l[i][j + 1] == maxLength
&& (m[i][j + 1] == m[i][j] + 1 || m[i][j + 1] == m[i][j] - 1)) {
j++;
continue;
}
if (i + 1 < m.length && l[i + 1][j] == maxLength
&& (m[i + 1][j] == m[i][j] + 1 || m[i + 1][j] == m[i][j] - 1)) {
i++;
continue;
}
}
}
private static void printMatrix(int[][] m) {
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
System.out.print(m[i][j] + " ");
}
System.out.println();
}
}
}
Comparable<Pets> would be better
- thelineofcode September 20, 2013Correct, but if you prefer creating String using 'new' operator you can always
interning them like: new String().intern();
1) Find min and max value in the array
2) Count the number of occurrence for each value in array. Keep result in a separate array say count[max-min+1]
3) Recreate the original array by traversing the 'count' array and each time decrements the count for particular value till all elements are equal 0.
Code:
public static void main(String[] args) {
int arr[] = { 2, 9, 1, 5, 1, 4, 9, 7, 2, 1, 4 };
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
} else if (arr[i] < min) {
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
int i = 0;
while (i < arr.length) {
for (int j = 0; j < count.length; j++) {
if (count[j] > 0) {
arr[i++] = j + min;
count[j]--;
}
}
}
System.out.println(Arrays.toString(arr));
}
Time O(n), Space O(n)
- thelineofcode September 16, 20131) Compute LIS for the whole array using a standard DP approach -> You will find LIS for the last element.
2) Check if there is a circle:
if (arr[length-1] < arr[0]) {
set LIS[0] (for arr[0]) == LIS[arr.length-1] + 1;
invoke step 1 (this time we start from LIS[0] == LIS[arr.length-1] + 1 instead of 1 like during the first invocation);
}
3) Find max value of LIS
Code:
public static void main(String[] args) {
// int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
// int[] arr = { 5, 6, 7, 1, 2, 3 };
// int[] arr = { 5, 6, 7, 1, 2, 3 };
int[] arr = { 5, 4, 3, 2, 1 };
int[] L = new int[arr.length];
increasingSubsequence(arr, L);
if (arr[0] > arr[arr.length - 1]) {
L[0] = L[arr.length - 1];
increasingSubsequence(arr, L);
}
int max = 0;
for (int i = 0; i < L.length; i++) {
if (L[i] > max) {
max = L[i];
}
}
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(L));
System.out.println(max);
}
public static void increasingSubsequence(int[] arr, int[] L) {
L[0] += 1;
for (int i = 1; i < L.length; i++) {
int maxn = 0;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i] && L[j] > maxn) {
maxn = L[j];
}
}
L[i] = maxn + 1;
}
}
This is obvious. The question is how to traverse a tree without root and additional pointer in nodes?
Cheers!
What does it mean "You may assume that the system already knows what are nouns and verbs" ? Do we have a function like isVerb(String word) or isNoun(String word)? If yes we can check words one by one and print them if at least one function return true. Can you explain the task in more detail?
- thelineofcode July 30, 2013The original version of this question is here:
red.cliff.jp/topcoder/RoughStrings.txt
Algo is as follows:
1) Iterate over possible values of roughness and check if given value can be achieved
a) if yes reduce the value
b) if no increase the value
2) Repeat a and b till no change is possible
3) To check if roughness can be achieved check every possible combination of min and max value counting number of needed changes which has to be done to achieved given roughness. If number of changes <= n then roughness can be achieved.
Code:
boolean check(int r, int[] freq, int n, int len) {
for (int min = 1; min <= len; min++) {
int max = r + min;
int need = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] == 0) {
continue;
}
if (freq[i] < min) {
need += freq[i];
} else if (freq[i] > max) {
need += freq[i] - max;
}
}
if (need <= n) {
return true;
}
}
return false;
}
public int minRoughness(String s, int n) {
int[] freq = new int[26];
int len = s.length();
for (int i = 0; i < len; i++) {
freq[s.charAt(i) - 'a']++;
}
int left = 0;
int right = len;
while (left < right) {
int mid = (left + right) / 2;
if (check(mid, freq, n, len)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] noOfRemoves = { 1, 5, 1, 5, 17, 2 };
String[] s = { "aaaaabbc", "aaaabbbbc", "veryeviltestcase", "gggggggooooooodddddddllllllluuuuuuuccckkk",
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", "bbbccca" };
for (int i = 0; i < s.length; i++) {
System.out.println(new RoughStrings().minRoughness(s[i], noOfRemoves[i]));
}
}
Trie would help, if keys had common prefixes. We don't know that, though.
- thelineofcode July 27, 2013public static void main(String[] args) {
BinaryTreeNode n2 = new BinaryTreeNode(null, null, 2);
BinaryTreeNode n6 = new BinaryTreeNode(null, null, 6);
BinaryTreeNode n5 = new BinaryTreeNode(n2, n6, 5);
BinaryTreeNode n12 = new BinaryTreeNode(null, null, 12);
BinaryTreeNode n14 = new BinaryTreeNode(null, null, 14);
BinaryTreeNode n13 = new BinaryTreeNode(n12, n14, 13);
BinaryTreeNode n20 = new BinaryTreeNode(null, null, 20);
BinaryTreeNode n15 = new BinaryTreeNode(n13, n20, 15);
BinaryTreeNode root = new BinaryTreeNode(n5, n15, 10);
BinaryTreeNode head = treeToList(root);
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
}
public static BinaryTreeNode treeToList(BinaryTreeNode root) {
if (root == null) {
return null;
}
BinaryTreeNode right = treeToList(root.right);
BinaryTreeNode listNode = new BinaryTreeNode(null, null, root.value);
listNode.next = right;
BinaryTreeNode left = treeToList(root.left);
if (left != null) {
BinaryTreeNode n = left;
while (n.next != null) {
n = n.next;
}
n.next = listNode;
}
return left != null ? left : listNode;
}
//output: 2 5 6 10 12 13 14 15 20
public static void main(String[] args) {
int[] a = { 5, 1, 6, 1, 1, 7 };
//int[] a2 = { 6, 7, 3, 4, 8 };
triplet(a);
}
public static void triplet(int[] a) {
int[] triplet = new int[3];
int min = triplet[0] = a[0];
triplet[1] = triplet[2] = Integer.MAX_VALUE;
for (int i = 1; i < a.length; i++) {
if (a[i] <= min)
min = a[i];
else if (a[i] <= triplet[1]) {
triplet[0] = min;
triplet[1] = a[i];
} else {
triplet[2] = a[i];
System.out.println("T1: " + Arrays.toString(triplet));
break;
}
}
}
1. Initialize list 'result' and queues Q2, Q3 and Q5
2. Insert 1 into result.
3. Insert 1*2, 1*3 and 1*5 into Q2, Q3 and Q5 respectively.
4. Let x be the minimum element in Q2, Q3 and Q5. Append x to result.
5. If x was found in:
Q2 -> append x*2, x*3 and x*5 to Q2, Q3 and Q5. Remove x from Q2.
Q3 -> append x*3 and x*5 to Q3 and Q5. Remove x from Q3.
Q5 -> only append x*5 to Q5. Remove x from Q5.
We do not need to append x*2 and x*3 to all lists because
they will already be found in another list.
6. Repeat steps 4 - 6 until we’ve found k elements.
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<Integer>();
numbers.add(1);
LinkedList<Integer> q2 = new LinkedList<Integer>();
LinkedList<Integer> q3 = new LinkedList<Integer>();
LinkedList<Integer> q5 = new LinkedList<Integer>();
List<LinkedList<Integer>> queues = new ArrayList<LinkedList<Integer>>(3);
q2.add(2);
q3.add(3);
q5.add(5);
queues.add(q2);
queues.add(q3);
queues.add(q5);
int k = 15;
for (int i = 1; i < k; i++) {
int min = Integer.MAX_VALUE;
int minQueue = 0;
for (int j = 0; j < 3; j++) {
if (queues.get(j).getFirst() < min) {
min = queues.get(j).getFirst();
minQueue = j;
}
}
queues.get(minQueue).removeFirst();
numbers.add(min);
switch (minQueue) {
case 0:
q2.add(min * 2);
case 1:
q3.add(min * 3);
case 2:
q5.add(min * 5);
}
}
System.out.println(numbers);
}
It is not D&C algorithm
- thelineofcode July 24, 2013Use quick select algorithm O(n) time
blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html
This is a variation of telephone words:
public static void main(String[] args) {
Map<Character, char[]> map = new HashMap<Character, char[]>();
map.put('f', new char[] { 'F', '4' });
map.put('b', new char[] { 'B', '8' });
String s = "fab";
printStrings(s.toCharArray(), new StringBuilder(), map, 0);
}
public static void printStrings(char[] s, StringBuilder sb, Map<Character, char[]> map, int pos) {
if (sb.length() == s.length) {
System.out.println(sb);
return;
}
char[] subs = map.get(s[pos]);
sb.append(s[pos]);
printStrings(s, sb, map, pos + 1);
sb.setLength(sb.length() - 1);
if (subs != null) {
for (int i = 0; i < subs.length; i++) {
sb.append(subs[i]);
printStrings(s, sb, map, pos + 1);
sb.setLength(sb.length() - 1);
}
}
}
Use two Stacks first for operators and the other for operands. Just like in postfix expression conversion algo.
- thelineofcode July 23, 2013This problem can be solved using recursion.
For each a[i][j] check if a[i][j] == word[k]
if(yes) {
go to eight neighbors and check if any of them is equal word[k+1]
} else {
return false;
}
Additionally keep track of the visited elements to avoid faulting results
I think this logic is correct. I just extended it to handle duplicates:
public static void main(String[] args) {
int[] arr = { 2, 2, 2, 1, 1, 1, 4, 4, 4, 3, 3, 3, 5, 5 };
//int[] arr = { 2, 2, 2 };
quickSort(arr, 0, arr.length - 1);
int[] triplet = new int[3];
for (int i = 0; i < arr.length - 2;) {
triplet[0] = arr[i];
while (i < arr.length && arr[i] == triplet[0]) {
i++;
}
for (int j = i; j < arr.length - 1;) {
triplet[1] = arr[j];
while (j < arr.length && arr[j] == triplet[1]) {
j++;
}
for (int l = j; l < arr.length;) {
triplet[2] = arr[l];
System.out.println(Arrays.toString(triplet));
while (l < arr.length && arr[l] == triplet[2]) {
l++;
}
}
}
}
}
Here is O(n) solution:
geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent
By using recursion: From each position we move by 1 and then by 2 positions:
package facebook;
public class GenerateAlphaCode {
public static char[] ALPHABET = { ' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
public static void main(String[] args) {
generateString("1123", new StringBuilder(), 0);
}
public static void generateString(String nums, StringBuilder sb, int pos) {
if (pos > nums.length()) {
return;
}
if (pos == nums.length()) {
System.out.println(sb);
return;
}
sb.append(ALPHABET[Integer.parseInt(nums.substring(pos, pos + 1))]);
generateString(nums, sb, pos + 1);
sb.setLength(sb.length() - 1);
if (pos + 2 <= nums.length()) {
sb.append(ALPHABET[Integer.parseInt(nums.substring(pos, pos + 2))]);
generateString(nums, sb, pos + 2);
sb.setLength(sb.length() - 1);
}
}
}
Assuming the range is limited and numbers are infinite:
1) Find min, max value inside the range
2) declare boolean array of length max-min+1
3) For each number set true in array in this way: arr[num-min] = true. If you the array has been already set then you have duplicate.
Good sol using 2 stacks.
- thelineofcode July 18, 2013I think it should be min-heap and hashmap - in hash map keep all products and its number of likes. Each time a user likes particular product update hashmap and check if number of likes for product is bigger then current min element in the heap.
- thelineofcode July 18, 2013First two conditions are simple so here is the implementation of the last condition which checks if there are neighboring sequences in the string. Algo is follows:
1) In array are kept the latest indexes of each character in the string.
2) If the character occurred first time we add it to the array.
3) If the character occurred second time we check if the sequence is created by checking contiguous character from the previous occurrence and current
Code:
public static void main(String[] args) {
// char[] s = "123123qs".toCharArray();
//char[] s = "123qs123qs".toCharArray();
char[] s = "1w23qs1a2323qs".toCharArray();
int[] latestIndex = new int[256];
Arrays.fill(latestIndex, -1);
int startOfSeq = -1;
int startOfPrevSeq = -1;
int seqLength = 0;
for (int i = 0; i < s.length; i++) {
if (latestIndex[s[i]] == -1) {
latestIndex[s[i]] = i;
if (startOfSeq != -1) {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
} else {
for (int j = startOfSeq; j < i; j++) {
latestIndex[s[j]] = j;
}
}
}
startOfSeq = -1;
startOfPrevSeq = -1;
seqLength = 0;
} else {
if (startOfSeq == -1) {
startOfPrevSeq = latestIndex[s[i]];
startOfSeq = i;
seqLength = 1;
} else if (s[startOfPrevSeq + seqLength] == s[i]) {
seqLength++;
} else {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
} else {
for (int j = startOfSeq; j < i; j++) {
latestIndex[s[j]] = j;
}
startOfSeq = -1;
startOfPrevSeq = -1;
seqLength = 0;
i--;
}
}
}
}
if (startOfSeq != -1) {
if (startOfPrevSeq + seqLength == startOfSeq) {
System.out.println("Not valid");
return;
}
}
System.out.println("Valid");
}
If we can work on distributed environment we can also use MapReduce algo to improve performance.
- thelineofcode December 18, 2013