Showing posts with label Programming. Show all posts
Showing posts with label Programming. Show all posts

May 16, 2011

Full Question:
What is the C-language command for opening a connection with a foreign host over the internet?

Intuitively, there's no such direct command built into the programming language. Sockets need to be used but they are platform dependent.

Actually, there's no single C command or function to open a connection to a foreign host.

To do this, first, you need a socket that is provided by the socket() function. Then, you need to call connect() to establish the connection with the host. However, that requires that all host names have been resolved, so you may have had to call gethostbyname() or similar, to turn a hostname into an IP address.

Simple Example codes here. It is a TCP client implementation.
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <netdb.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>

int main(){
        int sock, bytes_recieved;  
        char send_data[1024],recv_data[1024];
        struct hostent *host;
        struct sockaddr_in server_addr;  

        host = gethostbyname("127.0.0.1");

        if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
            printf("Socket Error");
            exit(1);
        }

        server_addr.sin_family = AF_INET;     
        server_addr.sin_port = htons(5000);   
        server_addr.sin_addr = *((struct in_addr *)host->h_addr);
        bzero(&(server_addr.sin_zero),8); 

        if (connect(sock, (struct sockaddr *)&server_addr,
                    sizeof(struct sockaddr)) == -1) {
            perror("Connect");
            exit(1);
        }

        while(1) {
          bytes_recieved=recv(sock,recv_data,1024,0);
          recv_data[bytes_recieved] = '\0';
 
          if (strcmp(recv_data , "q") == 0 || strcmp(recv_data , "Q") == 0){
             close(sock);
             break;
          }
          else
             printf("\nRecieved data = %s " , recv_data);
           
          printf("\nSEND (q or Q to quit) : ");
          gets(send_data);
           
          if (strcmp(send_data , "q") != 0 && strcmp(send_data , "Q") != 0)
           send(sock,send_data,strlen(send_data), 0); 
          else {
           send(sock,send_data,strlen(send_data), 0);   
           close(sock);
           break;
          }
        }   
        return 0;
}

April 29, 2011

Full Question:
Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

The given function, let's call rand(5), generates a random number between 1 to 5 in uniform manner. So, we can generate a random number from 1 to 5n in also uniform manner. For example, 25*(rand(5)-1) + rand(5) generates a random number between 1 to 125, and 5*(rand(5)-1)+rand(5) generates a random number between 1 to 25 uniformly. From this derivation, we can get a random number between 1 to 7 under uniform distribution.

public static void main(String args[]) {
Random g = new Random(1929304);
int N = 100000000;
int num[] = {0, 0, 0, 0, 0, 0, 0};

for(int i=0; i<N; i++ ) {
int j;
do {
j = 5*g.nextInt(5) + (g.nextInt(5)+1); // uniform between 1 and 25
} while(j>21); // uniform between 1 and 21
num[(j%7)]++; // uniform between 1 and 7 (0 and 6)
}

for(int i=0; i< 7; i++ )
System.out.println(i+1 + ": " + num[i]);
}

Following box shows results after a hundred million times try.
1: 14289981
2: 14288932
3: 14286841
4: 14284775
5: 14283995
6: 14285958
7: 14279518

April 28, 2011

Full Question:
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Simply, it can be solved in O(n2) time, by using double loop. For example,
int[] multiplicationExceptMe() {
int ret[N] = {1,};
for (int i=0; i < N; i++)
 for (int j=0; j < N; j++) {
  if(i != j)
     ret[i] *= A[j]
 }
return ret;
}

But, we have to solve in in O(n). The idea is to do multiply in both side (i.e. from start to end and from end to start) in each loop.

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;  
ret[n-1-i] = ret[n-1-i]*right;
//after multiplication, set new left and right value
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Obviously, it's O(n) time complexity.

April 25, 2011

Find All Permutations of the Letters in a Particular String

Permutations of string 'ABC' are:
ABC, ACB, BAC, BCA, CAB, CBA.

Taking the backtracking strategy, here is a solution. The program prints all permutation of the given string .It's assumed that NO same character in the string. So, the given string has same character, some redundant results are shown. You can avoid it by maintaining array to save permutations.

public static void main(String args[]) {
char[] input = {'A', 'B', 'C'};
permute(input, 0, input.length-1);
}

public static void swap(char[] str, int i, int j) {
char temp;

temp = str[j];
str[j] = str[i];
str[i] = temp;
}

public static void permute(char[] str, int start, int end) {
if (start == end)
System.out.println(str);
else {
for (int i=start; i<=end; i++) {
swap(str, start, i);
permute(str, start+1, end);
swap(str, start, i);
}
}
}
Question:
  • There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
