## Thursday, June 9, 2016

### 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`

```  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) {
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) {
121         }
122         for (i = 1; i <= n; ++i) {
123             j = bit.lowerBound(people[i - 1].taller + 1);
124             queue[j - 1] = i;
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 p``1``, Person p``2``)`
`    ``{`
`        ``if (p``1``.Height < p``2``.Height)`
`        ``{`
`            ``return ``1``;`
`        ``}`
`        ``else if (p``1``.Height > p``2``.Height)`
`        ``{`
`            ``return ``-1``;`
`        ``}`
`        ``else`
`        ``{`
`            ``return ``0``;`
`        ``}`
`    ``}`
`    ``public void TestCountSmaller()`
`    ``{`
`        ``int[] nums``1` `= new int[] { ``5``, ``2``, ``6``, ``1` `};`
`        ``IList<int> result``1` `= CountSmaller(nums``1``);`
`        ``int[] nums``2` `= new int[] { ``2``, ``0``, ``1` `};`
`        ``IList<int> result``2` `= CountSmaller(nums``2``);`
`    ``}`
https://www.careercup.com/question?id=4699414551592960
https://www.careercup.com/question?id=24532662

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

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