Killbill
BAN USER- 1of 1 vote
AnswersGiven a sorted array and n, find the count of sum of 2 numbers greater than or equal to n
- Killbill in United States| Report Duplicate | Flag | PURGE
Google
SK has given an overview about the solution, here's the details and code
1.) Convert contact array to list of Contact Object
2.) Create a map with key all the contact details(email, phone) and value be list of Contact(Person1, person2).
3.) Go through the map and for each contact in the list get the contact details(email, phone) and go over the map recursively and find out what other contact are mapped, while doing so mark contact as visited true.
4.) Add the person to a set.
5.) Add set to result list
import java.util.*;
class UnionPerson2 {
static class Contact {
List<String> contactList;
String name;
boolean visited;
Contact(List<String> contactList, String name, boolean visited) {
this.contactList = contactList;
this.name = name;
this.visited = visited;
}
}
public static void main(String a[]) {
String [][]contacts = {{"John", "john@gmail.com", "john@fb.com"},
{"Dan", "dan@gmail.com", "+1234567"},
{"john123", "5412312", "john123@skype.com"},
{"john1985", "5412312", "john@fb.com"},
{"john19856", "john123@skype.com", "john@fb1.com"},
{"Dan2", "dan123@gmail.com", "+1234567"},{"Dan3", "dan@gmail.com", "+123456712312"},
{"Sandy", "sandy@gmail.com", "+123456712"},{"sandy4", "sandy@fb.com", "sandy@gmail.com"}};
List<Contact> conList = new ArrayList<Contact>();
for(int i = 0 ; i < contacts.length; i++) {
List<String> contactList = new ArrayList<String>();
for(int j = 1 ; j < contacts[i].length; j++) {
contactList.add(contacts[i][j]);
}
Contact con = new Contact(contactList, contacts[i][0], false);
conList.add(con);
}
Map<String, List<Contact>> map = new HashMap<String, List<Contact>>();
for(Contact c: conList) {
List<Contact> indexList = new ArrayList<Contact>();
for(String detail: c.contactList) {
if(map.containsKey(detail)) {
indexList = map.get(detail);
indexList.add(c);
map.put(detail, indexList);
} else {
indexList = new ArrayList<Contact>();
indexList.add(c);
map.put(detail, indexList);
}
}
}
List<Set<Contact>> resultList = new ArrayList<Set<Contact>>();
for(List<Contact> ls: map.values()) {
Set<Contact> resultSubList = new HashSet<Contact>();
for(Contact c: ls) {
if(!c.visited) {
resultSubList = findUnion(map, c, resultSubList);
}
}
resultList.add(resultSubList);
}
for(Set<Contact> subList: resultList) {
if(subList.size() > 0) {
for(Contact co: subList) {
System.out.print(co.name + ", ");
}
System.out.println();
}
}
}
static Set<Contact> findUnion(Map<String, List<Contact>> map, Contact cont, Set<Contact> resultSubList) {
if(!cont.visited){
cont.visited = true;
resultSubList.add(cont);
for(String contactListStr: cont.contactList) {
for(Contact c: map.get(contactListStr)){
if(!c.visited) {
resultSubList.add(c);
findUnion(map, c, resultSubList);
}
}
}
}
return resultSubList;
}
}
A recursive approach based on SK's solution
public static String getNthSequence(int n) {
if(n==1) {
return 1 + "";
}
String prevRes = "";
String output = "";
prevRes = getNthSequence(n-1);
for(int i=1; i <= prevRes.length(); i++) {
int count = 1;
while(i < prevRes.length() && (prevRes.charAt(i) == prevRes.charAt(i-1))) {
count ++;
i++;
}
output += count + "" + prevRes.charAt(i-1) + "";
}
return output;
}
A much simpler version.
import java.util.*;
class ListOfIterator{
static class CombinedIterator implements Iterator {
List<Iterator<String>> itList;
int curList = 0;
int listSize = 0;
CombinedIterator() {
itList = new ArrayList<Iterator<String>>();
}
void add(Iterator<String> it){
itList.add(it);
listSize ++;
}
public boolean hasNext() {
while(listSize != 0) {
if(itList.get(curList).hasNext()) {
return true;
} else {
itList.remove(curList);
listSize--;
}
}
return false;
}
public void remove(){}
public String next() {
String nextItem = itList.get(curList).next();
curList++;
if(curList == listSize)
curList = 0;
return nextItem;
}
}
public static void main(String args[]) {
List<String> list1 = new ArrayList<String>();
list1.add("a1");
list1.add("a2");
list1.add("a3");
List<String> list2 = new ArrayList<String>();
list2.add("b1");
list2.add("b2");
List<String> list3 = new ArrayList<String>();
list3.add("c1");
list3.add("c2");
list3.add("c3");
list3.add("c4");
CombinedIterator cIt = new CombinedIterator();
cIt.add(list1.iterator());
cIt.add(list2.iterator());
cIt.add(list3.iterator());
while(cIt.hasNext()) {
System.out.println(cIt.next());
}
}
}
An implementation to compare objects without using stack
static boolean checkInOrder(Node root1, Node root2) {
InOrderIterator ita1 = new InOrderIterator(root1);
InOrderIterator ita2 = new InOrderIterator(root2);
while(ita1.hasNext() || ita2.hasNext()){
Node node1 = ita1.next();
Node node2 = ita2.next();
if(node1 == null || node2 == null) {
return false;
}
if(node1.value != node2.value)
return false;
}
return true;
}
static class InOrderIterator {
Node root;
InOrderIterator(Node root){
this.root = root;
}
boolean hasNext() {
return root != null?true:false;
}
Node next() {
Node next = null;
while(root != null) {
if(root.left == null){
next = root;
root = root.right;
break;
} else {
Node temp = root.left;
while(temp.right != null && temp.right != root) {
temp = temp.right;
}
if(temp.right == null) {
temp.right = root;
root = root.left;
} else {
next = temp.right;
temp.right = null;
root = root.right;
break;
}
}
}
return next;
}
}
1.) I suppose we could reuse the n that's given to find the peak
right rotation: peak = n - 1;
left rotation: peak = len - n - 1;
2.) To rearrange the numbers we have to rotate len - n times. Here is the code done using the 3 times reversearr method.
It seems to be working fine, let me know if there are any issues.
static int findPeak(int[] arr, int rotated) {
int len = arr.length;
if(len < 1) {
return -1;
}
if(rotated == 0)
return arr[len-1];
else
return arr[rotated - 1]; //for left rotation its len - rotated - 1
}
static void rearrangeArr(int[] arr, int rotated) {
int len = arr.length;
int originalArr = len - rotated;
reverseArr(arr, 0, len - 1);
reverseArr(arr, 0, originalArr - 1);
reverseArr(arr, originalArr, len - 1);
for(int i=0; i < len; i++) {
System.out.println(arr[i]);
}
}
static void reverseArr(int[] arr, int i, int j) {
while(i<j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
i++;
j--;
}
}
Complexity:
O(n) time
O(1) space
- Killbill October 20, 2016