geekyjaks
BAN USER- 0of 0 votes
AnswersA furniture can be made of material like metal, wood, .... Also there are different furniture types chair, table, sofa. A wood furniture should be tested against choaking. metal furniture is tested against fire, etc. Design these in OOAD.
- geekyjaks in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersThere are N nodes. Each node has a non negative integer value. Define a optimistic algorithm which ensures that all node has all other node's value.
- geekyjaks in India
Constraint: While a node is sending data to another data, it can't receive data, vice versa.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
This problem is a variation of optimum sellers to ship the products. Here is the working solution,
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class OptimumDish {
private Set<Integer> result = new HashSet<Integer>();
public void print(){
for(int r:result)
System.out.print(r + " ");
}
public void find(int[][] m, int r, int c, int mr, int mc, Stack<Integer> dishes) {
dishes.push(c);
if (r == mr) {
Set<Integer> d = new HashSet<>(dishes);
if(result.size() == 0 || result.size() > d.size())
result = d;
}
else if (r < mr) {
for (int i = 0; i <= mc; i++) {
if (m[r + 1][i] == 1) {
find(m, r+1, i, mr, mc, dishes);
break;
}
}
}
dishes.pop();
for (int i = c + 1; i <= mc; i++) {
if (m[r][i] == 1) {
find(m, r, i, mr, mc, dishes);
}
}
}
public static void main(String[] args) {
int[][] m = {
{ 0, 1, 1, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 1 }
};
int mr = m.length - 1;
int mc = m[0].length - 1;
int c = 0;
for (int i = 0; i <= mr; i++) {
if (m[0][i] == 1) {
c = i;
break;
}
}
OptimumDish od = new OptimumDish();
Stack<Integer> dishes = new Stack<>();
od.find(m, 0, c, mr, mc, dishes);
od.print();
}
}
Reverse inorder traversal. right->root->left. Calculate the sum and pass to left node.
public int sumGreaterNodes(Node node, int sum){
if (node == null)
return sum;
int rs = sumGreaterNodes(node.getRight(), sum);
int cs = node.getKey() + rs;
node.setKey(cs);
int ls = sumGreaterNodes(node.getLeft(), cs);
return ls;
}
sumGreaterNodes(root, 0);
import java.util.ArrayList;
import java.util.List;
public class Rank {
public long findRank(int[] dictionary, int x) {
List<Integer> numberIndex = new ArrayList<>();
for (int index = 0; index < dictionary.length; index++)
numberIndex.add(dictionary[index]);
return 1 + findRank(getDigits(x), 0, numberIndex);
}
private long findRank(int digits[], int position, List<Integer> indexes) {
if (position >= digits.length)
return 0;
int digit = digits[position];
int index = getIndex(indexes, digit);
int n = indexes.size();
// Remove the index from the list
indexes.remove(index);
// rank(abc) => rank(a) + rank(bc);
// rank(a) => index(a)*(n-1)!
return index * factorial(n - 1) + findRank(digits, position + 1, indexes);
}
private int getIndex(List<Integer> indexes, int value) {
for (int index = 0; index < indexes.size(); index++)
if (indexes.get(index) == value)
return index;
return -1;
}
private int[] getDigits(int x) {
int size = 1 + (int) Math.floor(Math.log10(x));
int[] digits = new int[size];
int divider = 1;
int index;
for (index = 1; index < size; index++)
divider *= 10;
index = 0;
while (x > 0) {
digits[index] = x / divider;
x -= digits[index] * divider;
divider /= 10;
index++;
}
return digits;
}
private long factorial(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
public static void main(String[] args) {
int[] dictionary = { 1, 2, 3, 4 };
Rank r = new Rank();
System.out.println(r.findRank(dictionary, 4321));
}
}
A little improvement over above code,
public class Division {
public int quotient(int a, int b){
int q = 1;
while(q*b<a)
q *=2;
return binSearch(q>>1, q, a, b);
}
public void divide(int a, int b){
int quotient = quotient(a, b);
System.out.println("Quotient: " + quotient);
int k = 5;
int d[] = new int[k];
int remainder = a - quotient * b;
for (int index = 0; index < 5; index++){
remainder *= 10;
d[index] = quotient(remainder, b);
remainder -= d[index] * b;
}
System.out.print("Digits: ");
for(int digit:d)
System.out.print(digit);
}
public int binSearch(int start, int end, int a, int b){
int mid = (start+end)>>1;
if (start == mid || mid == end)
return mid;
if (mid * b == a)
return mid;
else if (mid * b <a)
return binSearch(mid, end, a, b);
else
return binSearch(start, mid, a, b);
}
public static void main(String[] args) {
Division d = new Division();
d.divide(1023, 19);
}
}
This is called Maximum Sub Array problem (refer MIT Introduction to Algorithms by Cormen)
public class MaxSubArray {
private static class SubArray {
int start;
int end;
int sum;
SubArray(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
}
}
private SubArray findMaxCrossingSubArray(int[] data, int start, int mid,
int end) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
int maxLeft = mid;
for (int index = mid; index >= start; index--) {
sum += data[index];
if (leftSum < sum) {
leftSum = sum;
maxLeft = index;
}
}
int rightSum = Integer.MIN_VALUE;
int maxRight = mid + 1;
sum = 0;
for (int index = mid + 1; index <= end; index++) {
sum += data[index];
if (rightSum < sum) {
rightSum = sum;
maxRight = index;
}
}
return new SubArray(maxLeft, maxRight, leftSum + rightSum);
}
public SubArray findMaxSubArray(int[] data, int start, int end) {
if (start == end)
return new SubArray(start, end, data[start]);
int mid = (start + end) / 2;
SubArray ls = findMaxSubArray(data, start, mid);
SubArray rs = findMaxSubArray(data, mid + 1, end);
SubArray mcs = findMaxCrossingSubArray(data, start, mid, end);
if (ls.sum >= rs.sum && ls.sum >= mcs.sum)
return ls;
else if (rs.sum >= ls.sum && rs.sum >= mcs.sum)
return rs;
else return mcs;
}
public static void main(String[] args) {
int[] data = { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };
MaxSubArray msa = new MaxSubArray();
SubArray sa = msa.findMaxSubArray(data, 0, data.length - 1);
System.out.println("Start: " + sa.start + ", End: " + sa.end + ", Sum: "
+ sa.sum);
}
}
The code runs in O(n log n)
- geekyjaks April 27, 2014Sort by ascending. Then,
public int find(int[] data, int diff) {
QuickSort qs = new QuickSort();
qs.sort(data, 0, data.length - 1);
int count = 0;
int end = data.length - 1;
int start = end - 1;
while (start < end) {
if (data[end] - data[start] == diff)
count++;
if (data[end] - data[start] >= diff)
end--;
start--;
if (start < 0)
break;
}
return count;
}
Following solution runs in O(n+m) where m < n.
public class SubSequence {
public String get(String data){
if (data == null || data.length() <=1)
return null;
int start = -1, end = -1;
int tempStart= -1, tempEnd = data.length();
// assume that first char is interested one
char interested = data.charAt(0);
// store position of 1s
Stack<Integer> stack = new Stack<>();
for(int index = 0; index < data.length(); index++){
if (data.charAt(index)== interested){
stack.push(index);
if (tempStart == -1)
tempStart = index;
}else{
if (tempStart == -1)
continue;
if (stack.isEmpty()){
if ((index - tempStart) > (end - start)){
start = tempStart;
end = index;
}
tempStart = -1;
}else
// pop the matching 1
stack.pop();
}
}
// if the input itself is longest sequence, it should come here
if (stack.isEmpty() && tempStart != -1){
if ((tempEnd - tempStart) > (end - start)){
start = tempStart;
end = tempEnd;
}
}
// if input has more 1s, stack is not empty
while(!stack.isEmpty()){
tempStart = stack.pop();
if ((tempEnd - tempStart) > (end - start)){
start = tempStart + 1;
end = tempEnd;
}
tempEnd = tempStart;
}
return data.substring(start, end);
}
public static void main(String[] args) {
SubSequence seq = new SubSequence();
System.out.println(seq.get("111001110011100011100"));
}
}
Here it is
public class ReverseSentence {
public String get(String data) {
if (data == null || data.length() <= 2)
return data;
char space = ' ';
char[] src = data.toCharArray();
char[] reversed = new char[data.length()];
int pos = 0, end = data.length();
for (int index = data.length() - 1; index >= 0; index--) {
int start = -1;
if (src[index] == space)
// word starts next to space
start = index + 1;
else if (index == 0)
start = 0;
if (start != -1 && start <= end) {
int len = end - start;
// copy the word
System.arraycopy(src, start, reversed, pos, len);
end = index;
pos += len;
if (pos < data.length())
// add space between words
reversed[pos++] = space;
}
}
return new String(reversed);
}
public static void main(String[] args) {
ReverseSentence rs = new ReverseSentence();
System.out.println(rs.get("repeat these words to reverse the sentence "));
}
}
Simple & elegant.
- geekyjaks August 14, 2015