Welcome~~~


Another blog:
http://fun-st.blogspot.com/

It is easier to write an incorrect program than understand a correct one.

Monday, February 28, 2011

Some Note when reading the Puzzle-Blog

Some notes from: http://inder-gnu.blogspot.com/ 
Many problems are very good. 


####### Design Questions #######
# how do you design an elevator algorithm
Elevator:
Responsibilities -- no. of passengers aboard, destination floors, state & direction, current floor
Methods: load /unload passengers, current floor/passeengers/directions/ state
Attributes: passengers, floor, dir, state, elevator_id

Passenger:
Res -- keep track of the desitnation fllor
Mds -- current destination
Att - desintation fllor

Observer:
Res -- keeps track of the passengers entering & leaving the elevator
Mda -- total entry /exit passengers, passenger enter /exit
Att - total -entry/ exit passengers.

# How would you design a server that has to process a fair number of good number of requests a second. What if you didn't know how many requests you'd be getting? What if requests had different priorities? (I always think of the Apache design for this question)
# Design malloc and free. (give up? see how G++ malloc works or this page for more examples)
# Design an elevator control system. Don't forget buttons on every floor and supporting multiple elevators. (What objects/methods/properties/how components communicate)
# Design a chess game (what objects? what methods? which data where? how will it work?)
# Design a deck of cards class (object/methods/data)
# How would you design the infrastructure front half of a very large web ecommerce site? what if it was very personalized? (how sessions are handled? where and what you can cache? how to load-balance?)

# Composition is a OOP concept:
It works similar functionality to inheritance but creates a different relationship. Compostion a "has-a" relationship - versus the inheritance of "is-a" relationship
Composition - the way you model objects that contain other objects. In OOP- you use instance variables of one object to hold references to other objects.
Car Object must have an Engine. So Car is composed of Engine. That is a composition.


Write code for Shuffle() method.

enum Suit { spades, clubs, hearts, diamonds,};
enum Face {ACE, TWO, THREE, FOUR, FINE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, };

class card{
public: 
Card(Suit suit, Face face): suit(suit), face(face) {}
Card(const Card& orig): suit(orig.suit), face(orig.face) {}
Suit getSuit() const {return suit;}
Face getFace() const {return Face;}

private:
Card() {}
Suit suit;
Face face;
friend class Deck;
};

class Deck{
public: 
Deck()
{
int index = 0;
for (int = 0; i < SUITS_PER_DECK; ++I){
for( int j = 0; j < CARDS_PER_SUIT; ++j){
index = i * CARDS_PER_SUIT +J;
CARDS[index].suit = (Suit) i;
CARDS[index].face = (face) j;
}
         }
}
Deck(const Deck& orig)
{
for (int i = 0; i < SUITS_PER_DECK * CARDS_PER_SUIT; ++ i){cards[i] = orig.cards[i];}
}

void Shuffle()
{
int bagSize = SUITS_PER_deck * CARDS_pER_SUIT;
in t index = 0;
srand(time(NULL));
while(bagSize){
index = rand() & bagSize;
swap(cards[--bagSize], cards[idex]);
         }
}

static const int SUITS_PER_DECK = 4;
static const int CARDS_PER_SUIT = 13;

private:
Card cards[SUITES_PER_DECK * CARDS_PER_SUIT];
friend ostream & operator<< (ostream&, cont Deck&);
};


# Minimum number of scales required A company produces play ball of weights 0-25kg, 25-50kg, 50-75kg, 75-100kg. You need to put the balls in four different buckets daily depending on the number of ball company produces.BucketA (0-25kg), BucketB (25-50kg), BucketC (50-75kg) and BucketD(75-100kg).
A scale is provided on which you can weigh only 1 ball at a time which has a bulb. If the weight of the ball matches the scale category, the bulb will light up otherwise it will be OFF. e.g. If scale is marked to measure 10-25 kg, then any ball between 10 to 25kg (inclusive 10 and 25) will switch on the bulb and say if you weigh 26 it wont switch on the bulb. The cost of scale is 1 million dollar.
Question: You need to find the minimum number you will use to do the job.Also what is weight category you will choose for the scales to do the job.
==> 2 scales can do the job .... 0-50 and 25-75 ....

