Massive Algorithms: Careercup - Google面试题 - 4699414551592960 - zhuli19901106

Careercup - Google面试题 - 4699414551592960 - zhuli19901106 - 博客园

we have a random list of people. each person knows his own height and the number of tall people in front of him. write a code to make the equivalent queue.  for example :  input: <"Height","NumberOfTall","Name">,  <6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">  output: "F","E","D","C","B","A" --> end of queue

题目：有一队人正在排队，告诉你每个人的姓名、身高(目前默认都不相同)，以及他/她所看到的前面比他高的人。请你计算出这个队伍里各个人的顺序。
解法：从最矮的人入手。对于最矮的人，他所看到的所有人都比他高，所以如果他看到有K个人比他高，那么他一定排在K + 1名。我的代码是当时琢磨了很久，采用树状数组写出来的。此处的树状数组提供快速修改区间、查询单个元素的能力，能做到对数时间。现在居然已经忘了当时的具体思路。总体思想是先按身高升序排序，然后逐个确定每个人在队列里的位置。关键的一点：每次都只能确定当前最矮的人排在哪儿。树状数组中维护的值c[i]的意义，是记录当前位置的前面有多少个比它高。其中还有个方法用到二分搜索，所以整体复杂度是比较奇怪的O(n * log(n) + n * log^2(n)) = O(n * log^2(n))。

  8 struct Person {
  9     int height;
 10     int taller;
 11     string name;
 12     Person(int _height = 0, int _taller = 0, string _name = ""): 
 13         height(_height), taller(_taller), name(_name) {};
 14     bool operator < (const Person &other) {
 15         return this->height < other.height;
 16     };
 17     
 18     friend ostream& operator << (ostream &cout, const Person &p) {
 19         cout << '<'<< p.name << p.height << '>';
 20         return cout;
 21     };
 22 };
 23 
 24 template <class T>
 25 class BinaryIndexedTree {
 26 public:
 27     BinaryIndexedTree(int _n = 0): n(_n), v(_n + 1) {};
 28     
 29     int size() {
 30         return n;
 31     };
 32     
 33     void addAll(int x, const T &val) {
 34         while (x >= 1 && x <= n) {
 35             v[x] += val;
 36             x -= lowBit(x);
 37         }
 38     };
 39     
 40     void addInterval(int x, int y, const T &val) {
 41         addAll(x - 1, -val);
 42         addAll(y, val);
 43     };
 44     
 45     void clear() {
 46         v.resize(1);
 47         n = 0;
 48     };
 49     
 50     void resize(int new_n) {
 51         v.resize(new_n + 1);
 52         n = new_n;
 53     }
 54     
 55     T sum(int x) {
 56         T res = 0;
 57         while (x >= 1 && x <= n) {
 58             res += v[x];
 59             x += lowBit(x);
 60         }
 61         
 62         return res;
 63     };
 64     
 65     int lowerBound(const T &val) {
 66         int ll, mm, rr;
 67         
 68         if (n == 0) {
 69             return 0;
 70         }
 71 
 72         T res;
 73         if (val <= (res = sum(1))) {
 74             return 1;
 75         }
 76         if (val > (res = sum(n))) {
 77             return n + 1;
 78         }
 79         
 80         ll = 1;
 81         rr = n;
 82         while (rr - ll > 1) {
 83             mm = (ll + rr) / 2;
 84             res = sum(mm);
 85             if (val > res) {
 86                 ll = mm;
 87             } else {
 88                 rr = mm;
 89             }
 90         }
 91         
 92         return rr;
 93     }
 94 private:
 95     vector<T> v;
 96     int n;
 97     
 98     int lowBit(int x) {
 99         return x & -x;
100     };
101 };
102 
103 int main()
104 {
105     vector<Person> people;
106     vector<int> queue;
107     BinaryIndexedTree<int> bit;
108     int i, j;
109     int n;
110     
111     while (cin >> n && n > 0) {
112         people.resize(n);
113         for (i = 0; i < n; ++i) {
114             cin >> people[i].height >> people[i].taller >> people[i].name;
115         }
116         sort(people.begin(), people.end());
117         bit.resize(n);
118         queue.resize(n);
119         for (i = 1; i <= n; ++i) {
120             bit.addInterval(i, n, 1);
121         }
122         for (i = 1; i <= n; ++i) {
123             j = bit.lowerBound(people[i - 1].taller + 1);
124             queue[j - 1] = i;
125             bit.addInterval(j, n, -1);
126         }
127         for (i = 0; i < n; ++i) {
128             cout << people[queue[i] - 1];
129         }
130         cout << endl;
131         
132         people.clear();
133         queue.clear();
134         bit.clear();
135     }
136     
137     return 0;
138 }

