Archive

Tag Archives: find

Snapsack problem refers to the situation you want to find a combination of items that can fill up a container. Each items should be attached with a value, and there should be a target value that means a container is filled up. For example, a container has 25 spaces and there are items that will take 1, 5, 7, 6, 4 or 10 spaces. You have to find all the combinations that fit the container.

Question

Given a number, find the number of 1 in the number’s binary expression. For example, binary express of 10 is 1010. So the number of 1 in it is 2.

Solution

To solve this, we can check each bit by shifting the bits one by one.

1. 1010 -> check 0
2. 101 -> check 1
3. 10 -> check 0
4. 1 -> check 1

So how to check it? we could use the AND function.

1. 1010 -> check 1010 & 1 = 0
2. 101 -> check 101 & 1 = 1 -> counter + 1
3. 10 -> check 10 & 1 = 0
4. 1 -> check 1 & 1 = 1 -> counter + 1

However, negative number will put this program into infinite loop. For example, shifting -10 (0xFFFFFFF6) several times gives 0xFFFFFFFF. Then shifting 0xFFFFFFFF will give 0xFFFFFFFF and makes infinite loops. Therefore instead of shifting the inputting number, we should shift the comparing number.

1. 1010 -> check 1010 & 1 = 0
2. 1010-> check 1010 & 10 = 1 -> counter + 1
3. 1010 -> check 1010 & 100 = 0
4. 1010 -> check 1010 & 1000 = 1 -> counter + 1

Sample

Question

Given a function prototype: int continumax(char *output_string,char *input_string). Implement it to find the longest consecutive digits. This function must return the length of the longest digits. The found longest digits should be written to the memory location that output_string is pointing. For example, if input_string is “abcd12345ed125ss123456789”, function returns 9 and output_string becomes “123456789”.

Solution

This question must be implemented in C/C++. Just skip letters, count the length and save the head position to a temp pointer.

Sample

#include <iostream>

int continumax(char *output_string, char *input_string)
{
	int max_length = 0;
	char *max_string = new char[sizeof(input_string)];

	while (true) {

		// skip all non-digit characters
		while (*input_string != 0 && (*input_string < '0' || *input_string > '9')) input_string++;
		if (*input_string == 0) break;

		// current char is digit
		int length = 0;
		char *temp_string = input_string;
		while (*input_string!=0 && *input_string >= '0' && *input_string <= '9') {
			length++;
			input_string++;
		}

		// check if this is longer
		if (length > max_length) {
			max_length = length;
			max_string = temp_string;
		}
	}

	// write maximum string to output and add null to end.
	int i;
	for (i = 0; i < max_length; i++) output_string[i] = max_string[i];
	output_string[i] = 0;

	return max_length;
}

int main()
{
	char input[] = "abcd12345ed125ss123456789";
	char *output = new char[sizeof(input)];
	int length = continumax(output, input);
	printf("Length: %dn", length);
	printf("Output: %sn", output);
}

Question

Given a integers m and n, generate all combination within 1 to n that would give the sum m. For example, for m=5 and n=5, the combinations are {5}, {4+1}, {3+2}.

Solution

This is a knapsack problem.

# knapsack that store the found combination
knapsack = array

# find combination of 1..n with sum target
find_combination(target, n)
    if target <= 0 or n <= 0 then return
    if target == n then found()

    # put n to knapsack, find combination involves n
    push n to knapsack
    remain = target - n
    find_combination(remain, n-1)

    # remove n from knapsack, find combination involves n-1
    pop knapsack
    find combination(target, n-1)

Sample

# knapsack that store the found combination
knapsack = []

# what to do with found combination in knapsack
def found(n):
    for number in knapsack: print "%d +" % number,
    print n

# find combination
def find_combination(target, n):
    if n <= 0 or target <= 0: return
    if n == target: found(n)

    # find combinations with n
    knapsack.append(n)
    find_combination(target - n, n - 1)

    # find combinations without n
    knapsack.pop()
    find_combination(target, n - 1)

# find combination of 25 with 1..20
find_combination(25, 20)
#include <iostream>
#include <list>
using namespace std;

list<int> knapsack;

void found(int n)
{
	// reverse print
	for (list<int>::const_iterator item = knapsack.begin(); item != knapsack.end(); item++)
		printf("%d + ", *item);
	printf("%dn", n);
}

void find_combination(int target, int n)
{
	if (n <= 0 || target <= 0) return;
	if (n == target) found(n);
	knapsack.push_back(n);
	find_combination(target - n, n - 1);
	knapsack.pop_back();
	find_combination(target, n - 1);
}

int main()
{
	find_combination(25, 20);
}
import java.util.Stack;

public class InterviewPractice21
{
	private static Stack<Integer> snapsack = new Stack<Integer>();

	private static void found(int n)
	{
		for (int item : snapsack) System.out.printf("%d + ", item);
		System.out.printf("%dn", n);
	}

