N Coin Problem

Question:
Given a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S' (you can use as many coins you want). If it's not possible to sum to 'S', return -1

For Example, input N coins array { 1, 3, 5 } and S as 11, the answer should be 3


My Answer:  (I am not sure if it is correct.)

int minCoins(int* a, int count, int target)
{
    int N = count;
    int S = target;

    int *mina=NULL;
    mina = new int[S+1];
 
    mina[0]=0;
     
    for(int i=1;i<=S;i++)
    {
        mina[i]=-1;
 
        for(int j=0;j<N;j++)
        {
            if(a[j]<=i && mina[i-a[j]] != -1)  
            {
                if(mina[i]==-1 || mina[i-a[j]]+1 < mina[i])
                {
                   mina[i] = mina[i-a[j]]+1;
                }
            }
        }
    }
 
    return mina[S];
}

Circle sorted array searching.

Question:
Given a circle sorted array, please write a function to search a number and output its position.

Example:
Find number 6 in array { 1,2,3,4,5,6,7 }, output is 5
Find number 6 in array { 5,6,7,1,2,3,4 }, output is 1

My Answer:  (I am no sure if it is correct.)

#include "stdafx.h"
#include 

using namespace std;

int binarySearch(int n, int* a, int l, int r);

int _tmain(int argc, _TCHAR* argv[])
{
 int a[7] = { 4, 5, 6, 7, 1, 2, 3 };
 
 cout << binarySearch(6, a, 0, 6) << endl;
 cout << binarySearch(2, a, 0, 6) << endl;
 cout << binarySearch(5, a, 0, 6) << endl;

 cin.get();
 return 0;
}

int binarySearch(int n, int* a, int l, int r)
{
 int i = (l + r) / 2;
 if (n == a[i])
  return i;

 if (a[l] < a[r])
 {
  if (n > a[i])
  {
   l += 1;
  }
  else
  {
   r = i - 1;
  }
 }
 else
 {
  if (n > a[i] || n < a[l])
  {
   l += 1;
  }
  else
  {
   r = i - 1;
  }
 }

 return binarySearch(n, a, l, r);
}

Number Complement.

Question: 
A complement of a number is defined as inversion (if the bit value = 0, change it to 1 and vice-versa) of all bits of the number starting from the leftmost bit that is set to 1. 

For example, if N = 5, N is 101 in binary. The complement of N is 010, which is 2 in decimal. Similarly if N = 50, then complement of N is 13 
Complete the function getIntegerComplement(). This function takes N as it's parameter. The function should return the complement of N.  (The N >=0)


My Answer:  (I am not sure if it is correct.)

int getComplement(int n)
{
    if (n == 0)
        return 1;

    int b = 0;
    int a = n;
    while (a > 0)
    {
        a >>= 1;
        b++;
    };

    int mask = pow(2.0, b) - 1;
    int result = n ^ mask;
    return result;
}

Get Nth power of number.

Question:
Given two integer a and b (b >= 0), please write a function to return the result of "a to the power of b".

My Anwser: (I am no sure if it is correct.)
The easiest way is recursively multiply integer a.

int power(int a, int b)
{
    if (b <= 0)
        return 1;

    return a * power(a, b-1);
}

Question:
Improve time complexity to log(n)

My Anwser: (I am no sure if it is correct.)
Consider a to the power of 15 is power(a, 8) * power(a, 4) * power(a, 2) * power(a, 1) * power(a, 0)

#include "stdafx.h"
#include 

using namespace std;

int getPower(int a, int b);
int power(int a, int b);

int _tmain(int argc, _TCHAR* argv[])
{
    int a = 2, b = 15;
 
    cout << power(a, b) << endl;

    cin.get();
    return 0;
}

int getPower(int a, int logb)
{
    if (logb <= 0)
        return 1;

    return a * getPower(a*a, logb-1);
}

int power(int a, int b)
{
    if (b == 0)
        return 1;

    int logb = 0;
    while(b>0)
    {
        logb++;
        b >>= 1;
    }

    return getPower(a, logb);
}

Fibonacci Factor Problem

Story

Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. 

Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.

Input Format  

First line of the input contains an integer T, the number of testcases.

Then follows T lines, each containing an integer K.

Output Format

Output T lines, each containing the required answer for each corresponding testcase.

Sample Input 

3

3

5

161

Sample Output

3 3

5 5

21 7

