pradegup
BAN USER 0of 0 votes
AnswersHow we can perform insert, delete and findMax operations in O(1) time using a given queue ?
 pradegup in India Report Duplicate  Flag  PURGE
Directi  3of 3 votes
AnswersYou have given n numbers from 1 to n. You have to sort numbers with increasing number of set bits.
 pradegup in India
for ex: n=5.
output: 1,2,4,3,5
Note: If you have two number with equal number of set bits, then number with lowest value come first in the output. Report Duplicate  Flag  PURGE
Microsoft Algorithm
In Addition:
(Valid String,Valid String with dest doesn't exist without write permission) return false;
(Valid String,Valid String with dest doesn't exist with write permission) return true;
(Valid String, Valid String with dest already exists with Override permission) return true;
(Valid String, Valid String with dest already exists without Override permission) return false;
You can do it in o(n) time complexity by using additional space.
Store all the elements in a hashmap as keyvalue pair, where key is number and value is index.(this will take O(n) time.)
traverse through the list and for each number see whether (sumnum) is present or not in hashmap.(searching in hashmap will take O(1) time)
if(num is present in hashmap){
print both number with indexes
}else{
do nothing.
}
Logic:
1. Array is given with n elements. and we have to search an element say x.
2. take the mid element.
Its for sure, one half of array will be in correct order.
find half array with correct order. You can find it by comparing mid element with either
first element or last element.
3. If x lies in half array with correct order, do the binary search on this half.
Otherwise, repeat step 2 and 3.
for ex: 7 8 9 0 1 2 3 4 5 6 and suppose we have to search element say 9.
here the correct half order is 2 3 4 5 6 and 9 is not part of it.
so again we will process first half array 7 8 9 0 1
here correct half order is 7 8 9 and element 9 lies in this.
so we will perform binary search on this.
This complete process will take log(n) time.
Mean: keep track of sum and number of elements.
and print sum/no_of_element.
Median: Use linkedlist to store the items in sorted fashion.
keep track of number of elements stored in linked list
Whenever a new item comes, add it into list.
based on the count of elements find the median.
Any better idea is welcome...
This function will return 1 if Equal otherwise it will return 0.
int strMatch(char str1[],char str2[]){
int arr[256];
for(int i=0;i<256;i++){
arr[i]=0;
}
for(int i=0;str1[i]!='\0';i++){
arr[str1[i]]++;
}
for(int i=0;str2[i]!='\0';i++){
if(arr[str2[i]]<=0) return 0;
arr[str2[i]];
}
for(int i=0;i<256;i++){
if(arr[i]>0) return 0;
}
return 1;
}

pradegup
October 01, 2012 All integers that is power of 2, contains only one set bit in its bitrepresentation.
So idea is to check, only one bit is set or not in bit representation of a number.
Below is the code:
int isPowerOf2(int n){
return n && !(n&(n1));
}
this function will return 1, if number n is power of 2.
Else it will return 0;
It is possible to optimize 2nd step to O(n).
 pradegup November 13, 2012Steps:
1. Assuming we have two array sorted in ascending order. say arr1 and arr2.
2. Traverse through both array,starting from index 0.
3. if arr1[i]==arr2[j] then found matching element.
else if arr1[i]<arr2[j] then i++
else j++;
In steps, I am putting only logic not boundary conditions.