Java : reversing a doubly linkedlist on linear time

Complexity: O(N)

Program:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class DoublyLinkedListNode {
    private int value;
    private DoublyLinkedListNode previous;
    private DoublyLinkedListNode next;

    public DoublyLinkedListNode(int v){
        this.value = v;
        this.previous = null;
        this.next = null;
    }

    public void setPrevious(DoublyLinkedListNode prev){
        this.previous = prev;
    }

    public void setNext(DoublyLinkedListNode n){
        this.next = n;
    }

    public int getValue(){
        return this.value;
    }

    public DoublyLinkedListNode getNext(){
        return this.next;
    }

    public DoublyLinkedListNode getPrevious(){
        return this.previous;
    }
}

 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class ReverseDLinkedList {

    private static DoublyLinkedListNode tail = null;
    private static DoublyLinkedListNode head = null;
    public static void main(String args[]){
        for(int i=0; i < 10; i++){
            DoublyLinkedListNode node = new DoublyLinkedListNode(i);
            if(head == null){
                head = node;
                tail = node;
            }
            if(i != 0){
                tail.setNext(node);
                node.setPrevious(tail);
                tail = node;
            }
        }
        printList(head);

        System.out.println("");
        System.out.println("Reversing the list");

        printList(reverseList(head));
    }

    private static DoublyLinkedListNode reverseList(DoublyLinkedListNode head){
        DoublyLinkedListNode start = head;
        DoublyLinkedListNode temp = null;

        while(head != null){
            temp = head.getNext();
            head.setNext(head.getPrevious());
            head.setPrevious(temp);

            if(head.getPrevious() == null){
                head.setPrevious(start);
                break;
            }
            head = head.getPrevious();
        }
        return head;
    }

    private static void printList(DoublyLinkedListNode head){
        System.out.print("List : ");
        while(head != null){
            System.out.print(head.getValue() + " ");
            head = head.getNext();
        }
    }
}

Output:
run:
List : 0 1 2 3 4 5 6 7 8 9
Reversing the list
List : 9 8 7 6 5 4 3 2 1 0
BUILD SUCCESSFUL (total time: 0 seconds)
                    

implementing malloc in C

#include<stdio.h>

void* Malloc(int );

main(){

int size = 16;

int *a = NULL;

a = (int *)Malloc(size);

int i = 0;

for(i = 0; i < 4; i ++){

a[i] = i;

printf(“a[%d] = %d\n”,i,i);

}

}

void* Malloc(int size) {

int s = size/sizeof(char);

int array[s];

int i = 0;

for(i = 0; i < s; i ++){

array[i] = NULL;

}

return (void *)array;

}

implement 2D array dynamically in C

#include<stdio.h>

#include<stdlib.h>

main() {

int **a;

int n;

printf(“enter the size of n for nxn matrix : “);

scanf(“%d”,&n);

int input[n];

int k = 0;

printf(“enter %d numbers : “,(n*n));

for(k = 0; k < (n*n); k ++){

scanf(“%d”,&input[k]);

}

a = malloc(sizeof(int *) * n);

int i = 0;

for(i = 0; i < n ; i ++ ){

a[i] = malloc(sizeof(int *) * n);

}

int j = 0;

int num = 0;

printf(“\nArray\n\n”);

for(i = 0; i < n; i ++ ) {

for(j = 0; j < n; j ++){

a[i][j] = input[num];

num ++;

//printf(“a[%d][%d] = %d\n”, i, j, a[i][j]);

printf(“%d | “,a[i][j]);

}

printf(“\n”);

printf(“———-\n”);

}

for(i = 0; i < n; i++){

free(a[i]);

}

free(a);

}

output :

enter the size of n for nxn matrix : 3

enter 9 numbers : 1

2

3

4

5

6

7

8

9

Array

1 | 2 | 3 |

———-

4 | 5 | 6 |

———-

7 | 8 | 9 |

———-

remove duplicates from list of integers – C

#include<stdlib.h>

struct node {

int data;

struct node* next;

};

int doHash(int);

void fixInHash(int, struct node**);

void printHash(struct node**);

