wwu
BAN USER- 7of 7 votes
AnswersWhat is the maximum number of edges you could add to n vertexes to make a acyclic undirected graph?
- wwu in United States
Follow up:
What is the maximum number of edges you could add to n vertexes to make a acyclic directed graph?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 0of 0 votes
AnswersLeetcode: Jump Game.
- wwu in United States
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.| Report Duplicate | Flag | PURGE
Ebay Software Engineer Intern Algorithm - 0of 0 votes
AnswersGiven a string, reverse the word, but keep the comma, number and space.
- wwu in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer Intern Algorithm - 0of 0 votes
AnswerGiven a matrix, there are two 1s and many 0s. Find a path from the first 1 to the second 1.
- wwu in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer Intern Algorithm - 0of 0 votes
AnswersFind Top k most frequent elements
- wwu in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer Intern Algorithm - 0of 0 votes
AnswersFind Top k biggest numbers
- wwu in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer Intern Algorithm
Let me try to explain. f[i][j] means how many times target[0,i-1] appears in source[0,j-1]. So, if target[i] == source[j], f[i][j] = f[i-1][j-1](how many times target[0,i-2] appears in source[0,j-2]) + f[i-1][j] (how many times target[0,i-2] appears in source[0,j-1]).
if target[i] != source[j], f[i][j] = f[i][j-1](how many times target[0,i-1] appears in source[0,j-2]).
A long solution..
Do 2 dfs for parents and children.
public static class Group{
public String identity;
public HashMap<String, Group> memberOf;
public HashMap<String, Group> members;
public HashSet<String> users;
public Group(String name){
identity = name;
memberOf = new HashMap<String, Group>();
members = new HashMap<String, Group>();
users = new HashSet<String>();
}
}
public static class Node{
String identity;
List<Node> child;
int state;
List<Node> parent;
public Node(String name){
identity = name;
child = new ArrayList<Node>();
state = 0;
this.parent = new ArrayList<Node>();
}
}
public static List<Group> findGroup(HashMap<String, HashSet<String>>
groupMembers){
List<Group> result = new ArrayList<Group>();
HashMap<String, Node> nodeHashMap = new HashMap<String, Node>();
for(Map.Entry<String, HashSet<String>> entry : groupMembers.entrySet()){
String name = entry.getKey();
HashSet<String> member = entry.getValue();
Node node;
if(nodeHashMap.containsKey(name)){
node = nodeHashMap.get(name);
}else{
node = new Node(name);
nodeHashMap.put(name, node);
}
for(String elem : member){
Node child;
if(nodeHashMap.containsKey(elem)){
child = nodeHashMap.get(elem);
}else{
child = new Node(elem);
nodeHashMap.put(elem, child);
}
child.parent.add(node);
node.child.add(child);
}
}
HashMap<String, Group> groupHashMap = new HashMap<String, Group>();
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
Group group = new Group(entry.getKey());
groupHashMap.put(entry.getKey(), group);
result.add(group);
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()){
Node node = entry.getValue();
if(node.state == 2){
Group g = groupHashMap.get(node.identity);
if(!g.members.isEmpty() && !g.users.isEmpty()) continue;
for(Node nd : node.child){
String ndId = nd.identity;
if(ndId.startsWith("G")){
g.members.put(ndId, groupHashMap.get(ndId));
}else{
g.users.add(ndId);
}
}
continue;
}
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.add(node);
while(!nodeStack.isEmpty()){
Node curNode = nodeStack.peek();
if(curNode.state == 1){
curNode.state = 2;
Set<String> allchild = new HashSet<String>();
for(Node curNodeChild : curNode.child){
allchild.add(curNodeChild.identity);
for(Node curNodeGrandChild : curNodeChild.child){
allchild.add(curNodeGrandChild.identity);
}
}
curNode.child.clear();
for(String id : allchild){
curNode.child.add(nodeHashMap.get(id));
}
nodeStack.pop();
continue;
}
curNode.state = 1;
List<Node> child = curNode.child;
for(Node childNode : child){
if(childNode.state == 1){
return null;
}else{
nodeStack.push(childNode);
}
}
}
Group g = groupHashMap.get(node.identity);
for(Node nd : node.child){
String ndId = nd.identity;
if(ndId.startsWith("G")){
g.members.put(ndId, groupHashMap.get(ndId));
}else{
g.users.add(ndId);
}
}
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
entry.getValue().state = 0;
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
Node node = entry.getValue();
if (node.state == 2) {
Group g = groupHashMap.get(node.identity);
if (!g.memberOf.isEmpty()) continue;
for (Node nd : node.parent) {
String ndId = nd.identity;
g.memberOf.put(ndId, groupHashMap.get(ndId));
}
continue;
}
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.add(node);
while (!nodeStack.isEmpty()) {
Node curNode = nodeStack.peek();
if (curNode.state == 1) {
curNode.state = 2;
Set<String> allparent = new HashSet<String>();
for (Node curNodeParent : curNode.parent) {
allparent.add(curNodeParent.identity);
for (Node curNodeGrandParent : curNodeParent.parent) {
allparent.add(curNodeGrandParent.identity);
}
}
curNode.parent.clear();
for (String id : allparent) {
curNode.parent.add(nodeHashMap.get(id));
}
nodeStack.pop();
continue;
}
curNode.state = 1;
List<Node> parent = curNode.parent;
for (Node parentNode : parent) {
if (parentNode.state == 1) {
return null;
} else {
nodeStack.push(parentNode);
}
}
}
Group g = groupHashMap.get(node.identity);
for (Node nd : node.parent) {
String ndId = nd.identity;
g.memberOf.put(ndId, groupHashMap.get(ndId));
}
}
return result;
}
Good idea to store the states! One small nit:
The for loop can be cleaner as follows:
for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
{
// Have we calculated those results before?
count += getCount(nextPossibleNumber, n-1);
}
I thing all the things you tried to do in the for loop is already done before.
- wwu August 02, 2015/**
*
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4
*
* Created by wwu on 1/26/15.
*/
public class num_of_countries {
public void bfs(int[][] matrix, boolean[][] visited, int i, int j, int
label){
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length ||
visited[i][j] || matrix[i][j] != label)
return;
visited[i][j] = true;
bfs(matrix, visited, i-1,j,label);
bfs(matrix, visited, i+1,j,label);
bfs(matrix, visited, i,j-1,label);
bfs(matrix, visited, i,j+1,label);
}
public int driver(int[][] matrix){
int count = 0;
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix[0].length; j ++){
if(!visited[i][j]){
count++;
bfs(matrix, visited, i, j, matrix[i][j]);
}
}
}
return count;
}
public static void main(String[] args){
num_of_countries obj = new num_of_countries();
int[][] matrix = {{1,1,1,1},
{0,0,0,0},
{1,0,0,1}};
System.out.println(obj.driver(matrix));
}
}
/**
*
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4
*
* Created by wwu on 1/26/15.
*/
public class num_of_countries {
public void bfs(int[][] matrix, boolean[][] visited, int i, int j, int
label){
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length ||
visited[i][j] || matrix[i][j] != label)
return;
visited[i][j] = true;
bfs(matrix, visited, i-1,j,label);
bfs(matrix, visited, i+1,j,label);
bfs(matrix, visited, i,j-1,label);
bfs(matrix, visited, i,j+1,label);
}
public int driver(int[][] matrix){
int count = 0;
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix[0].length; j ++){
if(!visited[i][j]){
count++;
bfs(matrix, visited, i, j, matrix[i][j]);
}
}
}
return count;
}
public static void main(String[] args){
num_of_countries obj = new num_of_countries();
int[][] matrix = {{1,1,1,1},
{0,0,0,0},
{1,0,0,1}};
System.out.println(obj.driver(matrix));
}
}
One idea, not sure whether this is correct.
Construct two graphs, one for x-coordinate--Gx, one for y-coordinate--Gy.
For Gx, If x1 < x2, then we have an edge from x1->x2, if x1 > x2, one edge x1<-x2. If x1 == x2, combine x1 and x2 together.
Similarly for Gy.
In the end, we check whether there exists a cycle in Gx or Gy. If this is true, then the answer is impossible.
For example, p1 SE p2, we have x1 > x2 and y1 < y2.
Gx: x1 <-- x2 Gy: y1 -->y2
p2 SE p3, we have x2 > x3 and y2 < y3.
Gx: x1 <-- x2 <-- x3 Gy: y1 -->y2 -->y3
p3 SE p1, we have x3 > x1 and y3 < y1
In Gx, we have a cycle from x1 <-- x2 <-- x3 <-- x1. So it is impossible.
Any comment/correction/improvement is welcome...
Code...
class CountInversions{
public:
long* nums;
long count(long nums[], int begin, int end){
this->nums = nums;
return count(begin,end);
}
long count(int begin, int end){
if(begin >= end) return 0;
long c1 = count(begin, (begin+end)/2);
long c2 = count((begin+end)/2 + 1, end);
long c3 = mergeCount(begin, (begin+end)/2, (begin+end)/2+1, end);
return c1 + c2 + c3;
}
long mergeCount(int b1, int e1,int b2, int e2){
int p1 = b1;
int p2 = b2;
int len = e1-b1+1 + e2-b2+1;
long temp[len];
memset(temp,0,sizeof(temp));
long count = 0;
for(int i = 0; i < len; i ++){
if(p1 > e1){
temp[i] = nums[p2];
p2++;
}else if(p2 > e2){
temp[i] = nums[p1];
p1++;
}else{
if(nums[p1] <= nums[p2]){
temp[i] = nums[p1];
p1++;
}else{
temp[i] = nums[p2];
p2++;
count += e1-p1+1;
}
}
}
memcpy(nums+b1, temp, sizeof(temp));
return count;
}
};
If the string only contains ‘a’, return [0,0];
We only could reverse of a substring begin with ‘b’ in order to get a smaller string.
Find the first ‘b’ from the beginning
Check each substring begin with ‘b’, count how many ‘a’ after ‘b’ in each substring.
Suppose we have the following string (eliminate the heading ‘a’)
b{a*c1}b{a*c2}b{a*c3}….b{a*c_n}
If we reverse the first substring b{a*c1}, the resulting substring would be
{a*c1}bb{a*c2}b{a*c3}….b{a*c_n}——–(1)
If we reverse the first two substrings b{a*c1}b{a*c2}, the resulting substring would be
{a*c2}b{a*c1}bb{a*c3}….b{a*c_n}——–(2)
(2) is smaller than (1) c2 > c1
If we reverse the first three substrings b{a*c1}b{a*c2}b{a*c3}, the resulting substring would be
{a*c3}b{a*c2}b{a*c1}b….b{a*c_n}——–(3)
(3) is smaller than (2) c3 > c2 (c2 > c1)
(3) is smaller than (1) c3 > c1 (c1 > c2)
Therefore, every time we reverse the string to get a smaller substring as long as we have a bigger cn.
class OptimalSubstringReversal{
public:
void driver(string str){
int i = 0;
while(i < str.length()){
if(str[i] == 'b'){
break;
}
i++;
}
if(i == str.length()) {
cout << "[0,0]";
return;
}
int pre_count = 0;
int pre_end = 0;
int start = i;
int end = i;
int count = 0;
for(; i < str.length(); i ++){
if(str[i] == 'a'){
end = i;
count ++;
}else{
if(count > pre_count){
pre_count = count;
pre_end = end;
}
count = 0;
}
}
if(count > pre_count){
pre_end = end;
}
cout <<"["<<start <<"," << pre_end << "]" << endl;
}
};
class NodeLength{
public:
int result = -1;
int findNode(TreeNode* root, TreeNode* nd1, TreeNode* nd2, int len){
if(root == NULL) return 0;
int plen1 = findNode(root->left, nd1, nd2, len+1);
int plen2 = findNode(root->right, nd1, nd2, len+1);
if(result == -1){
if(plen1 != 0 && plen2 != 0){
result = plen1 + plen2;
return result;
}
if(root == nd1){
if(plen2 != 0){
result = plen2 - len;
return result;
}else
return len;
}
if(root == nd2){
if(plen1 != 0){
result = plen1 - len;
return result;
}
return len;
}
if(plen1 != 0) return plen1;
if(plen2 != 0) return plen2;
return 0;
}
return 0;
}
int driver(TreeNode* root, TreeNode* nd1, TreeNode* nd2){
findNode(root, nd1, nd2, 0);
return result;
}
};
class ReadNumbers{
string readOneNumber(long number){
switch(number){
case 1: return "one"; break;
case 2: return "two"; break;
case 3: return "three"; break;
case 4: return "four"; break;
case 5: return "five"; break;
case 6: return "six"; break;
case 7: return "seven"; break;
case 8: return "eight"; break;
case 9: return "nine"; break;
case 10: return "ten"; break;
case 11: return "eleven"; break;
case 12: return "twelve"; break;
case 13: return "thirteen"; break;
case 14: return "fourteen"; break;
case 15: return "fifteen"; break;
case 16: return "sixteen"; break;
case 17: return "seventeen"; break;
case 18: return "eighteen"; break;
case 19: return "nineteen"; break;
}
return "";
}
string readTy(long number){
switch (number) {
case 2:
return "twenty";
break;
case 3:
return "thirty";
break;
case 4:
return "fourty";
break;
case 5:
return "fifty";
break;
case 6:
return "sixty";
break;
case 7:
return "seventy";
break;
case 8:
return "eighty";
break;
case 9:
return "ninety";
break;
default:
break;
}
return "";
}
string readBase(long num){
switch (num) {
case 0:
return "hundred";
break;
case 1:
return "thousand";
break;
case 2:
return "million";
break;
case 3:
return "billion";
break;
default:
break;
}
return "";
}
string readTwoNumbers(long num){
if(num < 20) return readOneNumber(num);
else{
string first = readTy(num/10);
string second = readOneNumber(num%10);
if(second.length() == 0) return first;
return first + "-" + second;
}
}
string readThreeNumbers(long num){
if(num < 100) return readTwoNumbers(num);
long val = num/100;
string hstr = readOneNumber(val);
return hstr+" " + readBase(0)+" and " + readTwoNumbers(num%100);
}
public:
string driver(long number){
string result;
long modd = 1000;
int count = 0;
while(number != 0){
string part = readThreeNumbers(number%modd) + " " + readBase(count);
result = part + " " + result;
number /= 1000;
modd = 1000;
count++;
}
return result;
}
};
class StringDictionary{
public:
bool checkConcatenation(unordered_set<string>& dictionary, string str){
if(str.length() == 0) return true;
for(int i = 1; i <= str.length(); i ++){
string t = str.substr(0,i);
if(dictionary.find(t)!= dictionary.end()){
if(checkConcatenation(dictionary, str.substr(i))){
return true;
}
}
}
return false;
}
};
int numOfSubPalindroms(string str){
int len = (int)str.length();
bool flag[len+1][len+1];
memset(flag, false, sizeof(flag));
int count = 0;
for(int i = len; i >= 1; i --){
for(int j = i; j <= len; j ++){
if(j == i||(j-i == 1 && str[j-1] == str[i-1]) || (flag[i+1][j-1] && str[i-1] == str[j-1])){
count++;
if(j != i)
cout << str.substr(i-1,j-i+1) << endl;
flag[i][j] = true;
}
}
}
return count;
}
map< Node*,Node*> mmap;
Node *copyRandomList(Node *head) {
if(head == NULL) return head;
if(mmap.find(head) != mmap.end()){
return mmap[head];
}
Node* node = new Node(head->label);
mmap[head] = node;
node->next = copyRandomList(head->next);
node->random = copyRandomList(head->random);
return node;
}
Sort the array.
For each interval (i,j), find m,n in the interval which have the same sum.
struct ValIndx{
int value;
int index;
ValIndx(int v, int i):value(v), index(i){}
};
static int ValIndxCompare(const ValIndx& v1, const ValIndx& v2){
return v1.value < v2.value;
}
vector<ValIndx> v;
void find(vector<int>& nums){
int len = (int)nums.size();
if(len == 0) return;
for(int i = 0; i < len; i ++){
ValIndx vi(nums[i],i);
v.push_back(vi);
}
sort(v.begin(), v.end(), ValIndxCompare);
for(int i = 0; i < len; i ++){
for(int j = i+1; j < len; j ++){
int sum = v[i].value + v[j].value;
int begin = i+1;
int end = j;
while(begin < end){
int part = v[begin].value + v[end].value;
if(part == sum){
cout << v[i].index << " " << v[j].index << " "
<< v[begin].index << " " << v[end].index << endl;
begin++;
end--;
}
if(part < sum){
begin++;
}
if(part > sum){
end--;
}
}
}
}
}
- wwu August 07, 2015