Convert from char* to wchar_t*

To Convert char* to wchar_t*

Assume we have a char* string named c

    const size_t cSize = strlen(c)+1;
    wchar_t* wc = new wchar_t[cSize];
    mbstowcs (wc, c, cSize);

Now you have wchar_t* string wc.

You can also refer to http://twnin.blogspot.tw/2012/03/convert-between-char.html for more type to convert.

[C#] Download files from website.

We have two ways to download files from website by using .net framework.

1. WebClient.

using System.Net;

private void button1_Click(object sender, EventArgs e)
{
    WebClient wc = new WebClient();
    wc.DownloadFile("http://www.taifex.com.tw/DailyDownload/Daily_2013_05_24.zip", "d:\\Daily_2013_05_24.zip");
}

2. HttpRequest + Stream

using System.IO;
using System.Net;

private void button1_Click(object sender, EventArgs e)
{
    string url = "http://www.taifex.com.tw/DailyDownload/Daily_2013_05_24.zip";
    HttpWebRequest httpRequest = (HttpWebRequest)WebRequest.Create(url);
    HttpWebResponse httpResponse = (HttpWebResponse)httpRequest.GetResponse();

    System.IO.Stream dataStream = httpResponse.GetResponseStream();
    byte[] buffer = new byte[8192];

    FileStream fs = new FileStream("d:\\Daily_2013_05_24.zip", FileMode.Create, FileAccess.Write);
    int size = 0;
    do
    {
        size = dataStream.Read(buffer, 0, buffer.Length);
        if (size > 0)
            fs.Write(buffer, 0, size);
    } while (size > 0);
    fs.Close();

    httpResponse.Close();

    Console.WriteLine("Done at " + DateTime.Now.ToString("HH:mm:ss.fff"));
}

Reference:
http://blog.darkthread.net/post-2008-10-14-download-file-with-c.aspx

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.