Microsoft面试智力题

1.你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段 ，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？
将金条切成1,2,4
day1：给1
day2：给2，工人归回1
day3：给1
day4：给4，工人归还1，2
day5：给1
day6：给2，工人归回1
day7：给1

2. 请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。
把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分给第8个人。

3.小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？
1. 小明与弟弟过桥，小明回来，耗时4秒；
2. 小明与爸爸过河，弟弟回来，耗时9秒；
3. 妈妈与爷爷过河，小明回来，耗时13秒；
4. 小明与弟弟过河，耗时3秒，总共耗时29秒

4.一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑帽，依此类推，应该是关了几次灯，有几顶黑帽。

5. 烧一根不均匀的绳要用一个小时，如何用它来判断半个小时？如果有两根这样的绳子，如何判断45分钟。
1. 两边一起烧。烧绳子可理解为在单位时间内烧掉的绳子体积是一定的。两头点可理解为燃烧速度增加一倍，自然时间是原来的1/2。
2. 同时点燃其中一根绳子的两头和另一条绳子的一头。第一条燃尽的时候过去了半个小时。同时第二条绳子还能烧半个小时。此时马上点燃第二条绳子的另一头。燃尽时间为15分钟。相加为45分钟。
6. 有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以外30公里每小时的速度和两辆火车现时启动，从洛杉矶出发，碰到另辆车后返回，依次在两辆火车来回的飞行，直道两面辆火车相遇，请问，这只小鸟飞行了多长距离？
假设洛杉矶到纽约的距离为s
那小鸟飞行的距离就是(s/(15+20))*30。

7. U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？
1. 1和2过，1回，耗时3
2. 5和10过，2回，耗时12
3. 1和2过，耗时2。
总耗时17

8. 有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？
方法1:
1. 在天平一端2克砝码，将140克盐分成69和71克
2. 在天平一端7克砝码，将69克盐分成31克和38克
3.不放砝码，将38课盐平分
31+19 = 50 

方法2
1. 先把2克和7克法码放一边,称出9克盐
2. 再把7克法码和9克盐放在一起,称出16克的盐
3. 再把9克盐和16克的盐放在左边,右边再称出25克盐
9+16+25 = 50

9. 你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了
1号罐取1个，2号罐取2个，3号罐取3个，4号罐取4个，称量该10个药丸，比正常重量重几就是几号罐的药有问题。

10. 如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出4夸脱的水？

方法1

1. 加满3，倒入5
2. 加满3，倒入5直至其满，则3中剩1
3. 清空5，将3中的1倒入5
4. 加满3，倒入5，则5中为4

方法2

1. 加满5，倒入3加满

2. 清空3，将5中剩余的2倒入3

3. 加满5，倒入3加满，5中剩余的则为4

11. 你有一桶果冻，其中有黄色，绿色，红色三种，，闭上眼睛选出同样颜色的两个，抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
4个

12. 对一批编号为1~100 全部开关朝上开的灯进行以下操作
凡是1 的倍数反方向拨一次开关2 的倍数反方向又拨一次开关3 的倍数反方向
又拨一次开关。问最后为关熄状态的灯的编号。
就某个亮着的灯而言，如果拨其开关的次数是奇数次，那么，结果它一定是关着的。根据题意可知，号码为N的灯，拨开关的次数等于N的约数（divisor）的个数，约数个数是奇数，则N一定是平方数。因为10的平方等于100，可知100以内共有10个平方数，即，最后关熄状态的灯共有10盏，编号为1、4、9、16、25、36、49、64、81、100。

13. 假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色
。假设你有数量不限的一些颜色传感器。要想确定圆盘转动的方向，你需要在它周
围摆多少个颜色传感器？它们应该被摆放在什么位置？
两个。可随意摆放，只要不同时放在圆的同一条直径上。根据变色顺序判断。

