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.

# Tag Archives: find

# Interview Practice 28 – Counting One in Binary Expression

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

# Interview Practice 25 – Longest Consecutive Digits

### 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); }

# Interview Practice 21 – Summing Combinations

### 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); } }

# Interview Pizzle 1 – Find the Heavier Marble

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

# Interview Practice 18 – Last Surviving Number in Loop

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; }

# Interview Practice 17 – Find The String Appeared Once

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 ///////////////////////////////////////////