careeradmirer
BAN USER- 0of 0 votes
AnswersQuestion was on Arithmetic progression
- careeradmirer in United States
Example :
Given the AP :- 1 3 7 9 11 13 find the missing value "which would be 5 here".
Conditions :
Get an user for the length of AP sequence and make sure user provides length is above 3.
Get the input in a single line ex:- "1 3 5 7 9 11"
Provide the solution in O(n) or less if you can.| Report Duplicate | Flag | PURGE
Facebook Algorithm
O(N) - Using TreeMap
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
public class matrixMul {
public static void main(String[] args) {
TreeMap<String,Integer> hm = new TreeMap<String,Integer>();
TreeMap<String,Integer> tm1 = new TreeMap<String,Integer>();
TreeMap<String,Integer> tm2 = new TreeMap<String,Integer>();
hm.put("1,1",1); hm.put("2,1",1); hm.put("3,1",-1);
hm.put("1,2",2); hm.put("2,2",0); hm.put("3,2",1);
hm.put("1,3",3); hm.put("2,3",-1); hm.put("3,3",1);
hm.put("1,4",1); hm.put("2,4",2); hm.put("3,4",1);
Set<Entry<String, Integer>> s = hm.entrySet();
Iterator<Entry<String, Integer>> i = s.iterator();
while(i.hasNext()){
@SuppressWarnings("rawtypes")
Map.Entry he = (Map.Entry)i.next();
String Key = he.getKey().toString();
int Value = (Integer)he.getValue();
String [] sarray = Key.split(",");
if(tm1.containsKey(sarray[0])){
int num = (Integer)tm1.get(sarray[0]);
tm1.put(sarray[0], num*Value);
}
else
tm1.put(sarray[0], Value);
if(tm2.containsKey(sarray[1])){
int num = (Integer)tm2.get(sarray[1]);
tm2.put(sarray[1], num*Value);
}
else
tm2.put(sarray[1], Value);
}
System.out.println(tm1);
System.out.println(tm2);
Set<Entry<String, Integer>> st = hm.entrySet();
Iterator<Entry<String, Integer>> it = st.iterator();
while(it.hasNext()){
@SuppressWarnings("rawtypes")
Map.Entry he = (Map.Entry)it.next();
String Key = he.getKey().toString();
String [] sarray = Key.split(",");
int Value1 = tm1.get(sarray[0]);
int Value2 = tm2.get(sarray[1]);
int Value3 = Value1*Value2;
if(Value3 == 0){
hm.put(Key, 0);
}
else if(Value3 < 0){
hm.put(Key, -1);
}
else{
hm.put(Key, 1);
}
}
System.out.println(hm);
}
}
Runs in O(n).
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class CommonElements {
public static void insertArray(int arr[],TreeMap<Integer,Integer> mp){
int i =0;
while(i < arr.length){
int var = arr[i];
int a;
if(mp.containsKey(var)){
a = mp.get(var)+1;
mp.put(var, a);
}
else{
mp.put(var, 1);
}
i++;
}
}
public static void main(String[] args) {
int arr1[] = {7,10,12};
int arr2[] = {8,7,10};
int arr3[] = {7,10,9};
int arr4[] = {13,10,7};
int arr5[] = {6,7,10};
TreeMap<Integer,Integer> mp = new TreeMap<Integer,Integer>();
insertArray(arr1,mp);
insertArray(arr2,mp);
insertArray(arr3,mp);
insertArray(arr4,mp);
insertArray(arr5,mp);
Set set = mp.entrySet();
Iterator i = set.iterator();
while(i.hasNext()){
Map.Entry me = (Map.Entry)i.next();
int key = (Integer) me.getKey();
int value = (Integer)me.getValue();
if(value == 5){
System.out.println("Number : "+key);
}
}
}
}
Constant Time O(1).
import java.util.*;
public class Stack {
public static LinkedList<String> l = new LinkedList<String>();
public static void push(String s, LinkedList<String> l){
l.add(s);
}
public static String pop(LinkedList<String> l){
String s = l.getLast();
l.removeLast();
return s;
}
public static void main(String[] args) {
push("a",l);
push("b",l);
push("c",l);
push("d",l);
pop(l);
System.out.println("Contents of the Stack " + l);
}
}
The Solution is O(n) -- Still can be reduced
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class cubeN {
public static void main(String[] args) {
int sum = 0,l = 1;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
System.out.println("Enter the Value of N :");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
for(int j = 0; j < n; j++){
sum = j*j*j;
hm.put(sum,j);
}
Set set = hm.entrySet();
Iterator i = set.iterator();
while(i.hasNext()){
Map.Entry me = (Map.Entry)i.next();
int Value = n - (Integer) me.getKey();
int num1 = (Integer)me.getValue();
if(hm.containsKey(Value)){
int num2 = hm.get(Value);
System.out.println("Combination -"+l+" "+num1+","+num2);
l++;
}
}
}
}
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next != null)
fast = fast.next.next; // 2 hops.
else
return false; // next node null => no loop.
if(slow == null || fast == null) // if either hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
import java.util.*;
public class NonRepeatingCharacters {
public static void main(String[] args) {
//char c [] = {'a', 'b', 'c','d','a'};
String s = "abcda";
char c [] = s.toCharArray();
HashMap <Character,Boolean> hm = new HashMap <Character,Boolean>();
int i =0;
while(i < c.length){
char a = c[i];
if(hm.containsKey(a))
hm.put(a, true);
else
hm.put(a, false);
i++;
}
Set set = hm.entrySet();
Iterator ir = set.iterator();
while(ir.hasNext()){
Map.Entry m = (Map.Entry) ir.next();
if(m.getValue().toString()== "false")
System.out.println("Non Repeting Chars: "+m.getKey());
}
}
}
O(NLogN) - Using In-Order Traversal
- careeradmirer February 09, 2014