# Multiple lines, which the cost for connecting them is their sum of the length, how to connect n ropes with least cost
ANS: x, y, z wherein x < y < z
         if you tie y+z first
         then you tie x+ y +z which is essentially x + 2* (y+z)

so all ropes which have been tied before actually keep adding to the cost again and again. Hence the best strategy would be to include smaller ropes initially so that they contribute lower cumulative cost in future
keeping it in min heap..

# Find maximum interval across two arrays
We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0...
we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal...
i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
ANS==> 

# Find consecutive numbers from n sorted arrays
Suppose there are n arrays storing integers in a sorted manner. You need to find all those sequences of numbers one frm each array so that the numbers are consecutive...
For example: let us consider 2 arrays
            array 1 has 2 4 7 9 11 14 16 19
            array 2 has 3 8 15 20
            the answer must be (2,3),(7,8),(14,15),(19,20)
==> this could borrow some idea from the list merging, where we may add some condision, when judging, such as whether their differences is within (-1 or 1)

# Longest increasing subsequence in chain of numbers
Find out the the longest increasing subsequence in a sequence of 'n' numbers.
eg: 1, 5, 3, 2, 100
==> we can borrow the idea from bubble sort,where the comparision of each pari is conducted, increase the count, whenever there is a swap
Or try the recursive structure:
Here x is first element and y is successive of x. Call this method as lcs(1,2,1); x,y are first,second element of array. len is initial length which is 1.

void lcs(int x, int y, int len) {
             if( y <= array.length-1){
                        if( array[x] <= array[y]){
                                     if( largest < len +1){
                                                                    largest = len+1;
                                                             }
                                           lcs(y,y+1,len+1);
                                  }
                       else{ 
           lcs(x-1,y,len -1);
           lcs(x,y+1,len);
                 }
}
}
It was said that the "patience sorting" can solve this problem in O(n log n) :


# Partition array in k ranges to minimize the maximum sum over all ranges
A given arrangement S of non-negative numbers  and an integer k.
Output: Partition S into k ranges, so as to minimize the maximum sum over all the ranges. This so-called linear partition problem arises often in parallel processing, since we seek to balance the work done across processors so as to minimize the total elapsed run time. Indeed, the war story of Section  revolves around a botched solution to this problem.
Application - Suppose that three workers are given the task of scanning through a shelf of books in search of a given piece of information. To get the job done fairly and efficiently, the books are to be partitioned among the three workers. To avoid the need to rearrange the books or separate them into piles, it would be simplest to divide the shelf into three regions and assign each region to one worker.     
But what is the fairest way to divide the shelf up? If each book is the same length, say 100 pages, the job is pretty easy. Just partition the books into equal-sized regions,
so that everyone has 300 pages to deal with.
But what if the books are not the same length? 

==> First find the sum of all the numbers in S, divide it by k and store it in b.
Our aim now to divide S, so that sum should be as close to b as possible, for that purpose purpose we'd define a range b - k/2 and b + k/2. Now start scanning the array from start and keep adding to sum, if the sum falls in range previously mentioned, try to get closer to b by removing last array element or by adding the next one, whichever is closer should be end of first partition. On the similar lines partition rest of array.
Though this does not guarantee the fair partitions but I think if difference between array elements is not much, it would lead to near fair distribution.
I hope it made sense.

# Arrange numbers in decreasing order of their frequency
Input : {5, 13, 6, 5, 13, 7, 8, 6, 5}
Output : {5, 5, 5, 13, 13, 6, 6, 7, 8}
The question is to arrange the numbers in the array in decreasing order of their frequency, preserving the order of their occurrence.
If there is a tie, like in this example between 13 and 6, then the number occurring first in the input array would come first in the output array.
==> -1- traverse the arraay, use the map to recored their frequency
-2- sort the frequency, acending order
-3- start from the smallest frequency, and also start from the end of the array, multiplication of the element to re-stored it into the array ( actaully we can do thing by using the deceding frequecy, and start from the front of the array) 

