CareerCup

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

-Sort gasStation on the basis of remaining distance.
-Now start traversing from biggest remaining distance gas station to lower
-Keep track of upto what max distance we can ride in case opt for current gas station
-In case max distance capability is higher than previous max distance, override it else ignore
-Keep traversing upto distance current fuel capacity allows and we have our first stop to help us on longest ride in one gas filling stay. Save it in a list.
-Repeat all above step and keep adding optimal gas filling station in list.
-At the end we have all the required stops in list.

Time complexity:
=> Sorting: n log(n) + Traversing: n
=> n log (n)

public class StringMatch {

String[] dict = {"go","bat","me","eat","goal", "boy", "run"};
char[] arr = {'e','o','b', 'a','m','g', 'l'};

boolean isPresent(String str) {
//We can implement HashMap as well for this operation
for (String x:dict) {
if(x.equals(str)){
return true;
}
}
return false;
}

void printAllStrings(String larr, String rstr) {
if(larr.length()>0) {
for(int i=0; i<larr.length(); i++) {
String myStr = rstr + larr.charAt(i);
if(this.isPresent(myStr)) {
System.out.println(myStr);
}
printAllStrings(larr.substring(0,i)+larr.substring(i+1,larr.length()),myStr);
}
}
}

public static void main(String[] args) {
StringMatch sm = new StringMatch();
sm.printAllStrings(String.valueOf(sm.arr), "");
}
}

Carry can also be managed without any extra carry array.

-Create tokens from strings for numbers and signs
-Calculate all multiplications and division
-Calculate all plus minus from result of above


Code:

import java.util.ArrayList;

public class Calculation {

private String str = null;
public String resStr = null;

public String getStr() {
return str;
}

public void setStr(String str) {
this.str = str;
}

public ArrayList Tokenization() {
int i = this.getStr().length();
int j = 0, l = 0;
ArrayList al = new ArrayList();

int si = 0;
if (i == 0) {
System.out.println("No String Passed");
System.exit(0);
} else {
while (j < i) {
// System.out.println("-->" + this.getStr().charAt(j));

l = Character.getNumericValue((char) this.getStr().charAt(j));

if (this.getStr().charAt(j) == '+'
|| this.getStr().charAt(j) == '-'
|| this.getStr().charAt(j) == '*'
|| this.getStr().charAt(j) == '/') {
al.add(this.getStr().substring(si, j));
al.add(this.getStr().charAt(j));
si = j + 1;
}

else if (l > 9 || l < 0) {
System.out.println("==>" + this.getStr().charAt(j));
System.out.println(" encountered...");
System.out.println("Wrong Input...");
System.out.println("Exiting...");
System.exit(1);
}

j++;
}
al.add(this.getStr().substring(si, j));
}

if ("".equals(al.get(0))) {
al.set(0, 0);
}

return al;
}

public ArrayList calculateMultDevide(ArrayList al, int index) {
int length = al.size();
int i = 0, j = 0;
for (i = index; i < length - 1; i = i + 2) {
if ("*".equals(al.get(i).toString())) {
System.out.println("visited *");
j = i - 1;
while (al.get(j) == null) {
j = j - 2;
}
al.set(i + 1,
(Integer.parseInt(al.get(i + 1).toString()) * Integer
.parseInt(al.get(j).toString())));
al.set(i, null);
al.set(i - 1, null);
if (i + 2 < (length - 1)) {

al = this.calculateMultDevide(al, i + 2);
break;
}

}

else if ("/".equals(al.get(i).toString())) {
System.out.println("visited /");
j = i - 1;
while (al.get(j) == null) {
j = j - 2;
}
al.set(i + 1, (Integer.parseInt(al.get(j).toString()) / Integer
.parseInt(al.get(i + 1).toString())));
al.set(i, null);
al.set(j, null);
if (i + 2 < (length - 1)) {

al = this.calculateMultDevide(al, i + 2);
break;
}

}

}

return al;
}

public int calculatePlusMinus(ArrayList arl) {
int total = 0;
int i = 0;
int flag = 0;
int length = arl.size();

while (i < length - 1) {
while (arl.get(i) == null) {
i++;
}
if (i % 2 == 0) {
if (flag == 0) {
total = total + Integer.parseInt(arl.get(i).toString());
} else {
total = total - Integer.parseInt(arl.get(i).toString());
}
}
if (i % 2 != 0) {
if ("-".equals(arl.get(i).toString())) {
flag = 1;
} else {
flag = 0;
}
}

i++;

}
return total;
}

public static void main(String[] args) {
// TODO Auto-generated method stub

int total = 0;

Calculation cal = new Calculation();
cal.setStr("333-1+23*566*1-9/2*2*3");
// cal.setStr("");
ArrayList arl = cal.Tokenization();

int length = arl.size();
int i = 0;
for (i = 0; i < length; i++) {
System.out.println("arl--" + i + "-->" + (arl.get(i)).toString());
}

if (arl.size() == 1) {
System.out.println("No Calculation Required: "
+ (arl.get(0)).toString());
}

else {
arl = cal.calculateMultDevide(arl, 1);
for (i = 0; i < length; i++) {
System.out.println("arl--" + i + "-->" + (arl.get(i)));
}

total = cal.calculatePlusMinus(arl);

System.out.println("Result is: " + total);

}

}

}

