sreemana@buffalo.edu
BAN USER 0of 0 votes
AnswersIm sure everyones heard of this.
Matrix with rows and column sorted. Find a particular element.
I mentioned the O(m+n) solution. He asked to make it better.
Thought for a while, then told him that you start with the last element of the first row and once you find the row which might contain the element, do a binary search on that row (since its sorted).
This further brings down the complexity to O(m+logn).
He said make it even better.
So I said do a binary search on the last column and look for the row where the element in the previous row is smaller and the element in the current row is greater than or equal to the target.
So the complexity becomes O(log m + log n).
He said ok.
When I was about to code this, he said there are two ways to implement it.
1) One you implement the dual binary search method.
2) Make use of the facts that the rows and columns are sorted.
Thought this over for a while and mentioned that instead of doing two binary searches, you can do just one considering the entire matrix as a linear array and doing binary search.
The complexity would be log(m*n)=log(m) + log(n).(Same as the previous optimal solution).
There would be some logic involved in translating the indices to (row,col) pairs. I got this working, but he wanted me to return the (row,col) pair if the element was found or (1,1) if not found.
For this he gave me the function signature
void find(int A[][10], int m, int n, int target,int&row, int col)
which is what I couldn't figure out. Here m = number of rows and n=no of cols
Here is the solution I gave// Initially pass start as 0 and end as m*n when calling function find(int A[][10],int start,int end,int target,int cols) { int mid = (start+end)/2; if (start > end) { element not found; } int r = mid/cols; int c = mid%cols; if(A[r][c] == target) { element found; } else if (target>A[r][c]) { start = mid+1; find(A[][10],start,end,target,cols); } else { end = mid1; find(A[][10],start,end,target,cols); } }
Can somebody tell me how i can return the (row,col) pairs (yes! return two values) using the function signature he mentioned.
 sreemana@buffalo.edu in United States
PS: Thanks for reading the whole post.. I know its kinda long. But I hope it helps someone. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  0of 0 votes
AnswerDifference between threads and process.
 sreemana@buffalo.edu in United States
Simple enough. Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer  1of 1 vote
AnswersCelebrity problem:
 sreemana@buffalo.edu in United States
You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one. Noncelebrities may/may not know anyone in the room. Give an algorithm to find the celebrity. Discuss the complexity. Report Duplicate  Flag  PURGE
Yahoo Software Engineer / Developer Algorithm  0of 0 votes
AnswersThis is a very simple question. But im not sure why the answer is the way it is.
 sreemana@buffalo.edu in United States
int main()
{
char *c = "abc";
*c = 'd';
printf("%s",c);
return 0;
}
What gets printed?
I said dbc for which he dint say anything and went ahead.
I coded this and found that I my compiler doesn't even give a response. I don't understand, *c sets the value being pointed to 'd' so technically this is legal right?
Can someone pitch in? Report Duplicate  Flag  PURGE
Yahoo Software Engineer / Developer
Gosh!!! Why don't you guys read the question properly.
If nobody knows anybody else other than the celebrity it becomes all the more easier.
If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)
Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!
plz read the comments for the correct solution before posting your's..Not to be rude or anything, but im tired of having to explain time and over again how the solution is O(n) for absolutely all situations!
 sreemana@buffalo.edu June 19, 2012Use a hash table.
Iterate through every character in the string and insert into the hash table with key = character and value = count.
No reiterate through the string checking the values in the hash table for each character. The first element with count = 1 should be your first nonrepeated character.
// Assume you have an ASCII coded string
char first_non_rep(char* string, int length)
{
static int hash_table[256];
int i=0;
for (i = 0;i<length;i++)
{
hash_table[string[i]]++;
}
for (i=0;i<length;i++)
{
if (hash_table[string[i]]==1)
return string[i];
}
return '\0'
}

sreemana@buffalo.edu
March 30, 2012 I think this is an overly complicated solution to a simple problem.
A lot of the details you've mentioned overlooks the coding complexity involved. Heres how:
1) Lets say Im making my graph, before I even start constructing the graph I(as a coder) need to all information about who knows whom. This information can get stored in a confusion matrix. So if I need to code this, I would have an extra memory requirement to store this information.
2) When you talk about iterating through the graph, you need to ensure that given a particular node, you should be able to reach every other node. What happens if no individual knows anybody else in the room other than the celebrity. How do you iterate through your graph then?
3) Considering directed graphs, you need to consider the possibility of having loops in them. If they do, you could easily end up in a typical infinite recursion scenario. Sure, you could maintain a visited flag variable for each node, but that again adds to your memory. Not asymptotically, but practically for small n.
4) If I give you this problem to solve in place, your graph method wont work.
5) My solution when implement in code, requires just one fuction bool knows(a,b) which simply returns true if a knows b and false otherwise. Your solution requires way more.
Your solution is valid, but you need to take the above points into consideration. As I said, this problem looks for an efficient algorithm, not your data structure manipulation skills.
Thanks.
Valid point santosh but you fail to understand the logic here. We are not looking at two people knowing each other, we are interested in knowing if one knows the other or not.(a knows b doesnt mean b knows a).
If a and be dont know each other, they both will eventually get eliminated. Try this out, trust me it works!
sure, because drawing graphs and finding the node with the maximum number of incoming nodes is what people do when a celebrity is in a room right!!!!
 sreemana@buffalo.edu March 27, 2012Ok heres the solution. SantiagoYMG is pretty close.
The solution is O(n) in time complexity.
Make all of them stand in a row.
Lets say the people are a,b,c,d,e,f,g,h,i,j,.......n
Compare a and b.
if a knows b => a is certainly not the celebrity. Probable celebrity = b
if a doesnt know b => b is certainly not the celebrity. Probable celebrity = a
In either case compare the probable celebrity to the next person in line ie 'c' and repeat the process. Each comparison should eliminate 1 person and have another as the probable celebrity. At the end, the probable celebrity who survives is the certain celebrity.
Complexity = O(n)
Guys this a pretty cool algorithmic problem. Give it a shot.
 sreemana@buffalo.edu March 26, 2012In the previous case char*c is a const char*. Lets say we change it to be char* const c, which makes it a constant pointer to a character. SO by definition you should now be able to change the value but you cant make c point to anything else right?
The below code doesnt print c either.
char* const c = "assa";
*c ="ghj";
printf("%s",c);
Also as far as I know, when you declare an array or a pointer to an array, it is basically a constant pointer to a int/char whatever. There's no reason why it shouldn't allow you to change the value being pointed to. This thing is driving me nuts. Can some explain please?
RepJennyReimer, Dev Lead at Adobe
Badminton lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
RepSoccer lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...
Open Chat in New Window
Gosh!!! Why don't you guys read the question properly.
 sreemana@buffalo.edu June 19, 2012If nobody knows anybody else other than the celebrity it becomes all the more easier.
If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)
Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!