Showing posts with label Company-Facebook. Show all posts

Given an array A with N integers between 3500 and 4500, find the number of unique multisets that can be formed using elements from the array such that the bitwise XOR of all the elements of the multiset is a prime number.

Solution

First, we notice that 3500 ≤ a[i] ≤ 4500. So the bitwise XOR of any multiset is in the range [0,(2^13)-1].

Let count[i] be the number of i in array A.
Let f[i,j] be the number of unique multisets whose elements are within [3500,i], and whose XOR equals to j. So we have

f[i,j] = ((f[i-1,j] × (count[i]/2 + 1)) % mo + (f[i-1,j^i] × ((count[i]+1)/2) % mo)) %mo


int n,count[maxd];

bool is_prime[max_xor+2];

long long f[2][max_xor+2];



void init()

{

 for(int i=2;i<=max_xor;i++) is_prime[i]=true;



 for(int i=2;i<=max_xor;i++)

  if(is_prime[i])

  {

   int j=i<<1;

   while(j<=max_xor)

   {

    is_prime[j]=false;

    j+=i;

   }

  }

}



int main()

{

 init();



 int T;

 scanf("%d",&T);

while(T)

{

 T--;

 memset(count,0,sizeof(count));

 memset(f,0,sizeof(f));



 scanf("%d",&n);



 int tmp;

 for(int i=1;i<=n;i++)

 {

  scanf("%d",&tmp);

  count[tmp]++;

 }



 f[0][0]=1;

 int flag=1;

 for(int i=3500;i<=4500;i++)

 {

  for(int j=0;j<=max_xor;j++)

   if(count[i]==0)

    f[flag][j]=f[1-flag][j];

   else

    f[flag][j] = (f[1-flag][j]*(count[i]/2 + 1) % mo + f[1-flag][j^i]*((count[i]+1)/2) % mo) % mo;



  flag=1-flag;

 }



 long long ans=0;

 for(int j=0;j<=max_xor;j++)

  if(is_prime[j])

   ans = (ans + f[1-flag][j])%mo;



 printf("%lld\n",ans);

}

https://www.hackerrank.com/challenges/prime-xor/editorial

This problem can be solved using dynamic programming and pigeonhole principle. Using sieve of Eratosthenes, mark all the primes lying between

. Create a hashmap which stores the count of occurrences of all the array elements. Note that since the xor-sum of any subset of array elements will not exceed

. Using this property, we can write a

dynamic programming solution with

constant factor such that

would store the count of subsets that can be formed with the first

elements such that the xor-sum of the elements in the subset is

int a[5025];
vector<int> v;
bool prime[9025];
long long mem[2][8192];
void sieve( )   
{
    memset(prime, true, sizeof(prime));
    prime[1]=false, prime[0]=false; 
    for(int i=4;i<=9000;i+=2)
    prime[i]=false;
    for (int p=3; p*p<=9000;p+=2)
 {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=9000; i += 2*p)
                prime[i] = false;
        }
    }

}
int main() {
//freopen("input2.txt","r",stdin);
//freopen("output2.txt","w",stdout);
clock_t begin, end;
begin = clock();
int t;
sieve();
cin >> t;
while(t--) {
    int n;
    cin >> n;
    v.clear();
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++) {
        int x;
        scanf("%d",&x);
        a[x]+=1;
    }
    for(int i=3500;i<4525;i++)
        if(a[i]>=1)
            v.push_back(i);
    memset(mem,0,sizeof(mem));
    mem[0][0]=1;
    int flag=1;
    int k = v.size();
    for(int i=1;i<=k;i++) {
        for(int j=0;j<8192;j++) {
            mem[flag][j] = (mem[flag^1][j]*(1+(a[v[i-1]])/2))%mod + (mem[flag^1][j^v[i-1]]*((a[v[i-1]]+1)/2))%mod;
            if(mem[flag][j]>=mod)
                mem[flag][j]%=mod;
        }
        flag = flag^1;

    }
    long long ans=0;
    long long res=0;
    for(int i=1;i<8192;i++) {
        if(prime[i]){

            res+= mem[flag^1][i];
            res%=mod;
        }
    }
    cout << res << endl;
}
end = clock();
//cout << ((float) (end) - (float) (begin)) / CLOCKS_PER_SEC << endl;
fclose(stdout);
return 0;