Explanation 

There are three testcases. The first test case is 3, the smallest required fibonacci number  3. The second testcase is 5 and the third is 161. For 161 the smallest fibonacci numer sharing a common divisor with it is 21 and the smallest number other than 1 dividing 161 and 7 is 7.

Constraints :

1 <= T <= 5

2 <= K <= 1000,000

The required fibonacci number is guranteed to be less than 10^18.

My Answer: (I am no sure if it is correct.)

#include "stdafx.h"
#include <iostream>

using namespace std;

int fb(int i);

int _tmain(int argc, _TCHAR* argv[])
{
 int count = 0;
 cin >> count;
 int *input = new int[count];
 for (int i = 0; i<count; i++)
 {
  cin >> input[i];
 }

 for (int i = 0; i<count; i++)
 {
  int k = 1;
  int fbNumber = 1;
  while (fbNumber <= input[i]) 
  {
   for (int x=2; x<=fbNumber; x++)
   {
    if (fbNumber % x == 0 && input[i] % x == 0 )
    {
     cout << input[i] << " " << fbNumber << endl;
    }
   }

   k++;
   fbNumber = fb(k);
  };
 }

 return 0;
}

int fb(int i)
{
 if (i<=1)
  return 1;

 if (i==2)
  return fb(1);

 return fb(i-1) + fb(i-2);
}

Reference:
https://amazon.interviewstreet.com/challenges/dashboard/#problem/4fd653336df28

Candies giving problem

Story

Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.

Input

The first line of the input is an integer N, the number of children in Alice's class. Each of the followingN lines contains an integer indicates the rating of each child.

Output

On the only line of the output print an integer describing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Output

4













My Answer (I am no sure if it is correct.)

#include "stdafx.h"
#include <iostream;

using namespace std;

class child {
public:
    child() : m_candy(1) {}
    child(int rating) : m_rating(rating), m_candy(1) {}

    int Rating() { return m_rating; }
    void setRating(int rate) { m_rating = rate; }
    int Candy() { return m_candy; }
    void setCandy(int candies) { m_candy = candies; }

private:
    int m_rating;
    int m_candy;
};

void showCandies(int[], int);

int _tmain(int argc, _TCHAR* argv[])
{
    const int count = 10;
    int childs_rating[] = {9,2,3,3,3,2,1,1,3,4};

    showCandies(childs_rating, count);

    cin.get();
 return 0;
}

void showCandies(int* rating, int count)
{
    child* childs = new child[count];
    for(int i=0;i<count;i++)
    {
        childs[i].setRating(rating[i]);
    }

    bool run = false;
    do
    {
        run = false;

        for(int i=0;i<count-1;i++)
        {
            if( childs[i].Rating() ; childs[i+1].Rating() && childs[i].Candy() <= childs[i+1].Candy())
            {
                run = true;
                childs[i].setCandy(childs[i+1].Candy() + 1);
            }

            if( childs[i+1].Rating() ; childs[i].Rating() && childs[i+1].Candy() <= childs[i].Candy())
            {
                run = true;
                childs[i+1].setCandy(childs[i].Candy() + 1);
            }
        }

        for(int i=0;i<count;i++)
        {
            cout << childs[i].Candy() << '\t';
        }
        cout << endl;
    } while(run);

    delete[] childs;
}

Reference:
http://stackoverflow.com/questions/11292913/candies-interviewstreet

How to sum the Integers from 1 to N.

Question:
How to sum the Integers from 1 to N.

Answer:

#include "stdafx.h"
#include 

using namespace std;

int allPlus(int n);

int _tmain(int argc, _TCHAR* argv[])
{
    const int n = 100;
    int sum = allPlus(n);

    cout << sum << endl;

    std::cin.get();
 return 0;
}

int allPlus(int n)
{
    if (n == 0)
        return 0;

    return n + allPlus(n-1);
}

Advanced Answer:
Change function allPlus below for O(1) time complexity

int allPlus(int n)
{
    return (1 + n) * n / 2;
}

* All answer just my answer, I am no sure if it is correct.

Find duplicated numbers in an array.

Question:
Given an array with N+M items, each item is number between 1 to N, please give a O(M+N) solution to print all duplicated numbers.

Answer:

#include "stdafx.h"
#include 

using namespace std;

void printDuplicate(int arr[], int nm, int n);

