Interview questions from Pinank

here are the questions:
1. Given a library of Stack with 2 functions (push(x), pop()), implement a queue library (i.e. enqueue(x), dequeue())
Use 2 stacks:
enqueue() : keep push(x)ing in Stack1 only
dequeue() : keep pop()ing from Stack2 only. (Incase Stack2 is empty, pop() everything from Stack1 to push() into Stack2) and then pop() from Stack2

2. Explain working of HTTP protocol (some people answer in quite detail (about DNS lookup, TCP handshake, etc.)

3. How can you implement a HashTable?
Use an ‘Array’ to store values. (Each array element is actually a linked-list, so 2 values having same key can be inserted at the same-element in the Array.
Also need 2 functions:
a) to get hash-key (to decide where to store the element in the array)
b) compare() : I forgot the exact reason, but i think its used for resolving collision. (In Java they also store the ‘key’ along with the object’ instead of just storing the object and this compare() function is then used .. i’ll try to find the document that has more details on how its used..
c) Some people also ask what are good options of hash-functions ? (it will depend on type of data, but some common options are ‘mod’ function) e.g. 57 mod 8 = 1 (if array size is 8) ..

PHP Interview Questions (Set1)

1) What is the difference between this and self?
http://www.programmerinterview.com/index.php/php-questions/php-self-vs-this/

2) What is __toString used for ?
If an object needs to be used as a string (e.g.: echo $obj;). If you don’t use __toString then the statement will produce fatal error.

3)
$var1 = ‘Welcome to ‘; $var2 = ‘TechInterviews.com’;
What will work faster?

Code sample 1: –
$var 3 = $var1.$var2;
Or code sample 2:
$var3 = “$var1$var2”;

Both examples would provide the same result – $var3 equal to “Welcome to TechInterviews.com”. However, Code Sample 1 will work significantly faster. Try it out with large sets of data (or via concatenating small sets a million times or so), and you will see that concatenation works significantly faster than variable substitution.

4) Explain difference of explode(), implode(), extract()
extract makes variables from array elements. 

$var_array = array("color" => "blue",
                   "size"  => "medium",
                   "shape" => "sphere");
extract($var_array)
//$color is now blue;

5) Explain array_push(), array_pop(), array_shift(), array_unshift()
array_push : put elements at end of array
array_pop : retrieves element from end of array
array_shift : retrieve element from beginning of array
array_unshift : adds element to beginning of array

6) Explain parse_str() and parse_url()

parse_str Parses str as if it were the query string passed via a URL and sets variables in the current scope.

$str = "first=value&arr[]=foo+bar&arr[]=baz";

// Recommended
parse_str($str, $output);
echo $output['first'];  // value
echo $output['arr'][0]; // foo bar
echo $output['arr'][1]; // baz

parse_url() parses a URL and returns an associative array containing any of the various components of the URL that are present.

$url = 'http://username:password@hostname:9090/path?arg=value#anchor';

var_dump(parse_url($url));
var_dump(parse_url($url, PHP_URL_SCHEME));
var_dump(parse_url($url, PHP_URL_USER));
var_dump(parse_url($url, PHP_URL_PASS));
var_dump(parse_url($url, PHP_URL_HOST));
var_dump(parse_url($url, PHP_URL_PORT));
var_dump(parse_url($url, PHP_URL_PATH));
var_dump(parse_url($url, PHP_URL_QUERY));
var_dump(parse_url($url, PHP_URL_FRAGMENT));

array(8) {
  ["scheme"]=>
  string(4) "http"
  ["host"]=>
  string(8) "hostname"
  ["port"]=>
  int(9090)
  ["user"]=>
  string(8) "username"
  ["pass"]=>
  string(8) "password"
  ["path"]=>
  string(5) "/path"
  ["query"]=>
  string(9) "arg=value"
  ["fragment"]=>
  string(6) "anchor"
}

7) What is the “final” keyword in PHP?
final keyword, which prevents child classes from overriding a method by prefixing the definition with final. If the class itself is being defined final then it cannot be extended.

