CareerCup

with O(1) time! is this even possible??
Do u mean something like a hashmap where u give the key and get the value? The best searching takes o(logn) time atleast as far as I know.

First of all I have written the program for dollars and the same can be applied or extended to cents or any other currency.
The answer to the next part of the question where 30 is divided as 25+1+1+1+1+1 is not true. If u go thru the logic properly u will see that u get 30 = 10+10+5+5 which is what a coin vending machine actually gives.

package google;

public class ChangeVendingMachine {


private boolean isPossible(int amt){
if(amt == 5 || amt == 10 || amt == 20 || amt == 50 || amt ==100){
return true;
}

return false;
}

private int getHighestPossible(int amt){
assert(!(amt == 0));

if(amt > 100){
return 100;
}
else if(amt > 50){
return 50;
}

else if(amt > 20){
return 20;
}

else if(amt > 10){
return 10;
}
else if(amt >= 5){
return 5;
}

else{
System.out.println("Cant return any more notes!");
return 0;
}
}


public void getChange(int amt){

if(amt == 0){
System.out.println("Amount is Zero!");
return;
}
while(amt > 0){

if(amt == 5){
System.out.println(amt);
amt = amt - 5;
return;
}

int mid = amt/2;

if(isPossible(mid) == true){
System.out.println(mid);
amt = amt - mid;
}

else {
int highPossible = getHighestPossible(mid);
System.out.println(highPossible);
amt = amt - highPossible;
}
}

}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ChangeVendingMachine obj = new ChangeVendingMachine();
obj.getChange(30);

}
}
*****************output******************

10
10
5
5

package google;

public class ChangeVendingMachine {


private boolean isPossible(int amt){
if(amt == 5 || amt == 10 || amt == 20 || amt == 50 || amt ==100){
return true;
}

return false;
}

private int getHighestPossible(int amt){

assert(!(amt == 0));

if(amt > 100){
return 100;
}
else if(amt > 50){
return 50;
}

else if(amt > 20){
return 20;
}

else if(amt > 10){
return 10;
}
else if(amt >= 5){
return 5;
}

else{
System.out.println("Cant return any more notes!");
return 0;
}
}


public void getChange(int amt){

if(amt == 0){
System.out.println("Amount is Zero!");
return;
}


while(amt > 0){

if(amt == 5){
System.out.println(amt);
amt = amt - 5;
return;
}

int mid = amt/2;

if(isPossible(mid) == true){
System.out.println(mid);
amt = amt - mid;
}

else {
int highPossible = getHighestPossible(mid);
System.out.println(highPossible);
amt = amt - highPossible;
}
}

}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ChangeVendingMachine obj = new ChangeVendingMachine();
obj.getChange(55);

}
}

i%3 is necessary because if i am incrementing one character at a time in the input string and so, in the out put string, i dont want all these combinations to be appended.
Ex if my input is abcdef and the output is of length say 3, then i am checking for
abc,bcd,cde,def but in the output string, i only want abcdef and not abc+bcd+cde+def.

We can use the API's provided by Java. This will be the most efficient method.

package google;

public class RemoveInput2FromInput1 {

private String a,b;

public RemoveInput2FromInput1(String a, String b) {
// TODO Auto-generated constructor stub

this.a = a;
this.b = b;

assert(!this.a.equals(null));
assert(!this.b.equals(null));
}

private void removeExp(){
String out = a.replaceAll(b,"");
assert(!out.equals(null));
System.out.println(out);
assert(out.equals("abcthabdshhtexyzaaa"));
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RemoveInput2FromInput1 obj = new RemoveInput2FromInput1("abcthabdtheshhtexyztheaaa","the");
obj.removeExp();
}

}

package google;

import java.util.concurrent.ArrayBlockingQueue;

