jenish.shah
BAN USER- 1of 1 vote
AnswersWhy would you chose Java of C# to build your application?
- jenish.shah in United States| Report Duplicate | Flag | PURGE
Software Developer Software Development Manager Application / UI Design
Above solution is O(n) and without extra space
- jenish.shah June 23, 2015public static void findMagnitude(int[] a) {
int min = Integer.MAX_VALUE, max = -1, mg_idx = -1, mg_val = -1;
for (int i = 0; i < a.length; i++) {
int t = a[i];
if (t == mg_val) {
continue;
}
if (t < mg_val) {
mg_val = -1;
mg_idx = -1;
}
if (t >= max && mg_val == -1) {
mg_val = t;
mg_idx = i;
}
if (t < min)
min = t;
if (t > max)
max = t;
}
System.out.println(mg_idx);
}
public static void main(String[] args) {
int[] a= {4,1,2,3,1,4,7,8,6,9};
findMagnitude(a);
}
LinkedHashSet?? How?
I think you meant HashMap.. right? Because we need to keep track of occurrence with the word.
Solution------
public class RotateArrayMinSum {
public static void main(String[] args) {
int[] A = {5,4,3,2,1};
long digitSum = 0;
long minSum = 0;
long prevSum = 0;
for(int i = 0;i<A.length;i++){
digitSum += A[i];
minSum += ((i+1)*A[i]);
}
prevSum = minSum;
for(int i =0;i<A.length - 1;i++){
prevSum = prevSum - digitSum + (A[i]*A.length);
if(prevSum < minSum){
minSum = prevSum;
}
}
}
}
Solutions-----
public class RotateArrayMinSum {
public static void main(String[] args) {
int[] A = {5,4,3,2,1};
long digitSum = 0;
long minSum = 0;
long prevSum = 0;
for(int i = 0;i<A.length;i++){
digitSum += A[i];
minSum += ((i+1)*A[i]);
}
prevSum = minSum;
for(int i =0;i<A.length - 1;i++){
prevSum = prevSum - digitSum + (A[i]*A.length);
if(prevSum < minSum){
minSum = prevSum;
}
}
}
}
Wrote in Java with O(N). Taking input from main directly instead of reading file.
package sample;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TimeZone;
import java.util.TreeMap;
public class URLMap {
private static String convertEpochToDate(long epoch){
Date dt = new Date((long) epoch);
DateFormat df = new SimpleDateFormat("dd/MM/yyyy");
df.setTimeZone(TimeZone.getTimeZone("GMT"));
String dtStr = df.format(dt);
return dtStr;
}
private static void createMap(String input){
Map<Long, Map<String,Integer>> dateToURLMap = new TreeMap<Long, Map<String,Integer>>();
String[] inputLines = input.split(",");
for (String line : inputLines) {
String[] tokens = line.split("\\|");
long epoch = Long.parseLong(tokens[0]) * 1000;
epoch = (long)Math.floor(epoch / (24*60*60*1000));
epoch = epoch * (24*60*60*1000);
//String dt = convertEpochToDate(Long.parseLong(tokens[0]) * 1000);
Map<String, Integer> urlToCntMap = dateToURLMap.get(epoch);
if (urlToCntMap == null) {
urlToCntMap = new HashMap<String, Integer>();
}
Integer cnt = urlToCntMap.get(tokens[1]);
if (cnt == null) {
cnt = 0;
}
cnt++;
urlToCntMap.put(tokens[1], cnt);
dateToURLMap.put(epoch, urlToCntMap);
}
for(Entry<Long, Map<String,Integer>> e : dateToURLMap.entrySet()){
System.out.println(convertEpochToDate(e.getKey()));
Map<String,Integer> urlToCntMap = e.getValue();
Entry<String,Integer>[] countEntries = urlToCntMap.entrySet().toArray(new Entry[urlToCntMap.size()]);
Arrays.sort(countEntries, new Comparator<Entry<String,Integer>>(){
@Override
public int compare(Entry<String, Integer> o1,
Entry<String, Integer> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
for(Entry<String,Integer> en : countEntries){
System.out.println(en.getKey()+" "+en.getValue());
}
}
}
public static void main(String[] args) {
String input = "1407564301|nba,1407478021|facebook,1407478022|facebook,1407481200|news.ycombinator,1407478028|google,1407564301|sports.yahoo,1407564300|cnn,1407564300|nba,1407564300|nba,1407564301|sports.yahoo,1407478022|google,1407648022|twitter";
createMap(input);
}
}
@DRADM, this will not work if first word to be inserted in trie is DEEDBA. And second word comes as AB so if you reverse it (BA) and try to compare in trie. You will end up returning false.
In this scenario, apart from reversing word (BA) and checking trie, we have to take original word (AB) and try to match with the reverse of words which are inserted in tried (DEEDBA) so that will match here.
But it will be expensive to lookup word(AB) in reverse side in trie (DEEDBA).
So to simplify, we need to maintain two tries, when we insert DEEDBA in one trie, we will add ABDEED in second trie. And then for second word first we try to lookup reverse (BA) in first trie and original (AB) in second trie
Here it will be there in second trie and we can apply rest of the logic
Below is the code without using parent link
public class LCABT {
static BTNode lca = null;
static BTNode foundNode = null;
private static boolean findLCA(BTNode root,int a, int b, boolean inPath){
if(root == null)
return false;
if(root.getData() == a || root.getData() == b){
if(foundNode!=null && foundNode.getData()!=root.getData()){
if(inPath)
lca = foundNode;
return true;
}else{
foundNode = root;
inPath = true;
}
}
boolean inLeft = false;
boolean inRight = false;
if(lca == null)
inLeft = findLCA(root.getLeft(),a,b,inPath);
if(lca == null){
inRight = findLCA(root.getRight(),a,b,inPath);
if(lca==null && inLeft && inRight){
lca = root;
}
}
if(lca == null && root == foundNode){
inPath = false;
return true;
}
return inLeft || inRight;
}
public static void main(String[] argv){
BTNode n1 = new BTNode(5);
BTNode n2 = new BTNode(2);
BTNode n3 = new BTNode(3);
BTNode n4 = new BTNode(9);
BTNode n5 = new BTNode(11);
BTNode n6 = new BTNode(50);
BTNode n7 = new BTNode(7);
n1.setLeft(n2);
n1.setRight(n3);
n2.setLeft(n4);
n2.setRight(n5);
n3.setRight(n6);
n4.setLeft(n7);
findLCA(n1,11,7,false);
System.out.println("LCA : "+lca.getData());
}
}
class BTNode{
private int data;
private BTNode left;
private BTNode right;
public BTNode(int data){
this.setData(data);
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getLeft() {
return left;
}
public void setRight(BTNode right) {
this.right = right;
}
public BTNode getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
}
Using LinkedHashMap-----
static Map<Integer,Integer> inputs = new LinkedHashMap<Integer,Integer>();
private static void processStream(int a){
int count = 0;
if(inputs.containsKey(a)){
count = inputs.get(a);
}
inputs.put(a, ++count);
}
private static int findNumber(int index){
int i = 0;
for(Entry<Integer,Integer> ent : inputs.entrySet()){
if(ent.getValue() == 1){
i++;
if(i==index){
return ent.getKey();
}
}
}
return -1;
}
We can start with keeping pointer on 1st node. Every second element comes in stream we can increment the pointer.
- jenish.shah October 26, 2012How about this?
public class OddEvenTreeTraversal {
private static void printTree(TreeNode root){
Stack<TreeNode> oddStack = new Stack<TreeNode>();
Stack<TreeNode> evenStack = new Stack<TreeNode>();
oddStack.push(root);
while(!oddStack.empty() || !evenStack.empty()){
while(!oddStack.empty()){
TreeNode n = oddStack.pop();
System.out.println(n.data);
if(n.left!=null)
evenStack.push(n.left);
if(n.right!=null)
evenStack.push(n.right);
}
while(!evenStack.empty()){
TreeNode n = evenStack.pop();
System.out.println(n.data);
if(n.right!=null)
oddStack.push(n.right);
if(n.left!=null)
oddStack.push(n.left);
}
}
}
public static void main(String[] argv){
TreeNode d = new TreeNode('d');
TreeNode e = new TreeNode('e');
TreeNode f = new TreeNode('f');
TreeNode g = new TreeNode('g');
TreeNode c = new TreeNode('c');
TreeNode b = new TreeNode('b');
TreeNode a = new TreeNode('a');
a.left = b;
a.right = c;
b.left = d;
b.right= e;
c.left = f;
c.right = g;
printTree(a);
}
}
class TreeNode{
char data;
TreeNode left;
TreeNode right;
public TreeNode(char data){
this.data = data;
}
}
Is this possible to increase array length for output? Because in case of abcd output should a1b1c1d1 which is bigger than the input.
- jenish.shah October 23, 2012Is this proper?
public class FindMissingAndDuplicate {
private static void printMissingAndDuplicate(int[] a){
Set<Integer> set = new HashSet<Integer>();
int duplicate = 0;
long sum = 0;
boolean isAdded = false;
for(int i = 0;i<a.length;i++){
isAdded = set.add(a[i]);
if(!isAdded){
duplicate = a[i];
}
sum += a[i];
}
sum = sum - duplicate;
long idealSum = (a.length)*((a.length+1)/2);
long missing = idealSum - sum;
System.out.println("Duplicate and Missing "+duplicate+" "+missing);
}
public static void main(String argv[])
{
int[] ar = {1,2,3,4,4};
printMissingAndDuplicate(ar);
}
}
Making BST is not a problem. Problem is fetching valid word back from BST.
- jenish.shah October 17, 2012public class PossiblePaths {
private static List<String> getPath(int[][] a,int row, int col, int sum){
if(row <0 || row > 2)
return new ArrayList<String>();
if(col < 0 || col > 2)
return new ArrayList<String>();
List<String> paths = new ArrayList<String>();
//sum = sum + a[row][col];
paths.addAll(getPath(a,row+1,col-1,0));
paths.addAll(getPath(a,row+1,col,0));
paths.addAll(getPath(a,row+1,col+1,0));
for(int i =0;i<paths.size();i++){
paths.set(i,String.valueOf(a[row][col]) + "-->"+paths.get(i));
}
if(paths.isEmpty()){
paths.add(String.valueOf(a[row][col]));
}
return paths;
}
public static void main(String[] argv){
int a[][] = {{1,2,3},{4,5,6},{7,8,9}};
List<String> paths = getPath(a,0,0,0);
for(String path: paths){
System.out.println(path.toString());
}
}
}
@Deepak, I think answer of your matrix should be 3 only.
Please let me know if I am wrong
Yeah that is what I wanted to say so in my program no matter whatever condition is any element of the array will be traversed at the max 2 times.
Isnt this called 2O(n) and eventually o(n). O(n2) is totally different I think.
Below is the code. I think this will work for O(n) because in this case every element will be traversed at the max 2 times. Please let me know if you find bug in this.
public class MinSubArrayWithK {
static int[] printSubArray(int[] a,int k){
int min_diff=a.length-1;
int sum = 0,i= 0,j=0;
for(i =0;i<a.length;i++){
sum += a[i];
if(sum >= k){
while(sum - a[j] >= k){
sum -= a[j];
j++;
}
int diff = i - j ;
if(diff < min_diff){
min_diff = diff;
}
}
}
int[] answer = new int[min_diff+1];
int index = 0;
for(i = j;i<=j+min_diff;i++){
answer[index++] = a[i];
System.out.println(a[i]);
}
return answer;
}
public static void main(String[] argv){
int[] a = {3,5,2,7,5,3,8,3,9,8,4,2};
printSubArray(a,12);
}
}
private void validate(List<Integer> input,int k){
getReducedElements(input,k);
Collections.sort(input);
boolean isPass = removeElements(input);
if(isPass)
isPass = checkForPairs(input,k);
if(!isPass){
System.out.println("We can not make pairs....");
System.exit(0);
}
System.out.println("We can make pairs....");
}
private boolean removeElements(List<Integer> nodes){
Iterator<Integer> it = nodes.iterator();
int count = 0;
while(it.hasNext()){
Integer n = it.next();
if(n == 0){
it.remove();
count++;
}
}
if(count%2 != 0){
return false;
}
return true;
}
private void getReducedElements(List<Integer> nodes,int k){
for(int i =0;i<nodes.size();i++){
Integer n = nodes.get(i);
nodes.set(i, n%k);
}
}
private boolean checkForPairs(List<Integer> nodes,int k){
while(!nodes.isEmpty() && nodes.size()%2==0){
if(nodes.get(0) + nodes.get(nodes.size()-1) == k){
nodes.remove(0);
nodes.remove(nodes.size()-1);
}else
return false;
}
if(nodes.isEmpty())
return true;
return false;
}
Repsandrafdenn, Associate at CareerCup
Je suis développeur web dans une société de Wild Oats Markets, j'adore faire du shopping et j'ai une ...
RepDedicated administrative assistant with years of experience managing large and small offices. I have worked with numerous branches,including payroll ...
Repjuanktait, Blockchain Developer at ADP
I am Juan from Seattle, WA. I am working as a LAN administrator. I love music, reading historical books, and ...
- jenish.shah June 24, 2015