8) Which php profiler do you use?
xdebug is a debugging and profiling tool for php. Xdebug’s built-in profiler allows you to find bottlenecks in your script and visualize those with an external tool such as KCacheGrind. When Xdebug is activated it will show a stack trace whenever PHP decides to show a notice, warning, error etc. The information that stack traces display, and the way how they are presented, can be configured to suit your needs.
Xdebug’s basic functions include the display of stack traces on error conditions, time tracking, maximum nesting level protection (Controls the protection mechanism for infinite recursion protection. The value of this setting is the maximum level of nested functions that are allowed before the script will be aborted.)

9) Different between const and define()
http://stackoverflow.com/questions/2447791/define-vs-const

What are magic methods, magic quotes, short tags in php?

Magic Methods:

PHP functions that start with a double underscore – a “__” – are called magic functions (and/or methods) in PHP. They are functions that are always defined inside classes, and are not stand-alone (outside of classes) functions. The magic functions available in PHP are: __construct(), __destruct(), __call(), __callStatic(), __get(), __set(), __isset(), __unset(), __sleep(), __wakeup(), __toString(), __invoke(), __set_state(), __clone(), and __autoload().

Why are they called Magic Methods?
The definition of a magic function is provided by the programmer – meaning you, as the programmer, will actually write the definition. This is important to remember – PHP does not provide the definitions of the magic functions – the programmer must actually write the code that defines what the magic function will do. But, magic functions will never directly be called by the programmer – actually, PHP will call the function ‘behind the scenes’. This is why they are called ‘magic’ functions – because they are never directly called, and they allow the programmer to do some pretty powerful things.

PHP: What are magic methods?

Magic Quotes:
Magic Quotes is a process that automagically escapes incoming data to the PHP script. It’s preferred to code with magic quotes off and to instead escape the data at runtime, as needed.

This feature has been DEPRECATED as of PHP 5.3.0 and REMOVED as of PHP 5.4.0.

Short Tags:
< ?= Hello World ? >
Output is displayed directly to the browser.

– PHP also allows for short open tags which are discouraged because they are only available if enabled with short_open_tag php.ini configuration file directive
– Can have problems with portability if the server does not allow short tags
– Can interfere with XML documents.

PHP script to report download size of any URL

Write a PHP script to report the total download size of any URL. You may not use any 3rd-party code that performs the entire task described below.

No HTML interface is necessary for this exercise; you can write this as a command-line script that accepts the URL as an argument.

For a single-file resource such as an image or SWF, the script would simply report on the total size of the document.

For a complex resource such as an HTML document, the script would need to parse it to find references to embedded, included resources: javascript files, CSS files, iframes, etc.

The goal of this exercise is to output the following information for a given URL:
– total number of HTTP requests
– total download size for all requests

Answer: http://www.programmerinterview.com/index.php/php-questions/php-interview-questions-and-answers/

Find Longest Palindrome in a string

Find longest palindrome in a string.

Brute Force: N^3

Below Method by Dynamic Programming is N^2. Video for below method:
https://www.youtube.com/watch?v=obBdxeCx_Qs

There is another algorithm called Mancher’s Algorithm which is in linear time.

Note that here since we are dealing with single string we just need to populate top triangle of matrix. In longest substring since we were dealing with 2 strings we populated the whole matrix. 

$str = "BANANA";
$len = strlen($str);
$matrix = array();
$palindromeBegins = 0;
$max = 1;

// single letter palindromes
for ($i=0; $i < $len; $i++) {
    $matrix[$i][$i] = 1;
};

// 2 character palindromes
for ($i=0; $i < $len-1; $i++) {
    if ($str[$i] == $str[$i+1]) {
        $matrix[$i][$i+1] = 1;
        $max = 2;
        $palindromeBegins = $i;
    }
}

// 3 character and above
for ($curr_len=3; $curr_len <= $len ; $curr_len++) {

    for ($i=0; $i < $len-$curr_len+1; $i++) {
        $j = $i+$curr_len-1;
        // 1. first and last chars should match
        // 2. rest of string from previous calculations should be a palindrome
        if (($str[$i] == $str[$j]) &&
            ($matrix[$i+1][$j-1] == 1)) {
            $matrix[$i][$j] = 1;
            $max = $curr_len;
            $palindromeBegins = $i;
        }
    }
}

echo "Max Palindome: $max\n";
echo "Palindrome: " . substr($str, $palindromeBegins, $max);
echo "\n";

Another approach:
http://krenzel.org/articles/longest-palnidrome