int _tmain(int argc, _TCHAR* argv[])
{
    const int n = 10, m = 5;
    const int nm = n+m;
    int arr[nm] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,2};

    printDuplicate(arr, nm, n);

    std::cin.get();
    return 0;
}

void printDuplicate(int arr[], int nm, int n)
{
    int* pArray = new int[n];
    for (int i=0; i<n; i++)
    {
        pArray[i] = 0;
    }

    for (int i=0; i<nm; i++)
    {
        int value = arr[i];
        pArray[value]++;

        if (pArray[value] == 2)
            cout << value << endl;
    }
}

Advanced Question:
Give an answer without using extra space.

Answer:
Change function printDumplicate as below.

void printDuplicate(int arr[], int nm, int n)
{
    int pArray = 0;

    for (int i=0; i 0)
            cout << value << endl;

        pArray |= (1 << (value-1));
    }
}

Thinking:
If you use bits of an integer variable to keep all status, remember that there are 32 bits only.


* All answer just my answer, not the best one.

How to swap two variables without using a temporary variable.

Question:
How to swap two variables without using a temporary variable.


Anser:
There are 3 methods to tackle this issue.

1. XOR

a = a ^ b;
b = a ^ b;
a = a ^ b;

2. Addition and Minus

a = a + b;
b = a - b;
a = a - b;

3. Multiplying and Division

a = a * b;
b = a / b;
a = a / b;

Thinking:
It is possible overflow if you use method 2 and 3.

Why method 1 work? Because N ^ N = 0 and N ^ 0 = N, so you can think

a' = a ^ b;
b' = a' ^ b 
   = a ^ b ^ b 
   = a ^ 0 
   = a;
a'' = a' ^ b' 
    = a ^ b ^ a 
    = 0 ^ b 
    = b;

Reference:
http://emn178.pixnet.net/blog/post/92113175
http://emn178.pixnet.net/blog/post/92389195-%E9%9D%A2%E8%A9%A6%E5%B8%B8%E8%A6%8B%E7%A8%8B%E5%BC%8F%E8%80%83%E9%A1%8C-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E5%81%9A

[C++] Sample for Using stdlib to implement Extend Quick Sort function

As last example, I use standard library to implement quick sort again.

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

void quickSortEx(int[], int, bool, int, int);
int cmp(const void* a, const void* b);

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));
    const int count = 10;
    int number[count] = {0};

    printf("Before: ");
    int i;
    for(i = 0; i < count; i++) {
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }
    printf("\n");

    quickSortEx(number, count, true, 0, count-1);

    printf("Afer: ");
    for(i = 0; i < count; i++)
        printf("%d ", number[i]);

    printf("\n");
    return 0;
}

void quickSortEx(int number[], int count, bool desc, int left, int right)
{
    qsort(number, count, sizeof(number[0]), cmp);

    if (desc)
        std::reverse(number, number+count);
}

int cmp(const void* a, const void* b)
{
    const int x = *static_cast<const int*>(a);
    const int y = *static_cast<const int*>(b);

    if (x == y)
        return 0;

    return x > y ? 1 : -1;
}

Reference:
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/
http://www.cplusplus.com/reference/algorithm/reverse/

[C++] A sample for Extended Quick Sort

I need to implement a function to sort items with specified ascending order.
I modify other's sample as below.

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quickSortEx(int[], int, bool, int, int);
void swap(int &x, int &y);

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));
    const int count = 10;
    int number[count] = {0};
 
    printf("Before: ");
    int i;
    for(i = 0; i < count; i++) {
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }
    printf("\n");

    quickSortEx(number, count, false, 0, count-1);

    printf("Afer: ");
    for(i = 0; i < count; i++)
        printf("%d ", number[i]);
 
    printf("\n");
    return 0;
}

void quickSortEx(int number[], int count, bool desc, int left, int right) {
    if(left < right) {
        int i = left;
        int j = right + 1;

        while(1) {
            // To find the item should sort after 'left'
            while(i + 1 < count && (desc ? number[left] < number[++i] : number[++i] < number[left]));
            // To find the item should sort before 'left'
            while(j -1 > -1 && (desc ? number[left] > number[--j] : number[--j] > number[left])) ;
            if(i >= j)
                break;
            swap(number[i], number[j]);
        }

        swap(number[left], number[j]);

        quickSortEx(number, count, desc, left, j-1);
        quickSortEx(number, count, desc, j+1, right);
    }
}