public class CommonAncestor {

private class Node {
int data;
Node left;
Node right;
Node parent;
}

Node root;

private void constructTree(int data) {

if (root == null) {
root = new Node();
root.data = data;
root.left = null;
root.right = null;
root.parent = null;
return;
}

Node cur = root;

while (cur.left != null && data < cur.data) {
cur = cur.left;
}

while (cur.right != null && data > cur.data) {
cur = cur.right;
}

Node temp = new Node();

temp.data = data;
temp.left = null;
temp.right = null;

if (data < cur.data) {
cur.left = temp;
}
else {
cur.right = temp;
}
temp.parent = cur;
}

private void bfs() {

ArrayBlockingQueue<Node> Q = new ArrayBlockingQueue<Node>(20);

if (root == null) {
System.out.println("Invalid Tree!!!");
return;
}

Q.add(root);

while (Q.isEmpty() == false) {

Node tmp = Q.remove();

if (tmp.left != null)
Q.add(tmp.left);

if (tmp.right != null)
Q.add(tmp.right);

System.out.println(tmp.data);
}
}

private void findCommonNode(Node n1 , Node n2){

int node1= n1.data;
int node2 = n2.data;

int low = Math.min(node1, node2);
int high = Math.max(node1, node2);


Node cur = root;

while(high < cur.data && cur.left != null){
cur = cur.left;
}

while(low > cur.data && cur.right != null){
cur = cur.right;
}

assert (!(cur.equals(null)));
System.out.println("The Common Node for Nodes "+ n1.data + " and "+n2.data+" is : "+cur.data);

}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

CommonAncestor obj = new CommonAncestor();
obj.constructTree(5);
obj.constructTree(2);
obj.constructTree(7);
obj.constructTree(1);
obj.constructTree(3);
obj.constructTree(6);
obj.constructTree(9);
obj.bfs();


Node n1 = obj.new Node();
Node n2 = obj.new Node();


n1.data = 3;
n2.data = 1;

obj.findCommonNode(n1, n2);
}

}

package google;

import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;

public class Dates {

private Date d1 = new Date();
private Calendar c1;
private Calendar c2;

private int numYears;
private int numMonths;
private int numDays;

private void initDates(){
c1 = new GregorianCalendar(2006,06,11);
c2 = new GregorianCalendar(2008,06,21);
}

private int getNumYears(){
int numYears = Math.abs(c1.get(Calendar.YEAR) - c2.get(Calendar.YEAR));
return numYears;
}

private int getNumDays(){

int dayOfTheYear = c1.get(Calendar.DAY_OF_YEAR);
int daysRemaining = 365 - c1.get(Calendar.DAY_OF_YEAR);
return daysRemaining;
}

private int getDiff(){
int dayOfTheYearC1 = c1.get(Calendar.DAY_OF_YEAR);//DAY_OF_YEAR;
int dayOfTheYearC2 = c2.get(Calendar.DAY_OF_YEAR);

int diff = dayOfTheYearC2 - dayOfTheYearC1;
return diff;
}


private int calcNumDays(){

Integer numYears = getNumYears();
int numDays = 0;

if(numYears == null){
System.out.print("Null Number of Years!");
return 0;
}

while(numYears > 1){
numDays = numDays + 365;
numYears--;
}

if(numYears == 1){
int numDaysinThisyear = getNumDays();
int numDaysTotal = numDaysinThisyear + c2.get(Calendar.DAY_OF_YEAR);
return numDays + numDaysTotal;
}

else {
numDays = numDays+getDiff();
return numDays;
}
}


/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

Dates obj = new Dates();
obj.initDates();
int numDays = obj.calcNumDays();
System.out.println(numDays);
}

}

Not a completely correct program..

package google;

import java.util.ArrayList;
import java.util.HashMap;

