Free Bird
BAN USERYou are right @sai. But what you are talking theoritical. Normally in interview questions we do not assume worst case for HashMaps that is the reason we are able to do questions like find two numbers in an unsorted array that sum to k in O(n) time else again it would be O(n^2). So assuming this i gave the logic for the above question.
- Free Bird April 24, 2012How can the worst case be O(n^2). You iterate once to put the array elements in HashMap which is of O(n). For the second time when we iterate through the array once again this time the only difference is that each time we are at the ith element we substract the d from ith element and search it in HashMap which is a O(1) operation. Also this second iteration takes O(n). So in worst case it is O(n)+O(n) = 2O(n)=O(n). I hope this helps. :)
- Free Bird April 24, 2012So my solution is sort the given list of co ordinates using the first element.
After sorting just scan through the list checking the second element in each pair with the first and second element of the next element in the list. If second element of ith element is more than or equal to 1st element of (i+1)th element and <= 2nd element of (i+1)th element then new pair is 1st element of (i)th element and 2nd element of (i+1)th element or if 2nd element of ith element < 1st element of (i+1)th element then dont merge. and go to next element or if 2nd element of (i)th element is more than 1st element of (i+1)th element and > 2nd element of (i+1)th element then we have our new pair as ith element only and we will remove (i+1)th element. Time Complexity is O(nlogn).
What we can do is have our Node class contain a field middle which will be integer. Now as we are pushing a new node on stack we can calculate middle element using middle=n/2+1. Thus we are keeping track of the middle element at each instance of Stack either while pushing or popping.
- Free Bird April 22, 2012If we have n people then the probability is 2/n-1.
Below is the proof:-
no of ways n people are sitting around a table is (n-1) ! while probability that now taking both people who should be sitting together as 1 unit we have n-1 people so no of ways now is (n-2)! .Also for each of (n-2)! ways both of them have two choices so total no of ways in which two people who always sit together can be arranged around the table with other n-2 memeber is 2*(n-2)!. Thus probability is (2*(n-2)!)/(n-1)! which comes down to 2/n-1. Putting n=5 we get 1/2 etc.
One Aprroach :- I believe it is an insertion sort so the time complexity is O(n^2).
Second Approach:- If transitive behaviour is given then it becomes a sorting algorithm where we have to sort in ascending order of number of matches won. Time Complexity O(nlogn).
Question does not seem to be very clear to me but if i understand it correctly following is my approach to the same.
We can do it through recursion and we should actually search for the first element and then we should check all the characters present in the neighbourhood to check the next character in the pattern if we find it we should again search for the next character in the pattern in the neighbour of the all the occurence of last character we found in the neighbourhood of first character. If anytime it fails we return false else we keep searching.
We can create a point class with x,y coordinate and hashmap<integer,arraylist<point>> this will give us the most common distance for each point then we can iterate to get the point with max number of points which satisfies the above criteria. We can maybe add a little optimization in running time if we can have a one more hashmap<point,hashmap<point,distance>>. So one we compute a distance between two pints we can add it to above map once for each of the points between which we just computed the distance. This way we can avoid calculating the distance again and again and we just look it up in the above map.
- Free Bird April 11, 2012Put the Pattern in the HashMap with Key as char and value as frequency.
Iterate through the 2D array and if u get the collision decrement the value of that char in the HashMap. After completion just check the HashMap whether it has frequency as all zero if yes we have the pattern else we do not have.
The question says when we have finished reading the stream we want to return a character with equal probability. We know when we have finished reading the stream the length. So when we say equal probability we mean each of the characters in the pool should have equal probability to be selected i.e if we have n characters in the pool our probability should be 1/n.
We can generate any random number between 1 to n and thus return that particular number.
What we can do here is we can sort suppose file 1 and do a binary search using elements of the file 2 on file 1. After we have the common elements. We can do the BS of common elements found in last BS on file 1 on file 3 after sorting file 3.
Time Complexity would be O(nlogn).
My solution without data structure is of the order O(nlogn) where A.length=n and B.length=m and n>m. Sort one of the arrays and do a binary search using the elements of the other array.
My solution with data structure is of the order O(n) where A.length=n and B.length=m and n>m. traverse the array and put it in hashmap then traverse another array check for its existence in the Hashmap.
When you say the sequence should be i1,c1..... so by this you mean first integer in the element followed by first character in the array or integer followed by character but integer and character subarrays sorted. One more thing are the number of characters and integers equal.
- Free Bird January 11, 2012
Good Logic.
- Free Bird May 27, 2012