# Design an algorithm for an automated parking lot
You have a set of parking slots along with the distance from entrance, you need to devise an algorithm to support the following operations
1. Figure out a nearest free parking slot in the quickest way
2. Figure out where the car is parked for a valet to take it out in the quickest way.
==> 
1. use a min heap for storing Parking Lot objects which are ordered by minDistance from entrance.
2. Find and provide a free lot is O(logn), take the top from the heap and put it in the hash table and rearrange the heap
3. Have a hash table with key--> car number and value as NODE
4. find where the car is parked for valet --> given a care number sesarch in hashtable, free from hash table and ass it to the heap of free nodes in log(n)

# Design an algorithm for optical character reading
Assuming you have been given some very old papers which are scanned as JPG images.
You have been asked to write a program which can read those images and identify lines in the same.
Trick lies in the fact that the lines could have negative/positive slopes as they are old documents.
Source - Algorithm design manual by Stevens
1. create a graph which each and every pixel of the image
2. if the area from left to right is grey/empty give a weight of edge  0 else 1
3. now the problem is to find a path in the graph from left to right as straigt as possible so that the path remains positive.

#  find row with minumum 0's
You have a matrix with 0 & 1 with rows being in sorted order. Find the row with minimum number of 1's
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 0 1 1 1

==> Solution 1
1. Start from row1 till you keep getting a 0, as soon as you encounter a 1 go south and use the following table

1 -> 1 similar row
1 -> 0 better row make this is as candidate for answer

1. let's run through the algorithm from row1, col4 go south as row1, col4 is 1 
2. transition is 1->1 so ignore second row and go south
3. 1 -> 1 similar row ignore row3 also
4. on same logic ignore row4 also so answer is row1

Let's take another matrix and run the same algo again

0 0 1 1 1
0 0 0 1 1
0 0 0 0 1

1. first transtion on row1, col3 is 1->0 so row is better
2. now run right on row2 till you get a 1 which is row3,col4 and now go south for which the transition is 1->0 making it a better row and since this is the last row hence the final answer

Time complexity analysis
1. best case-> 0(number of rows) it's a straight down south
2. worst case -> 2 (number of rows) wherein it's a zig zag motion

==> Solution2:
We first traverse 1st row and count number of 0's in it.
Now we start checking for second row and moment we find more number of 0's in it we skip the row.
if it has less number of 0's then keep this as reference for other rows..keep doing the same.

# Map rectangles to plane
In my graphics work I need to solve the following problem. Given an arbitrary set of rectangles in the plane, how can I distribute them into a minimum number of buckets such that the subset of rectangles in the same bucket do not intersect each other? In other words, there should not be any overlapping area between any two rectangles in the same bucket.'
==>Use graph coloring, you need to create a graph so that adjacent nodes should be colored in different colors

#Find k-th largest in two sorted arrays
Find kth largest element in two sorted arrays.
Can there be a solution better that O(k)

Solution 1: 
Suppose input array's are in the following fashion
A[] = {2, 3, 7, 12, 27, 81, 91}
b[] = {1, 25, 32, 74, 89}

1. Take two pointers ptr1 and ptr2 at start in A[] and B[]
2. if(A[i] > B[j])
j++;
else
i++;
3. if ( (i +j ) == k)
compare A[i] and B[j] and return the larger of them
else
repeat step2.

Time Complexity = O(k)

Solution2: 
Idea = We have to find the median of first k elements of A and B and k = 5

1. The kth largest among the union of A[] and B[] would be in the first k elements of of A[] and b[]
2. Consider k elements from A[] and B[] which results in the following array
a[] = {2. 3, 7, 12, 27}
b[] = {1, 25, 32, 74, 89}
3. Compare (A[mid], B[mid])
if (A[mid] is GT)
{
For ArrayA = We can skip a[mid]..a[k] elements since a[mid] is greater and all elements from a[0]..a[mid] are valid candidates for being the median; since A[mid] is the greater element no point considering bigger elements than that for the median
For Array B = We can skip b[0]...b[mid] elements since b[mid] is less; so all elements less than are not valid candidates for being median.
}
4. Repeat Step3 till you are left with either 2 or 3 elements then you do a comparision and find kth largest.