https://stackoverflow.com/questions/44958697/understanding-the-editorial-for-prime-xor-hackerrank

Explanation of Flag

This is a standard approach to reduce memory usage when using dynamic programming.

The idea is that often each row of a DP array only depends on the previous row. In this case, instead of storing the whole 2d DP[i][j] array, you can instead just use 2 rows of the array.

In other words, DP[i][j] is stored in mem[0][j] if i is even, and in mem[1][j] if i is odd. The mem array is reused multiple times and after each iteration holds the most recent two rows of the full DP array.

Explanation of recurrence

Suppose we have 5 duplicates of a certain value v. There are 1+5/2 ways of making an xor of 0 (take either 0,2 or 4 copies). There are (1+5)/2 ways of making an xor of v (take either 1,3 or 5 copies).

So to make the new value j, we can either start with j and add 0,2 or 4 copies of v, or start with j^v and add 1,3 or 5 copies

LCA of Deepest Nodes in Binary Tree - Facebook

https://www.cnblogs.com/EdwardLiu/p/6551606.html

给一个 二叉树 ， 求最深节点的最小公共父节点
     1
  2   3
     5  6    return 3.

       1  
    2   3
4      5 6   retrun 1. 
先用 recursive  ， 很快写出来了， 要求用 iterative 。 时间不够了。。。

Recursion: 返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就返回这个node，如果有一个子节点depth更深就返回个子节点lca，这个o(n)就可以了

Iteration: tree的recursion换成iteration处理，一般用stack都能解决吧（相当于手动用stack模拟recursion）。感觉这题可以是一个样的做法，换成post order访问，这样处理每个node的时候，左右孩子的信息都有了，而且最后一个处理的node一定是tree root

我的想法是要用hashMap<TreeNode, Info>

class Info{

　　int height;

　　TreeNode LCA;

}

 5     private class ReturnVal {
 6         public int depth;   //The depth of the deepest leaves on the current subtree
 7         public TreeNode lca;//The lca of the deepest leaves on the current subtree
 8 
 9         public ReturnVal(int d, TreeNode n) {
10             depth = d;
11             lca = n;
12         }
13     }
14 
15     public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
16         ReturnVal res = find(root);
17         return res.lca;
18     }
19 
20     private ReturnVal find(TreeNode root) {
21         if(root == null) {
22             return new ReturnVal(0, null);
23         } else {
24             ReturnVal lRes = find(root.left);
25             ReturnVal rRes = find(root.right);
26 
27             if(lRes.depth == rRes.depth) {
28                 return new ReturnVal(lRes.depth+1, root);
29             } else {
30                 return new ReturnVal(Math.max(rRes.depth, lRes.depth)+1, rRes.depth>lRes.depth?rRes.lca:lRes.lca);
31             }
32         }
33     }

find lowest common ancestor among deepest nodes in k-nary tree
前⼏几年年的经典题

LeetCode 674 - Longest Continuous Increasing Subsequence

https://leetcode.com/problems/longest-continuous-increasing-subsequence/

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000

https://leetcode.com/articles/longest-continuous-increasing-subsequence/

public int findLengthOfLCIS(int[] nums) {

int ans = 0, anchor = 0;

for (int i = 0; i < nums.length; ++i) {

if (i > 0 && nums[i - 1] >= nums[i])

anchor = i;

ans = Math.max(ans, i - anchor + 1);

}

return ans;

}

https://leetcode.com/problems/longest-continuous-increasing-subsequence/discuss/107352/Java-code-6-liner

public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0) return 0;
        int length=1,temp=1;
        for(int i=0; i<nums.length-1;i++) {
            if(nums[i]<nums[i+1]) {temp++; length=Math.max(length,temp);}
            else temp=1; 
        }
        return length;
    }

follow up1 要求subsequence中前后两个元素最⼤大间隔为1
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/LCIS%20Gap%20One/LCISGapOne.java

    public int findLengthOfLCIS(int[] nums) {
        if (nums.length < 2) return nums.length;
        int pp = 1;
        int p = nums[0] < nums[1] ? 2 : 1;
        int ans = p;
        
        for (int i = 2; i < nums.length; i ++) {
            int tmp = 1;
            if (nums[i - 2] < nums[i] && pp + 1 > tmp) tmp = pp + 1;
            if (nums[i - 1] < nums[i] && p  + 1 > tmp) tmp = p  + 1;
            ans = Math.max(ans, tmp);
            pp = p; p = tmp;
        }
        
        return ans;
    }