It is from Google and Microsoft interview Question List. If you want to be hired, see the code. If we use divide operator (/), it's easy to solve in O(n). Multiply of all elements once, and divide into the value of A[i]. And we can implement division function without divide operator, but it may be not way to go. 

Here is a solution. Just define two variable, left and right to store multiplication results of left of A[i] and right of A[i]. We need just one loop of n and hence it's in O(n).


public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;
ret[n-1-i] = ret[n-1-i]*right;
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

April 24, 2011

Implementing Division without Divide Operator

Implementing dividing operation is a popular interview question in programmer and software engineering job. When you're asked, of course you must not use divide (/) operator obviously.

Since Multiplication (Devision) is derived from Addition (Subtraction) mathematically, the dividing operation can be implemented using subtraction.

Following function implement the dividing operation. there're two way- using multiplication and subtraction. However, you should use subtraction because multiplication has same property of division. You know devision can be converted to multiplication, and vise versa.



public int divide(int numerator, int denominator) {
int result = 0;

if (numerator == 0)
return numerator;
else if (denominator == 0) {
System.out.println("Error: Divided by 0");
return ERROR;// define constant for ERROR Message
else {
int sign = numerator*denominator > 0? 1:-1;
if(numerator < 0)
numerator *= -1;
if(denominator < 0)
denominator *= -1;
/* using multiplication
while(true) {
result++;
if(result*denominator > numerator) {
result--;
break;
}
}
*/
//using subtraction
while (true) {
numerator = numerator - denominator;
if(numerator>=0)
result++;
else
break;
}

return (sign*result);
}
}

Reverse String Funcion in C/Java Code

To Reverse String is not difficult, but it's one of the most popular question for interviewing in programmer job. Simple is the best, but in this case recursive function can be a better answer and efficient solution.

First method, swap first and last character repeatedly. Almost same in C and Java programming.
public String reverseString(char[] str) {
char temp;
int i, j;
for(i=0, j=str.length-1; i<=j; i++, j--){
temp = str[i];
str[i] = str[j];
str[j] = temp;
}

return new String(str);
}


Second, a recursive function can be defined. call the function within the function with Substring of input string. In Java:

public String reverseStringByRecursion(String str) {
if(str.length() == 1)
return str;
return reverseStringByRecursion(str.substring(1))
+ str.substring(0,1);
}

For C(++):
(just print character or you need global variable.)

     void StrReverse4(char *str)
     {
         if(*str)
         {
             StrReverse4(str+1);
             putchar(*str);
         } 
     }

April 19, 2011

Building Binary Search Tree in Java - Insertion

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: [from wiki]

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Node Structure.
Each node has left-child, right-child, height, value, and parent member. In fact, the parent member is not necessary, but it is added for easy understanding of binary tree, and especially when deleting node from the tree. With children of node, the parent of a node can be found easily. (see BinarySearchTree.java)

The setHeight() and getHeight() methods are not necessay too for binary search tree. They need for balanced tree such as AVL tree and Red-Black Tree.
public class Node {
private Node leftChild;
private Node rightChild;
private Node parent;
private int value;
private int height;

public Node(Node p, Node l, Node r, int v, int h) {
leftChild = l;
rightChild = r;
value = v;
height = h;
parent = p;
}

public Node(int v, Node p) {
this(p, null, null, v, 0);

}
public Node (int v) {
this(null, null, null, v, 0);
}

public boolean isBalanced() {
if(leftChild == null && rightChild == null)
return true;
else if (leftChild == null)
return rightChild.getHeight() == 0;
else if (rightChild == null)
return leftChild.getHeight() == 0;

return Math.abs(leftChild.getHeight()- rightChild.getHeight()) < 2;
}

public void setParent(Node parent) {
this.parent = parent;
}

public Node getParent() {
return parent;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getLeftChild() {
return leftChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

public Node getRightChild() {
return rightChild;
}

public void setValue(int value) {
this.value = value;
}

public int getValue() {
return value;
}

public void setHeight() {
if(leftChild == null && rightChild == null)
height = 0;
else if (leftChild == null)
height = rightChild.getHeight() + 1;
else if (rightChild == null)
height = leftChild.getHeight() + 1;
else
height= leftChild.getHeight() >= rightChild.getHeight()?
leftChild.getHeight() + 1: rightChild.getHeight() +1;
}

public int getHeight() {
setHeight();
return height;
}
}

Building BST, inserting node.
Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.


public class BinarySearchTree {
private Node root;

public BinarySearchTree(Node root) {
this.root = root;
}
public BinarySearchTree() {
this.root = (Node)null;
}

private void setRoot(Node r) {
root = r;
}

private Node getRoot() {
return root;
}

public Node findParent(int value, Node node) {
if (node.getValue() == value)
return (Node)null; // root itself
else if(node.getLeftChild() != null && node.getLeftChild().getValue() == value)
return node;
else if(node.getRightChild() != null && node.getRightChild().getValue() == value)
return node;
else if (node.getValue() > value)
return findParent(value, node.getLeftChild());
else
return findParent(value, node.getRightChild());
}

public Node insertNode(int value) {
return insertNode(value, null, null);
}

public Node insertNode(int value, Node node, Node parent) {
if(node == (Node)null)
node = new Node(parent, null, null, value, 0);
else if (value < node.getValue())
node.setLeftChild(insertNode(value,node.getLeftChild(), node));
else if (value > node.getValue())
node.setRightChild(insertNode(value, node.getRightChild(), node));
node.setHeight();
return node;
}

/* in-order traversal for showing inside of tree */
public void traverseInOrder(Node node) {
if(node.getLeftChild() != (Node)null)
traverseInOrder(node.getLeftChild());
System.out.print("Value: [" + node.getValue() + "], Height: [" +
node.getHeight() + "], Parent: [");

Node n = findParent(node.getValue(), getRoot());
if(n == (Node)null)
System.out.println("root]");
else
System.out.println(n.getValue() + "]");

if(node.getRightChild()!= (Node)null)
traverseInOrder(node.getRightChild());
}

public static void main(String[] args) {
TestCode tree = new TestCode();
Node root = new Node(5);
tree.setRoot(root);
int[] input = {7, 9, 3, 1, 2, 8, 10, 6};

for (int i = 0; i<input.length; i++)
tree.setRoot(tree.insertNode(input[i], root, null));

tree.traverseInOrder(tree.getRoot());
}
}



April 16, 2011

Computation Complexity - Double Loop

Given a sorted array in descending order, following code counts pairs of two elements with the difference d. It is easy to give an O(n2) bound for the time complexity of the function countingDifference in below codes; n times in outer for-loop and n times inner while-loop.

But a more careful analysis shows that in fact we can give an O(2n) = O(n) bound on the time complexity of this functions.  The command j++; is executed no more than n times totally, while outer for-loop is looping n times.  So, time complexity of this function is O(n+n) = O(2n) = O(n). 

The statement 'this function(algorithm) is O(n2)' is still right. 'this algorithm is O(n)' gives more information about the function.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {112, 39, 34, 32, 30, 27, 12, 11, 9, 8, 5, 2, 0};
int d = 2;

System.out.print("Input: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");
System.out.println();
System.out.println( "For " + input.length + " -length array: " + countDiffernce(input, d) + " pairs are " + d + "-differences " );
System.out.println ("Outer Loop: " + counter1 + " times, Inner Loop: " + counter2 + " times");
}

public static int countDiffernce(int input[], int d) {
int cnt =0, n = input.length;
int j = 1;
for (int i = 0; i < n && j < n; i++) {
counter1++;
while ( (j < n-1) && (input[i] - input[j] < d)) {
counter2++;
j++;
}
if(input[i] - input[j] == d) {
cnt++;
System.out.println("\t" + input[i] + " - " + input[j] + " = " + d);

}
return cnt;
}
}

April 14, 2011

Insertion Sort in Java/C of an Integer Array

Average Performance: О(n2)
Best Case Performance:О(n)
Worst Case Performance: О(n2)
Classification: stable, in-place, online
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: [from Wiki]

  • Simple implementation
  • Efficient for (quite) small data sets
  • Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
  • More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
  • Stable; i.e., does not change the relative order of elements with equal keys
  • In-place; i.e., only requires a constant amount O(1) of additional memory space
  • Online; i.e., can sort a list as it receives it

Below source code is written in Java, but you can use the function insertionSort() without any modification. Just write your main() function with input array and call insertionSort() with two parameters: array and array size.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

insertionSort(input, input.length);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\n Outerfor loop: " + counter1 + " times, inner while loop: " + counter2 + " times");
}

public static void insertionSort(int input[], int length) {
int i, j, key;

for(i = 1; i<length;i++) {
counter1++;
key = input[i];
j = i - 1;

while (j>=0 && input[j] > key) {
counter2++;
input[j+1] = input[j];
j--;
}
input[j+1] = key;
}
}
}