Time Complexity = O(log k)

Example showing Solution 2
A[] = { 2, 3, 7, 12, 27}
B[] = {1, 25, 32, 75, 89}
          After step2 i.e. k elements from both arrays
          A[mid] = 7 and B[mid] = 32

B[mid] is Greater.

Now array becomes after step3
a[] = {7, 12, 27}
b[] = { 1, 25, 32}

a[mid] = 12 and b[mid] = 25
After step3 the arrays become
a[] = { 12, 27} -- skpping the left portion of smaller element array
b[] = { 1, 25} -- skipping the right portion of larger element array

Now a[mid] = 12 and b[mid] = 1
after step3 the array becomes
a[] = {12}
b[] = {1,25}

Find the median of 12, 1, 25 in O(1) which is 12 which is the 5th largest

#Find the nth number with m binary 1s
There is a series of numbers in ascending order. All these numbers have the same number of binary 1s in them. Given the number of 1 bits set in the numbers, write an algorithm/C program to find the nth number in
the series.  
Example: Given a number m find the next higher number r, that has same number of 1-bits
Ex. 3(0000011) ==> 5 (0000101)
6(0000110) => 9 ( 0001001)
11(0000110) ==> 13 ( 0001101)

+ The left hand side is:
- A 0 followed by
- One or more 1's (say x) followed by 
- Zero or more 0's (say y)
+ is changed to 
- A 1 followed by
- (y+1) zeros followed by
- (x-1) 1's 

An example:    001 ==> 101       .....       011000 => 100001

Now let's frame the algorithm
- Given a bit-pattern, start from right, find successive zeros (xxxx011110000)
- Followed by zeros find successive 1's (xxxx011110000)
- Stop on hitting a zero (xxxx01111000)
- Interchage that zero with a 1 from successive 1's (xxxx101110000)
- Now move the remaining 1's to extrem right, filling the gap with zeros (xxxx100000111)

---- Doing it progammatically in C -----

unsigned snoob( unsigned x)
{
unsigned smallest, ripple, ones;
// x = xxx011110000
smallest = x & -x;  // 0000 0001 0000
ripple = x + smallest;    // xxx1 0000 0000
ones = x^ripple; // 0001 1111 0000
ones = (ones >> 2)/smallest;     // 0000 0000 0111
return ripple | ones;   // xxx1 0000 01111

}

# Find path in two nodes of Trees
Suppose you have a tree. A binary tree (for something like simplicity :p). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you "cant" change:
struct node{Data data; node *right,*left;};
what will you strategy be to tackle this problem.
To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).
Solution::
In this case say i was give 3 and 9 then
Two cases:: First case tree is BST
1. Find and store the path from root till 3 and 4 in 2(LOG(n)) time
now path is 5,4,3 and 5,8,9
2. Now since both the sublists are sorted using two pointers in one pass find the common node in the two lists from the last.
Say in the above example the common node is 5 so 4,3,5,8,9 is the path between 3 and 9.
Step requires O(n) time complextiy.
So overall complexity is O(n)

# Notes of grep search for files

Example of using grep

searching for the word "modules":

  grep -r "modules" .

By using the "-r" switch, we're telling grep to scan files in the current directory and all sub-directories. It will return a list of files the string was found in, and a copy of the line it was found on.

To just return the file name with out the line that matched: 

  grep -lr "modules" .

Use the grep to find strings match a regular expressions

  grep -lr "mod.*" .

That command will print a list of files containing any word starting with "mod".

to search for multiple words:

  grep -r "drupal\|joomla\|wordpress" .

Also to search for multiple patterns

# Interview question on grep:

A often asked question is to use grep to find the phone numbers in a very large file:

a folder consists of 10000 files and some files contain US phone numbers. What would you do to display the names of files containing US phone numbers?

For the following 4 kinds of patterns:
1. xxx-xxx-xxxx
2. (xxx)xxx-xxxx
3. xxx xxx xxxx
4. xxxxxxxxxx

grep '\(([0-9]\{3\})\|[0-9]\{3\}\)[ -]\?[0-9]\{3\}[ -]\?[0-9]\{4\}' file