https://moonstonelin.wordpress.com/2016/04/22/reconstruct-tree/

public class Node

{

    public Person Person { get; set; }

    public int LeftSelfCount { get; set; }

    public Node Left { get; set; }

    public Node Right { get; set; }

    public Node(Person person, int leftSelfCnt)

{

        this.Person = person;

        this.LeftSelfCount = leftSelfCnt;

        this.Left = null;

        this.Right = null;

}

}

public class Tree

{

    public Node Root { get; set; }

    public Tree()

{

        this.Root = null;

}

    public void Insert(Person p)

{

        if (this.Root == null)

{

            this.Root = new Node(p, 1);

}

        else

{

            if (p.AheadTallerCount < this.Root.LeftSelfCount)

{

                this.Root.LeftSelfCount++;

                InsertHelper(this.Root, this.Root.Left, p);

}

            else

{

                InsertHelper(this.Root, this.Root.Right, p);

}

}

}

    public void InOrder(Node node, List<Node> result)

{

        if (node == null)

{

            return;

}

        InOrder(node.Left, result);

        result.Add(node);

        InOrder(node.Right, result);

}

    private void InsertHelper(Node parent, Node child, Person p)

{

        if (child == null)

{

            if (p.AheadTallerCount < parent.LeftSelfCount)

{

                parent.Left = new Node(p, 1);

}

            else

{

                parent.Right = new Node(p, 1);

}

}

        else

{

            if (p.AheadTallerCount < child.LeftSelfCount)

{

                child.LeftSelfCount++;

                InsertHelper(child, child.Left, p);

}

            else

{

                InsertHelper(child, child.Right, p);

}

}

}

}

    public void TestReConstructTree()

{

        ////<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">

        Person A = new Person("A", 6, 2);

        Person B = new Person("B", 1, 4);

        Person C = new Person("C", 11, 0);

        Person D = new Person("D", 5, 1);

        Person E = new Person("E", 10, 0);

        Person F = new Person("F", 4, 0);

        List<Person> input = new List<Person>() { A, B, C, D, E, F };

        List<Person> result = ReConstructTree(input);

}

    public List<Person> ReConstructTree(List<Person> people)

{

        people.Sort(this.SortByHeight);

        Tree tree = new Tree();

        foreach (Person p in people)

{

            tree.Insert(p);

}

        List<Node> list = new List<Node>();

        tree.InOrder(tree.Root, list);

        List<Person> result = new List<Person>();

        foreach (var n in list)

{

            result.Add(n.Person);

}

        return result;

}

    private int SortByHeight(Person p1, Person p2)

{

        if (p1.Height < p2.Height)

{

            return 1;

}

        else if (p1.Height > p2.Height)

{

            return -1;

}

        else

{

            return 0;

}

}

    public void TestCountSmaller()

{

        int[] nums1 = new int[] { 5, 2, 6, 1 };

        IList<int> result1 = CountSmaller(nums1);

        int[] nums2 = new int[] { 2, 0, 1 };

        IList<int> result2 = CountSmaller(nums2);

}

https://www.careercup.com/question?id=4699414551592960
https://www.careercup.com/question?id=24532662

Related:
https://moonstonelin.wordpress.com/2016/04/02/restruct-queue/
http://www.1point3acres.com/bbs/thread-154493-1-1.html
restruct queue题目意思大概是这样。一群人在一点商店的门口排好队站着，每个人的身高都不同，到中午了，大家都去吃饭，吃完饭之后回来，要求按照之前的顺序排好队，给的信息是每个人的身高和原来队伍中在其前面有多少个比他高的人。这轮本身不是很困难，但是楼主第一轮太紧张了，算法搞定后，在coding的时候卡在了插入的环节，国人姐姐很有耐心也帮助了我不少，最后想想，代码还是有点问题。

第一题可以bst吧，bst按照这个节点的位置排序，先从高到低sort，然后根据f(x)插入，f(x)表示x前面有多少个人比他高，同时每个节点维护当前有多少个节点在其左边，这可以在递归时候返回。

第一高的人是root。第二高的人，f(x)值决定是在root的左边还是右边。第n高的人，f(x)最多为n-1，由于我们已经维护了当前每个节点左边多少个节点，所以就知道插入的位置了。这里key point是，比x高的人是在他之前插入tree的，因为我们是按照从高到底插入tree。

bst最后in order traverse就是返回的结果。

但是因为没有balance，所以结果也不一定好哪里去。

Read full article from Careercup - Google面试题 - 4699414551592960 - zhuli19901106 - 博客园

Careercup - Google面试题 - 4699414551592960 - zhuli19901106 - 博客园

Labels

Popular Posts