Wayfair
  • OA
    • Karat
      • 811. Subdomain Visit Count
      • Ads Conversion Rate
      • Recommend Movie
      • Longest Common Continuous Subarray
      • Course Overlap
      • Halfway courses
      • Find one rectangle
      • Find all rectangles
      • Find Multiple Shapes
      • word wrap
      • word processor
      • Basic Calculator
      • Basic Calculator with parenthesis
      • 带变量计算器
      • Valid Matrix
      • nonogram
      • Node with 0 or 1 parents
      • 两个节点是否有公共祖先
      • 最远祖先
      • invalid Badge Records
      • 一小时内access多次
      • canSchedule
      • spareTime
      • sparse vector
      • sparse vector 实现add,dot和cos
      • userlogs earliest and latest access time
      • resource Access with in 5 min
      • Find Word Path in Grid
      • Find legal moves
      • 找能去的所有0区域
      • 最短路径找treasure
  • VO
    • Coding
      • Valid Palindrome
      • Add String
      • Coupon
    • System design
    • BQ
    • OOD
  • SD
  • LeetCode Tag
  • VO Onsite
Powered by GitBook
On this page
  1. OA
  2. Karat

Node with 0 or 1 parents

输入是int[][] input, input[0]是input[1] 的parent,比如 {{1,4}, {1,5}, {2,5}, {3,6}, {6,7}}会形成上面的图 第一问是只有0个parents和只有1个parent的节点

  1    2    3
/  \  /      \
4    5        6
                \
                  7
 public List<Integer> findNodesWithZeroOrOneParent(int[][] edges)
    {
        List<Integer> res = new ArrayList<Integer>();
        // child -- > set of its parents
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i = 0; i< edges.length; i++)
        {
            int parent  = edges[i][0];
            int child = edges[i][1];
            map.putIfAbsent(child, new HashSet<Integer>());
            map.get(child).add(parent);
        }

        for(Map.Entry<Integer, Set<Integer>> entry : map.entry.Set())
        {
            if(entry.getValue().size() <=1)
            {
                res.add(entry.getKey());
            }
        }
        return res;
    }
PreviousnonogramNext两个节点是否有公共祖先

Last updated 3 years ago