follow up2 要求subsequence中前后两个元素最⼤大间隔为k
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/LCIS%20Gap%20One/LCISGapK.java

    public int findLengthOfLCIS(int[] nums, int k) {
        if (nums.length == 0) return 0;
        
        int[] f = new int[nums.length];
        Arrays.fill(f, 1);      // every number itself can be a shortest increasing subsequence
        
        int ans = 1;
        for (int i = 1; i < nums.length; i ++) {
            for (int j = Math.max(0, i - k - 1); j < i; j ++)   // the limit of gap k
                if (nums[i] > nums[j])                          // make sure subsequence is increasing
                    f[i] = Math.max(f[i], f[j] + 1);
            ans = Math.max(ans, f[i]);                  // update result
        }
        return ans;
    }

follow up3 允许⼀一个break Example:
Input: [7, 3, 2, 3, 5, 6, 4, 2, 1]
Output: 5 - [2, 3, 5, 6, 4], [6, 4] is the break OR [3, 2, 3, 5, 6], [3,2] is the break
要有⼀一个变量量判断当前状态是否break过, 还有breaking index是另⼀一个 subarray的开始

Friend Recommendation

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=452567
就是找朋友那道题，地里有面经。就是给你一个功能，获取好友, 可以返回这个user的所有好友。要求你： 1 返回两个用户的共同好友。 2 让你实现一个推荐好友的功能。比如，如果好友1 是好友2 的好友，好友2 是好友3的好友，则好友3是好友1的推荐好友。要求返回好友1的所有推荐好友，并且把他们按照共同好友的数目来排序

1. getMutualFriends() 给你⼀一⼀一个getfriends的function然后写找共同好友
2. suggest() 排序好友的好友，谁共同好友多就放前⾯面⾯面。
1. Set->Map->Bucket

在这里的优势就是复杂度优势
BucketSort往往需要自行划分Bucket区域，还需要在Bucket内部进行排序，因此对数据是否uniformly distributed和空间会有要求
而这题里面公共好友数量可以直接作为下标使用，空间为O(n)不变，Bucket内部也不用担心顺序从而无需再次排序，所以时间也为O(n)
虽说相比QuickSort的O(nlogn)在实际运行中提升的效率不大，但算法面试中往往关心的是理论复杂度

HashMap统计次数然后用BucketSort排序

Tax Calculator - Facebook

2. 如果当前的⼯工资到这⼀一档就到头了了，需要break
给出⼀一⼀一个2D数组代表tax bracket[[10000,.1],[8000,.2],[6000,.3],[null, .
4]]，求 effective tax
给你⼀一些list，⾥里里⾯面存的是关于⼯工资收税的信息。⽐比如{{1000，0.1}，
{2000，0.2}，{null, 0.4}}. 还给了了员⼯工的salary。让你根据这个list中的信
息来计算员⼯工最后要交多少税
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Tax%20Calculator/TaxCalculator.java

    public static class Tax {
        double base, rate;
        public Tax(double base, double rate) {
            this.base = base;
            this.rate = rate;
        }
    }

    public double calculate(Tax[] taxs, double money) {
        Arrays.sort(taxs, new Comparator<Tax>(){
            public int compare(Tax a, Tax b) {
                if (a.base < b.base) return -1;
                else if (a.base == b.base) return 0;
                else return 1;
            }
        });
        double pay = 0;
        for (int i = 0; i < taxs.length; i ++) {
            if (i < taxs.length - 1 && money >= taxs[i + 1].base)
                pay += (taxs[i + 1].base - taxs[i].base) * taxs[i].rate;
            else {
                pay += (money - taxs[i].base) * taxs[i].rate;
                break;
            }
        }
        return pay;
    }

    public static void main(String[] args) {
        TaxCalculator sol = new TaxCalculator();
        Tax[] taxs = new Tax[4];
        taxs[0] = new Tax(10000, 0.1);
        taxs[1] = new Tax(8000, 0.2);
        taxs[2] = new Tax(6000, 0.3);
        taxs[3] = new Tax(0, 0.4);
        System.out.println(sol.calculate(taxs, 4000));
    }

Facebook Algorithm Interview Summary and Follow up

Prime XOR - HackerRank