Approach:

-Have 3 pointer (or three char var in case Java String) prev, char and next
-Move pointer one by one and check whether prev and next are same
-In case prev and next are not same keep moving
-In case prev and next are same, save char in MaxPalindromeMid, check prev's prev and next's next and keep checking, increase counter util not same not occurs
-Resume moving step by step and check all the palindrome and update counter and MaxPalindromeMid only in case got bigger then prev palindrome.

can you please your approach to get these 4 numbers :)

For clarification on Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

1/12

To delete only one duplicate row as asked in qus:
delete
from Table
where rowid in (SELECT rowid FROM Table group by a1,a2 having count(1) >1)



To show one duplicate less data
select *
from Table
where rowid not in (SELECT rowid FROM Table group by a1,a2 having count(1) >1)

To delete only one duplicate row as asked in qus:

delete
from Table
where rowid in (SELECT rowid FROM Table group by a1,a2 having count(1) >1)

cool...

To get no of duplicate from a table userTab(id,name):

select sum(duplicate) from
(select id, (count(id)-1) as duplicate
from userTab
group by id
having count(id)>1);


TestData:
create table userTab(id number,salary number)

Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (2,2000);
Insert into "userTab" (ID,SALARY) values (3,3000);
Insert into "userTab" (ID,SALARY) values (4,4000);
Insert into "userTab" (ID,SALARY) values (4,4000);
Insert into "userTab" (ID,SALARY) values (5,5000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (6,6000);
Insert into "userTab" (ID,SALARY) values (1,1000);
Insert into "userTab" (ID,SALARY) values (1,1000);

SELECT USER
FROM
(SELECT USER,COUNT(1) AS TotalLogins FROM TABLE GROUP BY USER
)
WHERE rownum = 1
ORDER BY TotalLogins DESC;

For some more sol:

question?id=4974004955774976

Yes find any combination of two number whose sum is half of sum of all numbers:

Array: a1, a2, a3, a4, a5
Sum: a1 + a2 + ... +a5
condition: [ai + aj] = [Sum - (ai + aj)]   =>   (ai + aj) = Sum/2

Testing Code:
public class Test {

public static void main(String[] args) {


int n = 15;

ArrayList al = new ArrayList();
al.add(new Integer(1));
int i1, i2, i3;
i1 = i2 = i3 = 0;
int min = -1;
int index = 0;
for (int i = 1; i < n + 1; ++i) {
min = Math.min(
Math.min((2 * (int) al.get(i1)), (3 * (int) al.get(i2))),
(5 * (int) al.get(i3)));
al.add(min);
index++;
if (min == 2 * (int) al.get(i1))
i1++;
if (min == 3 * (int) al.get(i2))
i2++;
if (min == 5 * (int) al.get(i3))
i3++;
// System.out.println("Index:"+index+"="+min);
}
System.out.println("Index:" + index + "=" + min);


}

}

super...

oh ok...my fault.... i misunderstood the qus...

Logic:

Step 1:
Row wise operation:
Replace the matrix data with the sum of element in row upto current column number.
Replace A[x,y] = A[x,0]+A[x,1]+A[x,2]+A[x,3]+......+A[x,y]
If A =
[1 2 3]
[4 5 6]
[7 8 9]
then after first step:
A=
[1 3 6]
[4 9 15]
[7 15 24]


Step 2:
Column wise operation:
Replace the matrix data with the sum of element in column upto current row number.
Replace A[x,y] = A[0,y]+A[1,y]+A[2,y]+A[3,y]+......+A[x,y]

Now A =
A=
[1 3 6]
[5 12 21]
[12 27 45]


Step 3:
Now find the max diff b/w to A[x,y]-A[x',y'] elements in the result matrix where
X>=X' and
Y>=Y'

Correct...
Also we can prepare a graph b/w no. of connection to website v/s time for better analysis.

Design:
Tournament to Match [one to many]
Match to Player [Many to Many]

-A tournament class contains Arraylist<Match>
-Match class contains Arraylist<Player>, ArrayList<PlayerScore> and a event method.
-Player class contains Arraylist<Match>, totalPointForAllMatches and a event method to calculate scores

As mentioned in qus ' smallest sub-sequence in a' so smallest is possible for single char, hence just find a char which is present in a and b but not in c is the ans.

I think qus should had to be ' longest subsequence in a'

If you will mention your approach in 2 lines as well and then provide code, it would be easy to understand your logic very quickly. :)

