life ideas

November 7, 2007

brainstorm

Filed under: Uncategorized — manoftoday @ 3:54 am

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:

  1. Checking if array[i] key exists in our hashtable.
  2. If the key does not exist in our hashtable:
    1. Add the key to the hashtable
    2. The value mapped with this key is the difference between the sumvalue and array[i].
  3. Check if the difference between sumvalue and array[i] exists as a key in our hashtable.
  4. Continue loop if the difference value does not exist as a key.

Notice that all of this is done in linear time – Ɵ(n).

 

Give a one-line C expression to test whether a number is a power of 2. [No loops allowed – it’s a simple test.]

if (x && !(x & (x-1)) == 0)

(a-1) xor a == 0 – What does this do?

a is a power of 2.

How many points are there on the globe where by walking one mile south, one mile east and one mile north you reach the place where you started.

The answer is “many points”. The set of such points is given as {North pole, special circle}.

 

You are given a list of n numbers from 1 to n-1, with one of the numbers repeated. Devise a method to determine which number is repeated.

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.

 

You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

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.

 

 

You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest – it is either hollow while the rest are solid, or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.

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.

 

 

Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

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:

  1. Start with two pointers ptr1 and ptr2.
  2. Set ptr1 and ptr2 to the head of the linked list.
  3. 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).
  4. Stop when ptr1 reaches the end of the list, or when ptr1 = ptr2.
  5. 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.

 

There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower mans pace.

Man 1:1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross

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.

http://www.techinterview.org/Solutions/fog0000000120.html

Advertisements

Create a free website or blog at WordPress.com.