liju.leelives
BAN USERHere is the Java solution
import java.util.ArrayList;
public class LongestPath {
static class Node{
int data;
Node left = null;
Node right = null;
Node(int data){
this.data = data;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
root.left = two;
root.right = three;
three.left = four;
three.right = five;
four.left = six;
//printGraph(root);
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(root.data);
Node curr = root;
while(curr.left !=null || curr.right!=null){
if(checkDepth(curr.left)>=checkDepth(curr.right)){
arr.add(curr.left.data);
curr = curr.left;
System.out.println("Hello");
}
else {
arr.add(curr.right.data);
curr = curr.right;
System.out.println("Hello2");
}
//System.out.println(curr.data);
}
System.out.println(arr.toString());
}
static void printGraph(Node root){
if(root == null)
return;
System.out.println(root.data);
if(root.left != null){
printGraph(root.left);
}
if(root.right != null){
printGraph(root.right);
}
}
static int checkDepth(Node root){
if(root == null)
return 0;
return 1+ Math.max(checkDepth(root.left), checkDepth(root.right));
}
}
Quite a simple solution
import java.util.HashMap;
import java.util.TreeMap;
public class MinAverage {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] scores = {{1001,7},{1001,7},{1001,7},{2001,10},{3001,5},{2001,5}};
System.out.println(get_hotels(scores, 5));
System.out.println(get_hotels(scores, 7));
}
public static String get_hotels(int[][] scores, int min_avg) {
TreeMap<Integer, Integer> scoreSum = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> scoreCount = new HashMap<Integer, Integer>();
for(int i=0; i < 6; i++) {
int val = scores[i][0];
if(!scoreSum.containsKey(val)) {
scoreSum.put(val, scores[i][1]);
scoreCount.put(val, 1);
}
else {
scoreSum.put(val, scoreSum.get(val)+ scores[i][1]);
scoreCount.put(val, scoreCount.get(val) + 1);
}
}
String result = "";
for(int val : scoreSum.keySet()){
if(scoreSum.get(val)/scoreCount.get(val) >= min_avg) {
result +=val+" ";
}
}
return result;
}
}
Here is a working solution using a Hash Table and recursion.
import java.util.HashMap;
public class InterLeave {
static String inp = "AMAZON";
static char[][] a = { {'B', 'B', 'A', 'B', 'B', 'N'},
{'B', 'B', 'M', 'B', 'B', 'O'},
{'B', 'B', 'A', 'B', 'B', 'Z'},
{'N', 'O', 'Z', 'B', 'B', 'A'},
{'B', 'B', 'B', 'B', 'B', 'M'},
{'B', 'B', 'B', 'B', 'B', 'A'} };
static HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
static int counter = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 0;
for(int i=0; i<a[0].length; i++){
resetHash();
for(int j=0; j<a[0].length; j++){
if(hash.containsKey(a[i][j]) && hash.get(a[i][j]) > 0){
count+=findCount(i, j);
//hash.put(a[i][j], hash.get(a[i][j]) - 1);
//a[i][j]=0;
}
}
}
System.out.println(count);
for(int i=0; i < a[0].length; i++ ){
for(int j=0; j < a[0].length; j++){
System.out.print(a[i][j]);
}
System.out.println();
}
}
static int findCount(int i, int j){
int found = 0;
boolean nonZero = false;
for(int val : hash.values()){
//System.out.print(val);
if(val > 0){
nonZero = true;
break;
}
}
//System.out.println();
if(!nonZero && counter == inp.length()){
//System.out.println("Hello");
counter = 0;
return 1;
}
if(i< 0 || j <0 || i>=a[0].length || j >= a[0].length){
return found;
}
if(hash.containsKey(a[i][j]) && hash.get(a[i][j]) > 0){
hash.put(a[i][j], hash.get(a[i][j]) - 1);
a[i][j]=0;
counter++;
found+=findCount(i+1, j)+findCount(i,j+1)+findCount(i-1, j)+ findCount(i, j-1);
}
return found;
}
static void resetHash(){
for(int i =0; i< inp.length(); i++){
char val = inp.charAt(i);
if(hash.containsKey(val)){
hash.put(val, hash.get(val)+1);
}
else{
hash.put(val,1);
}
}
}
}
Simple and not too fancy!!
public class CalcMaxChar {
public static void main(String[] args) {
// TODO Auto-generated method stub
String inp = "HO HELLO!";
inp = inp.toLowerCase().trim();
int[] hashArr = new int[26];
int maxIndex = 0;
int maxCount = 0;
for(int i=0; i< inp.length(); i++){
if(inp.charAt(i) >= 'a' && inp.charAt(i) <= 'z') {
int idx = inp.charAt(i)- 'a';
hashArr[idx]++;
if(hashArr[idx] > maxCount){
maxIndex = i;
maxCount = hashArr[idx];
}
}
}
System.out.println(inp.charAt(maxIndex));
}
}
Use BFS with two stacks, that will do it!
bfsModTraversal(Node root){
Stack<Node> visitStack = new Stack<Node>();
Stack<Node> traversalStack = new Stack<Node>();
visitedStack.push(root);
while(!visitStack.isEmpty()) {
Node curr = visistStack.pop();
traversalStack.push(curr);
for(Node var in curr.children)
visistStack.push(var);
}
while(!traversalStack.isEmpty()) {
System.out.println(traversalStack.pop().data);
}
}
1. Sum all elements first
2. for each element check ((Sum - element)%2) == 0
3. The element for which the above is true is the index
int arr [] ={1,2,3,4,0,6};
int sum = 0;
for(int i =0 ; i<arr.length ; i++){
sum+= arr[i];
}
for(int i =0 ; i<arr.length ; i++){
tempSum = sum;
if((tempSum - arr[i])%2 == 0)
return i;
}
Why do u need two for loops???..this can easily be done by an O(M) algorithm!!
public class ToePliz {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {{6, 7, 8, 9, 2},
{4, 6, 7, 8, 9},
{1, 4, 6, 7, 8},
{0, 1, 3, 6, 7}};
System.out.println(toePliz(matrix));
}
private static boolean toePliz(int[][] arr){
int zeroth = arr[0][0];
for(int i=0 ; i< arr.length; i++){
if(arr[i][i] != zeroth)
return false;
}
return true;
}
}
Here is the solution with an array implemetation
public class BulbArray {
static Bulb[] bulbs = { new Bulb(0, true),
new Bulb(1, false),
new Bulb(2,true) };
public static void main(String[] args) {
int index = 1;
System.out.println(getBulbState(index));
toggleState(1, 2);
System.out.println(getBulbState(index));
}
public static boolean getBulbState(int Index){
return bulbs[Index].getState();
}
public static void toggleState(int strt, int stop){
if(strt > bulbs.length || stop > bulbs.length)
System.out.println("Enter correct indexes within limits!");
else
for(int i=strt; i <= stop; i++){
bulbs[i].toggleState();
}
}
public static class Bulb{
int index;
boolean state;
Bulb(int index, boolean state){
this.index = index;
this.state = state;
}
public boolean getState(){
return state;
}
public void toggleState(){
state = !state;
}
}
}
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class PatternMatching {
public static String findPattern(Hashtable<String, Integer> patternMatcher){
Enumeration<String> keys = patternMatcher.keys();
String key;
String pattern = "";
while(keys.hasMoreElements()){
key = (String) keys.nextElement();
if(patternMatcher.get(key) > 0){
pattern += patternMatcher.get(key)+"";
}
}
return pattern;
}
public static Hashtable<String, Integer> initializePatternMatcher(){
Hashtable<String, Integer> patternMatcher = new Hashtable<String, Integer>();
for(int i = 97; i <= 122; i++ ){
patternMatcher.put(Character.toString ((char) i), 0);
}
return patternMatcher;
}
public static Hashtable<String, Integer> computePattern(Hashtable<String, Integer> patternMatcher, String s){
char[] key;
key = s.toCharArray();
for(char k : key){
if(patternMatcher.containsKey(Character.toString(k))){
int value = patternMatcher.get(Character.toString (k));
patternMatcher.put(Character.toString(k), ++value);
}
}
return patternMatcher;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> dict = new ArrayList<String>();
dict.add("cdf");
dict.add("too");
dict.add("hgfdt");
dict.add("paa");
Hashtable<String, Integer> patternMatcher = initializePatternMatcher();
String pattern = "caa";
patternMatcher = computePattern(patternMatcher, pattern);
String testPattern = findPattern(patternMatcher);
patternMatcher = initializePatternMatcher();
int patLen = pattern.length();
for(String s : dict)
{
if(s.length() == patLen){
patternMatcher = computePattern(patternMatcher, s);
String finalPattern = findPattern(patternMatcher);
if(testPattern.equalsIgnoreCase(finalPattern)){
System.out.println(testPattern +" "+ finalPattern);
System.out.println(s);
}
patternMatcher = initializePatternMatcher();
}
}
}
}
shouldn't it be y<=y1 && y >= y2 and putting equal to signs would be better
- liju.leelives July 08, 2015Tried and tested...i would consider this as O(N)...not considering the adding of items into the Hashtable, as it would be O(N+N) => O(2N) => O(N) :P
import java.util.*;
class pairs
{
public static void main(String args[])
{
int[] arr = new int[]{5,2,8,6,9,1,4,3};
int sum = 9;
Hashtable vals = new Hashtable();
for(int i=0; i<arr.length;i++)
vals.put(arr[i],arr[i]);
for(int i=0; i<arr.length;i++)
{
if(vals.contains(sum-arr[i]))
{
System.out.println(arr[i]+" "+(sum-arr[i]));
vals.remove(arr[i]);
}
}
}
}
Follow a greedy approach..Considering the Track 1 : take the first half as having 3 hours and adding sessions one by one till the 3 hr slot is done...then after lunch..we have 4 hours (remember greedy, so we take max time) and fit the rest of the sessions in the greedy manner
Repeat the same procedure for the rest of the items by creating Track 2
Why do you have to go for a trie?
why not create a n-tree having nodes like
Class Employee
{
int Id;
String Name;
Employee Manager;
}
The root node will have no Manager;
If needed you can also maintain a HashTable and an array of linkedlist with <Employee, index>
and LinkedList<Integer>[] subordinates= new LinkedList[];
and index will map to the respective employees subordinate list
i guess all of the operations can be done from these!
Radix Sort...as age will be max 100.. but ofcourse a treeset needs to be maintained!
just another apporach.
import java.util.*;
class printNos
{
static Hashtable vals = new Hashtable();
public static int Conv(String n)
{
for(int i=0; i<10; i++)
{
vals.put(i+"",i);
}
char[] num = n.toCharArray();
int val = 0;
int exp = num.length -1;
for(int i=0;i<num.length;i++)
{
val += (int)vals.get(num[i]+"") * (int)Math.pow(10, exp);
exp--;
}
return val;
}
public static void main(String args[])
{
System.out.println(Conv("1204"));
}
}
- liju.leelives July 01, 2015Here is a straighforward approach!
1. Subtract from last element in the array the number(let's say X) u want to find.
2. Go back that many indexes(result of subtraction above) in the array.
3. Check whether the number at current index is equal to X
4. Else subtract X from the number at current index.
5. Repeat steps 3-4 till start of array!!
Taking your example: Int arr[]={1,2,3,4,3,4,5,6,7} and to find 6
subtract: 7 - 6 =1
Go back one index: Value is 6.
Return.
Suppose u want to find 2:
subtract 7 - 2 = 5
Go back 5 indexes in the array: Value is 4
Check value: 2 ! =4
subtract 4- 2 = 2
Go back 2 indexes in the array : Value is 2
Return.
Here is a straighforward approach!
1. Subtract from last element in the array the number(let's say X) u want to find.
2. Go back that many indexes(result of subtraction above) in the array.
3. Check whether the number at current index is equal to X
4. Else subtract X from the number at current index.
5. Repeat steps 3-4 till start of array!!
Taking your example: Int arr[]={1,2,3,4,3,4,5,6,7} and to find 6
subtract: 7 - 6 =1
Go back one index: Value is 6.
Return.
Suppose u want to find 2:
subtract 7 - 2 = 5
Go back 5 indexes in the array: Value is 4
Check value: 2 ! =4
subtract 4- 2 = 2
Go back 2 indexes in the array : Value is 2
Return.
Two hashing enabled DSs are only required. I have used hashmap and hashtable
import java.util.*;
class managers
{
public static void main(String args[])
{
Map<String,String> emp = new HashMap<String,String>(){
{
put("A","C");
put("B","C");
put("C","F");
put("D","E");
put("E","F");
put("F","F");
}};
Hashtable mgrs = new Hashtable();
Iterator it = emp.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry)it.next();
if(!mgrs.containsKey(pair.getValue()))
mgrs.put(pair.getValue(),0);
if(!mgrs.containsKey(pair.getKey()))
mgrs.put(pair.getKey(),0);
mgrs.put(pair.getValue(),(int)mgrs.get(pair.getValue())+1);
if(pair.getValue() == pair.getKey())
mgrs.put(pair.getValue(),(int)mgrs.get(pair.getValue())+1);
}
System.out.println(mgrs);
}
}
sorry may not be O(m+n)..can be O(n+n) => O(2n) => O(n)?? i guess!! :/
- liju.leelives June 18, 2015Here is an O(m+n) solution with lots of places where u can check for various boundary conditions and other test inputs. Build it on that. You have actually sort of specified test cases like requirements!!
import java.util.*;
class pairs
{
public static void main(String args[])
{
int[] arr = new int[]{5,2,8,6,9,1,4,3};
int sum = 9;
Hashtable vals = new Hashtable();
for(int i=0; i<arr.length;i++)
vals.put(arr[i],arr[i]);
for(int i=0; i<arr.length;i++)
{
if(vals.contains(sum-arr[i]))
{
System.out.println(arr[i]+" "+(sum-arr[i]));
vals.remove(arr[i]);
}
}
}
}
what??????
wrong post man!!
class Rev
{
public static char[] Reverse(char[] arr, int left, int right)
{
char temp;
while(left != right && left <= right)
{
temp = arr[left] ;
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
return arr;
}
public static void main(String args[])
{
String str = "George";
int n = 3;
char[] s = str.toCharArray();
char[] s1 = Reverse(s,0,n-1);
char[] s2 = Reverse(s1,n,s1.length-1);
System.out.println(Reverse(s1,0,s1.length-1));
//Output is rgeGeo
}
}
How about a modified KMP algorithm???
the password is the substring that you want to search from the sequence of the key presses which maybe treated as a longer string
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 ...
RepCecilPonton, Java Developer at Boeing
Cecil , an enthusiastic professional Photographer with 2 years of experience with a true passion for capturing life’s moments through ...
RepJaninaGilden, Java Experienced at Boeing
I am Janina , a Registered Nurse with 3 years experience providing healthcare to a variety of patients in different institutions ...
Repracheljennir, Personnel consultant at Infinite Wealth
Rachel, I am a Personnel consultant who acts as mediator between employers and job seekers. The main task of I ...
Here is the complete code for all the three parts.
Trie may be a good option but, the question specifically mentions no pre-computing!!
- liju.leelives January 11, 2017