thelineofcode
BAN USERIn other words we have to find max sum such that no two elements are adjacent.
Code
private static void findMaxSum(int arr[]) {
int incl = arr[0];
int excl = 0;
int excl_new;
int i;
for (i = 1; i < arr.length; i++) {
excl_new = Math.max(incl, excl);
incl = excl + arr[i];
excl = excl_new;
}
System.out.println(Math.max(incl, excl));
}
Space O(1), time O(n)
Refer to geeksforgeeks for details.
If I come up with a better idea I'll post it. I'm not sure if it can be done faster.
- thelineofcode January 12, 2014Make preorder traversal and for each leaf count its depth. In a separate variable keep the level of the previously found leaf. When you reach next leaf compare its depth with the previous one.
Code:
Integer lastLevel = null;
public boolean checkDepth(Node n, int level) {
if (n.left == null && n.right == null) {
if (lastLevel == null || lastLevel.equals(level)) {
lastLevel = level;
return true;
}
return false;
}
boolean result = true;
if (n.left != null) {
result = checkDepth(n.left, level + 1);
}
if (result == true && n.right != null) {
result = checkDepth(n.right, level + 1);
}
return result;
}
I think its about first option.
- thelineofcode January 12, 2014You can use k means algorithm.
For example n = 12 and k = 3. So we have to create 4 clusters (call it 'nc' - number of clusters) which contain 3 points.
1) Choose randomly 'nc' - 4 points as an initial cluster's centers.
2) Assign remaining points to the centers (closest points to the center's center are assigned to it). in this way we have just created clusters.
3) Recompute a center of each cluster. New cluster's center is the average of coordinates of all points in the cluster.
4) Repeat 2,3 till there is no changes in the clusters. In other words we found nc clusters which contain k closest points.
5) Check the total distance between points in each cluster and choose the one for which the total distance is minimum.
Do inorder traversal till you find first higher value then n - 9.
public static Integer find(Node root, int n) {
if (root == null) {
return null;
}
Integer result = null;
result = find(root.left, n);
if (root.v <= n) {
result = find(root.right, n);
} else {
return root.v;
}
return result;
}
Modification of binary search. I assume there is no duplicates in array.
int rotatedBinarySearch(int A[], int N, int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
int M = L + ((R - L) / 2);
if (A[M] == key)
return M;
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
Refer to leetcode.
- thelineofcode January 11, 2014Do inorder traversal till you find first higher value then n - 9.
public static Integer find(Node root, int n) {
if (root == null) {
return null;
}
Integer result = null;
result = find(root.left, n);
if (root.v <= n) {
result = find(root.right, n);
} else {
return root.v;
}
return result;
}
public static int count(String s) {
char[] c = s.toCharArray();
int max = 0;
int count = 0;
int leftCount = 0;
int rightCount = 0;
for (int i = 0; i < c.length; i++) {
if (rightCount > leftCount) {
return -1;
}
if (c[i] == '(') {
leftCount++;
count++;
if (count > max) {
max = count;
}
} else if (c[i] == ')') {
rightCount++;
count--;
}
}
if (leftCount != rightCount) {
return -1;
}
return max;
}
id=5024570117455872
- thelineofcode January 11, 2014Create a Trie out of the dictionary. Search time will be O(c) where c is the number of letters in the word which you want to find regardless how many words is in the dict.
- thelineofcode January 11, 2014Longest common substring doesn't have to palindrome.
- thelineofcode January 10, 2014Here good description of the algo:
books.google.pl/books?id=4j_GfM0tyPUC&pg=PA60&dq=longest+common+substring+problem&hl=pl&sa=X&ei=v1_QUt-gHqrV4ATPtoGQDQ&ved=0CDUQ6AEwAA#v=onepage&q=longest%20common%20substring%20problem&f=false
Note building generalized suffix tree can be done using ukkonen's algorithm in linear time.
- thelineofcode January 10, 2014Here is my attempt:
Lets say there is an array of n elements int[] arr = new int[n];
1) Sort array
2) For every element a[i] find its perfect matching pair. By perfect matching pairs I mean elements a[i], a[j] which sum a[i] + a[j] % 100 is the closest to 0.
2) Mix them and insert new element on its position in the original array so that it is taken in to account during the next 'search and merge' phase.
3) Repeat the process till there is only one element.
Eg.
int[] arr = {3,5,95, 99}
Starting from the first element a[i] = 3 find perfect pair:
1)
100 - a[i] = 97
- the perfect match for 3 would be 97 say X
2) Use binary search to find X. However there is no such value. But we will get next bigger element from 97 which is 99 call it Y as a result of bin search.
2) Because the perfect match was not found we have to check the following conndition
min ((a[i] + a[i+1]) % 100, (a[i] + Y) % 100)
to find a perfect match. In our example it is
min ((3+ 5) % 100, (3 + 99) % 100)
so we choose (3,99) and mix them.
3) New array is
int[] arr = {2,5,95}
, Repeat 1 and 2 to find pairs for the rest of elements.
- (5, 95), (2, 0), (2)
At the and we should get min smoke.
@Arth my interpretation of this question is that the final smoke is the sum of all smokes produced during mixing. So though in the last step you will get color with 0 smoke it doesn't mean that the sum of previous ones is minimum.
- thelineofcode January 09, 2014Well explained +1
- thelineofcode January 08, 2014Is it the same id=5717814883123200?
- thelineofcode January 08, 2014I'm not sure if this answer is correct. The question is about subsequence not subarray. In case of the input: {1, -10, 2, -10, 3} the output should be 6 not 3.
- thelineofcode January 08, 2014You can refer to this question: id=5932349506191360
- thelineofcode January 07, 2014Graph can have a cycle ie. {"abcde" efgea","ekl"}; First and second element create a cycle. According to topological sort theory "A topological ordering is possible if and only if the graph has no directed cycles". So how do you want to perform topological sort on it?
- thelineofcode January 07, 2014I think such simple approach won't work.
Consider this: {"abcde", "efgea","ekl"};
In your solution you will concatenate abcde - > efgea since "efgea" is first in alphabetical order and "ekl" has no match. Whereas correct sort is
"efgea" - > "abcde" -> "ekl"
@Nikhil Katre, I didn't use any sophisticated formula :) Here is simple explanation on example:
What we know:
1) There are 9 numbers consisting of 1 digit (range from 1-9)
2) There are 90 numbers consisting of 2 digits (10-99)
3) There are 900 numbers consisting of 3 digits (100-999)
and so on...
Now consider number 121. It is in range from 100 to 999 - 3 digits numbers
We have to compute how many digits consisting of 3 digits are located before this number - (n - 100) * 3
And add all remaining numbers 90 * 2 + 9
Hope this helps.
Here is more general solution for new requirements:
public static int findIndex(int n) {
int range = 1;
int numsBefore = 0;
int count = 0;
int temp = n;
while (temp > 10) {
int numsInRange = (int) (9 * Math.pow(10, count++) * count);
numsBefore += numsInRange;
range *= 10;
temp /= 10;
}
return (n - range) * (count + 1) + numsBefore;
}
@ekta1007 you don't understand the question. It is not pattern matching.
- thelineofcode January 07, 2014Yes, that was my assumption. I updated my answer to handle or ASCII characters.
- thelineofcode January 06, 2014What kind of graph?
Here are some approches: stackoverflow.com/questions/12188887/using-a-map-for-a-graph
Java but it requires minor changes to adjust to C
public static void main(String[] args) {
int[] count = new int[128];
char[] input = { 'A', 'B', 'C', 'B', 'A', 'C', 'A', 'B', 'C', 'A', '#' };
for (int i = 0; i < input.length; i++) {
count[input[i]]++;
}
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
System.out.println((char) (i) + " = " + count[i]);
}
}
}
Q1)
public static int divide(int divisor, int dividend) {
int quotient = 0;
while (divisor <= dividend) {
dividend = dividend - divisor;
quotient++;
}
return quotient;
}
Q2)
Method 1: Sort the array and then do the following (O(n log n)):
p=0,q=n-1;
while(p<q)
{
if(a[p]+a[q]==k)
{
cout<<a[p]<<"\t"<<a[q];
p++;
q--;
}
else if(a[p]+a[q]>k)
q--;
else
p++;
}
Method 2: We can use set (O(n)):
public static void findTwoNumbers(int a[], int sum) {
Set<Integer> set = new HashSet<Integer>();
int count = 0;
for (int i = 0; i < a.length; i++) {
if (!set.contains(a[i])) {
int remainder = sum - a[i];
if (set.contains(remainder)) {
System.out.println(++count + ") Found sum: " + sum + " = " + a[i] + " + " + remainder);
}
set.add(a[i]);
}
}
}
I would go for a graph solution.
Construct a graph and connect all employees who work together e.g if A works with B and B works with C then the connection is as follows A-B-C. For each node perform search and create its team. Skip nodes which has been already assigned to teams. In this way transitive property will be handled quite well.
Yes, it provides max count. Each time a new customer is assigned to the room increment counter. Just like in the example. At the end you will have max.
- thelineofcode January 03, 2014Group customers according to their favorite room's number:
1) Map<Integer, List<Customer>>
2) Sort each customer's list according to arrival time (you can also use Queue instead of list and write custom comparator. it might be more realistic :) )
3) for each room iterate over its queue
- first customer get access
- counter++;
- set variable departureTime = customer.endingTime
if(nextCustomer.startTime > departureTime){
departureTime = nextCustomer.endingTime
counter++
}
In most cases when the question is related to sub array the Kadane's algorithm is very useful. The real problem in this question is to find largest contiguous sub array for which difference 'numberOfZeros - numberOfOnes' is the biggest to maximize the sum of ones after flipping zeros.
Here is modified version of Kadane's algorithm to do this job.
It converts 0 to -1 and computes the sum till the sum is <=0 (there is more 0s then 1s).
If the sum is > 0 starts from the beginning.
The major difference compare to ordinary Kadane's algorithm is that we are looking for the biggest negative sum instead of positive.
Code:
public static void flipBits(int[] a) {
int maxDiff = 0;
int flipStartIndex = 0;
int flipEndIndex = 0;
int onesToFlip = 0;
int totalNumberOfOnes = 0;
int currentDiff = 0;
int currentStart = 0;
int currentOnesToFlip = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
currentDiff -= 1;
} else {
currentDiff += 1;
currentOnesToFlip++;
totalNumberOfOnes++;
}
if (currentDiff < maxDiff) {
maxDiff = currentDiff;
flipStartIndex = currentStart;
flipEndIndex = i;
onesToFlip = currentOnesToFlip;
} else if (currentDiff > 0) {
currentDiff = 0;
currentStart = i + 1;
currentOnesToFlip = 0;
}
}
System.out.println(flipEndIndex - flipStartIndex + 1 - onesToFlip + totalNumberOfOnes - onesToFlip);
}
Space O(1), Time O(n)
- thelineofcode January 02, 2014Doesn't work for { 0,0,0,0,1,1,1,0,0,0,0 }.
Correct ans is 8, whereas output is 7
Doesn't work for: {1,1,1,0,0,1,1,1,0,0};
- thelineofcode January 02, 2014Its not majority voting algorithm. In Moore's algo you decrease the counter if the currently checked element is different then the candidate till the counter is equal 0.
So the part:
else
{
element=a[i];
count=1;
}
should be change as follows for Moore's algo:
else
{
element=a[i];
count--;
}
In arunkumar267's solution he simply starts counting from the beginning when he finds new value and its perfectly fine.
- thelineofcode January 02, 2014public Map<Integer, Double> getFinalScores(List<TestResult> resultList) {
Map<Integer, Double> finalScores = new HashMap<Integer, Double>();
for (TestResult result : resultList) {
if (finalScores.containsKey(result.studentId)) {
finalScores.put(result.studentId, finalScores.get(result.studentId) + result.testScore);
} else {
finalScores.put(result.studentId, Double.valueOf(result.testScore));
}
}
return finalScores;
}
There is well known solution for finding loops in the list.
Maintain two pointers fast and slow.
fast change as follows fast = fast.next.next
slow change as follows slow= slow.next
If they meet at some point then there is a loop.
If fast reach the end of the list then there is no loop.
public static Node mergeLists(Node head1, Node head2) {
Node newHead = new Node();
if (head1.value <= head2.value) {
newHead.value = head1.value;
head1 = head1.next;
} else {
newHead.value = head2.value;
head2 = head2.next;
}
Node prev = newHead;
while (head1 != null && head2 != null) {
Node n = new Node();
if (head1.value <= head2.value) {
n.value = head1.value;
head1 = head1.next;
} else {
n.value = head2.value;
head2 = head2.next;
}
prev.next = n;
prev = n;
}
while (head1 != null) {
Node n = new Node();
n.value = head1.value;
head1 = head1.next;
prev.next = n;
prev = n;
}
while (head2 != null) {
Node n = new Node();
n.value = head2.value;
head2 = head2.next;
prev.next = n;
prev = n;
}
return newHead;
}
The second number in your example is out of range of int type in java.
I assume that the result and numbers are in range of int type:
Code:
private static void concat(long a, long b) {
long temp = b;
while (temp > 0) {
temp /= 10;
a *= 10;
}
a += b;
System.out.println(a);
}
Time complexity O(m) - m number of digits in sec number.
- thelineofcode December 30, 2013question?id=5684901156225024
- thelineofcode December 23, 2013char[] s1 = "TEHUNOOL".toCharArray();
char[] s2 = "ONLEHTUO".toCharArray();
transpose(s1, s2);
public static void transpose(char[] s1, char[] s2) {
int i = 0;
System.out.println(Arrays.toString(s1));
System.out.println(Arrays.toString(s2) + "\n");
while (i < s2.length) {
if (s2[i] == s1[i]) {
i++;
System.out.println(Arrays.toString(s1));
} else {
int j = i;
while (j < s1.length - 1 && s2[i] != s1[i]) {
char temp = s1[j];
s1[j] = s1[j + 1];
s1[j + 1] = temp;
j++;
}
}
}
System.out.println("\n" + Arrays.toString(s1));
System.out.println(Arrays.toString(s2));
}
Some neither have top nor limit ;)
- thelineofcode December 20, 2013Yes, there can be one 0 and one max (N -1)
- thelineofcode December 20, 2013Here are some of my thoughts which in my opinion can be used for solving this problem:
Assuming that all players play with each other and each group consists N players:
1) Total number of scores for a particular group has to be equal N(N-1)/2 e.g
- N = 2 => total is 1
- N = 3 => total is 3
- N = 4 => total is 6
2) Max score for a particular player is N - 1 when he won all of his games
So:
For each group check if the following constraints are not violated.
If the group contains -1 values check all permutations of '-1' values replacing them with numbers from 0 - (N-1).
Sum number of all combinations which don't break constraints.
Yep, taking into account only binary search it is - O(logn).
- thelineofcode December 20, 2013String accumulate(iBinaryOperator op, int[] operands) {
if(operands.length == 0) {
return "error"
}
Integer result = operands[0];
for(int i=1; i < operands.length; i++) {
result = op.calc(result, operands[i]);
}
return result.toString();
}
1) Just iterate over array and check if the element is equal 'e'. O(n) time O(1) space
2) If you sort an array (eg. quick sort) you can use binary search to find first and last location of 'e'.
Whole operation - O(n logn) time, O(1) space , Bin Search O(log(n)) time
So 2 is better only if we are considering searching phase. For whole algo better is 1.
1) Iterate over tails and:
a) count number of wild cards (blank tails)
b) if tail is not blank add the char to Set<Char>
2) For each word check if Set contains all its letters
- if letter is not included decrease number of wildcards
- if letter is not included and number of wildcards is 0 then you can not create a word
I think it is nor possible to do it in O(n) time complexity without extra space. In order to remove duplicates we have to keep track of elements which have been already processed or time complexity will be bigger cause multiple check of the same elements is required.
- thelineofcode December 19, 2013Can we reuse the same array's elements to compute multiple sums? I mean for this ex and K = 4:
a[]: 1 2 3
b[]: 1 4 7
The correct answer is 1+1, 2 + 1, 3+1, 1+4 ?
Obviously it won't since Integers and primitives are immutable in Java. If you want to pass it as an argument you have to create wrapper for Integer and pass the value in that wrapper object.
like
This is the reason why I used instance variable.
- thelineofcode January 12, 2014