main(){

int a[] = {2,1,2,3,4,5,4,3,5};

//int a[] = {8,2,9,3,1,4,5,12,4,3,12,15};

int len = sizeof(a)/sizeof(a[0]);

printf(“len : %d\n”,len);

struct node* hashMap[len];

int i = 0;

printf(“Input array : “);

for( i = 0; i < len; i ++ ){

printf(“%d “, a[i]);

}

printf(“\n”);

for( i = 0; i < len; i ++){

hashMap[i] = NULL;

}

for( i = 0; i < len; i ++){

int index = doHash(a[i]);

fixInHash(a[i],&(hashMap[index]));

}

printf(“After removing duplicates : “);

for(i = 0; i < len; i ++ ){

printHash(&hashMap[i]);

}

printf(“\n”);

}

void printHash(struct node** elem){

while((*elem) != NULL){

printf(” %d “,(*elem)->data);

(*elem) = (*elem)->next;

}

}

int doHash(int num){

int a = 1;

int b = 2;

int n = 5;

int ret = 0;

/* we will use hash function as h(x) = (ax + b)mod n */

ret = (a * num + b) % n;

return ret;

}

void fixInHash(int value, struct node** elem) {

struct node* current = NULL;

current = (struct node*) malloc(sizeof(struct node));

int flag = 0;

//printf(“value : %d\n”,value);

if( *elem == NULL){

current->data = value;

current->next = *elem;

*elem = current;

//printf(“null : %d\n”,(*elem)->data);

} else {

//printf(“inside else : %d \n”, (*elem)->data);

while((*elem) != NULL ){

if((*elem)->data == value){

//printf(“match : %d\n”,(*elem)->data);

flag = 1;

break;

}

if((*elem)->next != NULL) {

(*elem) = (*elem)->next;

}else{

break;

}

}

if(flag == 0){

current->data = value;

current->next = *elem;

*elem = current;

//printf(“inside flag : %d\n”,(*elem)->data);

}

}

}

Output :

Input array : 2 1 2 3 4 5 4 3 5

After removing duplicates :  3  4  5  1  2

binary search – c

#include<stdio.h>

#include<stdlib.h>

void doBinarySearch(int [], int , int , int );

main() {

//int a[] = { 0,1,2,3,4,5,6,7,8,9,10 };

int a[] = { 1,2,3,4,5,8,9 };

int num;

int length = sizeof(a)/sizeof(a[0]);

printf(“Enter the number from 0 – 10 : “);

scanf(“%d”,&num);

doBinarySearch(a, 0, length -1, num);

}

void doBinarySearch(int a[], int start, int len, int num) {

if(start > len) {

//printf(“start : %d and len : %d\n”,start,len);

printf(“Number not found\n”);

exit(-2);

}

int mid = (start + len) / 2;

if(num == a[start]){

printf(“start – found at index : %d\n”,start);

exit(0);

}

if(num == a[len]){

printf(“end – found at index : %d\n”,len);

exit(0);

}

if(num == a[mid]){

printf(“mid – found at index : %d\n”,mid);

exit(0);

}

if(num < a[mid]){

//printf(“less: %d – %d\n”, start, (mid-1));

doBinarySearch(a, start, (mid -1), num);

}

if(num > a[mid]){

//printf(“greater : %d – %d\n”, (mid+1),len);

doBinarySearch(a, (mid + 1), len, num);

}

}

sort array of 0s and 1s

#include<stdio.h>

void sort(int [],int);

main(){

int a[] = {0,1,0,0,1,1,1,1,0,0,1,0};

int length = sizeof(a)/sizeof(a[0]);

sort(a,length-1);

}

