loveCoding
BAN USERIf both arrays are sorted, This can be done in O(log m log n).
Here is how
1. Find middle element of both arrays say a=A[mid1] and b=B[mid2].
2. If a==b return 0, we have found the min
3. If(a>b) min is Min(|a-b|, minimum in A(0.. mid1) and B(mid2... end))
4. if(a<b) min is Min(|a-b|, minimum in A(mid1... end) and B(0... mid2))
Two approaches
1. Build Hash with smaller file and check for match in other Time O(n) Space O(n)
2. Sort both files (nlogn) and now find match with 2 fingered approach O(n) total complexity O(nlogn) + O(n) = O(nlogn)
Here is the algo
1. Find average for whole array
2. Now start with first element and parse through array. Find average so far stop if equal.
3. return the index;
Code Below:
int findEqualAverage(int[] A){
int sum = 0;
for(int i=0;i<A.length;i++){
sum += A[i];
}
float average = (float)sum/(float)A.length;
sum = 0;
for(int i=0;i<A.length;i++){
sum+=A[i];
float averageSofar = ((float)sum)/(i+1);
if(averageSofar == average)
return (i+1);
}
}
The comment has been deleted
- loveCoding December 04, 2013@Diego so what is your answer for {(1,2) (3,4) (5,6) (7,8)}
SO in this case when you compare only 2,6 and 7,8, you need to output (1,2)(7,8) , (3,4)(7,8) and (5,6)(7,8).. so outputing your result will any way take n^2 time
Complexity can never be less than O(n^2) for this case as there can be possible n^2 cases if all of the ranges are NOT overlapping e.g. (1,2) (3,4) (5,6) (7,8) in this case total number of ranges that are not overlapping is C(n,2) which in O(n^2)
- loveCoding December 03, 2013DO we have to ouput always in pairs? For example can answer in example be {(1,2) (3,6) 8,10)}
- loveCoding December 03, 2013Here is the approach
1. First reduce the string to non-repetitive characters like fors hhiirreee -> hire or hhiirreehhii->hirehi
2. Now in final reduced String check if its repettion of "hire". E.g. hir or hirehire wil be valid whereas hirehi is NOT
boolean isValid(String word){
//TODO:Check for null and empty
String reduced = new String(word.charAt(0));
for(int i=1;i<word.length;i++){
char c = word.charAt(i);
if(c==reduce.charAt(reduced.length-1))
continue;
else
reduced += c;
}
//Check if reduced is made up with only "hire"
for(int i=0;i<reduced.length;i=i+4){
if(reduced.length<i+4)
return false;
else{
if("hire".equals(reduced.substring(i,i+4))
return false;
}
}
return true;
}
Have an extra field in stack that tracks the min so far.
- loveCoding August 13, 2013If this was the question for a software engineer, yahoo should soon be closing I think..
- loveCoding July 24, 2013void sort(Node p1, Node p2) {
if (p1 == null)
return p2;
if (p2 == null)
return p1;
Node res = new Node(p1.data < p2.data ? p1.data : p2.data);
if (p1.data < p2.data)
p1 = p1.next;
else
p2 = p2.next;
Node endNode = res;
while (p1 != null && p2 != null) {
if (p1.data < p2.data) {
endNode.next = p1;
endNode = endNode.next;
p1 = p1.next;
endNode.next = null;
} else {
endNode.next = p2;
endNode = endNode.next;
p2 = p2.next;
endNode.next = null;
}
}
if (p1 == null)
endNode.next = p2;
else if (p2 == null)
endNode.next = p1;
return res;
}
Akbar-The-Slave, The emperor has written his own power method.
- loveCoding July 24, 2013Ans is 5*P*P
- loveCoding July 24, 2013The simple mirroring is easy here is the solution for alternate mirroring
//Initial value for level is 1 i.e root
void alterMirror(Node noot, int level){
if(root==null)
return;
if(level%2==0){
Node tem = root.left;
root.right = root.left;
root.left = temp;
}
level++;
alterMirroe(root.left,level)
alterMirror(root.right,level);
}
}
n!
- loveCoding July 16, 2013oh nice.....
- loveCoding May 17, 2013Are you sure without second traversal... it can be done in O(n) but second traversal would be needed
- loveCoding May 17, 2013//This in my opinion is best solution as I love CODING...
reverseBinary(int num){
int rev = 0;
//Considering num is 4 bytes
for(int i=0;i<4*8;i++){
rev = (rev<<1) | (num&1);
num = num>>1;
}
return rev;
}
I agree tries may be a better solution BUT can someone give code?
- loveCoding January 11, 2013I am assuming in case of "aaaa" . "aaa" is repeated string
public static String findRepeated(String str){
HashMap<String, Integer> map = new HashMap<String,Integer>();
int start = 0;
while(start+3 <= str.length()){
String key = str.substring(start, start+3);
if(map.containsKey(key))
return key;
else
map.put(key, 1);
start += 1;
}
return "";
}
hashcode()
- loveCoding October 26, 2012N = (N & 0xAAAA)>>1 | (N & 0x5555)<<1
- loveCoding October 24, 2012Two easy steps
1. First find transpose
2. Swap first and last column, second and second last column and so on
Code here
static void rotate90(int[][]a){
int n = a.length;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
//Swap a[i][j] and a[j][i]
a[i][j] = a[i][j] ^ a[j][i];
a[j][i] = a[j][i] ^ a[i][j];
a[i][j] = a[i][j] ^ a[j][i];
}
}
//Now swap colums
int i=0;
int j=n-1;
while(i<j){
for(int k=0;k<n;k++){
//Swap a[k][i] and a[k][j]
a[k][i] = a[k][i] ^ a[k][j];
a[k][j] = a[k][j] ^ a[k][i];
a[k][i] = a[k][i] ^ a[k][j];
}
i++;
j--;
}
}
}
Delete the Nth node and the next (N-1)th node , next (N-2)th node and so on unless you come to end.
- loveCoding October 22, 2012http://ideone.com/MV0Sd
- loveCoding October 17, 2012We can maintain a Minheap of most occuring N words and a Hasmap for occurence of words.
- loveCoding October 16, 2012Here is the solution.
1. Set String one = s1+s2
2. Set String two = s2+s1
3. Now if(one > two) return one+two else return two+one
Below is the java Code
String maxNumber(String s1, String s2){
String one = s1 + s2;
String two = s2 + s1;
for(int i=0;i<one.length();i++){
if(one.charAt(i) > two.charAt(j))
return one;
else if(one.charAt(i) < two.charAt(j))
return two;
}
//If we come here means both are equal, so return anything
return one;
}
Yes both question are very similar
- loveCoding October 12, 20121. We can build a bool array of 256 (assuming all ASCII) and then build hash for String B O(n) space and O(n) time
2. Now go through A and check the bool array if any index is false return false. Below is the code
boolean isAinAB(String A, String B){
boolean[] map = new boolean[256];
// Build HashMap
for(int i=0;i<B.length();i++)
map[B.charAt(i)] = true;
for(int i=0;i<A.length();i++)
if(map[A.charAt(i)] == false)
return false;
return true;
}
Good Question again. This is the limitation.
Do you have any solution for unsorted array when adding n overflows?
Please try to explain algorithm before posting the code..
- loveCoding September 27, 2012Good question.
Actually in that case we can modify the logic by adding n to the number and checking for if number is greater than n instead of checking for -ve.
This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element
E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a[2]) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}
Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4
This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element
E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a[2]) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}
Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4
This is an interesting approach but it has limitation but I think amir will be given some points for this in real interview.. better than people like CuriousCat who just give non-contructive comments in all the posts...
- loveCoding September 26, 2012since N<1000, I think O(N^3) Vs O(N) does NOT matter. Query time is what is important and thats constant in my solution.
- loveCoding September 25, 2012Do we need something like "boolean isElementUnique(int x)"?
If you want to find identical that can be done in O(n)
Brute force would be O(n*n). That is comparing all possible permutation.
We can do little better if we calculate permutation only starting with minimum element i.e. A. In this example we have 3 permutations for that.
We gonna create hashMap for every parent and have ArrayList of childs
For Each line in the file(e.g. 4,17,Scott)
1. Check if parent (17) is present in Hash
1a If No create and Arraylist and add (4,Scott) in that.
1b If yes add (4,Scott) in the existing ArrayList.
2. Now start with 0 and print the output
NOTE : Solution works only when 0 is the root directory. If NOT we will need to track for a node that does NOT have any parent.
correct
- loveCoding September 24, 2012Space O(n*n) time O(1)
1. Initial array of Solution[n,n] with all zeros
2. for every (x,y) Increment values of Solution[0][0] till Solution[x][y] by 1.
3. Now we can provide the result in constant time
No.
- loveCoding September 20, 2012I am not sure if I got your question.
The rightmost child in a level will be the maximum element
Here is the Algo Say two sets A and B have size a and size b where a<=b
1. Build Hashmap of size a for each element in A
2. Now go through each element of B(say x) and look for (val - x) in HashMap, If found return true.
1. MultiThreading
2. If code depends on system time
O(n) algo
Take two pointers and point to first and second element respectively
1. If first pointer points to odd number and second points to even, they are in correct position so move both pointers by two.
2. If first pointer points to even number and second points to odd, swap values and move both pointers by two.
3. If exactly one pointer moves to wrong position i.e first pointer points to even on second pointer points to odd, move the pointer in correct position by two places and go to step 1.
EDIT : To maintain the order, we can change the third condition by swapping the values at wrong pointer and right pointer before moving forward by two places.
What if two tiny URL point to same link.. How will you handle that case..
- loveCoding September 13, 2012It can be sone in O(m+n) and O(m) space where m<=n
1. First find Inorder travelsal of smaller tree and store it in array. O(m).
2. Now Go through second tree inorder and start with the first element of array. If found print the element. If the element in array is less than the element on tree move to the next element of array.
are the elements need to be continuous?
- loveCoding September 06, 2012
First go through the array and find max with all indices(store indices in arrayList).
- loveCoding July 21, 2014This can be done in O(n).
Now with newly created indices arraylist, return the random element.