niraj.nijju
BAN USERB.Tech CSE'12
http://codes-to-problem.blogspot.in/
- 1of 1 vote
AnswersImplement Cache in Java.
- niraj.nijju in United States for kindle
function should support
Object get(key)
void put(key, value)| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswerFor a given number, print this number in words(in Indian style number system).
- niraj.nijju in India for looking for some good solution.
eg:
i/p 345 o/p: three hundred fourtyfive
i/p 3145 o/p: three thousand one hundred fourtyfive
i/p 314520 o/p: three lakh fourteen thousand five hundred twenty.
* http://en.wikipedia.org/wiki/South_Asian_numbering_system| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersto reverse the content of stack,by only using stack operations.
- niraj.nijju in India
can it be better than n^2.| Report Duplicate | Flag | PURGE
- 0of 0 votes
AnswersFind a Pythagoras triplet from an array of integers
- niraj.nijju in India
better than O(n^2log n)| Report Duplicate | Flag | PURGE
i/p : -3 , h9k
- niraj.nijju April 21, 2015public static Integer convert(String word){
int index = 0;
if(0==word.length() )
return null;
int num=0;
boolean isNegative = false;
char [] chWords = word.toCharArray();
if(chWords[index]=='-' || chWords[index]=='+'){
if(chWords[index]=='-')
isNegative = true;
index++;
}
for(;index < chWords.length; index++){
if(chWords[index]<'0' || chWords[index]>'9'){
System.out.println("Invalid input");
return null;
}else{
num=num*10 + chWords[index]-'0' ;
}
}
if(isNegative)
num *=-1;
return num;
}
hi Mudit,
Where does it fails.
static void printHash (int [] A){
int len = A.length;
int [] countArray = new int[len];
for(int a : A){
countArray[len - a]++;
}
int previousCount = 0;
for(int a : countArray){
previousCount += a;
for(int i=0;i<previousCount;i++){
System.out.print("# ");
}
System.out.println();
}
}
m*n matrix, only n elements can be read at a time not m elements as per your example.
- niraj.nijju March 06, 2015/*given class (my assumption)*/
class People{
List<People> peopleIKnow;
List<People> getPeopleIKnow();
}
/*my proposed DataStructure*/
HashMap<People, Integer>
algo
------
List<People> getFavoriteGroup(List<People> peoples){
HashMap<People, Integer> map = new HashMap<People, Integer>();
List<People> favoriteGroup = new List<People>();
for(People p: peoples)
map.put(p,0);
for(People p: peoples){
for(Peoples m: p.getPeopleIKnow()){
map.put(m, (map.get(m)+1) );
}
}
for(People p: map.keySet() )
if(map.get(p) == peoples.length )
favoriteGroup.add(p);
return favoriteGroup;
}
finding the minimum from n queue === finding minimum of n numbers. O(n)
(this have to go for each element, so inefficient)
TC: O(n)
n: sum total of all ranges
Interval
int low
int high
int getLow()
int getHigh()
int getKthSmallestNumber(List<Interval> I, int k){
int max = 0;
for(Interval i: I)
if (max< i.getHigh())
max=i.getHigh();
int []A=new int[max];
for(Interval i : I){
int x = i.getLow();
int y = i.getHigh();
for(;x<=y; x++)
A[x]++;
}
for(int i=0; i<=max; i++){
if(k<=A[i])
return i;
k=k-A[i];
}
return null
}
note: in above algo i assume all intervals are positives, If not then find the lowest no. add it to max after completing first for loop and in 2nd for loop add lowest no to both x & y, In 3rd loop return (i-lowest no)
- niraj.nijju April 03, 2014?? what will you show when we will search for "joh"
- niraj.nijju April 03, 2014?? how will you search through phone number.
- niraj.nijju April 03, 2014public static void getList(LinkedList head){
if(head == null)
return;
int i=1;
Stack S = new Stack();
while(head != null){
int d = head.getData();
if(i%2==0)
S.push(d);
else
System.out.print(" "+d);
head = head.getNext();
i++;
}
while(!S.isEmpty()){
System.out.print(" "+S.pop());
}
}
public static void getList(LinkedList head){
if(head == null)
return;
int i=1;
Stack S = new Stack();
while(head != null){
int d = head.getData();
if(i%2==0)
S.push(d);
else
System.out.print(" "+d);
head = head.getNext();
i++;
}
while(!S.isEmpty()){
System.out.print(" "+S.pop());
}
}
does structure doesn't mean data of the node should also match.
- niraj.nijju November 23, 2013correction
isSameBTree(node ptr1, node ptr2){
if(ptr1==ptr2)
return true; // both null or both are same node
else if((prt1==null)||(ptr2==null))
return false;
else if(ptr1.data != ptr2.data)
return false;
return (isSameBTree(node ptr1.left, node ptr2.left)
&& isSameBTree(node ptr1.right, node ptr2.right));
}
isSameBTree(node ptr1, node ptr2){
if(ptr1==ptr2)
return true; // both null or both are same node
else if(ptr1.data != ptr2.data)
return false;
return (isSameBTree(node ptr1.left, node ptr2.left)
&& isSameBTree(node ptr1.right, node ptr2.right));
}
-1 for
if(node1==node2)
return true;
it will return true only it they correspond to same node. If this is true they why do you need to check further. mean as both node is same then data/child will also be same.
- niraj.nijju November 22, 2013this code will fail in case of white spaces " " (string containing only spaces)
so takecare of edge case correctly.
@URIK LAGNES
sorry forgot to add i++ at last of while loop,
my bad
O(n) time and space
- niraj.nijju October 17, 2013int i =0;
HashMap map;
while(i<k){
maxHeap.insert( xi^2 +yi^2 );
map.put(xi^2 +yi^2, i);
i++;
}
while(i<n){
a = xi^2 +yi^2 ;
if( a< maxElemetOfHeap){
maxHeaaap.remove(maxElemetOfHeap);
map.remove(maxElemetOfHeap);
maxHeap.insert(a)
map.put(a,i);
}
}
iterate map
/**
* to find the commonRegion which is prifix of read1 as well as suffix of read2
*
* @param read1
* @param read2
* @return String (the commonRegion)
*/
public String getCommonRegion(String read1, String read2){
List<Integer> occurences = new ArrayList<Integer>();
int maxCommonLength = read1.length()>read2.length()? read2.length() : read1.length();
int l1 = read1.length();
int l2 = read2.length();
for(int i=0;i<maxCommonLength;i++){
if(read1.charAt(0) == read2.charAt(l2-maxCommonLength+i)
&& (read1.charAt(maxCommonLength-i-1)==read2.charAt(l2-1))){
int k = l2-maxCommonLength+i;
boolean isCommomRegion = true;
for(int j=1;k+j<l2;j++)
if(read1.charAt(j)!=read2.charAt(k+j)){
isCommomRegion = false;
break;
}
if(isCommomRegion)
return read2.substring(k);
}
}
return "";
}
@eugene.yarovoi
no that's not in O(n), i have done in O(n^2)
have done similar as Jordi Marés Soler with little more optimization,
--no list
--no sorting of list
--not calculating other indexes after getting my answer
(putting my solution here)
worst method
- niraj.nijju October 17, 2013no, I don't think so
I have made a solution having worst case O(n^2).
and the answer by Jordi Marés is also O(n^2) in worst case
try for
AAAABX & AAAAAB
grow up man
try for
AAAAB & AAAAAB
good approach but will fail for
s1: ABCADE
s2: ABCABC
so -1
not good approach, as making suffix tree but still it is O(n^2).
-1 for not returning longest one. in fact it will alwayse return Strign of zero length("") for i=0
-1 for O(n^3)
- niraj.nijju October 16, 2013-1
it is O(n^3)
you should use String.equals()
O(n^3)
--
use hashing for O(n^2)
use ahocorasic O(n)
time O(n), space O(n),
use hash
@Zzenith set.contain() is O(1),
@ZachD in ur ans add that it is O(m) space.
convert the int elements into string elements and sort them(like words)
e.g
> input {21,9,23}
> convert into array of String {21,9,23}
> sort the array of String {9,23,21}
>make a complete String(92321) from array and convert it into integer
why we need this ?
- niraj.nijju June 20, 2013we have only 'friendship' graph not there likes,schools or other
- niraj.nijju June 04, 2013we have only 'friendship' graph not there likes,schools or other
here my pseudo code
Let we need to suggest for niraj.nijju(a user).
Set firstOrderFriend = getFriendsList(niraj.nijju);
Set<Friend, Integer> secondOrderFriend;
for(Friend aFriend: firstOrderFriend){
Set tempList = getFriendsList(aFriend);
for each Friend atempFriend in tempList{
if(firstOrderFriend.contains(atempFriend))
continue;
if(secondOrderFriend.contain(atempFriend)){
secondOrderFriend.put(atempFriend,secondOrderFriend.get(atempFriend)+1);
else
secondOrderFriend.put(atempFriend,1);
}
}
Sort secondOrderFriend on basis of the Integer value(count of common friend)
Suggest the first n friends from secondOrderFriend
First Element and size of both array should be same.
All the element smaller than first element should be in same Order in both array.
Slly: all the element greater than first element should be in same Order in both array.
(Assuming : all different element in array
n1:- size of A1
n2:- size of A2
)
Boolean function(){
if((n1 != n2) && (A1[0] != A2[0]))
return false;
int i=0,j=0;
while(i<n1 || j<n1){
while(i<n1){
if(A1[i]>A1[0])
i++;
}
while(j<n1){
if(A2[j]>A2[0])
j++;
}
if(A1[i++] != A2[j++])
return false;
}// end of while
i=0;j=0;
while(i<n1 || j<n1){
while(i<n1){
if(A1[i]<A1[0])
i++;
}
while(j>n1){
if(A2[j]>A2[0])
j++;
}
if(A1[i++] != A2[j++])
return false;
}// end of while
return true;
}// end of function
read this :
whynosql.com/scaling-distributed-counters/
highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html
// O(n*m)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i*n+j] =a[i]+b[j];
median = c[c.length/2]
- niraj.nijju May 30, 2013dude do have an idea what you did?
read the question?
make a dry run for case: 000000
giveing me wright result "matching"
- niraj.nijju November 26, 2012// codes-to-problem.blogspot.in/2012/11/write-function-to-check-given-string.html
public class isMatchingWithWildcard {
public static void main(String [] args){
String pattern = "*abc*def*.doc*";
String str = "adsfabcxyzdefgh.do1docx";
if(isMatching(str, pattern))
System.out.print("Matching");
else
System.out.print("Not Matching");
}
public static Boolean isMatching(String str, String pattern){
int l = pattern.length();
if(pattern.lastIndexOf("*") == l-1)
pattern= (String) pattern.subSequence(0, l-1);
if(pattern.charAt(0) == '*')
pattern= (String) pattern.subSequence(1, pattern.length());
pattern = pattern.replace("*", "__");
String [] patternArray = pattern.split("__");
String sorttenString =str;
for(String aPattern:patternArray){
String [] temp = sorttenString.split(aPattern);
if(temp.length==1 && (aPattern == patternArray[patternArray.length-1]
&& !sorttenString.toLowerCase().contains(aPattern.toLowerCase())))
return false;
str.substring(temp[0].length()+aPattern.length());
}
return true;
}
}
it will be O(n + 100log100) = O(n)
- niraj.nijju November 25, 2012codes-to-problem.blogspot.in/2012/11/finding-pythagorean-triplets-in-array.html
http://codes-to-problem.blogspot.in/
import java.util.Arrays;
public class PythagoreanTripletsInArray {
public static double [] getSquare(String [] args){
double [] array = new double[args.length];
for(int i=0;i<args.length;i++){
double j=Integer.parseInt(args[i]);
array[i]=j*j;
}
return array;
}
public static void main(String [] args ){
double [] array =getSquare(args);
Arrays.sort(array);
Boolean flage = true;
for(double aInt : array){
for(int i=0,j=(array.length-1);i<j;){
double sum = array[i]+array[j];
if(aInt == sum){
System.out.println(Math.sqrt(aInt)+", "+Math.sqrt(array[i])+", "+Math.sqrt(array[j]));
flage = false;
break;
}
else if(aInt > sum)
i++;
else
j--;
}
}
if(flage)
System.out.print("No such solution exist");
}
}
Let me know your thoughts
I am trying to write the code, but my algo is n^2.
I don't think it can be less than this.
finding a[i]^2 +a[j]^2 is O(n^2)
- niraj.nijju November 25, 2012whole we need to traverse 2 times, so O(n)
and need stack of size n/2, so O(n) again.
i don't get what you(REAMS.AL) want to say
Repstacimdalton, Dev Lead at ASAPInfosystemsPvtLtd
At the moment I'm implementing Slinkies in the financial sector. My current pet project is researching break up a ...
@manuelcastroh, I have updated your method
- niraj.nijju May 21, 2015