14. 假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分
针共重叠多少次？你知道它们重叠时的具体时间吗？
23或22次(依据算不算24小时候的的12点整）。首先，将12小时划分成12个区间,[12, 1), [1,2)...[11, 12]。每个区间中都有一次相遇的时刻，其中在[12, 1)和[11, 12]相遇的时刻都是12点整。那么完成前半天12个小时就相遇了12次。在后12个小时中，由于起始的12点整已经被计算进入前12次中的一次，则后面只有11次相遇。所以总共23次。若不计算最后的那次12点整，则是22次（题目是一天之中，所以这个时候是第二天的开始）。

由于每次相遇到下一次相遇的时间是一定的，我们知道在12个小时内（包括12个小时)　相遇了12次,　又知道第一次和最后一次分别在这个时间段的起始和结束。那么可将这12个小时等分成11段，每一段的长度就是相遇的时间间隔。那么间隔 interval = 60*12 /11 = 720 / 11分钟。
知道间隔时间以后就可以从12点开始每次加上这个间隔时间算出每次相遇的时刻。

另一种方法是解方程。将时钟的一圈分成60个格子，设相遇时分针相对12点的时刻走了x个格子。我们知道分针每走一格，相当于时针走了1/12格。那么可根据指针重合条件列出方程。

假设我们要求[1, 2)区间内的相遇时刻，则有：
x / 12 = x - 5

类似的我们可以求出[2, 3), [3,4)...[11, 12]区间的相遇时刻([0, 1]和[11, 12]的相遇时刻相同)：
x / 12 = x - 10,
x / 12 = x - 15
...
x / 12 = x

15. 中间只隔一个数字的两个质数被称为质数对，比如17和19。证明质数对之
间的数字总能被6整除（假设这两个质数都大于6），并证明没有由三个质数组成
的质数对。
大于6的质数（prime number, 合数 composite number）都是奇数（只有2是唯一的偶质数）。所以质数对中间的数字一定是偶数，能被2整除（divisible）。由于在大于6的数中，任取三个连续的数字其中有且仅有一个数字能被3整除，而质数对的两个质数肯定不能被3整除（否则不是质数），则中间的那个数必定能被3整除。
一个数既能被2又能被3整除，则它能被6整除。

反证法（Reductio ad absurdum）：设x，x+2是一质数对，假设有连续三个质数组成的质数对，则x2+4或者x-2为质数。那么x-2，x和x+2，x+4是可能的两个质数对。则x-1或x+3应能被6整除。但是，由于x+1能被6整除，则x-1和x+3不可能被6整除。所以不存在三个质数组成的质数对。

16. 一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这 盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。
同时开两盏，过一段时间关闭一盏。进门根据灯泡温度决定刚刚关掉的是哪一盏。

17. 假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将两个球放在天平上对比。最少要称多少次才能找出这个较重的球？
2次。
第一次分别取3个求放在天平两端，若不平横则重球在重的一端的三个球中。若不平衡，第二次任取两球放在天平两端，若不平衡则找到重球，若平横则剩下的一球为重球。
若第一次天平平衡。则重求在剩下的2个球中。第二次称量可直接找到重球。