Merge Sort in Java/C of an Integer Array

Conceptually, a merge sort works as follows [From wiki]

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying the merge sort.
  4. Merge the two sublists back into one sorted list.

Merge sort incorporates two main ideas to improve its runtime:

  1. A small list will take fewer steps to sort than a large list.
  2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted .

public class CodeTest {
static int counter =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

mergeSort(input, 0, input.length-1);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\nmergerSort() Function is called " + counter + " times");
}

public static void mergeSort(int input[], int left, int right) {
int center;

counter++;

if (left < right) {
center = (left + right)/2;
mergeSort(input, left, center);
mergeSort(input, center+1, right);

merge(input, left, right, center);
}
}

public static void merge(int input[], int left, int right, int center) {
int i = left, j = center + 1, idx = left;
int[] temp = new int[input.length];

while( i<=center && j<=right) {
if(input[i] < input[j])
temp[idx++] = input[i++];
else if (input[i] > input[j]) 
temp[idx++] = input[j++];
else {
temp[idx++] = input[i++];
temp[idx++] = input[j++];
}

if(i > center ) 
while(j<=right)
temp[idx++] = input[j++];
else if (j > right)
while(i<=center)
temp[idx++] = input[i++];
}

for (i = left; i <=right; i++)
input[i] = temp[i];
}
}