For any combination of elements :
Presteps:
-sort the list
-keep only those elements which are < sumWeHaveToFind and pass to following function:

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;

public class Comb {

public HashSet getAllSum(ArrayList al, int val) {
int counter = 0;
int x = al.size();
long l = (long) Math.pow(2, x);
HashSet result = new HashSet();

while (counter < l) {
int temp = 0;
String str = Integer.toBinaryString(counter);
// System.out.println("---"+str) ;
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '1') {
temp = temp + (int) al.get(str.length() - 1 - j);
}
}

if (temp == val) {
StringBuffer res = new StringBuffer();
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '1') {
res.append(al.get(str.length() - 1 - j));
res.append('+');
// System.out.print(al.get(str.length()-1-j));
// System.out.print("+");
}
}
String resu = res.toString();
result.add(resu);
}
counter++;

}
return result;
}

public static void main(String[] args) {
Comb b = new Comb();

ArrayList al = new ArrayList();
al.add(1);
al.add(1);
al.add(1);
al.add(1);
al.add(1);
al.add(2);
al.add(2);
al.add(2);
al.add(3);
al.add(3);
al.add(3);

HashSet hst = b.getAllSum(al, 6);
Iterator itr = hst.iterator();
while (itr.hasNext()) {
String st = (String) itr.next();
System.out.println(st);

}
}
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;


public class Comb {
	TreeSet hs = new TreeSet();	
	public TreeSet permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
        {
        	hs.add(prefix);
        	//System.out.println(prefix);
        }
        else
        {
        	hs.add(prefix);
            //System.out.println(prefix);
        }
            for(int i = 0;i < n;i++)
                permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
            return hs;
        
    }
	void print (TreeSet hs)
	{
		Iterator itr = hs.iterator();
		while(itr.hasNext())
		{
			String str = (String)itr.next();
            System.out.println(str);
		}
	}


	public static void main(String[] args) {
Comb b = new Comb();
String ss = "abc";
TreeSet hss = b.permutation("", ss);
System.out.println("Printing in acsending order....................");

b.print(hss);
int i;
ArrayList al = new ArrayList();
for (i = 1;i<=ss.length() ; i++)	
{
	Iterator itr = hss.iterator();
	while(itr.hasNext())
	{
		String str = (String)itr.next();
		if(str.length()==i)
		{
			al.add(str);
		}
	}	
}
System.out.println("Printing in acsending order and ascending length....................");
for (i=0;i<al.size(); i++)
{
	System.out.println((String)al.get(i));
}
	}

}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;


public class Comb {
	TreeSet hs = new TreeSet();	
	public TreeSet permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
        {
        	hs.add(prefix);
        	//System.out.println(prefix);
        }
        else
        {
        	hs.add(prefix);
            //System.out.println(prefix);
        }
            for(int i = 0;i < n;i++)
                permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
            return hs;
        
    }
	void print (TreeSet hs)
	{
		Iterator itr = hs.iterator();
		while(itr.hasNext())
		{
			String str = (String)itr.next();
            System.out.println(str);
		}
	}


	public static void main(String[] args) {
Comb b = new Comb();
String ss = "abc";
TreeSet hss = b.permutation("", ss);
System.out.println("Printing in acsending order....................");

b.print(hss);
int i;
ArrayList al = new ArrayList();
for (i = 1;i<=ss.length() ; i++)	
{
	Iterator itr = hss.iterator();
	while(itr.hasNext())
	{
		String str = (String)itr.next();
		if(str.length()==i)
		{
			al.add(str);
		}
	}	
}
System.out.println("Printing in acsending order and ascending length....................");
for (i=0;i<al.size(); i++)
{
	System.out.println((String)al.get(i));
}
	}

}

Logic: 1:
----I am a human being
1. Reverse the string char by char
----gnieb namuh a ma I
2. Reverse the string words by words
----I ma a namuh gnieb


Logic: 2:
1. Traverse string char by char
2. create token(word) surrounded by space and reverse it
3. where ever space found print is as it is
4. keep forming tokens and reversing it.

@thelineofcode : I am sorry for that....

method sustring does not create new string insteade uses ogiginal string and the index limit to use hence no issue with space complexity.

Note: Check the internal working of substring

Optimize solution:

public void writeFibo(int num1, int num2, int count)
{
if(count <= 0)
{
return;
}
else
{
System.out.println("=>"+num2);
num2 = num1 + num2;
num1 = num2 - num1;
count--;
writeFibo(num1, num2, count);
}
}

