Matoy
 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.
 Matoy 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
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).
 Matoy 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
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.
 Matoy 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
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)},.......
 Matoy 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
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)}
 Matoy 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
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);
}
}

Matoy
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;
}
}

Matoy
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);
}

Matoy
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);
}

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