void sort(int a[],int j){

int i = 0;  int n = j;

while( i < j ) {

while(a[i] == 0 && i < j){

i ++;

}

while(a[j] == 1 && j > i){

j –;

}

if( i < j ){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

for(i = 0; i < n; i ++){

printf(“%d “,a[i]);

}

printf(“\n”);

}

This is O(N) solution

permute the string – C program

#include<stdio.h>

int permuteString(char []);void doPermute(char [], char [], int [], int , int );
main() {
char string[] = “sun”; int stat = permuteString(string);
}
int permuteString(char inString[]) {
int length,i, *used; char *out;
length = strlen(inString);
out = (char *)malloc(length + 1); if(!out) {        return 0; }
/* so that printf doesn’t run past the end of buffer */ out[length] = ”; used = (int *)malloc(sizeof(int) * length);
if(!used) {        return 0; }
/* start with no letters used, so zero array */ for( i = 0; i < length; i ++) {        used[i] = 0; }
doPermute(inString, out, used, length, 0);

free(out);

free(used);

return 1; //success

}

void doPermute(char in[], char out[], int used[], int length, int recurLevel ) {

int i ;

/* base case */

if(recurLevel == length ) {

printf(“%s\n”, out);

return;

}

/* recursive case */

for(i = 0; i < length ; i ++) {

if(used[i]) {

continue;

}

out[recurLevel] = in[i]; /* put current letter in output */

used[i] = 1; /* mark letter as used */

doPermute(in, out, used, length, recurLevel + 1);

used[i] = 0; /* unmark this letter */

}

}

output :

sun

snu

usn

uns

nsu

nus

Build linkedlist at tail/end – C

There are two approaches given in the solution – using addNode() and addNodeWithDummy()

#include<stdio.h>

struct node* addNode();

struct node* addNodeWithDummy();

struct node* Push(struct node**, int);

struct node{

int data;

struct node* next;

};

main(){

struct node* head = NULL;

head = malloc(sizeof(struct node));

head = addNode();

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

head = addNodeWithDummy();

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

}

struct node* addNode(){

struct node* head = NULL;

struct node* tail = NULL;

int i;

head = malloc(sizeof(struct node));

tail = malloc(sizeof(struct node));

/* dealing with head node here */

Push(&head,1);

tail = head;

/*dealing with all other nodes using ‘tail’ */

for(i=2; i<6; i++){

Push(&(tail->next),i);

tail = tail->next;

}

tail->next = NULL;

return head;

}

struct node* addNodeWithDummy(){

struct node dummy;

struct node* tail = &dummy;

int i;

dummy.next = NULL;

for(i = 6; i <11; i++){

Push(&(tail->next),i);

tail = tail->next;

}

tail->next = NULL;

return (dummy.next);

}

struct node* Push(struct node** elem, int data){

struct node* current = NULL;

current = malloc(sizeof(struct node));

current->data = data;

current->next = *elem;

*elem = current;

return *elem;

}

output :

1 2 3 4 5

6 7 8 9 10

Appending nodes in linkedlist – C program

#include<stdio.h>

struct node{

int data;

struct node* next;

};

void appendNode(struct node** headRef, int data){

struct node* current = *headRef;

struct node* newNode = NULL;

newNode = malloc(sizeof(struct node));

newNode->data = data;

newNode->next = NULL;

if(current == NULL){

*headRef = newNode;

}else{

while(current->next != NULL){

current = current->next;

}

current->next = newNode;

}

}

main(){

struct node* head = NULL;

//head = malloc(sizeof(struct node));

appendNode(&head,1);

appendNode(&head,2);

appendNode(&head,3);

appendNode(&head,4);

appendNode(&head,5);

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

}

output : 1 2 3 4 5

Integer/String conversions in C

a.) Given an string you have to convert the string into integer. The following program does that for you

#include <stdio.h>

int strToInt(char[]);

main(){

int number = 0;

char num[] = “15“; // try for negative numbers as well, it works

number = strToInt(num);

printf(“Number is : %d\n”,number);

}

int strToInt(char string[]){

int i = 0, isNeg = 0, num = 0;

if(string[0] == ‘-’){

output

isNeg = 1;

i = 1;

}

while(string[i]){

num *= 10;

num += (string[i++] – ’0′);

}

if(isNeg == 1){

num *= -1;

}

return num;

}

output Number is : 15

b.) Given an integer you need to convert it into String

#include<stdio.h>

#define MAX_INT_DIGITS 10

void intToStr(int, char[]);

main() {

int number = -1234;

char string[MAX_INT_DIGITS + 2];

intToStr(number,string);

}

void intToStr( int num, char* str) {

int i = 0, j = 0, isNeg = 0;

/* temp buffer to hold largest int, – sign and NUL */

char temp[MAX_INT_DIGITS + 2];

/* check if the number is negative */

if(num < 0){

num *= -1;

isNeg = 1;

}

/* fill the buffer with characters in reverse order */

do{

temp[i++] = (num % 10) + ’0′;

num /= 10;

}while(num);

if(isNeg){

temp[i ++] = ‘-’; // to make it compatible with negative numbers too

}

/* reverse the characters */

while( i > 0 ){

str[j ++] = temp[-- i];

}

/* Null terminated string */

str[j] = ”;

printf(” string is : %s\n”,str);

}

output : string is : -1234