	private static void find_combination(int target, int n)
	{
		if (target <= 0 || n <= 0) return;
		if (n == target) found(n);
		snapsack.push(n);
		find_combination(target - n, n - 1);
		snapsack.pop();
		find_combination(target, n - 1);
	}

	public static void main(String[] args)
	{
		find_combination(25, 20);
	}
}

Question

You have 9 marbles. 8 marbles weigh 1 ounce each, & one marble weighs 1.5 ounces. You are unable to determine which is the heavier marble by looking at them. You have a weighing scale that consists of 2 pans, but the scale is only good for 2 total weighings. How can you determine which marble is the heaviest one using the scale & in 2 weighings?

Solution

1. Divide 9 marbles into 3 groups of 3 marbles each.

2. Take any 2 groups and place them on each pan. If they balance, remove the marbles from the pans, & place any 2 of the marbles from the remaining un-weighed group on the pans, 1 on each pan.

2.1. If one is heavier, it is the heavier marble, but if they balance, the remaining un-weighed marble is the heavier one.

2.2. If your first weighing does not balance, the heavier pan has the heavy marble.

3. Remove the marbles from the lighter pan, & place 1 marble on each pan from the heavier pan.

3.1. The heavier 1 is the 1.5 ounce marble.

3.2. But if they balance, then the marble from the heavy pan from the first weighing that was not weighed in the second weighing is the heavy one.

Consider

Consider there is a list containing N numbers, and which formed a ring. That is, item n+1 is item 1. Construct an algorithm such that it traverses through the ring, and remove the Mth item. Repeat this process until there is only one number left in the ring and then output this number. For example, in the list {10, 11, 12}, and the remove the 3th item in every loop. Then in the first loop, 12 will be removed, followed by 10. Therefore the last surviving number is 11.

Solution

In python, it’s easy because it has build-in function to resize an array. We can construct an array, then pop the Kth item in every loop, where K = M mod Length of List.

Example

# last in list
def last_remain_number_in_list(list, m):
    length = len(list)
    while len(list) > 1:
        index = m % len(list)
        list.pop(index)
    return list.pop()

# main, answer is 5
list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print last_remain_number_in_list(list, 8)
#include <stdio.h>

int main()
{
    int i,k,m,n,num[50],*p;
    printf("input number of person:n=");
    scanf("%d",&n);

    printf("input number of the quit:m=");   //留下->18题
    scanf("%d",&m);                          //留下->18题

       p=num;
    for(i=0;i<n;i++)
        *(p+i)=i+1;    //给每个人编号
    i=0;   //报数
    k=0;   //此处为3
//    m=0;   //m为退出人数                     //去掉->18题
    while(m<n-1)
    {
        if(*(p+i)!=0)
            k++;
        if(k==3)
        {
            *(p+i)=0;    //退出,对应的数组元素置为0
            k=0;
            m++;
        }
        i++;
        if(i==n)
            i=0;
    }
    while(*p==0)
        p++;
    printf("The last one is NO.%d/n",*p);
}
int LastRemaining_Solution2(int n, unsigned int m)
{
      // invalid input
      if(n <= 0 || m < 0)
            return -1;

      // if there are only one integer in the circle initially,
      // of course the last remaining one is 0
      int lastinteger = 0;

      // find the last remaining one in the circle with n integers
      for (int i = 2; i <= n; i ++)
            lastinteger = (lastinteger + m) % i;

      return lastinteger;
}

Question

Given a string, write an algorithm to find the character inside that appeared only once. For example, the result for string “abaccdeff” is b.

Solution

We can use a hashtable to count the appearance times for each character. Then rescan the hashtable for the character that appeared only once. These two step take O(n) each, therefore the overall time complexity is O(n).

# function to find char appeared once
def find_appeared_once(string):
    hashtable = {} # a hashtable

    # loop for each char in string
    for char in string:
        if char not in hashtable:
            hashtable[char] = 1
        else:
            hashtable[char] += 1

    # find the item appeared only once
    for char, count in hashtable.items():
        if count == 1:
            return char

# main
print find_appeared_once('abaccdeff')

 

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

char FirstNotRepeatingChar(char* pString)
{
      if(!pString)
            return 0;

      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      char* pHashKey = pString;
      while(*(pHashKey) != '/0')
            hashTable[*(pHashKey++)] ++;

      pHashKey = pString;
      while(*pHashKey != '/0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }

      return *pHashKey;
}

int main()
{
    cout<<"请输入一串字符:"<<endl;
    char s[100];
    cin>>s;
    char* ps=s;
    cout<<FirstNotRepeatingChar(ps)<<endl;
    return 0;
}

//////////////////////////////////////////
请输入一串字符:
abaccdeff
b
Press any key to continue
///////////////////////////////////////////

 

 

%d bloggers like this: