CAFEBABE
BAN USER- 0of 0 votes
Answershow to find the sorted median of a continuous stream of integers. let the stream is 0,1,2,3,4 the median is 2. now let -2 comes and the median for stream -2,0,1,2,3,4 still the median is 2 or it can be 1. now again -4 comes the median for the stream -4,-2,0,1,2,3,4 is 1.
- CAFEBABE in United States for windows| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
public static int[] getlargest(int [] a, int k){
int max = Integer.MIN_VALUE;
int maxpos = 0;
int [] arr = new int [k];
for(int i=0; i<k; i++){
for(int j=0; j<a.length; j++){
if(a[j] > max){
max = a[j];
maxpos = j;
}
}
arr[i] = max;
a[maxpos] = Integer.MIN_VALUE;
max = Integer.MIN_VALUE;
}
return arr;
}
public static void main(String [] args){
int [] a = {3,5,6,41,4,7,1,2,8,19,65,21};
int [] res = getlargest(a,4);
for(int i=0; i<res.length; i++){
System.out.println((i+1)+"th largest element is : "+res[i]);
}
}
if you use only hash table or only counting array then you have to traverse the string twice making the complexity 2n. but if you use counting array along with a linked list then you can do it in one traversal and you can find kth non repeating character.
for example the input is "ccacbdedb". the steps of the algorithm are :
1. count of 'c' is 1 insert 'c' into the linked list and go ahead.
2. count of 'c' becomes 2 remove 'c' from the linked list and go ahead.
3. count of 'a' is 1 insert 'a' into the linked list and go ahead.
4. count of 'c' becomes 3 go ahead.
5. count of 'b' is 1 insert 'b' into the linked list and go ahead.
6. count of 'd' is 1 insert 'd' into the linked list and go ahead.
7. count of 'e' is 1 insert 'e' into the linked list and go ahead.
8. count of 'd' becomes 2 remove 'd' from the linked list and go ahead.
9. count of 'b' becomes 2 remove 'b' from the linked list and go ahead.
now the linked list contains only 'a' & 'e'. 'a' is the first non repeating character and 'e' is the second non repeating character. you can do it in O(n) (not O(2n)) time in single iteration.
public static int[] getlargest(int [] a, int k){
int max = Integer.MIN_VALUE;
int maxpos = 0;
int [] arr = new int [k];
for(int i=0; i<k; i++){
for(int j=0; j<a.length; j++){
if(a[j] > max){
max = a[j];
maxpos = j;
}
}
arr[i] = max;
a[maxpos] = Integer.MIN_VALUE;
max = Integer.MIN_VALUE;
}
return arr;
}
public static void main(String [] args){
int [] a = {3,5,6,41,4,7,1,2,8,19,65,21};
int [] res = getlargest(a,4);
for(int i=0; i<res.length; i++){
System.out.println((i+1)+"th largest element is : "+res[i]);
}
}
public class number_separation_epic {
public static void main(String [] args){
char [] str = {'4','6','7','8','9','1','2','3','5','6','0','1','2','3','5','6'};
char [] res = new char[str.length*2];
int prev = 0; int cur = 1; int i = 0;
while(cur < str.length){
int curval = (int)str[cur] - 48;
int preval = (int)str[prev] - 48;
if(curval == preval+1){
res[i] = str[prev];
prev += 1; cur += 1; i += 1;
}
else{
res[i] = str[prev]; res[i+1] = ';';
prev += 1; cur += 1; i += 2;
}
}
res[i] = str[prev]; res[i+1] = ';';
for(char c:res){
System.out.print(c);
}
}
}
to all of you who have implemented array to find the median : the input is a continuous string of integers. that means integers are coming continuously. so the number of integers tends to infinity theoretically and practically you are not obviously supposed to store them all in an ARRAY to find the median. if you do that then your program will crass after the memory is filled. this type of questions are asked to check if you are able to think of space complexity or not. so i would suggest never start with an array. it'll suddenly cost you negative points in the interviews.
and the answer of kill is the best described and the optimal one. my answer would work but i can get median in O(log n) time where kill can do it in O(1) time.
thanks friends for replying to this question.
hi all,
my answer was
1. create a BST and a counter.
2. each time you get a number insert it into the BST and increment the counter.
3. each node in the BST has a field "rank" that is the number of nodes in the subtree rooted at that node.
4. when median is asked return the node whose rank = counter/2 if counter is odd else return the node whose rank = (counter/2)-1
first the stream is 0,1,2,3,4. the tree will be
0(4)
\
1(3)
\
2(2)
\
3(1)
\
4(0)
counter = 5
now median is 2 as rank(2) = (counter/2).
now comes -2. the tree will be
0(5)
/ \
(0)-2 1(3)
\
2(2)
\
3(1)
\
4(0)
counter = 6
(counter/2)-1 = 2
median is node 2 as rank(2) = 2.
now comes -4. the tree will be
0(6)
/ \
(1)-2 1(3)
/ \
(0)-4 2(2)
\
3(1)
\
4(0)
counter = 7
counter/2 = 3
median = 1 as rank(1) = 3
please tell me if there is any problem in this algorithm. please try it on some other examples and if you find anything not working properly then please notify.
thanking you all
please go through the code and tell me if there is anything wrong. all the constructive comments are always welcome. thank you.....
public class linked_list_of_anagrams {
public static class node{
public String s;
public node next;
public node(String a){
s = a;
next = null;
}
}
public static class linked{
public node head = null;
public void insert(String s){
node n = new node(s);
if(head == null){
head = n;
}
else{
node hn = head;
while(hn.next != null){
hn = hn.next;
}
hn.next = n;
}
}
public void display(){
node h = head;
while(h != null){
System.out.println(h.s);
h = h.next;
}
}
}
public static void anagram(String sub, String a, linked l){
int n = a.length();
if(n == 0){
l.insert(sub);
}
else{
for(int i=0; i<n; i++){
String temp = sub+a.charAt(i);
String b = a.substring(0, i)+a.substring(i+1,n);
anagram(temp, b, l);
}
}
}
public static void main(String [] args){
String s = "abc";
linked l = new linked();
anagram("", s, l);
l.display();
}
}
ALGORITHM:
1. take the colored squares as 0 and the non-colored squares as 1. then form a n*n matrix 'a'.
2. now we have to find the largest square matrix having all 1's.
3. fill up the 1st row of the result (n*n) matrix as the matrix 'a'.
4. then from the second row on wards
4.1. if you find a[i][j] == 0 then res[i][j] = 0.
4.2. else res[i][j] = min(res[i-1][j], res[i][j-1], res[i-1][j-1])+1.
5. after creating the 'res' matrix the size of largest uncolored square will be the largest element in the 'res' matrix.
i'm giving the program that will find the size of the sub-square-matrix having all 1's.
the program for that is
public static void main(String [] args){
int [][] arr = {{0,1,1,0,1,0},
{1,1,0,0,1,0},
{0,1,1,1,0,1},
{0,1,1,0,0,1},
{0,1,1,1,0,1}};
int col = arr[0].length;
int row = arr.length;
int [][] res = new int [row][col];
for(int i=0; i<col; i++){
res[0][i] = arr[0][i];
}
for(int i=0; i<row; i++){
res[i][0] = arr[i][0];
}
for(int i=1; i<row; i++){
for(int j=1; j<col; j++){
if(arr[i][j] == 1){
res[i][j] = Math.min(Math.min(res[i][j-1], res[i-1][j]),res[i-1][j-1]) + 1;
}
else{res[i][j] = 0;}
}
}
System.out.println("the distance matrix is : ");
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
System.out.print(res[i][j]+" ");
}
System.out.println("");
}
int max = Integer.MIN_VALUE;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
max = Math.max(max, res[i][j]);
}
}
System.out.println("max square : "+max);
}
- CAFEBABE March 14, 2012