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
public String longString(String sa[], char ca[]) {
Set<String> memo = new HashSet<>();
return recFind(sa, buildCharMap(String.valueOf(ca)), memo, "", 0);
}
public String recFind(String sa[], Map<Character, Integer> charMap,
Set<String> memo, String istr, int i) {
System.out.println(istr+","+i);
if (i >= sa.length)
return istr;
String str1 = "";
if (isValid(istr + sa[i], charMap, memo))
str1 = recFind(sa, charMap, memo, istr + sa[i], i + 1);
String str0 = recFind(sa, charMap, memo, istr, i + 1);
if (str1.length() > str0.length())
return str1;
return str0;
}
public boolean isValid(String str, Map<Character, Integer> charMap, Set<String> memo) {
if (memo.contains(str))
return true;
Map<Character, Integer> strMap = buildCharMap(str);
for (char c : strMap.keySet())
if (!(charMap.containsKey(c) && strMap.get(c) <= charMap.get(c)))
return false;
memo.add(str);
return true;
}
public Map<Character, Integer> buildCharMap(String str) {
Map<Character, Integer> charMap = new HashMap<>();
for (char c : str.toCharArray())
if (charMap.containsKey(c))
charMap.put(c, charMap.get(c) + 1);
else
charMap.put(c, 1);
return charMap;
}
. Use a balanced Binary tree to maintain k numbers in order
. Use a queue to maintain k numbers in sequence
Whenever a new number comes in,
1) remove the old one from the queue(O(1)) and search and remove it from the binary tree O(log k)
2) add the new number to the queue O(1) and add the new number to the binary tree O(log k)
For N numbers,
Time complexity: O(N log k) if k is considered a constant then O(N)
Space complexity: O(2K) if K is considered a constant then O(1)
Bruteforce solution through recursion: O(N!) (I dont think given board has a solution)
for each row and each col from left to right, through recursion checks all the possible pieces
public class SolvePuzzle {
public static void main(String[] args) {
SolvePuzzle sp = new SolvePuzzle();
List<PuzPc> pcs = new ArrayList<>();
int r = 3, c = 3;
//for each piece start from the top in clock wise
pcs.add(new PuzPc('d', 'h', 'h', 'd'));
pcs.add(new PuzPc('s', 'h', 'c', 's'));
pcs.add(new PuzPc('c', 'd', 'd', 'c'));
pcs.add(new PuzPc('h', 'c', 'h', 's'));
pcs.add(new PuzPc('h', 'c', 'c', 'd'));
pcs.add(new PuzPc('d', 'h', 'c', 'c'));
pcs.add(new PuzPc('d', 's', 'h', 's'));
pcs.add(new PuzPc('d', 's', 'd', 'h'));
pcs.add(new PuzPc('s', 's', 'c', 'h'));
PuzPc b[][] = new PuzPc[r][c];
if (sp.recFind(b, new boolean[r][c], 0, pcs))
sp.printBoard(b);
else
System.out.println("cannot solve puzzle");
}
public boolean recFind(PuzPc b[][], boolean filled[][], int pos,
List<PuzPc> pcs) {
int r = pos / b[0].length;
int c = pos % b[0].length;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length
|| filled[r][c])
return true;
List<PuzPc> list = findFits(b, r, c, pcs);
if (list.isEmpty())
return false;
filled[r][c] = true;
for (PuzPc fpc : list) {
pcs.remove(fpc);
b[r][c] = fpc;
if (recFind(b, filled, pos + 1, pcs))
return true;
b[r][c] = null;
pcs.add(fpc);
}
filled[r][c] = false;
return false;
}
public List<PuzPc> findFits(PuzPc b[][], int r, int c, List<PuzPc> pcs) {
List<PuzPc> list = new ArrayList<>(pcs);
PuzPc tpc;
// check piece above
if (r - 1 >= 0) {
tpc = b[r - 1][c];
// filter the bottom part of above piece
for (PuzPc pc : pcs)
if (pc.s[0] != tpc.s[2])
list.remove(pc);
}
//check piece to the left
if (c - 1 >= 0) {
Iterator<PuzPc> iter = list.iterator();
PuzPc pc;
tpc = b[r][c - 1];
while (iter.hasNext()) {
pc = iter.next();
if (tpc.s[1] != pc.s[3])
iter.remove();
}
}
return list;
}
public void printBoard(PuzPc b[][]) {
for (int r = 0; r < b.length; r++) {
for (int l = 0; l < 3; l++) {
for (int c = 0; c < b[0].length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s[0] + " ");
break;
case 1:
System.out.print(b[r][c].s[3] + " " + b[r][c].s[1]);
break;
case 2:
System.out.print(" " + b[r][c].s[2] + " ");
}
}
System.out.println();
}
}
}
}
Bruteforce solution through recursion: O(N!) (I dont think given board has a solution)
for each row and each col from left to right, through recursion checks all the possible pieces
Through recursion takes each piece for rach
List<PuzPc> list = new ArrayList<>(pcs);
PuzPc tpc;
// check piece above
if (r - 1 >= 0) {
tpc = b[r - 1][c];
// filter the bottom part of above piece
for (PuzPc pc : pcs)
if (pc.s[0] != tpc.s[2])
list.remove(pc);
}
//check piece to the left
if (c - 1 >= 0) {
Iterator<PuzPc> iter = list.iterator();
PuzPc pc;
tpc = b[r][c - 1];
while (iter.hasNext()) {
pc = iter.next();
if (tpc.s[1] != pc.s[3])
iter.remove();
}
}
return list;
}
public void printBoard(PuzPc b[][]) {
for (int r = 0; r < b.length; r++) {
for (int l = 0; l < 3; l++) {
for (int c = 0; c < b[0].length; c++) {
switch (l) {
case 0:
System.out.print(" " + b[r][c].s[0] + " ");
break;
case 1:
System.out.print(b[r][c].s[3] + " " + b[r][c].s[1]);
break;
case 2:
System.out.print(" " + b[r][c].s[2] + " ");
}
}
System.out.println();
}
}
}
}
creates a set out of ngrams for document1 and cross checks ngrams from document2
public Set<String> ngramIntersection(String d1, String d2, int n){
//create n gram and add it to a set
Set<String> ns1 = new HashSet<>();
String words[] = d1.split(" ");
for(int i=0;i<words.length-n;i++){
StringBuilder sb = new StringBuilder();
for(int j=0;j<n;j++){
sb.append(words[i+j]+" ");
}
ns1.add(sb.toString());
}
words = d2.split(" ");
Set<String> result = new HashSet<>();
for(int i=0;i<words.length-n;i++){
StringBuilder sb = new StringBuilder();
for(int j=0;j<n;j++)
sb.append(words[i+j] + " ");
if(ns1.contains(sb.toString()))
result.add(sb.toString());
}
return result;
}
There are two cases here
1) if a number say no in the array is less than n/2 then we need to locate (n - no) or more. Everything after this will add up with no to give a sum >= n.
2) All the numbers >= n/2 will definitely will add up with each other to have a sum > n
Code:
public class Countofsum {
public static void main(String[] args) {
int ar[] = {1,2,3,4,8};
System.out.println(countPairs(ar, 6));
}
public static int countPairs(int ar[], int sum) {
int count = 0, l;
int i;
for (i = 0; i < ar.length-1 && ar[i] < sum / 2; i++) {
l = locate(ar, i + 1, sum - ar[i]);
if (l != -1)
count += ar.length - l;
}
int n = ar.length - 1 - i;
count += (n * (n+1))/2;
return count;
}
public static int locate(int ar[], int st, int no) {
int end = ar.length - 1;
int res = -1;
int mid;
while (st <= end) {
mid = (st + end) / 2;
if (ar[mid] == no)
return mid;
if (ar[mid] > no) {
res = mid;
end = mid - 1;
} else {
st = mid + 1;
}
}
return res;
}
}
Please explain how will the resulting representational graph is acyclic. It might not be acyclic. Try an example where four rooms connected like a 2x2 having doors that pushes towards each in sequence. This will be cyclic.
Ex:
|A|B|
-- ---
|D|C|
A has pushdoor to b, b to c, c to d, d to a.
Being cyclic does not stop you from DFS or BFS
Imagine solving this in 40 mins and the guy expected an A* algorithm based solution. I gave a graph based solution.
But the graph has two type of nodes - A room node and exit door node. Each room is connected to other by a directed edge that connects room1 to 2 if the door pushes from 1 to 2. All we need to do is to check from each room if there is atleast one path towards one of the fire exits.
Please note that this graph might not be acyclic.
Doing a BFS starting from one room node, gives the shortest path towards from this room to all the fire exits. If there exits a path to atleast one fire exit in this graph, then it is fine. Doing BFS from all the nodes can solve the problem of verification.
another solution is do a BFS or DFS and get parents of each node in the resulting traversal tree. Then check if there is a path from each room to one of the fire exits.
Need to see how to do this using A* algorithm and a 2d array representation of the room
For a string to form palindrome, number of character occuring odd number of times should be <= 1. For example, aabbaa(0 odd chars) or aabaa or abcccba (1 odd chars).
So this problem can be reduced to find the number of characters occurring odd number of times <= 1.
There are 2 solutions I can think of
1) Sort the characters and count the number of times each character occurs.
Complexity O(nlogn + n) = O(n log n )
2) Hash the characters with number of times they occur and check how many characters occur odd number of times = O(n + number of unique chars) = O(n)
Do a Inorder traversal. maintain the prev number and check if current is greater than prev.
//object level variable: int prev = Integer.MIN_VALUE; before this call
public boolean isSortedAsc(Node root){
if(root == null)
return true;
if(!isSortedAsc(root.lchild))
return false;
if(root.value < prev)
return false;
prev = root.value;
return isSortedAsc(root.rchild);
}
Primes after a point in the series are multiples of 6 +/-1. that is 31 = 30 + 1, 37 = 36 + 1 and so on.
So find the first number in 10 digits that is divisible by 6 and then from then on check if no-1 or no+1 is prime. increment by 6 and do the same check until the prime count = 5
An improved version using cache/memoize technique below
public class SumBrackets {
int sum;
String br[];
public static void main(String[] args) {
new SumBrackets().generate(4);
}
public void generate(int sum){
if(sum <= 0)
return;
this.sum = sum;
br = new String[sum];
br[0]="()";
for(int i=1;i<sum;i++)
br[i] = "("+br[i-1]+")";
gen("",0);
}
public void gen(String str, int ctr){
if(ctr == sum){
System.out.println(str);
return;
}
for(int i=1;i <= sum-ctr;i++)
gen(str+ br[i-1], ctr+i);
}
}
public void gen(int sum, String str, int ctr){
if(ctr == sum){
System.out.println(str);
return;
}
for(int i=1;i <= sum-ctr;i++)
//add brackets and recurse to next
gen(sum, str+ getBrackets(i), ctr+i);
}
public String getBrackets(int n){
StringBuffer sb = new StringBuffer();
for(int i=0;i<n;i++)
sb.append('(');
for(int i=0;i<n;i++)
sb.append(')');
return sb.toString();
}
This is O(n)
public class LaregSeq{
int arr[][] = {{1,5,9},{2,3,8},{4,6,7}};
int st, len;
boolean visited[][];
public static void main(String args[]){
st = 0;
len = 0;
visited = new boolean[arr.length][arr.length];
for(r =0;r<n;r++)
for(c=0;c<n;c++)
if(!visited[r][c])
printLarge(0,0,arr[r][c]-1,arr[r][c]);
for(int i =st;i<st+len;i++)
System.out.println(i);
}
public void printLarge(int r, int c,int prev,int st){
if(r < 0 || r > =arr.length || c < 0 || c >= arr.length)
return;
if(arr[r][c] !=prev+1){
if( prev-st+1 > len){
len = prev -st+1;
st = st;
}
return;
}
visited[r][c] = true;
printLarge(r+1,c,arr[r][c],st);
printLarge(r,c+1,arr[r][c],st);
printLarge(r-1,c,arr[r][c],st);
printLarge(r,c-1,arr[r][c],st);
}
}
public String longPrefix(String str){
String arr[] = str.split(“ “);
int len = arr[0].length;
int p;
for(int i =1; i < arr.length;i++){
p=0;
while(p < len && p < arr[i].length
&& arr[0].charAt(p) == arr[i].charAt(p))
p++;
len = p;
}
return arr[0].subString(0,len);
}
Finding medians of each of 10,000 server and finding the median among them will work as it is stated that there billion integers(equal number of numbers).
Problem breaks down into
1) finding median on each server
2) finding medians among the medians
As there are 1billion integers, 1billion/2th(or +1) biggest number will be the median. This becomes finding kth biggest number problem which has a complexity of O(N)
Reference: Search for finding Kth biggest element in an unsorted array in stackoverflow
Store this in an array of 10,000 and again find the 5000th biggest number in this array, whose complexity is O(M)
So total complexity = O(N)
For each bit position from LSD to MSD (for value upto 9 max 4 bit poistions)
Go through the array and move all the values with bit 0 to the left and 1 to the right
have two pointer one from left and right
increment the left pointer until an interger with bit 1 in digit i is encountered
decrement the right pointer until an interger with bit 0 in digit i is encountered
swap these two
proceed above until left < right
This would have split the numbers into two groups
Performing this for all the 4 bits would have grouped the same numbers next to each other
now scan through the array from 0 to n-1
xor i+1..n until the number is different - count the occurence
print if count is even
now the new number to xor was the different one encountered during xor
Total number of scans through the array = no_bits * n + 1 * n = (no_bits+1) * n = O(N)
As the sort / grouping was done inplace no additional space used.
NOTE:Stack space might be used if the split on groups is performed recursively, just the left and right pointers for each recursive call
In a board of 2 x N (2 rows and N cols) tiles, N - 2 x 1 tiles can be placed.
Therefore each of N tiles has an option of being placed Horizontal(0) or Vertical(1): Orientation and a choice of position.
The solution is split into solving Orientation for each tile and then its positions.
Deciding Orientation:
Choose 0 or 1 for each tiles, therefore pow(2,N) possibilities. For ex: 100 - place first tile vertical and next two tiles horizontal
But there are two restrictions to this approach
Restriction:1) There cannot be odd number of Horizontal tiles as it creates a horizontal space that can be filled only by another horizontal tile.(applicable for a board of 2 rows and N cols - for N x 2 board vice versa with Vertical applies)
So choose 0 or 1 for each tile from 1 to n-1.There are pow(2,n-1) possibilities and decide the orientation for the last tile based on the number of horizontal tiles.
If there are odd number of horizontal tiles upto n-1, then the choice for last tile is horizontal. If even number of horizontal tiles found upto n-1 then choice for the last is vertical. As there is only one orientation for the last tile, the total number of choices till now is pow(2,n-1)
Restriction:2) there should be two consecutive Horizontal tiles so that they can placed one below the other. Choice of 010 is physically invalid in the board as the arrangement will become either 001 or 100. In other words horizontal should be followed by horizontal. So from the pow(2,n-1) possibilities, some of the possibilites should be reduced
Summing up above two, there should be even number of tiles and horizontal tiles should be paired next to each other (that is 00 in choice)
For ex:
possibilities of placeing 3 - 2x 1 tiles in a 2 x 3 board
001
010 - invalid (when placed in the board will become 100 or 001)
011 - invalid (odd number of horizontal)
100
101 - invalid (odd number of horizontal)
110 - invalid (odd number of horizontal)
111
only 3 possiblities out of pow(2,3-1) = 4 possibilities (or out of 8 possibilties for 3 tiles as shown above)
Position:
for example if we choose the arrangement 100, three tiles A,B,C can be arranged 3! ways
Similarly for 001 and 111.
So there are 3 * 3! = 18 possible arrangements in the board.
A bruteforce recursion based solution in java without any optimization
public class SnakeFinder {
public static char board[][];
public static char[] tstr;
public static int maxr, maxc;
public static void main(String args[]) {
String str[] = { "SNBSN", "BAKEA", "BKBBK", "SEBSE" };
maxr = str.length;
maxc = str[0].length();
board = new char[maxr][maxc];
for (int s = 0; s < str.length; s++)
board[s] = str[s].toCharArray();
tstr = "SNAKES".toCharArray();
int count = 0;
for (int r = 0; r < maxr; r++) {
for (int c = 0; c < maxc; c++) {
if (board[r][c] == tstr[0]) {
count += find(r, c, 1);
}// if end
}// for c end
}// for r end
System.out.println(count);
}// end of main
//searches for the character targetString[i] from r, c
public static int find(int r, int c, int i) {
if (i == tstr.length)
return 1;
int count = 0;
if (r - 1 > -1 && board[r-1][c] == tstr[i])
count += find(r - 1, c, i + 1);
if (r + 1 < maxr && board[r+1][c] == tstr[i])
count += find(r + 1, c, i + 1);
if (c - 1 > -1 && board[r][c-1] == tstr[i])
count += find(r, c - 1, i + 1);
if (c + 1 < maxc && board[r][c+1] == tstr[i])
count += find(r, c + 1, i + 1);
return count;
}
}
I found the solution on a paper named design of a air traffic control system using UML .As I am unable to post the link here, if you are interested in solution please search for "DESIGN OF FORMAL AIR TRAFFIC CONTROL SYSTEM THROUGH UML"
Not sure if I was expected to do most of these in the 45 minutes slot
public class TwosComplement {
public static void main(String[] args) {
int no = -8;
printBits(no);
printBits(~no);
printBits(~no + 1);
}
public static void printBits(int no) {
System.out.println("\nBinary format of:" + no + "\n"
+ Integer.toBinaryString(no));
for (int i = 31; i >= 0; i--)
System.out.print((((no & (1 << i)) >>> i) > 0) ? "1" : "0");
}
}
This solution is same as @braap 's solution. It finds the kth largest number by using divide and conquer technique. This technique is similar to partition technique of quick sort. But we shall follow the partition where the kth largest element is. Hence the time complexity is O(k log n).
@braap I have just coded it a bit different way
public class KthMax {
public static void main(String args[]) {
// int arr[] = { -2, 1, 5, 3, -10, 20, 4 };
int arr[] = { -10, -2, 1, 3, 4, 5, 20 };
for (int i = 1; i <= arr.length; i++)
System.out.println(kthMax(arr, 0, arr.length - 1, i));
}
public static int kthMax(int arr[], int st, int end, int k) {
// base cases for recursion
if (st >= end)
return arr[st];
// recursion
int pivot = arr[end];
int i = st, j = end;
int temp;
while (i < j) {
// move right until we find something greater than pivot
while (arr[i] < pivot)
i++;
// move left until we find something less than or equal to pivot
while (arr[j] > pivot)
j--;
if (i < j) {
// swap
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
} else if (i == j)
j--;
}
if (k > end - j)
return kthMax(arr, st, j, k - (end - j));
else
return kthMax(arr, i, end, k);
}
}
Here is an in place algorithm of complexity O(n^2).
The method FindLong returns the starting locations in result[0], result[1] and length of the string in result[2]
public class LongPat {
public static void main(String args[]) {
int arr[] = { 3, 5, 1, 2, 7, 0, 4, 5, 6, 8, 3, 1, 4, 5 };
int result[] = findLong(arr);
System.out.println();
for (int i = 0; i < result[2]; i++)
System.out.print(arr[result[0] + i] + " ");
}
public static int[] findLong(int arr[]) {
if (arr == null || arr.length < 2)
return null;
int result[] = new int[3];
// locate and expand
int len = 0, maxlen;
int biglen = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
// match found then expand
maxlen = (j - i < arr.length - j) ? (j - i) : (arr.length - j);
if (maxlen > biglen) {
for (len = 0; len < maxlen; len++)
if (arr[i + len] != arr[j + len])
break;
if (len > biglen) {
storeResult(result, i, j, len);
biglen = len;
}
}
}
}
return result;
}
public static void storeResult(int arr[], int stpos1, int stpos2, int length) {
arr[0] = stpos1;
arr[1] = stpos2;
arr[2] = length;
}
}
1) Have two pointers left = 0 and right = str.length -1
- Phoenix November 10, 20172) left searches for zero and right searches for one
3) if (left < right) swap/switch and increment counter by 2
4) repeat 2-3 until left < right and return counter