Explanation:
([0-9]\{3\}) three digits inside parentheses
\| or
[0-9]\{3\} three digits not inside parens
...with grouping parentheses - \(...\) - around the alternation so the rest of the regex behaves the same no matter which alternative matches.
 
Some others

http://www.panix.com/~elflord/unix/grep.html

Suppose you want to match a specific number of repetitions of a pattern. A good example is phone numbers. 

You could search for a 7 digit phone number like this: grep "[[:digit:]]\{3\}[ -]\?[[:digit:]]\{4\}" fil


grep options search_string file...

http://www.macworld.com/article/41504/2004/12/jangeekfactor.html


If to
find the "same" line from two files, use
The correct solution is to avoid regular expressions and instead use fixed strings (-F) that must match an entire line (-x).
grep -Fxf file1 file2



--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

BashFAQ - Greg's Wiki

BashFAQ - Greg's Wiki

Contents

  1. How can I read a file (data stream, variable) line-by-line (and/or field-by-field)?
  2. How can I store the return value/output of a command in a variable?
  3. How can I insert a blank character after each character?
  4. How can I check whether a directory is empty or not? How do I check for any *.mpg files?
  5. How can I use array variables?
  6. How can I use variable variables (indirect variables, pointers, references) or associative arrays?
  7. Is there a function to return the length of a string?
  8. How can I recursively search all files for a string?
  9. What is buffering? Or, why does my command line produce no output: tail -f logfile | grep 'foo bar' | awk ...
  10. How can I recreate a directory hierarchy structure, without the files?
  11. How can I print the n'th line of a file?
  12. How do I invoke a shell command from a non-shell application?
  13. How can I concatenate two variables? How do I append a string to a variable?
  14. How can I redirect the output of multiple commands at once?
  15. How can I run a command on all files with the extension .gz?
  16. How can I use a logical AND/OR/NOT in a shell pattern (glob)?
  17. How can I group expressions in an if statement, e.g. if (A AND B) OR C?
  18. How can I use numbers with leading zeros in a loop, e.g. 01, 02?
  19. How can I split a file into line ranges, e.g. lines 1-10, 11-20, 21-30?
  20. How can I find and deal with file names containing newlines, spaces or both?
  21. How can I replace a string with another string in all files?
  22. How can I calculate with floating point numbers instead of just integers?
  23. I want to launch an interactive shell that has special aliases and functions, not the ones in the user's ~/.bashrc.
  24. I set variables in a loop. Why do they suddenly disappear after the loop terminates? Or, why can't I pipe data to read?
  25. How can I access positional parameters after $9?
  26. How can I randomize (shuffle) the order of lines in a file? (Or select a random line from a file, or select a random file from a directory.)
  27. How can two unrelated processes communicate?
  28. How do I determine the location of my script? I want to read some config files from the same place.
  29. How can I display the target of a symbolic link?
  30. How can I rename all my *.foo files to *.bar, or convert spaces to underscores, or convert upper-case file names to lower case?
  31. What is the difference between test, [ and [[ ?
  32. How can I redirect the output of 'time' to a variable or file?
  33. How can I find a process ID for a process given its name?
  34. Can I do a spinner in Bash?
  35. How can I handle command-line arguments (options) to my script easily?
  36. How can I get all lines that are: in both of two files (set intersection) or in only one of two files (set subtraction).
  37. How can I print text in various colors?
  38. How do Unix file permissions work?
  39. What are all the dot-files that bash reads?
  40. How do I use dialog to get input from the user?
  41. How do I determine whether a variable contains a substring?
  42. How can I find out if a process is still running?
  43. Why does my crontab job fail? 0 0 * * * some command > /var/log/mylog.`date +%Y%m%d`
  44. How do I create a progress bar? How do I see a progress indicator when copying/moving files?
  45. How can I ensure that only one instance of a script is running at a time (mutual exclusion)?
  46. I want to check to see whether a word is in a list (or an element is a member of a set).
  47. How can I redirect stderr to a pipe?
  48. Eval command and security issues
  49. How can I view periodic updates/appends to a file? (ex: growing log file)
  50. I'm trying to put a command in a variable, but the complex cases always fail!
  51. I want history-search just like in tcsh. How can I bind it to the up and down keys?
  52. How do I convert a file from DOS format to UNIX format (remove CRs from CR-LF line terminators)?
  53. I have a fancy prompt with colors, and now bash doesn't seem to know how wide my terminal is. Lines wrap around incorrectly.
  54. How can I tell whether a variable contains a valid number?
  55. Tell me all about 2>&1 -- what's the difference between 2>&1 >foo and >foo 2>&1, and when do I use which?
  56. How can I untar (or unzip) multiple tarballs at once?
  57. How can group entries (in a file by common prefixes)?
  58. Can bash handle binary data?
  59. I saw this command somewhere: :(){ :|:& } (fork bomb). How does it work?
  60. I'm trying to write a script that will change directory (or set a variable), but after the script finishes, I'm back where I started (or my variable isn't set)!
  61. Is there a list of which features were added to specific releases (versions) of Bash?
  62. How do I create a temporary file in a secure manner?
  63. My ssh client hangs when I try to run a remote background job!
  64. Why is it so hard to get an answer to the question that I asked in #bash?
  65. Is there a "PAUSE" command in bash like there is in MSDOS batch scripts? To prompt the user to press any key to continue?
  66. I want to check if [[ $var == foo || $var == bar || $var == more ]] without repeating $var n times.
  67. How can I trim leading/trailing white space from one of my variables?
  68. How do I run a command, and have it abort (timeout) after N seconds?
  69. I want to automate an ssh (or scp, or sftp) connection, but I don't know how to send the password....
  70. How do I convert Unix (epoch) timestamps to human-readable values?
  71. How do I convert an ASCII character to its decimal (or hexadecimal) value and back?
  72. How can I ensure my environment is configured for cron, batch, and at jobs?
  73. How can I use parameter expansion? How can I get substrings? How can I get a file without its extension, or get just a file's extension?
  74. How do I get the effects of those nifty Bash Parameter Expansions in older shells?
  75. How do I use 'find'? I can't understand the man page at all!
  76. How do I get the sum of all the numbers in a column?
  77. How do I log history or "secure" bash against history removal?
  78. I want to set a user's password using the Unix passwd command, but how do I script that? It doesn't read standard input!
  79. How can I grep for lines containing foo AND bar, foo OR bar? Or for files containing foo AND bar, possibly on separate lines?
  80. How can I make an alias that takes an argument?
  81. How can I determine whether a command exists anywhere in my PATH?
  82. Why is $(...) preferred over `...` (backticks)?
  83. How do I determine whether a variable is already defined? Or a function?
  84. How do I return a string (or large number, or negative number) from a function? "return" only lets me give a number from 0 to 255.
  85. How to write several times to a fifo without having to reopen it?
  86. How to ignore aliases or functions when running a command?
  87. How can I get a file's permissions (or other metadata) without parsing ls -l output?
  88. How can I avoid losing any history lines?
  89. I'm reading a file line by line and running ssh or ffmpeg, but everything after the first line is eaten!
  90. How do I prepend a text to a file (the opposite of >>)?
  91. I'm trying to get the number of columns or lines of my terminal but the variables COLUMNS / LINES are always empty
  92. How do I write a CGI script that accepts parameters?
  93. How can I set the contents of my terminal's title bar?
  94. I want to get an alert when my disk is full (parsing df output).
  95. I'm getting "Argument list too long". How can I process a large list in chunks?
  96. ssh eats my word boundaries! I can't do ssh remotehost make CFLAGS="-g -O"!
  97. How do I determine whether a symlink is dangling (broken)?
  98. How to add localization support to your bash scripts
  99. How can I get the newest (or oldest) file from a directory?
  100. How do I do string manipulations in bash?
  101. Common utility functions (warn, die)
  102. How to get the difference between two dates
  103. How do I check whether my file was modified in a certain month or date range?
  104. Why doesn't foo=bar echo "$foo" print bar?
  105. Why doesn't set -e (set -o errexit) do what I expected?
  106. I want to tee my stdout to a log file from inside the script. And maybe stderr too.