Great....
little correction:

public static int fib(int n) {
if(n<=1)
return 1;
else
return (ThreadTest.fib(n-1) + ThreadTest.fib(n-2));
}

Probability of having girls kid will be increasing generation by generation.... and for time before infinity time all girls will remain and there will not be any more generation.

Only the 'infinite time' mentioned in qus made me to think in this way else there is no certainty

oh ok....
you comment "any character of string a" made to think of this corner case which can be handled easily as you mentioned.
nice sol.

Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

 
   0  1  1  0  1 
   1  1  0  1  0 
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0
The maximum square sub-matrix with all set bits is

    1  1  1
    1  1  1
    1  1  1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a)	Copy first row and first columns as it is from M[][] to S[][]
     b)	For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print 
   sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

---From : geeksforgeeks

your solution doesn't handle sol for below mentioned scenario:

String 1:
abc

String 2:
xncbabkl

As per ur sol:
i picked any char from string 1 lets say 'a'
and then found all the anagrams starting with 'a':

abc
acb

but both of the anagrams are not present in string 2
Your sol is missing checking 'cba' case.

Most probably this qus is for tree/graph right?

good one..
to optimize this solution we can have a global flag initialized with true will be set for any mismatch of below mentioned condition:

node.info > node.left.info
&&
node.info < node.right.info

in case of any mismatch set global flag to false and exit;

After execution of method in case flag is still true then binary tree is a BST

Logic:
-Take 4 elements from given array for all combination out of 8 elements and assume these 4 elements are the 4 corner of 3X3 mattrix
[4 picked elements will represent in 2D mattrix as follows:]
[a[0][0] , a[0][2], a[2][0], a[2][2]]

-Now take rest of the 4 elements from array and check all the combination so that multiplication of all the phases will be equal
[rest of 4 elements will checked for below mentioned position]
[a[0][1], a[1][0], a[2][1], a[1][2]]

-Now we got 4 phases with equal multiplication
a[0][0] * a[0][1] * a[0][2] ==
a[2][0] * a[2][1] * a[2][2] ==
a[0][0] * a[1][0] * a[2][0] ==
a[2][0] * a[2][1] * a[2][2] ==

-Now find the minimum sum phase and rotate mattrix in any direction until we get minimum sum phase at desired position

-And then we can perform left phase to right phase exchange or top phase to bottom phase exchange to get desired mattrix

cool...

Recursive approach:

int sumOfNode(Node *node)
{
if(node == null)
{
	return 0;
}

int left=0,right=0;

left = sumOfNode(node->left);
right = sumOfNode(node->right);

sum = left + right;

if(node -> info < sum)
{
	node -> info = sum;
}
else
{
	sum = node -> info;
}

return sum;

}

For example say array is:
a 2 3 b c 5 d e 4 6

Start traversing from left side of array (0th index)
find the next sequence of numbers and sequence of char and exchange those in case numeric sequence is before char sequence

[Exchange the place of '2 3' to 'b c']
a b c 2 3 5 d e 4 6

apply same logic
[Exchange the place of '2 3' 5 to 'd e']
a b c d e 2 3 5 4 6

Good one coder...

if you will write few lines on algo and approach as well it would be easy and quick to understand logic.

nice solution by the way...

Approach:

-First find out all the row and column which has at-least one occurrence of '0'
--We can search row by row and save row and column value in two separate arrays
-Than make all rows and columns '0' as per above step result

neat and clean... short and simple solution..... good job..
but inner queries are generally cost effective..

For zero current descendant we need to check for some more level down upto we don't get a non zero value or all possible descendants are zero

and copy non zero value to all possible sequential parents having value zero.

to achieve this a almost complete sub tree traversal is required for each node

0
  0     0
2 3   4 5

Good job... neat and clean code...

The solid ans which works even in case water source is 'water tab' not any container

Clarification Required:

K closest point among each other?
OR
K closest point from origin?
OR
K closest point from some given point?

Incorrect qus:
Given String ss = "(a(b))(c(d(f))g)(y(h))

It should be
Given String ss = "(a(b))(c(d(f))g)(y(h))";

In case there was typo in qus as mentioned above:

Approach:

-Have two var counter,max=0 and and start traversing the string one char by next char
-For each '(' occurrence perform counter++ and compare incremented counter value with max in case max<counter copy counter value in max var
-For each ')' occurrence perform counter--

At last
-If counter is null that means there were no '(' or ')' occurrence
-If counter <> 0 that means few brackets are missing
-If counter == 0 then just print all the string after max upto next ')' occurrence in case we want to print deepest string or else MAX is your ans