void swap(int &x, int &y)
{
    int temp;
    temp = x;
    x = y;
    y = temp;
}

Reference:
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/QuickSort1.htm
http://emn178.pixnet.net/blog/post/88613503-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95(quick-sort)

[C++] Sample for String Compare

It is a simple sample for understanding how to implement a function to compare two string.

#include "stdafx.h"
#include <string.h>
#include <iostream>

using namespace std;

int codePointCompare(const char* c1, const char* c2)
{
 int l1 = strlen(c1);
 int l2 = strlen(c2);
        const unsigned lmin = l1 < l2 ? l1 : l2;
        unsigned pos = 0;
        while (pos < lmin && *c1 == *c2)
 {
             c1++;
             c2++;
             pos++;
        }

        if (pos < lmin)
             return (c1[0] > c2[0]) ? 1 : -1;

        if (l1 == l2)
             return 0;

 return (l1 > l2) ? 1 : -1;
}

int _tmain(int argc, _TCHAR* argv[])
{
 char* c1 = new char[1024];
 char* c2 = new char[1024];
 cout << "please input first string:";
 cin >> c1;
 cout << "please input second string:";
 cin >> c2;

 cout << codePointCompare(c1, c2);
 return 0;
}

Reference:
http://trac.webkit.org/changeset/110822/trunk/Source/JavaScriptCore/wtf/text/StringImpl.cpp

假鈔問題

Question：
有個商品賣30元，成本25元，客人用100元紙鈔跟商人買了商品，商人沒錢找所以拿了這張紙鈔去跟隔壁攤販換零錢找給客人，後來隔壁攤販跑來說那是假鈔，所以商人又賠了100元給隔壁攤販，試問商人總共虧多少錢?









Answer：
可以把買賣與鈔票交換分開來看
商人給了客人25元的商品，然後拿70元給客人，損失95元。
商人從客人收了100元的假鈔，去換成100元真鈔，然後又把真鈔歸還，損失0元。
因此總共損失 95元。

換個方式思考
商人原本有25元，買了25的東西來賣給客人，商人剩下 0元
商人拿了 100元的假鈔，然後去跟隔壁攤販拿了100元，商人身上剩下100元
商人找了70元給客人，商人身上剩下30元
商人把還了100元給隔壁攤泛，商人身上剩下 -70元
因此，原本有25元減去剩下-70元，商人共損失95元



reference: realtek

喊數字遊戲

Question：
如果兩個人比賽，從1數到100，喊到100的人獲勝，每一次最少喊一個數，最多喊七個數，先攻的人喊到幾時便保證必勝？
                                                                             









Answer：                                                                        
如果自己要喊100，對方必須只能喊99~93，
        自己要喊  92，對方必須只能喊91~85，
        ...........................
        自己要喊  12，對方必須只能喊11~  5，
        自己要喊    4

因此只要先喊到4，則先喊的人必獲勝
往後原則就是喊 [8-對方喊幾次]

例如 A喊4
         B喊1次到5
         A喊(8-1=7次)到12
         直到A喊到92時，B不管怎樣都不會贏



reference: realtek

九顆球秤重

 Question:
有九顆看起來一模一樣的球 ，但是有一顆不一樣重，也不知道它是比較輕還比較重，用一個天秤最少要量幾次可以"確保"找出這顆球?
                                                                             









Answer:
3次。
                                                                             
第一次
拿六顆球放在天秤上，假設有一邊比較重，那麼就能知道，不一樣重的球是這六顆其中之一

                             |O_O_O     (假設右邊有一顆比較輕的球) [也可能左邊是重球1個]
                O_O_O|                  (下一輪把右邊三顆換成最後三顆)
                                                                             
第二次
換掉輕的三顆，拿另外三顆上來量，如果天秤平衡了，就能知道不一樣重的球是剛剛被換掉的三顆其中之一

                 O_O_O|O_O_O     (確認假設正確，第一次的右邊果然有輕球)
                                                 [因為如果左邊有重球那第二次比還是要左邊天秤較重]
                                                                             
第三次    
拿另外三顆的其中兩顆來量，如果平衡了，那麼第三顆就是輕的球

                           O|O              (都知道有輕球了，平衡就是第三個是輕的)


衍生問題，如果已知不一樣重的球是比較輕的，那就只需要兩次了。



reference: realtek