1. Exchanging values with xor
Here’s some weird code I ran across once. It uses xor to exchange two values (x and y). Never use it; this is just a curiosity from the museum of bizarre code.
x = x ^ y; y = x ^ y; x = x ^ y;
2. Multiple a number by 7 without using * and + operator.
NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8
NewNum = NewNum – Num; // 8 – 1 = 7
3. print integer using only putchar
//
// recursive version
//
void PrintNum ( int Num )
{
if ( Num == 0 )
return;
PrintNum ( Num / 10 );
Puthcar ( ‘0’+ Num % 10 );
}
4. Counting set bits in a number.
First version:
int CoutSetBits(int Num)
{
for(int count=0; Num; Num >>= 1)
{
if (Num & 1) count++;
}
return count;
}
5. notions
Big O notation is used for Asymptotic(an sem ‘totic) upper bound
θ notation is used for tight bound
Ω notation is used for Asymptotic lower bound
6. Given an array of integers or other numbers (reals, doubles, etc), tell us if any two of the numbers in the array sum up to another given number.
There’s an n2 solution in which you compute all the possible pairs of numbers and then add them together to test the termination condition. Obviously, this is less than ideal. However, it is well known that integers can be sorted in O(n) time, where n is the number of integers to sort. Therefore, I proposed this additional precondition:
Allow the list of integers to be sorted in natural order before calling this method
The algorithm then is quite simple: keep an index at the far left side, and the far right side. If the indices become equal, or cross, we’ve failed to find a pair that works. To try to exhaustively find a matching pair, we try adding the numbers at our indices. If the sum too big, we decrement the right index. If the sum is too small, we increment the left index. If the sum is equal to what we’re looking for, we can return true. Pseudocode resembling Java might look like this:
public boolean inArr(int [] arr, int sought) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int test = arr[left] + arr[right] - sought;
if(test > 0) {
right–;
} else if(test < 0) {
left++;
} else {
return true;
}
}
return false;
}
good solution
http://blog.kirupa.com/?p=20
Let’s take some values as an example:
array = { 1, 12, 10, 4, 5, 7};
sumvalue = 16;
The array is my list of numbers, and number is the sum I am trying to find two numbers in the array to add up to.
So, I am going to scan through each element in the array and add the value at array[i] to my dictionary (hashtable). The Key is the number at i itself – array[i], and the Value is the difference, sumvalue – array[i]:
This is because the array[i] where i is 0 is 1, and that is our key, but I do check to make sure that the key doesn’t already exist in our hashtable first. Next, the difference between the value we seek and this number is 16 -1 = 15. This number becomes our value. Finally, I check whether the hashtable contains 15 as its key. It doesn’t, so I continue repeating this process of:
- Checking if array[i] key exists in our hashtable.
- If the key does not exist in our hashtable:
- Add the key to the hashtable
- The value mapped with this key is the difference between the sumvalue and array[i].
- Check if the difference between sumvalue and array[i] exists as a key in our hashtable.
- Continue loop if the difference value does not exist as a key.
Notice that all of this is done in linear time – Ɵ(n).
if (x && !(x & (x-1)) == 0)
(a-1) xor a == 0 – What does this do?
a is a power of 2.
The answer is “many points”. The set of such points is given as {North pole, special circle}.
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
Take one pill from first, two from second, three from third and so on. Total pills are n(n+1)/2 and should weigh 10n(n+1)/2. If it weighs x gm less than that then the x’th jar is contaminated, since we took x pills from that jar which weighed 1 gm less.
Let the balls be numbered 1 to 12. Firstly, put 1-4 on one side and 5-8 on other side. If both are equal then one of 9-12 is odd. Then second try, weigh 9-10 vs 1-2, if equal, one of 11-12 is bad, else 9-10 is bad. Testing which one is bad can be done by (third try) weighing 11 or 9, respectively, with good ball 1. It also gives whether the odd ball is heavy or light.
int main()
{
int a[10]={1, 2, 4, 4, 7, 8, 9, 14, 14, 20};
int i;
for (i = 0;i<9;i++)
{
if (a[i] != a[i+1])
printf("%d\n",a[i]);
}
return 0;
}
Write an algorithm to detect loop in a linked list.
You are presented with a linked list, which may have a “loop” in it. That is, an element of the linked list may incorrectly point to a previously encountered element, which can cause an infinite loop when traversing the list. Devise an algorithm to detect whether a loop exists in a linked list. How does your answer change if you cannot change the structure of the list elements?
One possible answer is to add a flag to each element of the list. You could then traverse the list, starting at the head and tagging each element as you encounter it. If you ever encountered an element that was already tagged, you would know that you had already visited it and that there existed a loop in the linked list. What if you are not allowed to alter the structure of the elements of the linked list? The following algorithm will find the loop:
- Start with two pointers ptr1 and ptr2.
- Set ptr1 and ptr2 to the head of the linked list.
- Traverse the linked list with ptr1 moving twice as fast as ptr2 (for every two elements that ptr1 advances within the list, advance ptr2 by one element).
- Stop when ptr1 reaches the end of the list, or when ptr1 = ptr2.
- If ptr1 and ptr2 are ever equal, then there must be a loop in the linked list. If the linked list has no loops, ptr1 should reach the end of the linked list ahead of ptr2.
1 and 2 cross together. 1 comes back. then 3 and 4 cross. 2 comes back. then 1 and 2 cross. Total time is 2+1+10+2+2 = 17.
给一个matrix of int,每个value的右面的值和下面的值都比它大，在里面search.
标准答案如下：
从右上角开始，和你要查找目标作比较。如果比目标小，往下走一格；如果比目标大，
往左走一格。算法复杂度O(m+n)。
给出一个任意pattern（abc*xyz，*abc,*abc*xyz*)
*代表任意0-N字母
给一个input string，要求写code匹配(不是伪代码)
bool matchPattern（string pattern, string input）;
bool matchPattern(const char* pattern, const char* input)
{
int match=false;
while(*pattern==’*’ && *pattern!=”)
++pattern;
if(*pattern==”)
return true;
const char* patternStart=pattern;
while(*input!=”)
{
//match from beginning
const char* inputPos=input;
if(!match && *input==*pattern)
{
do
{
match=true;
++pattern;
// updated on 11/09/2007
int wildcard=false;
if(*pattern==’*')
{
wildcard=true;
while(*pattern==’*’ && *pattern!=”)
++pattern;
}
if(wildcard)
{
while(*input!=” && *input!=*pattern)
++input;
}
else
++input;
}while(*input!=” && *pattern!=” && *input==*pattern);
while(*pattern==’*’ && *pattern!=”)
++pattern;
}
if(match && *pattern==”)
{
return true;
}
pattern=patternStart;
match=false;
input=inputPos+1;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<matchPattern(“*”,”*a”)<<endl;
cout<<matchPattern(“a*”,”")<<endl;
cout<<matchPattern(“*a”,”a”)<<endl;
cout<<matchPattern(“*ba*saf*”,”*abasaf”)<<endl;
cout<<matchPattern(“ba*saf**k”,”akbaadwesabawerwrsafaf2321k”)<<endl;
}
What new feature would you add to MSWORD if you were hired?
Ability to open .pdf files, Word completion, totally web interface based. To publish MS word docs as blogs on the sites, in one click , support wiki.
solution: reverse a string – word by word
problem: reverse “the house is blue”, the answer should be “blue is house the”. the words are reversed, but the letters are still in order (within the word).
solution: solving the initial problem of just reversing a string can either be a huge help or a frustrating hinderance. most likely the first attempt will be to solve it the same way, by swapping letters at the front of the string with letters at the back, and then adding some logic to keep the words in order. this attempt will lead to confusion pretty quickly.
for example, if we start by figuring out that “the” is 3 letters long and then try to put the “t” from “the” where the “l” from “blue” is, we encounter a problem. where do we put the “l” from “blue”? hmm… well we could have also figured out how long “blue” was and that would tell us where to put the “l” at… but the “e” from “blue” needs to go into the space after “the”. argh. its getting quite confusing. in fact, i would be delighted to even see a solution to this problem using this attack method. i don’t think its impossible, but i think it is so complex that it’s not worth pursuing.
here’s a hint. remember before when we just reversed “the house is blue”? what happened?
initial: the house is blue reverse: eulb si esuoh eht
look at the result for a minute. notice anything? if you still don’t see it, try this.
initial: the house is blue reverse: eulb si esuoh eht wanted : blue is house the
the solution can be attained by first reversing the string normally, and then just reversing each word.
part I: what is the angle between the minute hand and the hour hand at 3:15 on an analog clock? no, its not 0.
part II: how often does the minute hand pass the hour hand on an analog clock?
answer: part I: 12 hours on the clock make 360 deg. so one hour is 30 deg. the hour hand will be directly on the 3 when the minute hand is at 12 (3:00). after 15 minutes or 1/4 of an hour, the hour hand will be 1/4 * 30 deg = 7.5 deg. away from the minute hand.
part II: if you just think about it, intuitively you’ll see the minute hand passes the hour hand 11 times every 12 hours, so it must pass it every 1 1/11 hours. but this doesn’t make sense to me. i need to prove it.