In-Place Quick Sort of An Integer Array

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. [From wiki]
The steps are:
  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.

Time Complexity: for n entries,
   Θ(n log(n)) in the average case.
   Θ(n^2) in the worst case.

Space Complexity:
   Θ(log(n)) in the average case.
   Θ(n log(n)) when the input array is very large. the space is needed for storing variables like left, right and pivot. .

Java code for in-place Quick Sort here:


public void quickSort(int input[], int left, int right) {
int pivot = input[(left +right)/2];
int i = left, j = right;
int temp;


while (i <= j){
while(input[i] < pivot && i < right)
i++;
while(input[j] > pivot && j > left)
j--;

if (i <= j ) {
temp = input[j];
input[j] = input[i];
input[i] = temp;
i++; j--;
}
}

if (left <j)
quickSort(input, left, j);
if (i < right)
quickSort(input, i, right);
}

Binary Search of an Integer Array

Binary Search Program. It's written in Java, but it's almost same as C program. All you need is just use 'sizeOf()' macro (fuction) to get the length of array.


public static void main(String[] args) {
int input[] = {1,3,5,6,7,8,9,10,11};
                int query = 3;
System.out.println(query + " is in input[" + binarySearch(input, query) + "].");
}

public static int binarySearch(int tree[], int query) {
int beg = 0;
int end = tree.length-1;
int mid = (beg+end)/2;

for(int i=1; mid >=0 ;i++) {
System.out.println(i+ "th try - index:" + (mid + 1) + "/" + tree.length);
if(tree[mid] == query)
break;
else if(tree[mid] > query)
end = mid - 1;
else
beg = mid +1;

mid = (beg + end)/2;
   if (beg >= med)
      mid = -1;
}
return mid;
}

April 13, 2011

Full Question:
Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).

The result should be like
   A → 1,
   Z → 26,
   AA → 27, (Problem line indicates  'AA=26', but it's somehow strange. (i.e. Z=26)
   ZBC → 17631.

When considering only capitals, following Java function converts alphabet to decimal.  Excepting input.length, you can use in C program directly.

/* alphabet to decimal */
public int alphaToDecimal(char input[]){
  int ret = 0;  
  int a, b;  
  int i, j;  
  for (i=0; i<input.length; i++) {  
    a = input[i] - 'A' + 1;  
    b = 1; // you can use Math.pow();  
    for(j=0; j<input.length-i-1;j++)  
      b *= 'Z'-'A' + 1;  
    ret += a*b;  
  }  
  return ret; 
}

April 09, 2011

Comparison Between Hashtable and HashMap in Java

The HashMap class is roughly equivalent to Hashtable. Both provide key-value access to data. The Hashtable is one of the original collection classes in Java. HashMap is part of the Java 2, v1.2. The key difference between the two is that access to the Hashtable is synchronized on the table while access to the HashMap isn't. You can add it, but it isn't there by default. Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't. If you change the map while iterating, you'll know. And, a third difference is that HashMap permits null values in it, while Hashtable doesn't.

So, if you your process is multi-threaded, then it's good idea to select Hashtable. However there is a way of making Hashmaps thread safe using Collections.synchronizedMap(new Hashmap() ). If my Java version is 1.5 or higher, then I have the option of using ConcurrentHashMap.

One more, be careful with the class names, HashMap and Hashtable.

By the way, people tends to use HashMap rather than Hashtable. I don't know the reason, anyway, it's comfortable to use.