praveenkcs28
BAN USERKeep a variable,say lenOfSeq, which will count the length of the longerst sequence found till now. Now , start enumerating the set and analyze each element one by one. It's something similar to DFS , keep on finding the next element for the selected element and increase the count for each element. Now , whatever elements are being covered in this particular , we don't need to analyze them in future because they are alread part of a longer path. So ,we will store these elements in a separate set , say traversedElementSet , .
- praveenkcs28 November 07, 2014Pseudocode:
1. Break the given number into indivdual digits.
2. Store these digits into an array.
3. Now , calculate the product of all the possible subsequences and store the result in a set.
4. Repeat step 3 unless there is a duplicate element. In that case , return false.
5. If step 3 never returns false return true.
Here is the implementation :
public class ColorfulNumber {
public static void main(String[] args) {
System.out.println(isColorful(3245));
System.out.println(isColorful(326));
}
static boolean isColorful(int number){
Set<Integer> s = new HashSet<>();
String num = number+"";
int[] digits = new int[num.length()];
for(int i=0;i<num.length();i++){
digits[i]=Integer.parseInt(num.charAt(i)+"");
s.add(digits[i]);
}
for(int i=2;i<num.length();i++){
for(int j=0;j<digits.length-i+1;j++){
int tempi=i;
int tempj=j;
int product=1;
while(tempi>0){
product*=digits[tempj++];
tempi--;
}
if(s.add(product)==false){
return false;
}
}
}
return true;
}
}
Java provides library to create random number generator and generate random numbers. I have used system current time in milliseconds as seed so that even when JVM is re-booted there is very high chance that numbers will not be repeated. If one has to be hundred percent sure , then we will need to write all the random numbers to a file before JVM is shut down and then compare those while generating random numbers.
import java.util.Random;
public class RandomNumberGenerator {
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10; i++) {
System.out.println(getRandom(100));
Thread.sleep(1);
}
for (int i = 0; i < 10; i++) {
System.out.println(getRandom());
Thread.sleep(1);
}
}
static int getRandom(int range){
Random rand = new Random(System.currentTimeMillis());
return rand.nextInt(range);
}
static int getRandom(){
Random rand = new Random(System.currentTimeMillis());
return rand.nextInt();
}
}
The effective speed of beer is 1 foot/min , so it will take 58 minutes to climb 58 feet , then assuming his climbing speed to be uniform it will take 0.8 min to climb the next 2.5 feet. So , total time is 58.8 minutes or 59 minutes if you round it.
- praveenkcs28 October 27, 2014Put all the values of the second array in a hashSet , after that we can easily check each item of the first array . Time complexity : O(N)+O(M) Space Complexity O(M)
- praveenkcs28 August 28, 2014Also:
> DRY(Don't Repeat Yourself)
- Use the existing code through inheritance,association, aggregation or composition instead of rewriting it.
>Code should be written for interface
>Proper exception handling , handling the error or throwing it to the caller according to the requirements
>The name of the packages,classes,variables,interfaces etc. should be meaningful and according the organisation standard.
>
This is general definition , is there anything different in real-time java?
- praveenkcs28 August 28, 2014We can use doubly linked list for shopping cart item list. At the time of user log out we can persist the data in database against the user. Basic dictionary operations(add , remove , search ) should be implemented . It would be nice to provide sorting also on the basis of various factors such as name of the item , price of the item. Most of the sites now have coupons system.Each item can have an action of moving it to wishlist too. So apply coupon options will be provided. The shopping cart window will have button 'Checkout' which will redirect to the transaction page. Each user will have it's own shopping cart object and it's data will be initialized from the database.
- praveenkcs28 August 28, 2014Seriously , this question was asked in your interview ?
- praveenkcs28 August 28, 2014You can initiate prime to 1 million +1 and then increment by two since even numbers won't be prime.
- praveenkcs28 August 28, 2014I think people here have misunderstood the problem , we don't have to find the inorder successor here or the next greatest element of the array , we have to find the next greater element present in the right side of the element in the array , so even if there is a greater element in the left side of the array of the element being inspected the result would be -1. So , the index of the greater element should be more than the element being inspected. My solution would be like this:
1. Sort array using quick sort or merge sort and put the sorted array in a different array or create a binary search tree.(Time taken : nlogn)
2. In the above step modify the algorithm to store the index of each element in a map.
3. Now start inspecting elements of the array from left to right , pick the element one by one , find the successor from the sorted array or BST created in step one , then find the index of the successor from the map. If the index of the successor is more than the index of the element being inspected then replace the current element being inspected by the successor else replace it by -1.
If you are doing it using java , you just need to create people object , you can add as many fields to the object , and getter and setter methods for them and store them in an array or Arraylist or Set might be even better based on the requirements. When searching and sorting you can implement one Comparable interface for the natural ordering and various comparator objects for different kind of sorting. Seems straightforward in case of Java. If this problem is a database problem , store the values in different fields and do not allow extra spaces to the fields. Index the fields you want to do search upon.
- praveenkcs28 July 14, 2014The solution by Saurabh seems appropriate except a minor improvement of using quick sort to sort each of the server because , the number of integers is so huge and merge sort uses extra space whereas quick sort can do the sorting in place with almost equal efficiency. When finding the medians of these 10,000 servers we need to have 10000 variables pointing to each sorted array and we need to keep the count , also we need to identify and mark which server has what count.
- praveenkcs28 July 14, 2014I think backtracking can be used here , start from the source and start visiting neighbouring vertices along some random path , marking the visited vertices , the point at which we get stuck according the rules , we backtrack until there is a different path possible . In this way we should be able to arrive at the solution.
- praveenkcs28 July 14, 2014Take a new pointer say merged_pointer and point it to the lesser of the two start pointer , next keep on comparing the two linked list and keep on connecting the lesser to the merged_pointer. Whichever pointer was less that pointer will be moved to the next position. Keep on doing this until the end of one of the linked list is reached and then point the merged_pointer to the rest of the other linked list. This is very similar to the merge algorithm.
- praveenkcs28 March 21, 2014Take the median of the array as the root of the tree. For sake of clarity let's call it original_median. Now , take the median of the array to the left of the original_median and make it the left child and similarly the median of the array to the right of the original_median and make it the right child. Recursively apply it to the left child and right child.
- praveenkcs28 March 21, 2014Use Bubble sort ,instead of running it n times run it 1000 times only.
- praveenkcs28 March 21, 2014------------------ |Insert* | Search
-------------------|-----------------------------------------------------------
HashMap | O(1) | O(1)
--------------------------------------------------------------------------------
Array | O(1) | O(n)
--------------------------------------------------------------------------------
LinkedList | O(1) | O(n)
--------------------------------------------------------------------------------
Queue | O(1) | O(n)
--------------------------------------------------------------------------------
*Assuming insertion at the end
First process the dictionary according to the length of the words and convert it into an array of list such that array[1] contains words of length 1 , array[2] contains words of length 2 and so on.Store the length of the longest word is a variable say max_length. Going by the example value of max_length will be 7. Now get the length of the character set. Let's say the character set is {iiifrssst} , it's length is 9. It's more than max_lenght so we go to array[7] , which is program , we start by first character which is 'p' which is not present in the character set so we discard it , next we go to array[6] , nothing is there so we go to array[5] , and start with 'hello' again 'h' is not present in character set so we discard it , next we go to 'world' , discard it , next we go to 'first' , this fits so remove the characters constituting 'first' from the given character set {iiifrssst} , now we are left with {iiss} whose lenght is 4. So we go to array[4] , nothing is there , we go to array[3] , nothing there , we go to array[2] ,and 'is' is a match. We remove the 'i' and 's' characters from character set which is now reduced to {is} . Again following the same procedure makes the character set empty. Thus we return true.
- praveenkcs28 March 21, 2014/*
* Given a number N,
* find the smallest 3 digits number such that product of its digits is equal to N.
* For example for N=100 , 3 digits number is 455.
*/
public class Min3DigtProdEqualN {
public int findMin3DigitNum(int givenN){
for(int i=100;i<1000;i++){
if(givenN==getProductOfDigits(i))
return i;
}
return -1;
}
public int getProductOfDigits(int num){
int product=1;
do{
int a=num%10;
product*=a;
num/=10;
}while(num>0);
return product;
}
}
There is no name for this traversal , so lets call it reverse inorder traversal. :)
- praveenkcs28 April 21, 2013I will read character by character and store the character count in an array , and the word count in a map.
I have written the code for file containing a,b or c . Here is the code:
package fileio;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class WordCount {
public static void processFile(){
Map<String, Integer> m = new HashMap<String, Integer>();
BufferedInputStream bis =null;
try{
bis = new BufferedInputStream(new FileInputStream("E:/app.txt"));
}catch(FileNotFoundException e){
System.out.println(e);
}
int chars[]=new int[27];
StringBuilder sb = new StringBuilder();
String temp=null;
int ch;
try{
while((ch=bis.read())!=-1){
// System.out.println((char)ch);
switch(ch){
case 'a':
case 'A':
chars[1]++;
sb.append((char)ch);
break;
case 'b':
case 'B':
chars[2]++;
sb.append((char)ch);
break;
case 'c':
case 'C':
chars[3]++;
sb.append((char)ch);
break;
case ' ':
if(sb.length()>0){
temp=sb.toString();
// System.out.println(temp);
sb.delete(0, sb.length());
// System.out.println("sb:"+sb);
}
if(m.containsKey(temp)){
int count=m.get(temp);
count++;
m.put(temp, count);
}else{
m.put(temp, 1);
}
default:
if(sb.length()>0)
sb.delete(0, sb.length());
}
}
}catch(Exception e){
System.out.println(e);
}
System.out.println("A["+chars[1]+"]");
System.out.println("B["+chars[2]+"]");
System.out.println("C["+chars[3]+"]");
System.out.println(m);
Map<String,Integer> topwords = new LinkedHashMap<String,Integer>();
String tempStr="";
for (int i = 0; i < 3; i++) {
int temp1=0;
Set<String> keys = m.keySet();
for(String temp2:keys){
if(m.get(temp2)>temp1){
tempStr=temp2;
temp1=m.get(temp2);
}
}
topwords.put(tempStr,m.get(tempStr));
m.remove(tempStr);
}
System.out.println(topwords);
}
public static void main(String[] args) {
processFile();
}
}
select * from questionbank order by salary desc limit 1 offset n-1
- praveenkcs28 April 20, 2013Below is the connection pooling at the most basic level(for database connections ). One can easily put pool size and time out in it. To give the user the flexibility to use close method on connection we will have to provide a wrapper for connection and implement several methods.
package connection_pooling;
import java.sql.Connection;
import java.sql.DriverManager;
import java.util.LinkedList;
import java.util.List;
public class MyConnectionPool {
static List<Connection> pool;
static{
pool=new LinkedList<Connection>();
for (int i = 0; i < 5; i++) {
Connection connection = null;
try{
Class.forName("org.postgresql.Driver");
connection = DriverManager.getConnection("jdbc:postgresql://127.0.0.1:5432/mydb", "userName","Password");
pool.add(connection);
}catch(Exception e){
System.out.println(e);
}
}
}
public static Connection getConnection(){
if(pool.size()>0){
return pool.remove(pool.size()-1);
}else{
throw new Error("no conn available");
}
}
public static void returnConnection(Connection conn){
pool.add(conn);
}
public static void main(String[] args) {
Connection conn = MyConnectionPool.getConnection();
//do something
MyConnectionPool.returnConnection(conn);
}
}
Hi , you can use linkedhashmap to implement LRU cache in Java.
Here is the code ....
package algorithms;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRU {
private static final int MAX_ENTRIES = 3;
Map<Integer,Integer> m = new LinkedHashMap<Integer, Integer>(MAX_ENTRIES){
//Override this , if it returns true the eldest entry in the map is removed
protected boolean removeEldestEntry(Map.Entry eldest) {
return m.size() > MAX_ENTRIES;
}
};
// model function
int getValue(int x){
//some complex calculations
return ++x;
}
//to get value from cache
int getCacheValue(int x){
return m.get(x);
}
int get(int x){
int result=0;
if(m.containsKey(x)){
result=getCacheValue(x);
}else{
result=getValue(x);
}
m.put(x, result);
return result;
}
public static void main(String[] args) {
LRU obj = new LRU();
for (int i = 1; i <= 5; i++) {
obj.get(i);
System.out.println(obj.m);
}
}
}
Strategy pattern uses the polymorphic ability of OOP language to implement a specific logic based on the context of the problem .
- praveenkcs28 March 01, 2013One can use (aS+b)mod m to generate numbers from 0 to m , where S is a seed usually system current time is used , and a and b are some constants . After generating a number that number is used as seed for next random number
- praveenkcs28 March 01, 2013how does it relate RB tree ?
- praveenkcs28 March 01, 2013The minute hand will be exactly at 3 , while the hour hand will be slightly away from 3 , now in 60 minutes the hour hand covers ( 360/12)=30 degrees , so in 15 minutes it will cover (30/4)= 7.5 degrees and this will be our answer.
- praveenkcs28 March 01, 2013First , I will put all alphabets in a two dimensional array , say , alphabets[6][5] , thus , alphabets[0][0] becomes 'a' and so on. Now , I will create a hashmap for all 26 alphabets mapping there location on two dimension array . I can do that by creating a class say ,Coordinates , having two instance variables int row and int column . So , it can be written like this ,
Map<Character,Coordinate> keys = new HashMap<Character, Coordinate>;
Coordinate aobj = new Coordinate(0,0); // create obj for 'a', with row =0 , col =0
keys.put('a',aobj);
Or , we can simply put two digit integer and later retrieve the column and row from unit place and tens place respectively.
Now , lets say we have to write sequence for a word say 'word' ,
By using hashmap we will find location of 'w' is 4,2 and location of o is 2, 4
Travelling from 4,2 to 2,4 can be done in various ways , one way is to first traverse the difference in rows vertically , if difference of first-second is positive then upwards otherwise downwards , in this case ,4- 2=2 so two rows upwards , similarly for the columns can be done.
I will use a resizeable array. Because we don't know how many meetings can there be. I will add each new meeting interval in sorted order. Because our array will be sorted each insertion will take logn time . All the entries will be in pair , so the time at even position will be starting time of a meeting and the next value will be the ending time of that meeting. Using this information we can detect if there will be collision or not.
If one wish to store all possible meetings , he will have to use hashtable but I think the question demands not to store them.
The cloud must save last transaction id generated from unique product id or bill id , and must not allow it next time , instead just send back the ack .
- praveenkcs28 February 14, 2013It has to be a hashtable of patterns
- praveenkcs28 February 14, 2013The question statement is this much only ? Can you explain a bit more ?
- praveenkcs28 February 12, 2013On my machine sizeof(int) gives 4 .
and sizeof(x) is also coming 4 . So , in this case doesn't it have state behaviour and identity ? .
Also , when i add a double to x , sizeof(x) becomes 16. ( sizeof(double) is giving 8 )
??
If size of state and behaviour is increasing then they shouldn't be zero when only int is there.
I wasn't able to find the exact length or number of chars in the string but i found the approximate length withing range of 4 characters. Here is the code:
public class Sizeof
{
public static void main (String [] args) throws Exception
{
// Warm up all classes/methods we will use
runGC ();
usedMemory ();
// Array to keep strong references to allocated objects
final int count = 100000;
StringBuilder [] strings = new StringBuilder [count];
long heap1 = 0;
// Allocate count+1 objects, discard the first one
for (int i = -1; i < count; ++ i)
{
StringBuilder string = null;
// Instantiate your data here and assign it to object
/*
* 64-> 1-2 , 72 -> 3-6 , 80 -> 7-10 , 88 -> 11-14
*/
string = new StringBuilder ("12345671234");
if (i >= 0)
strings [i] = string;
else
{
string = null; // Discard the warm up object
runGC ();
heap1 = usedMemory (); // Take a before heap snapshot
}
}
runGC ();
long heap2 = usedMemory (); // Take an after heap snapshot:
final int size = Math.round (((float)(heap2 - heap1))/count);
System.out.println ("'before' heap: " + heap1 +
", 'after' heap: " + heap2);
System.out.println ("heap delta: " + (heap2 - heap1) +
", {" + strings [0].getClass () + "} size = " + size + " bytes");
int lower=3 ; int upper = 6; int increment=0;
if(size==64) {System.out.println("Num of char= 1 or 2");}
else if(size==72) {System.out.println("Num of char= 3 to 6");}
else {increment=((size-72)/8)*4; System.out.println("Num of char= "+""+ (lower+increment) +" to "+""+(upper+increment));}
for (int i = 0; i < count; ++ i) strings [i] = null;
strings = null;
}
private static void runGC () throws Exception
{
// It helps to call Runtime.gc()
// using several method calls:
for (int r = 0; r < 4; ++ r) _runGC ();
}
private static void _runGC () throws Exception
{
long usedMem1 = usedMemory (), usedMem2 = Long.MAX_VALUE;
for (int i = 0; (usedMem1 < usedMem2) && (i < 500); ++ i)
{
s_runtime.runFinalization ();
s_runtime.gc ();
Thread.currentThread ().yield ();
usedMem2 = usedMem1;
usedMem1 = usedMemory ();
}
}
private static long usedMemory ()
{
return s_runtime.totalMemory () - s_runtime.freeMemory ();
}
private static final Runtime s_runtime = Runtime.getRuntime ();
} // End of class
It seems like the problem can't be solved using expression trees. Using multiple set of random variables(to avoid the possibility of same answer for some values) , we can determine whether two expressions are equivalent , but can't decide they are same or not.
- praveenkcs28 January 30, 2013I am sorry . You are right . We can sort the array in O(nlogn) and then perform comparison in O(nlogn) time
- praveenkcs28 January 21, 2013All the parent-child relations would remain same except those who are parents of that leaf node .i.e, the parent of the leaf node , its parent , and so on till the root . Their relationship will be reversed . The parent will become child and vice versa .
To get the modified tree , just reverse that one chain of leaf's parents . It can be done easily by swapping the leaf with the root , leaf parent with the root child and so on .
A diagram could explain more properly . Hope this helps .
Node temp;
public Node getNthMin(int target){
if(target==1) return getMin();
else{
int counter=1;
temp=getMin();
while(true){
temp=temp.parent;
counter++;
if(counter==target) return temp;
if(temp.right!=null) {counter++;}
if(counter==target) return temp.right;
}
}
}
public Node getMin(){
temp=root;
while(true){
if(temp.left==null) return temp;
else temp=temp.left;
}
}
Node temp;
public Node getNthMin(int target){
if(target==1) return getMin();
else{
int counter=1;
temp=getMin();
while(true){
temp=temp.parent;
counter++;
if(counter==target) return temp;
if(temp.right!=null) {counter++;}
if(counter==target) return temp.right;
}
}
}
public Node getMin(){
temp=root;
while(true){
if(temp.left==null) return temp;
else temp=temp.left;
}
}
Seems like extra space would be required , to optimize the solution without extra space we can convert second array to BST in O(nlogn) and then print values in another O(nlogn) time.
Or simply sort the other array and then print values.
we can change the time zone of server
- praveenkcs28 January 20, 2013to display in the new dataset , sum all the positive values for total money transferred in and sum -ve for out
- praveenkcs28 January 12, 2013nice solution , can you explain a bit more
- praveenkcs28 January 12, 2013
Repwilliamland1990, Associate at Advent
Gifted in donating shaving cream worldwide. Crossed the country getting my feet wet with the elderly in Salisbury, MD. Have ...
Repmerrittmonique9, Android Engineer at AMD
I am Monique and working in high court from last 20 years.Handel many cases in my career.Build and ...
Read each line , split it with delimiter '=' , we will get the color , maintain a hashmap of color , keep on increasing the count. At the end print , color and count.
- praveenkcs28 November 07, 2014