Phoenix
BAN USER- 3of 5 votes
AnswersGiven a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
- Phoenix in United States
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answers
- Phoenix in United KingdomThere are multiple rooms in a floor. There are one or more fire exits. Each door can be designed with an option of pull or push. For fire safety, a door should be designed so as to open (push) towards the fire exit. Design a data structure to represent the floor and door design. A person could start from any room and moves towards fire exit. Write an algorithm to check if all the doors are designed to be pushed towards fire exit.
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersDesign a air traffic control system
- Phoenix in United Kingdom for video| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer System Design - 0of 0 votes
AnswersWrite the following function
- Phoenix in United States
void drawLine(byte[] img, int len, int wid, int r, int x1, int x2)
such that you draw a line from x1 to x2 at row r.
len is the length and wid is the width of the image/canvas.
Setting a pixel on to draw the line is to set the corresponding bit on the img array
Each byte corresponds to 8 pixels, that is each pixel is a bit in the array| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Coding
I see two approaches for doing this:
Approach 1:
1) Merge and sort the two lists
2) find duplicate from the list
lets say n are the sum of length of two lists, then space complexity is O(n) and time complexity - O(n log n) for sorting and O(n) for search
Approach 2:
1) Construct a Max heap to store the elements of the smallest list.(m -no of elems - O(m log m))
2) Search for elements from the second list in the max heap and flag the duplicate elements - n - no of elements n >= m O(n/2 log m)
3) Remove elements one by one from the max heap to find an element with a flag - O(1)
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public static String bigSeqs(String str) {
char c[] = str.toCharArray();
char c1, c2 = 0, lc;
int s1, s2 = 0, start = 0, bigstart = 0, bigend = 0;
if (c.length > 0) {
s1 = 0;
c1 = c[0];
lc = c1;
} else
return null;
for (int i = 1; i < c.length; i++) {
if (c2 == 0 && c[i] != c1) {
c2 = c[i];
s2 = i;
} else if (c[i] != c1 && c[i] != c2) {
if (i - start > bigend - bigstart) {
bigstart = start;
bigend = i;
}
if (lc == c2) {
c1 = c2;
s1 = s2;
}
start = s1;
c2 = c[i];
s2 = i;
} else if (lc == c1 && c[i] == c2) {
s2 = i;
} else if (lc == c2 && c[i] == c1) {
s1 = i;
} else if (i == c.length - 1) {
if (i + 1 - start > bigend - bigstart) {
bigstart = start;
bigend = i + 1;
}
}
lc = c[i];
}
if (bigend == 0)
bigend = c.length;
return str.substring(bigstart, bigend);
}
public static boolean matches(String str, String pat) {
int strLen = str.length();
int patLen = pat.length();
int pati = 0, stri = 0;
while (pati < patLen || stri < strLen) {
if (pati + 1 < patLen && pat.charAt(pati + 1) == '*') {
while (stri < strLen && str.charAt(stri) == pat.charAt(pati))
stri++;
pati += 2;
} else if (stri < strLen && pati < patLen
&& str.charAt(stri) == pat.charAt(pati)) {
stri++;
pati++;
} else
return false;
}
return true;
}
Here's a simple solution. Please note that the numbers to be selected is assumed from 0 - w.length-1. This can be replaced with an array oflength w.length and corresponding element can be selected
import java.util.Random;
public class RandGen {
public static void main(String[] args) {
int w[] = { 1, 2, 3, 2, 1 };
int arr[] = gen(w);
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
public static int[] gen(int w[]) {
int sum = 0;
for (int i = 0; i < w.length; i++)
sum += w[i];
Random gen = new Random();
int newArr[] = new int[sum];
int index;
//choose based on weight distribution
for (int i = 0; i < sum; i++) {
do {
index = gen.nextInt(w.length);
} while (w[index] < 1);
newArr[i] = index;//can be newArr[i] = elements[index];
w[index]--;
}
return newArr;
}
}
@aka will your algo work for the array [3,5,6,8,3,1,4,5,6,3,1,4]?
- Phoenix June 29, 2013