public class CrossWord {

//private char [][] puzzle;
private ArrayList<String> puzzle = new ArrayList<String>();
private HashMap<String,Integer> myMap = new HashMap<String,Integer>();

public CrossWord(){
puzzle.add("aerops");
puzzle.add("bharls");
puzzle.add("wrislo");
puzzle.add("asnktq");
}

private void createHashMap(){
int i = 0;

int row = 0;
int col = 0;

while(i < puzzle.size()){
String key = getWord(i,-1);
myMap.put(key,0);
i++;
}
while (col < (puzzle.get(row).length() )){
String key = getWord(-1, col);
myMap.put(key,0);
col++;
}

}

private String getWord(int row ,int col){
char[][] puzzleArr = null;
String tempo = null;
String temp = null;


if(row >= 0 && row < puzzle.size()){
temp = puzzle.get(row);
row++;
}

else{
if(col >= 0){
for(int i = 0; i < puzzle.size() ; i++){
char[] temp1= puzzle.get(i).toCharArray();
Character c = temp1[col];
tempo += (c.toString());
}
String correctWord = tempo.substring(4);
return correctWord;
}
}
return temp;

}

public void display(){
System.out.println(myMap.keySet().toString());
}

public void isPresent(String word){
if(myMap.keySet().contains(word)){
System.out.println("Found!");
}
else{
System.out.println("Not Found!");
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

CrossWord obj = new CrossWord();
obj.createHashMap();
obj.isPresent("slow");
}
}

I have given a sample start.. feel free to add to it.

package google;

import java.util.ArrayList;
import java.util.Random;

public class Cards {

private class card {
char suite;
Integer number;
}

private ArrayList<card> cardArray = new ArrayList<card>();

public Cards() {
// TODO Auto-generated constructor stub

char Suite = 'S';

switch (Suite) {

case 'S': {
for (int i = 1; i <= 10; i++) {
card c = new card();
c.number = i;
c.suite = 'S';
cardArray.add(c);
}

card A = new card();
A.number = 'A';
A.suite = 'S';
cardArray.add(A);

card J = new card();
J.number = 'J';
J.suite = 'S';
cardArray.add(J);

card Q = new card();
Q.number = 'Q';
Q.suite = 'S';
cardArray.add(Q);

card K = new card();
K.number = 'K';
K.suite = 'S';
cardArray.add(K);
Suite = 'C';
}
case 'C': {
for (int i = 1; i <= 10; i++) {
card c = new card();
c.number = i;
c.suite = 'C';
cardArray.add(c);
}

card A1 = new card();
A1.number = 'A';
A1.suite = 'C';
cardArray.add(A1);

card J1 = new card();
J1.number = 'J';
J1.suite = 'C';
cardArray.add(J1);

card Q1 = new card();
Q1.number = 'Q';
Q1.suite = 'C';
cardArray.add(Q1);

card K1 = new card();
K1.number = 'K';
K1.suite = 'C';
cardArray.add(K1);
Suite = 'H';
}
case 'H': {
for (int i = 1; i <= 10; i++) {
card c = new card();
c.number = i;
c.suite = 'H';
cardArray.add(c);
}

card A2 = new card();
A2.number = 'A';
A2.suite = 'H';
cardArray.add(A2);

card J2 = new card();
J2.number = 'J';
J2.suite = 'H';
cardArray.add(J2);

card Q2 = new card();
Q2.number = 'Q';
Q2.suite = 'H';
cardArray.add(Q2);

card K2 = new card();
K2.number = 'K';
K2.suite = 'H';
cardArray.add(K2);
Suite = 'D';
}
case 'D': {
for (int i = 1; i <= 10; i++) {
card c = new card();
c.number = i;
c.suite = 'D';
cardArray.add(c);
}

card A2 = new card();
A2.number = 'A';
A2.suite = 'D';
cardArray.add(A2);

card J2 = new card();
J2.number = 'J';
J2.suite = 'D';
cardArray.add(J2);

card Q2 = new card();
Q2.number = 'Q';
Q2.suite = 'D';
cardArray.add(Q2);

card K2 = new card();
K2.number = 'K';
K2.suite = 'D';
cardArray.add(K2);
break;
}

}

}

public void display(){
for(int i = 0; i < cardArray.size() ; i++){
if(cardArray.get(i) != null){
if(cardArray.get(i).number <= 10){
System.out.println(cardArray.get(i).suite+ " " + cardArray.get(i).number);
}
else{
System.out.println(cardArray.get(i).suite+ " " + (char)cardArray.get(i).number.intValue());
}
}
}
}

public void shuffle(){

for(int i = 0; i < 52; i++ ){
System.out.println("");
Random rand = new Random();

int r = i + ((Math.abs(rand.nextInt())) % 52-i);

//System.out.println(i + " "+ r);
card temp = cardArray.get(i);
card temp2 = cardArray.get(r);

if(temp.number <= 10){
System.out.print(temp.suite+ " " + temp.number);
}
else{
System.out.print(temp.suite+ " " + (char)temp.number.intValue());
}

if(temp2.number <= 10){
System.out.print(" " +temp2.suite+ " " + temp2.number);
}
else{
System.out.print(" "+temp2.suite+ " " + (char)temp2.number.intValue());
}

cardArray.add(i, cardArray.get(r));
cardArray.add(r, temp);
}
//System.out.println("");
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Cards obj = new Cards();
//obj.display();
obj.shuffle();
//obj.shuffle();
//obj.display();
}

}

I also have another solution if the pattern Foo is given before hand and we have a source string in which we shud find if the pattern is unique.

package google;

import java.util.HashMap;

public class FindUniqueRegExp {

private String src;
private String pattern;
private HashMap<String, Integer> myMap = new HashMap<String, Integer>();

public FindUniqueRegExp(String src, String pattern) {
// TODO Auto-generated constructor stub
if (src != null && pattern != null) {
this.src = src;
this.pattern = pattern;
}
}

private void createHashMap() {
int index = 0;
if (src == null) {
System.out.println("Invalid Source");
return;
}
if (pattern == null) {
System.out.println("Invalid Pattern");
return;
}

while ((index + pattern.length()) <= (src.length() - 1)) {

String key = (String) src
.substring(index, index + pattern.length());
Integer count = myMap.get(key);

if (count == null) {
myMap.put(key, 1);
// index++;
} else
myMap.put(key, count + 1);
index++;
}
}

private void isUnique() {

if (pattern != null) {
int value = myMap.get(pattern);
if (value == 1) {
System.out.println("Pattern " + pattern + " is unique!");
} else {
System.out.println("Pattern " + pattern + " is not unique!");
}
}

}

public void findIfUnique() {
createHashMap();
isUnique();
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

FindUniqueRegExp obj = new FindUniqueRegExp("jhkhFookjjk", "Foo");
obj.findIfUnique();

}

}

import java.util.ArrayList;
import java.util.HashMap;


public class nonRepeatingExpression {

private String src;
private HashMap<Character,Integer> myMap = new HashMap<Character,Integer>();
private char [] charArr;

public nonRepeatingExpression(String src) {
// TODO Auto-generated constructor stub
this.src = src;
}
private void constructHashMap(){

if(src == null){
System.out.println("Invalid String");
return;
}

charArr = src.toCharArray();

for(int i = 0; i < src.length()-1; i++){
Integer count = myMap.get(charArr[i]);
if(count == null){
myMap.put(charArr[i],1);
}
else{
myMap.put(charArr[i],count+1);
}
}
}


private void findUnique(){
ArrayList<Integer> valueList = new ArrayList<Integer>(myMap.values());
ArrayList<Character> keyList = new ArrayList<Character>(myMap.keySet());


for(int i = 0; i < valueList.size();i++ ){
if(valueList.get(i) == 1){
System.out.println(keyList.get(i));
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
nonRepeatingExpression obj = new nonRepeatingExpression("jkkjFoohkkh");
obj.constructHashMap();
obj.findUnique();
}

}

Can some one give some hints please?

delete [] array_name

Can you please explain the question?

package careercup;

public class CheckIfPrime {

public boolean hasFactors(int num) {
int i = 2;

int sqroot = (int) Math.sqrt(num);
int n = 1;

while (i <= sqroot) {
int generated_prime = 6 * n - 1;
int generated_prime2 = 6 * n + 1;
if (num % generated_prime == 0) {
System.out.println(generated_prime);
return true;
}
if (num % generated_prime2 == 0) {
System.out.println(generated_prime2);
return true;
}
i++;
n++;
}
int k = 2;
while (k < num / 2) {
if (num % k == 0) {
System.out.println(k);
return true;
}
k++;
}
return false;
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CheckIfPrime obj = new CheckIfPrime();
boolean hasFactors = obj.hasFactors(49);
if (hasFactors == true) {
System.out.println("Not prime");
} else
System.out.println("Prime number");
}

}

package careercup;

import java.util.ArrayList;

public class MaximalSubSection {

private final Integer MAX = 5;
private ArrayList<Integer> array = new ArrayList<Integer>(MAX);

private void constructArray(){
for(int i = 0; i < MAX; i++){
array.add(i,i);
}
}

private Integer findMaxSum(){

int sum=0;

for(int i = 0 ; i < array.size(); i++){
sum = max (sum,sum+array.get(i));
}
return sum;

}
private int max(int a, int b) {
// TODO Auto-generated method stub
return ( a > b ? a : b );
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MaximalSubSection obj = new MaximalSubSection();

obj.constructArray();
int sum = obj.findMaxSum();

System.out.println(sum);
}
}

/*Write code to reverse a singly linked list*/
#include<stdlib.h>
#include<stdio.h>

struct NODE{
int data;
struct NODE* next;
};
typedef struct NODE* node;

node getNode(){
node x;
x=(node)malloc(sizeof(struct NODE));
return x;
}
node createList(node head,int data){
node temp,cur;
if(!head){
head=getNode();
head->data=0;
head->next=NULL;
}
cur=head;
while(cur->next){
cur=cur->next;
}
temp=getNode();
temp->data=data;
temp->next=NULL;
cur->next=temp;
return head;
}
node reverseList(node head){
node cur,next,prev;
prev=NULL;
cur=head;
next=cur->next;
while(cur->next){
cur->next=prev;
prev=cur;
cur=next;
next=next->next;
}
head=prev;
return head;
}
void display(node head){
node cur;
if(!head){
printf("\nEmpty list");
return;
}
cur=head;
printf("\n");
while(cur->next){
printf("%d ",cur->data);
cur=cur->next;
}
printf("\n\n");

}
int main(){
int i;
node head;
head=NULL;
for(i=1;i<10;i++)
head=createList(head,i);
printf("\nThe original list is :\n");
display(head);
printf("\nThe reversed list is :\n");
head=reverseList(head);
display(head);
return(0);
}
/*
The original list is :

0 1 2 3 4 5 6 7 8


The reversed list is :

8 7 6 5 4 3 2 1

Press any key to continue . . .*/

/*Given a matrix (2D array) of m x n elements (m rows, n columns), write a function that
prints the elements in the array in a spiral manner.
Sample input matrix:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

Correct output for above sample input:
1 2 3 4 5 6 12 18 24 30 29 28 27 26 25 19 13 7 8 9 10 11 17 23 22 21 20 14 15 16*/


#include<stdio.h>
#include<stdlib.h>

void printLeftRight(int arr[][6],int startRow, int endRow,int startCol,int endCol){
int i,j;
j=startRow;
for(i=startCol;i<=endCol;i++){
printf("%d ",arr[j][i]);
}
}

void printTopBottom(int arr[][6],int startRow, int endRow,int startCol,int endCol){
int i,j;
j=endCol;
for(i=startRow;i<endRow;i++){
printf("%d ",arr[i][j]);
}
}

void printRightleft(int arr[][6],int startRow, int endRow,int startCol,int endCol){
int i,j;
j=endRow;
for(i=endCol;i>startCol;i--){
printf("%d ",arr[j][i]);
}
}

void printBottomTop(int arr[][6],int startRow, int endRow,int startCol,int endCol){
int i,j;
j=startCol;
for(i=endRow;i>=startRow;i--){
printf("%d ",arr[i][j]);
}
}

void printSpiral(int arr[][6],int startRow, int endRow,int startCol,int endCol){
if(startRow<endRow && startCol<endCol){
printLeftRight(arr,startRow,endRow,startCol,endCol);
printTopBottom(arr,startRow+1,endRow,startCol,endCol);
printRightleft(arr,startRow,endRow,startCol,endCol);
printBottomTop(arr,startRow+1,endRow,startCol,endCol);
startRow=startRow+1;
endRow=endRow-1;
startCol+=1;
endCol-=1;
printSpiral(arr,startRow,endRow,startCol,endCol);
}
else if(startRow=endRow){
printLeftRight(arr,startRow,endRow,startCol,endCol);
}

}

int main()
{

int i,j,a[6][6],num=1;
for(i=0;i<5;i++){
for(j=0;j<6;j++){
a[i][j]=num;
num++;
}
}
for(i=0;i<5;i++){
for(j=0;j<6;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}
printSpiral(a,0,4,0,5);
return (0);
}

/*1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
1 2 3 4 5 6 12 18 24 30 29 28 27 26 25 19 13 7 8 9 10 11 17 23 22 21 20 14 15 16
Press any key to continue . . .*/

/*give an efficient algo for searching for an elmt in a matrix sorted by row and coln.*/

#include<stdio.h>
#include<stdlib.h>

void findcol(int arr[],int numcols,int ele){
int i;

for(i=0;i<numcols;i++){
if(arr[i]==ele){
printf("\nElement %d is found at coloun %d ",ele,i);
return;
}
}

}
void findElem(int arr[][5],int numrows,int numcols,int ele,int startrow,int endrow){
//int startcol,endcol;
int testrow;
int i=0,j=0;


testrow=(endrow+startrow)/2;

if(arr[testrow][0]==ele){
printf("\nElement found in %d row and 0 col \n",testrow);
return;
}
else if(arr[testrow][numcols]==ele){
printf("\nElement found in %d row and %d col \n",testrow,numcols);
return;
}
else if(arr[testrow][0]>ele ){
endrow=testrow;
findElem(arr,numrows,numcols,ele,startrow,endrow);
}
else if(arr[testrow][0]<ele&&arr[testrow][numcols]<ele){
startrow=testrow;
findElem(arr,numrows,numcols,ele,startrow,endrow);
}
else if(arr[testrow][0]<ele&&arr[testrow][numcols]>ele){
findcol(arr[testrow],numcols,ele);
}
}

int main()
{
int arr[5][5],i,j,num=0;

for(i=0;i<5;i++){
for(j=0;j<5;j++){
arr[i][j]=num;
num++;
}
}

for(i=0;i<5;i++){
printf("\nRow %d : ",i);
for(j=0;j<5;j++){
printf("%d ",arr[i][j]);
}
}

findElem(arr,4,4,15,0,5);
return(0);
}

/*find the n th largest number in an array (using dynamic prog)*/


#include<stdio.h>
#include<conio.h>

int findLargest(int arr[],int len){
int largest,index;
int i=0;
largest=arr[0];
printf("\nThe array is : ");
for(i=0;i<len;i++){
printf("%d ",arr[i]);
}
for(i=0;i<len;i++){
if(arr[i]>largest){
largest=arr[i];
index=i;
}
}
arr[index]=0;
return largest;
}


int findMthLargest(int arr[],int len,int m){
int i=1;
int largest;
while(i<=m){
largest=findLargest(arr,len);
i++;
}
return largest;
}

int main()
{
int arr[9]={1,2,3,4,5,6,2,2,1};
int len=9;
int m=2;
int MthLargestnum=findMthLargest(arr,len,m);
printf("\nThe %d Largest number in the array is %d\n",m,MthLargestnum);
return(0);
}


/*The array is : 1 2 3 4 5 6 2 2 1
The array is : 1 2 3 4 5 0 2 2 1
The 2 Largest number in the array is 5
Press any key to continue . . */.

Symbolic links:
-----------------


A symbolic link, also termed a soft link, is a special kind of file that points to another file, much like a shortcut in Windows or a Macintosh alias. Unlike a hard link, a symbolic link does not contain the data in the target file. It simply points to another entry somewhere in the file system. This difference gives symbolic links certain qualities that hard links do not have, such as the ability to link to directories, or to files on remote computers networked through NFS. Also, when you delete a target file, symbolic links to that file become unusable, whereas hard links preserve the contents of the file.

To create a symbolic link in Unix, at the Unix prompt, enter the following command:
ln -s source_file myfile Replace source_file with the name of the existing file for which you want to create the symbolic link (this file can be any existing file or directory across the file systems). Replace myfile with the name of the symbolic link. The ln command then creates the symbolic link. After you've made the symbolic link, you can perform an operation on or execute myfile, just as you could with the source_file. You can use normal file management commands (e.g., cp, rm) on the symbolic link.

Note: If you delete the source file or move it to a different location, your symbolic file will not function properly. You should either delete or move it. If you try to use it for other purposes (e.g., if you try to edit or execute it), the system will send a "file nonexistent" message.


How it works:

Early implementations of symbolic links would store the symbolic link information in standard disk blocks, much like regular files. The file contained the textual reference to the link’s target, and an indicator denoting it as a symbolic link.

This arrangement proved somewhat slow, and could waste disk-space on small systems. An innovation called fast symlinks allowed storage of the link-text within the standard data structures used for storing file information on disk (inodes). This space generally serves to store the chain of disk blocks composing a file (60 bytes on the Unix File System). This simply means that users can reference shorter symbolic links quickly. Systems with fast symlinks often fall back to using the older method if the path and filename stored in symlink exceeds the available space in the inode, or for disk compatibility with other or older versions of the operating system. The original style has become retroactively termed slow symlinks.

Although storing the link value inside the inode saves a disk block and a disk read, the operating system still needs to parse the pathname information in the link, which always requires reading an additional inode and generally requires reading other — potentially many — directories, processing both the list of files and the inodes of each of them until it finds a match with the link pathname components. Only when a link points to a file inside the same directory do fast symlinks provide significant gains in performance.

Thread safe functions:
---------------------------


In C language, local variables are dynamically allocated on the stack. Therefore, any function that does not use static data or other shared resources is trivially thread-safe, as in the following example:

/* thread-safe function */
int diff(int x, int y)
{
        int delta;

        delta = y - x;
        if (delta < 0)
                delta = -delta;

        return delta;
}

The use of global data is thread-unsafe. Global data should be maintained per thread or encapsulated, so that its access can be serialized.

Race Condition :
-----------------------

A race condition occurs when multiple processes access and manipulate the same data concurrently, and the outcome of the execution depends on the particular order in which the access takes place.

A race condition is of interest to a hacker when the race condition can be utilized to gain privileged system access.

Consider the following code snippet which illustrates a race condition:

if(access("/tmp/datafile",R_OK)==0){
	fd=open("/tmp/datafile
        process(fd);
        close(fd);

This code creates the temporary file /tmp/datafile and then opens it.

The potential race condition occurs between the call to access() and the call to open().

If an attacker can replace the contents of /tmp/datafile between the access() and open() functions, he can manipulate the actions of the program which uses that datafile. This is the race.

It can be difficult to exploit a race condition, because you may have to "run the race" many times before you "win." You may have to run the vulnerable program and the vulnerability testing tool thousands of times before you get the expolit code to execute after the vulnerability opens and before the vulnerability closes. It is sometimes possible to give the attack an extra edge by using `nice` to lower the priority of the legitimate suid program.

Improper use of the function calls access(), chown(), chgrp(), chmod(), mktemp(), tempnam(), tmpfile(), and tmpnam() are the normal causes of a race condition.

Should Pointers always be initialized?


Notice that in the above example, pointer is initialized to point to a specific memory address before it is used. If this was not the case, it could be pointing to anything. This can lead to extremely unpleasant consequences to the program. For instance, the operating system will probably prevent you from accessing memory that it knows your program doesn't own: this will cause your program to crash. If it let you use the memory, you could mess with the memory of any running program--for instance, if you had a document opened in Word, you could change the text! Fortunately, Windows and other modern operating systems will stop you from accessing that memory and cause your program to crash. To avoid crashing your program, you should always initialize pointers before you use them.

virtual destructors
------------------------


void function()
{
Sample* p = new Derived;
delete p;
}
Since Sample does not have a virtual destructor, the delete p invokes the destructor of the class of the pointer (Sample::~Sample()), rather than the destructor of the most derived type (Derived::~Derived()). And as you can see, this is the wrong thing to do in the above scenario.

Armed with this information, you can now answer the question.

A class must have a virtual destructor if it meets both of the following criteria:

You do a delete p.
It is possible that p actually points to a derived class.

pointer vs reference
----------------------
when using pointers, the address must be dereferenced using the *, whereas,when using references, the address is dereferenced without using any operators at all!

The main effect of this is that the address can directly be manipulated if it is a pointer.We can do things such as: pi++;
to increment to the next address. This is not possible using references. Therefore, to summarize, a pointer can point to many different objects during its lifetime, a reference can refer to only one object during its lifetime.

References are the preferred way of indirectly accessing a variable. They are also a little
safer than pointers and, in some cases, are the only way to achieve a particular result such
as overloading certain operators. Consider the following:
enum day
{
Sunday, Monday, ...
};
If we define a variable;
day x;
pi
i
ri
addr
addr addr
and we wanted to write a method to overload the ++ operator such that the statement
++x;
increments x to the next day, we could write the following:
day &operator++(day &d)
{
d = (day)(d + 1);
return d;
}
Using pointers, we may think that the following declaration would work:
day *operator++(day *d);
However, this statement will not even compile because every overloaded operator function must either be a member of a class, or have a parameter of type T, T &, or T const &, where T is a class or enumeration type. So in this particular case, using a reference is the only way to do it.

bool isSymmetric(node root)
{
	int i=0;

	for (each child of the root)
	{
		mark(node,i)
			queue.enque(node);
		i++
	}
	while(!q.empty)
	{
		for (all child of the root node)
			child=getNode(queue);
		if(child!=NULL)
		{
			if(child->left)
			{
				list1.insert(mark(child,0));
				child=child->left;
			}
			if(child->middle)
			{
				list1.insert(mark(child,1));
				child=child->middle;
			}
			if(child->right)
			{
				list1.insert(mark(child,2));
				child=child->right;
			}
		}
	}
	for(i=0 - lenght of list1,list2,list3)
	{
		if (list1[i]!=list2[i]||list2[i]!=list3[i]||list1[i]!=list3[i])
		{
			print("Not Symmetrical");
			return false;
		}
		else
		{
			printf("Symmetrical");
			return true;
		}
	}
}

Given a node, We can convert its left subtree into a list and the right sub tree into a list. Now we can compare the lists . We have the following possibilities :
1. If one of the lists is longer than the other, then we know that they are not similar.
2. We can have a pointer for each of the lists and keep comparing the values. In case
we find a mismatch, then it is not symmentrical.

node convert_to_list(node *T)
{
	node *STL,*STR,*temp;
	
	if(T!=NULL)
	{
		STL=convert_to_list(T->left);
		STR=convert_to_list(T->right);
		// so now we have both SubTreeLeft and SubTreeRight and pointers STL and STR pointing to the beginning of 
		// the lists.So we compare them

		node *head1=STL;
		node *head2=STR;

		while(STL->right && STR->right)
		{
			if(STL->data!=STR->data)
			{
				printf("not symmetrical");
				break;
			}

			STL=STL->right;
			STR=STR->right;
		}
		else if(STR->right)
		{
			// the length of STL and STR are diff. so they are not symmentrical
			printf("not symmetrical");
			break;
		}
		else if(STL->right)
		{
			// the length of STL and STR are diff. so they are not symmentrical
			printf("not symmetrical");
			break;
		}
		else printf("Symmetrical");
		return T;
	}
	else
		return NULL;
}

The Following is an algorithm to find the strong component of a graph and this is a tweak of DFS. If we have a strong component in a graph, then we have a cycle.

S <- empty stack
i <- 0
for(all x in V) 
do 
{
	num(v)<-0
}
for (all x in V)
do
{
	if (num(x) = 0) 
		then 
		STRONG(x);
}

STRONG(v)
{
	i<-i + l;
	lowlink(v)<-i
		push v onto the stack S
		for (all w in adj(v))
		{
			num(v)<-i;
			if (num(w) = 0)
			{
				STRONG(w)
					lowlink( v)<-min(lowlink( v), lowlink( w))
			}

			else if (num(w) < num(v) )
			{
				if (w in S)
					( lowLink(v)<-min(Lowlink(v), num(w)));
			}
		}
		if (Lowlink(v) = num(v))
		{
		pop vertices off the stack while num(stack top)> num(v)
		all those vertices popped off the stack are output as a strong component
		}
end STRONG

we can build a hash table and set all the first names from the first file.
xor the hash value of the first names from the second file. Do a lookup on the hashtable and find all the names that have a 0. So these will be the repeated names. But to ensure the uniqueness of the names, now we can pick up all the names which has a zero in the hash table, from file one and do a binary search in file two for it. If it is found, then that is the common name.

does this mean that the 2 lists are sorted???

memory space contains a few different types of “objects” such as threads, manged object heaps, managed loader heap, native heaps, dll’s, and virtual allocations, so a good place to start is by running a performance monitor log with the following counters.

Process/Virtual Bytes
Process/Private Bytes
.net CLR Memory/# Bytes in all Heaps
.net CLR Memory/% Time in GC
.net CLR Memory/Large Object Heap size
.net CLR Loading/Bytes in Loader Heap
.net CLR Loading/Current Assemblies

The main thing to look for is if private bytes grow at approximately the same rate as virtual bytes and if # Bytes in all Heaps seem to follow the same curve.

If the private bytes keep increasing but # Bytes in all Heaps do not, you’re likely looking at a native memory leak (i.e. you are leaking in a COM component or similar) but if # Bytes in all heaps increase at the same rate as private bytes your leak is likely in managed code.

Much the same way, if you see a steady increase of virtual bytes but your private bytes stay pretty steady, your application probably has a problem where it is reserving a lot of virtual memory that it’s not using.

fork() is the name of the system call that the parent process uses to "divide" itself ("fork") into two identical processes. After calling fork(), the created child process is actually an exact copy of the parent - which would probably be of limited use - so it replaces itself with another process using the system call exec().

When exception occurs, interrupt is generated and control is transferred to the operating system. Operating System, in turn, calls the exception handler that inspects the function call sequence starting from the current function from where the exception originated, and performs its job of stack unwinding and control transfer. We can write our own exception handler and register it with the operating system that it would call in the event of an exception.

void g()
{
throw std::exception();
}

void f()
{
std::string str = "Hello"; // This string is newly allocated
g();
}

void main()
{
try
{
f();
}
catch(...)
{ }
}

The flow of the program:

* main() calls f()
* f() creates a local variable named str
* str constructor allocates a memory chunk to hold the string "Hello"
* f() calls g()
* g() throws an exception
* f() does not catch the exception.

Because the exception was not caught, we now need to exit f() in a clean fashion.
At this point, all the destructors of local variables previous to the throw
are called - This is called 'stack unwinding'.

* The destructor of str is called, which releases the memory occupied by it.

As you can see, the mechanism of 'stack unwinding' is essential to prevent resource leaks - without it, str would never be destroyed, and the memory it used would be lost forever.

* main() catches the exception
* The program continues.

The 'stack unwinding' guarantees destructors of local variables (stack variables) will be called when we leave its scope.

C++ exception handling:

The block of code you want to try starts with specifying the try command and surrounding the block with curly braces. Within this block, you can throw any occurring errors with the throw command. You must specify an error and this should be a class but we will get to this later. Immediately after the try-block is closed, the catch-block starts. Here the error handling code is placed. The following piece of pseudo code will show the idea:

try {
___...
___...
___throw Exception()
___...
___...
} catch( Exception e )
{
___...
___...
}

In this example, Exception is a defined class with a constructor with no parameters (as identified by the throw-call). It would be useful to have some info on what kind of error occurred. This could be done in two ways. We could define different exception-classes and throw them according to which error occurred. We also could give the class a parameter containing an error message and allow the class to display the message.

Why cant one throw exception from destructor.

# If a destructor, called by the language runtime during stack unwinding, terminates
with an exception the whole program is terminated.

# It becomes difficult (some people say impossible) to design predictable (correct)
containers in the face of throwing destructors.

# Unspecified (and thus undefined) behavior of some parts of C++ language in the face
of throwing destructors.

# It is unpleasant to think about the fate of an object that happened to throw
from its destructor. In other words, what happens to the object for which the
destruction process has failed?

BNP can u elaborate please?

void ReverseWords (char str[])
{
	int start = 0, end = 0, length;
	length = strlen(str);
	while (end < length) {
		if (str[end] != ' ') { /* Skip non-word characters */
			start = end;
			while (end < length && str[end] != ' ') end++;
			end--;
			ReverseString(str, start, end);
		}
		end++; /* Advance to next token */
	}
return;
}

void ReverseString (char str[], int start, int end) 
{ 
        char temp; while (end > start) {
	/* Exchange characters */
	temp = str [start];
	str [start] = str [end] ;
	str [end] = temp;
	/* Move indices towards middle */ start++; end--;
} 
	return; 
}

Is this the same as set and reset bits using a hash table for each state of the machine

void ReverseString (char str[], int start, int end) 
{ char temp; while (end > start) {
	/* Exchange characters */
	temp = str [start];
	str [start] = str [end] ;
	str [end] = temp;
	/* Move indices towards middle */ start++; end--;
} 
return;
}

Can you please give the code for this?

Jack can you explain your algorithm please? I am not clear about it.