s100banerjee
BAN USERStep 1) Sort all the n arrays in ascending order and create a set named "duplicate"
Step 2) create a heap with the first elements i.e. the smallest, of all the arrays.
Step 3) poll out the first 2 elements from heap and also insert 2 elements from the respective 2 arrays, who's elements are taken out of the heap.
Step 4) if the elements are same put it in the set. Throw away the first element, get the next element from heap and compare the current 2 elements and put in the set if same. Also insert another element from the respective array. Continue the process.
Create a new class with two String member variables "firstname" and "lastname".
Overwrite hashCode() with the firstname.hashCodexlastName.hashCode.
equals method should be overriden for both variation of fname+lName and lName+fName. In one word equality should be defined in such a way.
This object will be Key. Employee object will be value in the HashMap.
While searching create a new object with the fname+lName (or reverse) and find in the HashMap.
But Hash function should be more optimized.
Through JSon or XML.
- s100banerjee May 20, 2015The following cases must be eliminated.
Case 1) Only K songs are present => (NcK)xKx(K-1)...x2
Case 2) Only K+1 sings are present =>(Nc(K+1)) x(K+1)xK...x2
......
.....
Case N-K) Only N-1 songs are present => N x (N-1)x(N-2)x(N-K)x(N-1-K)^(L-K)
Let the sum be S
The answer is Nx(N-1)x...x(N-K+1)x(N-K)^(L-K) - S
Answer: Nx(N-1)x...x(N-K+1)x(N-K)^(L-K) - (the number of posibilities where at least one song is not played).
- s100banerjee May 20, 2015Answer: Nx(N-1)x...x(N-K+1)x(N-K)^(L-K) - (the number of posibilities where at least one song is not played).
- s100banerjee May 20, 2015Oh! you are right man... I missed that word... Yeah...
- s100banerjee May 17, 20151)Take 2 pointers each pointing to the start node of the singly linked list.
2)Move 1 pointer 1 node at a time and the 2nd pointer 2 nodes at a time. Do this until the 2nd pointer reaches the last node (even number of nodes) or the 2nd last node (odd number of nodes). Take a boolean variable which says whether this linkedlist has an even number of nodes or odd number of nodes in a variable.
3)Now the first pointer points to the mid of the list. Take a stack.
Now point the 2nd pointer to the start node. Put one by one the nodes in the stack. If the boolean variable indicates that the list has odd number of nodes move the 2nd pointer one more node.
Now pop the stack, move 2nd pointer one node and match if they are equal. Go on doing this till end or when get a mismatch.
Take left child of root. Say it's rLC
Take right child of root. Say it's rRC.
If both of them are null the tree is foldable.
Else
preOrder traversal of rLC where left subtree is always visited before right subtree.
preOrder traversal of rRC where right subtree is always visited before left subtree.
If the result is equal String then the answer is true.
The probability tree is a binary tree with 2 levels (not considering 0 level) and 4 branches till leaf.
The below branches of the probability tree gives the answer
Probability = pGoodCompany * 80/100 + pBadCompany * 20/100
Now pGoodCompany = pBadCompany = 1/2.
So probability is 50%
Sorry I was wrong
It should be
According to probability tree the branch is as below
Bad_company-->Good chip-->Good chip + Good_company-->Good chip-->Good chip
That means probability is
1/2 * pBad(Good chip) * pBad(Good chip) + 1/2 * pGood(Good chip)*pGood(Good chip)
Now as the company is a bad company pBad(Good chip) can never be 1. Otherwise it would never be a bad company.
Again pGood(Good chip) is always more than pBad(Good chip).
Now the answer will come accordingly.
According to probability tree the branch is as below
Bad_company-->Good chip-->Good chip
That means 1/2 * p(Good chip) * p(Good chip)
Now as the company is a bad company p(Good chip) can never be 1. Otherwise it would never be a bad company. That means the probability is less than 1/2 i.e. less than 50%
MyThread is runnable.
So to start a thread you must pass this object to a thread constructor and then call start() method of the thread. So it's not multithreading, what you are are doing.
You are running a single threaded program. It's not the answer.
Main class
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Synchronizer sync = Synchronizer.getInstance();
ObjRunnable objRunnable = new ObjRunnable(sync);
Thread t1 = new Thread(objRunnable,"1");
Thread t2 = new Thread(objRunnable,"2");
Thread t3 = new Thread(objRunnable,"3");
t3.start();
t1.start();
t2.start();
}
}
Singleton Synchronizer class
public class Synchronizer {
private static final Synchronizer sync = new Synchronizer();
private int nowAccessedBy ;//1 means first thread
private String quit;
private Synchronizer(){
nowAccessedBy = 1;
quit = null;
}
public synchronized void maintainOrder(){
String threadName;
while(quit==null){
threadName = Thread.currentThread().getName();
if(threadName.equals("1")&& nowAccessedBy == 1){
nowAccessedBy = 2;
System.out.println(threadName);
notifyOthers();
}else if(threadName.equals("2")&& nowAccessedBy == 2){
nowAccessedBy = 3;
System.out.println(threadName);
notifyOthers();
}else if(threadName.equals("3")&& nowAccessedBy == 3){
nowAccessedBy = 1;
System.out.println(threadName);
notifyOthers();
}else{
notifyOthers();
}
}
}
private void notifyOthers(){
notifyAll();
try {
wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public static Synchronizer getInstance(){
return sync;
}
}
ObjRunnable class
public class ObjRunnable implements Runnable {
private final Synchronizer lock;
public ObjRunnable(Synchronizer lock) {
this.lock = lock;
}
@Override
public void run() {
lock.maintainOrder();
}
}
Sort the array.
One variable points to the first element.
Another variable points to the last element.
Add the numbers in those indexes and move them as needed.
A few other testcase
Smallest and the biggest number should not add more than Integer.Max.
Array length must not be more than Integer.Max
Method parameters must not allow long.
Answer:
Can we do it like this?
Create a Hashset of these words.
Then take an iterator from this HashSet. Take out each word and find if the reverse is there in the HashSet. If found remove both of them and go on like this.
reversing a word takes O(k) time.
As we find a single pair of word we get the answer, right? Or we need to find the number of pair of words? Although worst case complexity will remain same...
- s100banerjee May 15, 2015Flip inversion may help in Mergesort
Sorry... it won't help.. I was wrong
HashMap<Course, HashSet<Student>> keyCourseValueStudents;
HashMap<Student, HashSet<Course>> keyStudentValueCourses;
Save the integers as a HashMap where key is the integer and value is the number of occurences. Then following program solves it.
package epic_passwords;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;
public class Passwords {
private static HashMap<Integer,Integer> password = new HashMap<Integer,Integer>();
private static LinkedList<Integer> oneCombination = new LinkedList<Integer>();
public static void main(String[] args){
password.put(1, 1);
password.put(9, 3);
password.put(4, 2);
findCombi(password, oneCombination);
}
private static void findCombi(HashMap<Integer,Integer> password, LinkedList<Integer> oneCombination){
Set<Integer> keys = password.keySet();
Iterator<Integer> keysItr = keys.iterator();
//Integer keyRemoved = null;
Integer value;
while(keysItr.hasNext()){
Integer key = keysItr.next();
if(password.get(key)==0){
continue;
}else{
value = password.get(key);
value--;
password.put(key, value);
}
oneCombination.add(key);
showPassword(oneCombination);
findCombi(password, oneCombination);
oneCombination.removeLast();
value++;
password.put(key, value);
}
}
private static void showPassword(LinkedList<Integer> oneCombination){
int size = oneCombination.size();
System.out.println("\n");
for(int i=0; i<size; i++){
System.out.print(oneCombination.get(i));
}
}
}
public class Solution {
private static int steps = 0;//Total steps taken so far
private static int distanceFromStart = 0;//Current distance from start
private static int multiplier = 1;//For 1x, 2x, 3x etc.
private static boolean moveDirection = true;//right direction means true, left means false
private static int nextMove = 0;
private static int x = 0;
private static int y = 0;
private static int totSteps = 0;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
distance(1,5,8);
System.out.println(distanceFromStart);
}
public static void distance(int x, int y, int totSteps){
Solution.x = x;
Solution.y = y;
Solution.totSteps = totSteps;
while(steps<totSteps){
nextMove = multiplier*x;//odd moves 1x, 2x, 3x
considerTotalSteps();
considerYAndDirectionChange();
if(moveDirection==true){
moveDirection=false;
}else{
moveDirection=true;
}
nextMove = multiplier + x;//even moves 1+x, 2+x, 3+x
considerTotalSteps();
considerYAndDirectionChange();
if(moveDirection==true){
moveDirection=false;
}else{
moveDirection=true;
}
multiplier++;
}
}
private static void considerTotalSteps(){
if((steps+nextMove) > totSteps){
nextMove = totSteps - steps;//Only as many steps to sum up to totSteps
steps = totSteps;
}else{
steps = steps + nextMove;
}
System.out.println("next move "+ nextMove);
}
private static void considerYAndDirectionChange(){
int changeDirection = nextMove/y;//without offset
int offset = 0;
if(moveDirection == true){
offset = distanceFromStart;
}else{
offset = y - distanceFromStart;
}
if((offset+(nextMove%y))>=y){
changeDirection++;
}
if(changeDirection%2==1){
if(moveDirection==true){
moveDirection=false;
}else{
moveDirection=true;
}
}
int newOffset = (offset+(nextMove%y))%y;
if(moveDirection==true){
distanceFromStart = newOffset;
}else{
distanceFromStart = y - newOffset;
}
System.out.println("current distance "+distanceFromStart);
}
}
Each node of the tree should have same height of it's left and right subtree. That solves it. If not true the method returns -1.
public int preOrder(Node root){
if(root==null){
return 0;
}
int lHeight = preOrder(root.getLChild());
if(lHeight == -1){
return -1;
}
int rHeight = preOrder(root.getRChild());
if(rHeight == -1){
return -1;
}
if(lHeight!=rHeight){
return -1;
}
return lHeight + 1;
}
Following method solves this. If it returns null, that means it is not a BST.
public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}
}
leftNodes.add(root);
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}
}
leftNodes.addAll(rightNodes);
}else{
return null;
}
return leftNodes;
}
Following method solves this. If it returns null, that means it is not a BST.
public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}
}
leftNodes.add(root);
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}
}
leftNodes.addAll(rightNodes);
}else{
return null;
}
return leftNodes;
}
public Cab{//Used by cab driver through mobile/web root is fixed for all from/to pair
//halting stops are also fixed
private int vehicleNo;
private String from;
private String to;
private String currentLocation;//milliseconds
private boolean sharable;//Sharable or not
//send the above info to uber onetime
public boolean sendInfoToUberRestService(){
//This method updates data for the ConcurrentHashMap i.e. locationCabs, in class
//SharedCabscatalog
}
public boolean sendCurrentLocation(){//every 2 minute/configurable
}
public void refreshData(){//called after every trip
}
public boolean book(int time, String from, String to){
//if sharable, still seat available and yet has not reached from then book it
}
}
public SharedCabscatalog{//Updated every 2 minutes
//seperate java process for every city
//For each location all vehicle numbers which are on the way to reach this location
//The location may not be the destination. It may be in the mid way
private ConcurrentHashMap<String,ArrayList<Integer>> locationCabs;
public int[] cabAvailability(String from, String to, int time){
//check locationCabs and see if from and to contains same vehiclenumber
//return that
}
public boolean update(String from, String to, int vehicleNumber){
//used by the webservice call from the cab
}
public boolean book(String from, String to, int vNo){
//call webservice to book the cab
}
}
I agree with sk.
Just use FileChannel in Java. Truncate function is available.
Following is the example.
Initial file
1234 5678 1234 56
left-shift 6-9th character by 1 position
123456788 1234 56
left-shift 11-14th character by 2 position
12345678123434 56
left-shift 16-17th character by 3 position
12345678123456 56
The file has 17 bytes.17/5 is 3
Now truncate by 3
1) Each employee contains a member integer variable, say "private int reportee" .
2)Manager to employee is a directed edge (--->)
3)Now it will be a forest of graphs. Each graph contains nodes as employees with directed edge.
4)Now run a stack based DFS on each graph.
5)Whenever there is a push in the stack, the "reportee" should be incremented by 1, for all the employee nodes below the newly pushed node.
6) After the DFS is complete on all the nodes of the forest "reportee" variable has the number of subordinates for each employee.
two heaps: one mean heap and one max heap. The median will be the top element from either the mean or the max heap. Then every node should have a link to the next node added after it and we should also have a pointer to the latest node added.
insertion/push: log N
1)insert a node in the proper heap so that half (or half + 1) nodes are in one heap and rest half is in the other.
2)add a link to this new node from the last added node and preserve a pointer to the new node.
deletion/pop: log N
1)Delete the last node added
2) Adjust the Heap and pointers
@Ranan see the following code
if(occurence.size()>;2)
The extra memory is O(3) i.e. constant
- s100banerjee April 05, 2015N log N time complexity
Think about any number the array cannot have. For example we assume that the array may not have -1 as an element.
Following program gives the solution in nlogn time complexity.
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
public class Repeating {
private static int[] numbers = {1,8,1,2, 3,9,7,6,5,3,2,3, 1};
/**
* This program finds second most repeating number in an array
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Arrays.sort(numbers);
for(int i=0; i<(numbers.length-1); i++){
if(numbers[i]==numbers[i+1]){
numbers[i]= -1;
}
}
TreeMap<Integer,Integer> occurence = new TreeMap<Integer,Integer>();
int k = 0;
for(int i=0; i<numbers.length; i++){
if(numbers[i] == -1){
k++;
//System.out.print(" "+numbers[i]);
}else{
k++;
occurence.put(k, numbers[i]);
k=0;
if(occurence.size()>2){
occurence.pollFirstEntry();
}
}
}
Map.Entry<Integer, Integer> entry = occurence.pollFirstEntry();
System.out.println(" "+entry.getValue());
}
}
Create a directed graph of managers and their reporters.
How to create.
Ans.
Create a HashMap<Integer, ArrayList<Integer>> //Key: ManagerID value array of empids
For each record 1 To N
if HashMap contains managerID
get the ArrayList as value for this key
enter the empId into the ArrayList
if the HashMap does not contain the empId as key, insert it
else
create an ArrayList
append the employee in the ArrayList
put this ArrayList for the key as ManagerId in this record
if the HashMap does not contain the empId as key, insert it
Run BFS for any key of the HashMap
Traverse the binary tree inOrder.
Then run margesort for flip inversion count.
Case 1) a product is given. Find the highest sale quantity and date
Ans: Traverse the file and create a heap(Max/Min) for each product. Heap may be in the array format. Each array is put as a value in a HashMap and key is the Product id. So the HashMap holds the values as Heap array and key as product id.
Case 2) A Date is given. Find the highest sold product and quantity.
Ans. Same. Only difference is that the Date will be the key for the HashMap.
Case 1) The board is a two dimensional array of vertexes. vertex arr[x][y] will have directed
edges of length 1 to any vertex reachable by one role of the dice. (role values 1,2,3,4,5,6)
Case 2) Ladder also is a directed edge and length is 1.
Case 3) Snake also has a directed edge with length 1.
Now run BFS from source and as the destination is reached count the levels.
Case 1) The board is a two dimensional array of vertexes. vertex arr[x][y] will have directed
edges of length 1 to any vertex reachable by one role of the dice. (role values 1,2,3,4,5,6)
Case 2) Ladder also is a directed edge and length is 1.
Case 3) Snake also has a directed edge with length 1.
Now run BFS from source and as the destination is reached count the levels.
Explaining case 3) 2 B 1 W: Two of them see 1 white and 1 blue. They are sure that they cannot have a white cap. Because then the one having blue cap will win. So 2B 1W is fair for the two employees. But this is unfair for the other single employee. Because in 2B 1W he always loses. So 2B 1W is unfair and impossible.
- s100banerjee March 28, 2015Case 1) all 3 white caps: Impossible as per one of the clauses
Case 2) 1 blue 2 white: Unfair, because the one with the blue cap wins. So impossible.
Case 3) 2 blue 1 white: Two of them see 1 white and 1 blue. They are sure that they cannot have a white cap. Because then the one having blue cap will win. Then the one with the blue cap will always lose and one of the other two wins. So Unfair and impossible.
Case 4) 3 blue caps. Only possible option.
Step 1) Sort the array A of sizes
- s100banerjee June 30, 2019Step 2) Take 2 variables p and q, p =0 and q = 1
Loop:
for A[p] find the smallest A[q] by iteration, Then each of A[p] and A[q], A[q+1],..... ......... make one pair each.
temp = p+1
Loop:
if(A[p] == A[temp])
temp++;
else{
A[p] = A[temp];
break;
}
End Loop:
Loop:
Find next A[q] for the new p.by iteration.
if(q==A.length) return;
End Loop:
End Loop