Tech Interview Random Collections

http://www.cracktheinterview.net/forum.php
http://cslibrary.stanford.edu/109/TreeListRecursion.html

http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html

http://techpuzzl.wordpress.com/

http://www.careercup.com/
--

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

Sample Interview Questions

Sample Interview Questions (372 Questions)

http://kundansingh.com/interview/

# Sort an array of 0s, 1s and 2s | GeeksforGeeks

Sort an array of 0s, 1s and 2s | GeeksforGeeks

Sort an array of 0s, 1s and 2s

June 30, 2010

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem is similar to our old post Segregate 0s and 1s in an array, and both of these problems are variation of famous Dutch national flag problem.

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–

# Level order traversal in spiral form | GeeksforGeeks

Level order traversal in spiral form | GeeksforGeeks

Level order traversal in spiral form

December 20, 2009

Write a function to print spiral order traversal of a tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7.

Algorithm:
This problem is an extension of the level order traversal post.
To print the nodes in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable ltr is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.

Templates in C++ | Technically Idle

Templates in C++ | Technically Idle

Build binary search tree using post-order traversal trace. | Technically Idle

Build binary search tree using post-order traversal trace. | Technically Idle

In the post-order traversal trace, starting from the root node, moving towards the start, the first key which is greater than (or equal to) the root’s key is the right child of root. Similarly, the first key lower than the root’s key is the left child of root.

Inorder Tree Traversal without recursion and without stack! | GeeksforGeeks

Inorder Tree Traversal without recursion and without stack! | GeeksforGeeks

Inorder Tree Traversal without recursion and without stack!

April 5, 2010

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

1. Initialize current as root 

2. While current is not NULL    

If current does not have left child       

a) Print current’s data      

 b) Go to the right, i.e., current = current->right   

 Else      

 a) Make current as right child of the rightmost node in current's left subtree      

 b) Go to this left child, i.e., current = current->left

Graph Theory - Algorithmist

Graph Theory - Algorithmist

This one has some abstract but clear explanation for Graph Theory, starting from the basic concept to the algorithms.

http://www.algorithmist.com/index.php/Graph_Theory

Linux grep command examples

Linux grep command examples | grep command in Unix and Linux | grep examples | devdaily.com
http://www.devdaily.com/unix/edu/examples/grep.shtml

1) A typical grep example - searching for a text string in one file
grep 'joe' *.txt

grep 'fred' /etc/passwd
2) Linux grep command - searching for a string in multiple files

3) Case-insensitive file searching with the Unix grep command
-i grep -i score gettysburg-address.txt
4) Reversing the meaning of a grep search
-v grep -v score gettysburg-address.txt
5) Using grep in a Unix/Linux command pipeline

6) Using the Linux grep command to search for multiple patterns at one time (egrep)
egrep 'score|nation|liberty|equal' gettysburg-address.txt

7) Linux grep pattern matching and regular expressions (regex patterns)
grep '[0-9][0-9][0-9]' *

grep '[FG]oo' *
8) Display only filenames with a grep search
-l grep -l StartInterval *.plist
9) Showing matching line numbers with Linux grep
-n grep -n we gettysburg-address.txt
10) grep before/after - Showing lines before or after your grep pattern match
-B 5
-A 5 grep -A 5 "the living" gettysburg-address.txt
11) Power file searching with find and grep
find . -type f -exec grep -il 'foo' {} \;

"." means "look in the current directory"
"-type f" means "look in files only"
"-exec grep -il foo" means "search for the string 'foo' in a case-insensitive manner, and return the matching line and filename when a match is found
"{} \;" is some bizarre find syntax that you need to add to the end of your find command whenever you add the -exec option. (Sorry for my opinion there ... but you have to agree, that syntax is a little unusual.)

External sorting

External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.

Analysis

Merge algorithms generally run in time proportional to the sum of the lengths of the lists; merge algorithms that operate on large numbers of lists at once will multiply the sum of the lengths of the lists by the time to figure out which of the pointers points to the lowest item, which can be accomplished with a heap-based priority queue in O(log n) time, for O(m log n) time, where n is the number of lists being merged and m is the sum of the lengths of the lists. When merging two lists of length m, there is a lower bound of 2m − 1 comparisons required in the worst case.

The classic merge (the one used in merge sort) outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.

[edit]Language support

The C++'s Standard Template Library has the function std::merge, which merges two sorted ranges of iterators, and std::inplace_merge, which merges two consecutive sorted ranges in-place. In addition, thestd::list (linked list) class has its own merge method which merges another list into itself. The type of the elements merged must support the less-than (<) operator, or it must be provided with a custom comparator.

Python (programming language)'s standard library (since 2.6) also has a merge() function in the heapq module, that takes multiple sorted iterables, and merges them into a single iterator.[1]

http://docs.python.org/library/heapq.html#module-heapq

http://wordaligned.org/articles/merging-sorted-streams-in-python

-- 

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

Hadoop - Standalone Operation

Glad to finish this first try - set- up the standalone operation on Ubuntu 10

Download

To get a Hadoop distribution, download a recent stable release from one of the Apache Download Mirrors.

Prepare to Start the Hadoop Cluster

Unpack the downloaded Hadoop distribution. In the distribution, edit the file conf/hadoop-env.sh to define at leastJAVA_HOME to be the root of your Java installation.

Prerequisites---Sun Java 6

Hadoop requires a working Java 1.5.x (aka 5.0.x) installation. However, using Java 1.6.x (aka 6.0.x aka 6) is recommended for running Hadoop. For the sake of this tutorial, I will therefore describe the installation of Java 1.6.

In Ubuntu 10.04 LTS, the package sun-java6-jdk has been dropped from the Multiverse section of the Ubuntu archive. You have to perform the following four steps to install the package.

1. Add the Canonical Partner Repository to your apt repositories:

1	$ sudo add-apt-repository "deb http://archive.canonical.com/lucid partner"

2. Update the source list

1	$ sudo apt-get update

3. Install sun-java6-jdk

1	$ sudo apt-get install sun-java6-jdk

4. Select Sun's Java as the default on your machine.

1	$ sudo update-java-alternatives -s java-6-sun

The full JDK which will be placed in /usr/lib/jvm/java-6-sun (well, this directory is actually a symlink on Ubuntu).

After installation, make a quick check whether Sun's JDK is correctly set up:

1	user@ubuntu:~# java -version

2	java version "1.6.0_20"

3	Java(TM) SE Runtime Environment (build 1.6.0_20-b02)

4	Java HotSpot(TM) Client VM (build 16.3-b01, mixed mode, sharing)

hadoop-env.sh

The only required environment variable we have to configure for Hadoop in this tutorial isJAVA_HOME. Open /conf/hadoop-env.sh in the editor of your choice (if you used the installation path in this tutorial, the full path is /usr/local/hadoop/conf/hadoop-env.sh) and set theJAVA_HOME environment variable to the Sun JDK/JRE 6 directory.

  # The java implementation to use.  Required. export JAVA_HOME=/usr/lib/jvm/java-6-sun

Standalone Operation

By default, Hadoop is configured to run in a non-distributed mode, as a single Java process. This is useful for debugging.

The following example copies the unpacked conf directory to use as input and then finds and displays every match of the given regular expression. Output is written to the given output directory. 
$ mkdir input 
$ cp conf/*.xml input 
$ bin/hadoop jar hadoop-*-examples.jar grep input output 'dfs[a-z.]+' 
$ cat output/*

--
REF: http://hadoop.apache.org/common/docs/current/single_node_setup.html#PreReqs

http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-single-node-cluster/

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