Patrick
BAN USER 0of 0 votes
AnswerI want to implement a simple HTTP DenialofService protection. There are clients that can send HTTP request to a Server (i.e. a GET Method of http://10.1.1.2:8080/?clientId=7)
 Patrick in United States
if in an interval of 10 seconds more then 10 request comes from a specific client the 11th, 12th.. requests will get blocked. until 10 seconds from the first request will pass and then a new time windows of 10 seconds will be open. the idea is no more than 10 requests per 10 secs.
The time frame starts on each client’s first request and ends 10 seconds later.
I want to implement this logic on the server. Which data structures/collection/custom made object would you build to implement such a logic...
it is also important to have a threats safe solution.. and performances is also a factor here..
Thanks. Report Duplicate  Flag  PURGE
Dropbox Software Trainee Java  2of 2 votes
AnswersI was asked to design a system on a whiteboard which simulate a executor.
 Patrick in United States
This system has a method that is being triggered every second. I need to add logic to the method (i.e. run jobs).
There is also a method called job_arrived() that is called when a new job arrives.. I need to implement it as well.
I needed to implement a system which tries to run each job right when it is arrived (it has a return value that gets a success status from a black box service). if the job ran successfully that's the end of it..
if not I need to rerun it after 2 seconds (and if that fails as well  there will be no reruns).
of course  more than one job can be accepted each second.
I was asked to describes the system (describe the classes and method) and consider the system to be large scale one (meaning.. threading is in order here..).
The answer I gave was apparently not multi threaded enough..
any idea to what I should have done?
Thanks guys Report Duplicate  Flag  PURGE
Facebook Software Developer Java  0of 0 votes
AnswersYou have a long string that contains of 0's and 1's, seprated with some delimiter (like "!"). the number of delimeters after each 0 or 1 is between 1 to 3.
 Patrick in United States
for example a string such as 0! 1!!! 0!! 1!! 0! 1! 0!!! 1!! 0!! (and so on...)
Take this long string and convert it to a 7 digits number by some porgramming algorythem,
(you can use every lanugage you want) Report Duplicate  Flag  PURGE
A9 abc Arrays  0of 0 votes
AnswerYou have a cycled doubly linked list (meaning there is a cycle and each node has prev() and next() method).
 Patrick in United States
You can set/check the value of each node in the list to be 0/1 (method setValue(0/1) getValue())
Find how many elements there are in the list.
You start from the some node and you don’t know the status of the nodes value, could be any combination of 1’s and 0’s).. Report Duplicate  Flag  PURGE
AMD Computer Scientist 24x7 Google chrome technical support number 18882012039  0of 0 votes
AnswersI am trying to write a method that will return true if a binary tree is full and complete (each node has 2 children or none and all the leaves of the tree are at the same depth).
My idea is to use recursion. I will check for any node if its left son has number of children that is equal to its right son's number of children. If so, I will return true, otherwise false.
The algorithm will look like this:public class Utils { public boolean isFullCompleteTree(Tree<Integer> t) { TreeInfo rootInfo = isFullCompleteTree(t.getRoot()); return rootInfo.valid; } public TreeInfo isFullCompleteTree(Node<Integer> node) { boolean valid = true; if (node == null) { return new TreeInfo(true, 0); } TreeInfo rightInfo = isFullCompleteTree(node.goRight()); TreeInfo leftInfo = isFullCompleteTree(node.goLeft()); if ((!rightInfo.valid)  (!leftInfo.valid)) { valid = false; } if (rightInfo.numChildern != leftInfo.numChildern) { valid = false; } return new TreeInfo(valid, rightInfo.numChildern + leftInfo.numChildern + 1); } } class TreeInfo { public boolean valid; public int numChildern; public TreeInfo(boolean valid, int numChildern) { this.valid = valid; this.numChildern = numChildern; } }
I didn't include the tree implementation but it is pretty straightforward.
 Patrick in United States