18. 如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点。
设两桶中红蓝颜料都是1。从红桶中舀去1/k。红桶中还有(k - 1)/k的红，蓝桶中有1的蓝和1/k的红。从蓝桶中舀去1/k。此1/k有(1/k) / (1+1/k) * 1 = 1/(k + 1)的蓝，和1/k - 1/k+1 = 1/(k*(k+1)的红。此时红桶中的红是 (k - 1)/k + 1/(k*(k+1) = k/(k + 1)。蓝桶中的蓝是1 - 1/(k + 1) = k/(k+1)。
比例相同。

递归求square root

设要求根的数为n, 定义f(x) = x^2 - n

应用Newton's Method估算 f(x) = 0 的正数解。首先猜测X[0] (X[0] > 0)为方程的解，之后根据recurrence relation: X[i] = X[i-1] - f(X[i-1]) / f''(X[i-1]) = (X[i-1] + n / X[i-1]) / 2 使X[i]不断逼近准确解。 当误差小于一定范围时，返回当前估算值。

double sqrtRecursive(double n, double guess)
{
     if(abs(guess * guess - n) < 0.00001)
         return guess;
     else
         return sqrtRecursive(n, (guess + n/guess)*0.5);
}

和为n连续正数序列

题目：输入一个正数n，输出所有和为n连续正数序列。不考虑一个数的序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。 

注意： 由于序列至少有两个元素且连续，所以序列起始元素最大不超过(int)(n/2), 结束元素最大不超过(int)(n/2) + 1, 因此无需遍历 1...n-1。

方法1.

使用枚举的方法，两个for循环可以搞定。时间复杂度O(n^2)。

void CountinousSequenceSum_1(int n)
{
    if(n < 3)
        return;

    int sum;

    for(int i = 1; i < n/2 + 1; i++)
    {
        sum = i;
        for(int j = i + 1; j < n/2 + 2; j++)
        {
            sum += j;
            if(sum == n)
            {
                for(int k = i; k < j + 1; k++)
                    cout << k << " ";
                cout << endl;
            }
        }
    }

    return;
} 

方法2.

因为整数序列是有序的，可以设立两个游标small,big，通过判区间[small,big]的和是
否为N来得到这个序列。如果区间和大于n,small往前移动，如果小于 n,big往前移动，等于就输出
这个区间。时间复杂度是0(n)。

void CountinousSequenceSum_2(int n)
{
    if(n < 3)
        return;

    int start = 1, end = 2;
    int sum = start + end;
   
    while(end < n/2 + 2)
    {
        if(sum == n)
        {
            for(int i = start; i < end + 1; i++)
                cout << i << " ";
            cout << endl;
            end++;
            sum += end;
        }
        else if(sum > n)
        {
            sum -= start;
            start++;
        }
        else
        {
            sum += end + 1;
            end++;
        }
    }
}

递归法求字符串的全排列 (permutation)

每次递归调用，解决一个当前元素数量为n-k ( k = 0...n-1)的全排列，为解决当前当前排列,　又需要递归解决n-k个元素数量为n-k-1的全排列

举例：字符串abc, n = 3, []中的元素为需要计算排列的元素集，[]外的元素为已经确定排列顺序的元素

                                   [abc]         
     /             |             \
               a[bc]          b[ac]          c[ba]
              /        |         /        \         |        \
  ab[c]   ac[b]   ba[c]   bc[a]  cb[a]   ca[b]
     |            |            |            |            |            |
  abc       acb       bac       bca     cba      cab

第一层：k = 0，1个全排列需解决，为此需解决3个元素数为2的全排列
第二层：k = 1，3个全排列需解决，解决每个全排列需要解决2个元素数为1的全排列
第三层：k = 2，6个全排列需解决，解决每个全排列需要解决2个元素数为0的全排列（说明当前层已解得所需的所有全排列）
第四层：k = 3， k等于n，到达递归底层，打印当前排列

static void RecursivePermute(char* str,int k)//递归函数

{

     int i;

     if(k==strlen(str))

          printf("%s\n",str);

     else

     {

          for(i=k;i<strlen(str);i++)

          {

               ExchangeCharacters(str,k,i);

               RecursivePermute(str,k+1);

               ExchangeCharacters(str,k,i);

          }

     }

}

static void ExchangeCharacters(char* str, int p1,int p2)

{

     char tmp;

     tmp=str[p1];

     str[p1]=str[p2];

     str[p2]=tmp;

}

<转>线性时间排序算法：Radix Sort

基数排序(Radix Sort) 算法的基本思想是，在待排序列里，分别从低位到高位依次排序，这样最后整个序列就有序了。例如，序列329,57,657,839,436 排序过程是这样的：

3 2 9 0 5 7 6 5 7 8 3 9 4 3 6      ^

=>

4 3 6 0 5 7 6 5 7 3 2 9 8 3 9   ^

=>

3 2 9 4 3 6 8 3 9 0 5 7 6 5 7 ^

=>

0 5 7 3 2 9 4 3 6 6 5 7 8 3 9

这样看似更麻烦了，本来只需要排一次的东西现在要排好几次了，其实，这个主要是为了减轻上面1所讲的技术排序的限制，例如，如果一个序列里的数的范围很大，是2^32或者2^64，那么这个序列就无法用计数排序(Counting Sort)了，但是，如果用基数排序，每一轮用一次计数排序，总得时间复杂度是m*O(n)=O(n)。我们还可以根据内存等条件的具体情况，可以每2位或者3位作为一个单位进行排序。

这个算法要注意的一点是：排序时必须从后往前排，并且各个数字必须对齐。

<转>线性排序算法：Counting Sort

计数排序的限制条件是：所排对象的各个元素都是介于0--k的，并且这个k不是无限的，是在有限的内存里能用数组表示的。

计数排序的基本思想是，当读到一个数时，如果能确定出比这个元素小的数的个数，那这个数应该排的位置自然就知道了。为了实现这个目标，计数排序引入了2个辅助数组，B和C。假设原数组是A，长度为n，数组B的长度也是n；假设每个元素的范围是0--k，那数组C的长度就是k。例如，已知我有一组数 2 5 3 0 2 3 0 3，所有数的范围都在0---5之间，那我们的数组C声明就应该是int C[6];

然后具体做法就是，遍历一遍A，读入一个数，就在对应C的位置+1，例如，读入一个数2，就让 C[2]++，这样，读完一遍以后就知道各个数出现了多少次。然后对C进行整理，得出比这个数小的有多少个(或者将这个数视为该数在排序后序列中应该存放的位置index，比如C[i] = 3,　则有3个数比A[i]小，A[i]应存在b[3]，即排序后的第4个位置上)，整理办法如下：

// assume C[0..k]

for i = 1 .. k do:

    C[i] = C[i-1] + C[i]

最后得出了各个数都有多少个比它小的个数以后，就可以进行最后的排序了：

遍历A，读入一个数x后就去C里找他应该放的位置，即C[x]的值就是他应该放的位置，放入B数组的该位置中，然后对应的C[x]-- (因为考虑到可能有重复的数)。

for i = 0 .. n do:

       x = A[i]

       index = C[x]

       B[index] = x

       C[x]--

cross product (外积)

向量A，B的叉乘结果为C
C = A×B = | i       j        k| = (AyBz - AzBy, AzBx - AxBz, AxBy - AyBx)
                   |Ax   Ay   Az|
                   |Bx   By    Bz|

| C | = | A×B | = | A | | B | sin<A,B>

| C | = 以A,B为其中两条边的quadrilateral的面积

向量的外积不遵守乘法交换
A×B = -B×A

求一个向量在一个平面上的投影向量

设向量为V, 平面normal为N, 其在平面上的投影向量为V'。

Normalize V和N。

v = normlize(V);
n = normaize(N);

计算v和n的夹角cos值，如果是负值则翻转n和cos值，保证所取的normal和V夹角在180以内。

cosVN = dot(v, n);
if(cosVN < 0)
{
     cosVN = -cosVN;
      n = -n;
}

根据V的长度(V_L)和V和N夹角的cos(cosVN) 计算N'长度(N'_L)和N'。N'满足其终点和V终点连线和平面平行。

N'_L = V_L * cosVN';
N' = N'_L * n;

最后算出V'。

V' =  V - N';

点到面的距离公式推导

求点P(x0,y0,z0)到平面Q: Ax + By + Cz + D = 0的距离d。

平面Q的normalized normal为N = (A, B, C) / sqrt(A^2 + B^2 + C^2)。这样，必存在一scalor s,使得点P - sN在平面上(s可正可负)。将P - sN带入平面Q的方程,　求得s = (Ax0 + By0 + Czo + D) / sqrt(A^2 + B^2 + C^2)。

将s取绝对值即为d。

d = | s | = | Ax0 + By0 + Czo + D | / sqrt(A^2 + B^2 + C^2)

最长公共子序列 (LCS = Longest Common Subsequence) 和最长公共子串 (LCS = Longest Common Substring)

两个序列a,b, L[i][j]为以a[i]和b[j]结尾的最长公共子序列的长度。a长度为m, b长度为n

Longest Common Subsequence (子序列无需连续）

Initial condition:
L[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
L[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : max(L[i][j-1], L[i-1][j])    i = 1...m, j = 1...n

最后L[m][n]即为结果

 Longest Common Substring（子串需要连续）

Initial condition:
a[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
a[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : 0   i = 1...m, j = 1...n结果为计算过程中最大的L[i][j] (用一个max变量跟踪）

最长单调递增子序列（LIS）

最长单调递增子 序列，就是在一个数列中最长的按单调递增的顺序排列的序列，该序列在原序列中可以不连续。

解法1:

设b[i]为截止到第i个数且以第i个数为结尾的最长单调递增子序列的长度，a为所给序列，则有：

Initial condittion:
b[0]  = 1
Recurrence relation:

b[ i ] = max( a[i] > a[j] ? b[j] + 1 : 1)    j = 0...i-1

//return value: length of LIS
//aMax: LIS array
//a: original array
//b: b[i] stores the length of the local LIS with the last member a[i]
//p: p[i] stores the previous index of member of the local LIS with the last member a[i]

int LIS(int *a, int *b, int *p, int *aMax, int n)
{
    int max = 0;
    int maxIndex;

    for(int i = 0; i < n; i++)
    {
        b[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[i] > a[j] && b[i] < b[j] + 1)
            {
                b[i] = b[j] + 1;
                p[i] = j;
            }
        }

        if(b[i] > max)
        {
            max = b[i];
            maxIndex = i;
        }
    }

    for(int i = max -1; i > -1;  i--)
    {
        aMax[i] = a[maxIndex];
        maxIndex = p[maxIndex];
    }

    return max;
}

复杂度o(n2)

解法2:

将原序列按升序排序，再对原序列和排序后的序列计算LCS(Longest Common Subsequence）的长度。

排序复杂度o(nlogn), LCS复杂度o(n2), 总复杂度o(n2)

最长连续数字序列， 计数并输出

 int longestNumString(char *string, char *output)
{
    int count = 0;
    int max = 0;
    char *start;
    char *startMax;

    while(true)
    {
        if(*string >= '0' && *string <= '9')
            start = string;

        while(*string >= '0' && *string <= '9' && *string)
        {
            string++;
            count++;
        }

        if(count > max)
        {
            max = count;
            startMax = start;
        }

        count = 0;

        if(*string)
            string++;
        else
            break;
    }

    for(int i = 0; i < max; i++)
    {
        *output = *startMax;
        startMax++;
        output++;
    }

    return max;
}

<转>基类和派生类的构造函数

1. 顺序
      当创建一个派生类的对象时，系统首先自动创建一个基类对象，也就是说，在调用派生类构造函数创建派生类对象之前，系 统首先调用基类的构造函数创建基类对象。当派生类对象生命期结束时，首先调用派生类的析构函数，然后调用基类的析构函数。简而言之，就是说，构造函数：基 类->派生类。析构函数：派生类->基类。
这个我们完全可以通过一个小程序来说明：

//通过输出就可以看出在创建派生类对象b1时各个函数的调用顺序了
#include <iostream>
using namespace std;
class A
{
public:
    A()
    {
        cout<<"A(Based Class) constructor is called"<<endl;
    }
    ~A()
    {
        cout<<"A(Based Class) destructor is called"<<endl;
    }
};
class B:public A
{
public:
    B()
    {
        cout<<"B(Derived Class) constructor is called"<<endl;
    }
    ~B()
    {
        cout<<"B(Derived Class) destructor is called"<<endl;
    }
};

int main()
{
    B b1;
    return 0;
}

OutPut：



2. 通过派生类的构造函数调用基类的构造函数有两种方式，隐式和显式两种。所谓隐式方式就是在派生类的构造函数中不指定对应的基类的构造函数，这个时候调用的 是基类的默认构造函数(即含有默认参数值或不带参数的构造函数)。而所 谓显式方式，就是在派生类的构造函数中指定要调用的基类的构造函数，并将派生类构造函数的部分参数值传递给基类构造函数。注：除非基类有默认的构造函数， 否则必须采用显式调用方式。
下面分别给出一个隐式和显式调用的例子：

#include <iostream>
using namespace std;

class A
{
public:
    A(int x = 0,int y = 0)
    {
        a = x;
        b = y;
    }
private:
    int a;
    int b;
};
//基类A有默认的构造函数，可以隐式调用
class B:public A
{
public:
    B(int z = 0)
    {
        c = z;
    }
private:
    int c;
};

int main()
{
    B b1;
    return 0;
}

显式调用的例子：

#include <iostream>
using namespace std;

class A
{
public:
    A(int x,int y)
    {
        a = x;
        b = y;
    }
private:
    int a;
    int b;
};
//基类A没有默认的构造函数，其现有的构造函数需要传递参数，通过
//派生类构造函数调用A构造函数时必须如下显式调用
class B:public A
{
public:
    B(int x,int y,int z):A(x,y)
    {
        c = z;
    }
private:
    int c;
};

int main()
{
    B b1(1,2,3);
    return 0;
}