The idea of the algorithm is to check if in every node the number of right son's children is equal to the left son's children. If a tree is not full and complete, then in some node this rule will not apply.
Do you think that my algorithm is correct or am I missing something? Report Duplicate  Flag  PURGE
ASU Accountant Algorithm  0of 0 votes
Answersyou have numbers between 1 to n. a set of number i.e. (4,5) means that person number 4 is connected to person number 5. find all the ways the a group of n pepole can be connected. i.e. for 0 and 1 there is the empty set, for 2 there is 2 ways, empty set and {1,2} only for 3 there are 4 ways: {}, {(1,2)} {(2,3)}, {(3,1)} for 4 there are 10 ways ({},{(1,2)}, {(1,2),(3,4)},.......
 Patrick in United States
you can do it by factorial and cobination but there is another way that state that:
T(n)=T(n1) + (n1)*T(n2)
(while T(n) is the function that computes the number of ways..
Can someone explain why this equation is true? Report Duplicate  Flag  PURGE
Abs india pvt. ltd. Computer Scientist Algorithm  0of 0 votes
Answersyou have a numbers between 1 to n. a set of number i.e. (4,5) means that person number 4 is connected to person number 5. find all the ways the a group of n pepole can be connected. i.e. for 0 and 1 there is the empty set, for 2 there is 2 ways, empty set and {1,2} only for 3 there are 4 ways: {}, {(1,2)} {(2,3)}, {(3,1)}
 Patrick in United States
for 4 there are 10 ways ({},{(1,2)}, {(1,2),(3,4)},.......
you can do it by factorial and cobination but there is another way that state that:
T(n)=T(n1) + (n1)*T(n2)
(while T(n) is the function that computes the number of ways..
can someone explain why this equation is true?
Thanks... Report Duplicate  Flag  PURGE
abc Computer Scientist Algorithm
Good thinking.
But in fact, you turn the problem above into this problem:
"Given an a equation of the form of x1+x2+...+xn=sum, while x1!=x2!=..!=xn, find a soultion from the group {1,2...2n} (i.e. 1<=x1,x2...xn<=2n))
How you can solve this problem by **not using** backtracking?
The answer is that you can't. This is a NPcomplete problem and if you solve it in a polynomail time that means that you prove that P=NP and you can get your turing prize this year! :)
I believe that the problem above cannot be solve without backtracking since it can be reducted into an NP complete one...
my 2 cents.
lets model the problem as a adjacency matrix one.
lets define int arr[][] and for each arr[i][j] is 1 <=> i knows j.
so we acutally need to find 2 thing:
1. all of the k rows that follow this rule: (arr[k][i]==0 iff k!=i) for (0<=i<=arr.length)
2. all of the m colums that follow this rule: (arr[i][m]==1) for (0<=i<=arr.length)
the 1's rule checks if the person k doesn't know no one else but himself.
the 2's rule checks if all the other person know who person m is.
we need to find k such as (k==m), meaning both of the conditions are followed.
for i.e. this is a matrix that has person with index 3 (starting from 0) as a celebrity:
1 0 0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0 1 0
0 0 0 1 1
note that there can be no more than one k and no more the one m.
we can travel in a manhattan distance path from the first line until we encouter the last line or column of the matrix fo find the celebrity (we are actully finding k which is unique and can only be equal to m).
100 1 1
1 1 1 1 1
0 0 1 1 0
0 0 010
0 0 0 1 1
and the code:
package findCelebs;
import java.util.HashSet;
import java.util.Set;
public class FindCelebrity {
static int knows[][];
public static void main(String[] args) {
knows = new int[][] {
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 0, 0, 1, 1, 0 },
{ 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1 } };
Set<Integer> people = new HashSet<Integer>();
for (int i = 0; i < 5; i++) {
people.add(i);
}
System.out.println(findCelebrity(people));
}
public static int findCelebrity(Set<Integer> group) {
return isCelebrity(group, 0);
}
public static int isCelebrity(Set<Integer> group, int personInKRow) {
if (personInKRow >= group.size()) {
return 1;
}
// a celebrity must knows himself
if (!knows(personInKRow, personInKRow)) {
// so check the next person in line
return isCelebrity(group, personInKRow + 1);
}
for (int j = personInKRow + 1; j < group.size(); j++) {
if (knows(personInKRow, j)) {
// personInKRow is not the celebrity  knows some one else but
// himslef
// so check the person in line j
return isCelebrity(group, j);
} else {
// personInKRow does not know j j is not the celebrity
}
}
return personInKRow;
}
private static boolean knows(int i, int j) {
return (knows[i][j] == 1);
}
}

Patrick
January 18, 2015 public static void printSeq(char[] word) {
int xPos = 0;
int yPos = 0;
char c;
for (int i = 0; i < word.length; i++) {
c = word[i];
for (int j = xPos; j < (c  'a') / 5; j++) {
System.out.println("Down");
}
for (int j = (c  'a') / 5; j < xPos; j++) {
System.out.println("Up");
}
for (int j = yPos; j < (c  'a') % 5; j++) {
System.out.println("Right");
}
for (int j = (c  'a') % 5; j < yPos; j++) {
System.out.println("Left");
}
System.out.println("Ok");
xPos = (c  'a') / 5;
yPos = (c  'a') % 5;
}
}

Patrick
December 06, 2014 lets take the worths case where there are m elements and each one of the m number is seprated between two numbers
i.e (1,3,5,7) and not (1,6).
then we will do binary search (O(log(n)) for each missing number (m) which will give us: m*log(n) which in case m is constat will give O(log(n))
right... so lets make it:
public static void findMissingNumbersBetweenToIndexes(int[] arr,
Set<Integer> set, int start, int finish) {
if (arr.length == 1) {
return;
}
if ((arr[finish]  arr[start] + 1)  (finish  start) == 0) {
return;
}
if (start + 1 == finish) {
for (int i = arr[start] + 1; i < arr[finish]; i++) {
set.add(i);
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);
// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}

Patrick
December 05, 2014 In Java:
public static Set<Integer> findMissingNumbers(int arr[], int m) {
Set<Integer> set = new HashSet<Integer>();
// dealing with array that does not start with 1
for (int i = 1; i < arr[0]; i++) {
set.add(i);
}
// dealing with the middle elements
findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length  1);
// recalculate m for any extra tail's numbers
m = m  (((arr[arr.length  1]  arr[0] + 1)  arr.length))
 (arr[0]  1);
// dealing with the any extra tail's numbers
for (int i = 1; i <= m; i++) {
set.add(arr[arr.length  1] + i);
}
return set;
}
public static void findMissingNumbersBetweenToIndexes(int[] arr,
Set<Integer> set, int start, int finish) {
if (arr.length == 1) {
return;
}
if ((arr[finish]  arr[start] + 1)  (finish  start) == 0) {
return;
}
if (start + 1 == finish) {
for (int i = arr[start] + 1; i < arr[finish]; i++) {
set.add(i);
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);
// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}

Patrick
December 05, 2014 Open Chat in New Window
 Patrick January 29, 2017