Design and Search in a Maze

On an office floor , there are e entities - Walls , Cubicles , Coffee Rooms. 

In what data structure we should store this design that when a new member joins the company , the cubicle number which is empty and next closest to any coffee room should be assigned to it. 

Basically , data structure DS.pop() should return that cubicle number in the most efficient way. 

A Person can walk through cubicles to reach a coffee room but not through walls.

http://shirleyisnotageek.blogspot.in/2015/01/the-amazing-maze.html

three ways to design a maze:

• Depth-first search;
• Randomized Kruskal's algorithm;
• Randomized Prim's algorithm;

http://shirleyisnotageek.blogspot.in/2015/01/the-amazing-maze-ii-searching-maze.html

Useful Discussion:
---------------------

http://www.careercup.com/question?id=6495252147863552

Design a meeting scheduler

Design a meeting scheduler:
How you will identify conflicting meetings?
How you will design data structure and supporting algorithm so that System will suggest Best Available Meeting time considering the fact that many folks on the invite might be in different geography.

Approach: Using Array and Binary search
Start with an empty list of meetings, each with a start_time and duration. We will maintain a sorted list of meetings by start_time.

To add a meeting to the list, find where it belongs in the list by performing a binary search. Once you find the index, perform two checks to avoid a collision; consider the meetings immediately before and after the to-be-inserted meeting (if they exist).

Assert the before-meeting's start_time + duration does not exceed the new meeting's start_time.
Assert the new meeting's start_time+duration does not exceed the after-meeting's start_time.
If the assertions are satisfied, add the meeting to the list.

This add operation takes O(log(list_size)) time.

Note: This approach assumes that adding a meeting with an overlap is an invalid operation. If overlaps are allowed to exist, you would have to check beyond the meetings immediately preceding/subsequent the new meeting.

Approach 2: using BST
We can have a Tree structure (BST) for storing the requests (Request object: start time/end time/date/priority etc.). By doing so, add/delete/search/update operations can be achieved by O(height_of_tree). If we use a balanced tree, we can get the optimized running time. i.e. O(log n) for each of the above mentioned operations.

This approach is better than the sorted list approach as the list is backed by an fixed sized array in case of ArrayList which takes O(n) for copying the elements from old array to new array. If we use a linkedlist, binary search is not possible.

Useful Discussion:------------------
http://stackoverflow.com/questions/15150188/amazon-interview-design-meeting-scheduler
https://www.careercup.com/question?id=15555745
http://www.careercup.com/question?id=5720778041458688

Producer–consumer problem--Multi process synchronisation-Using Semaphore

Implement Producer–consumer problem using

1.Semaphore and Mutex
2.Monitors


http://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem

Trie - Information Retrieval Data Structure

Design trie and discuss the applications

http://en.wikipedia.org/wiki/Trie
http://www.geeksforgeeks.org/trie-insert-and-search/
http://www.geeksforgeeks.org/trie-delete/

Design Patterns

Design Patterns:

http://www.geeksforgeeks.org/category/design/

0. http://www.coderanch.com/t/659856/Wiki/Singleton-Pattern
1. https://xmruibi.gitbooks.io/interview-preparation-notes/content/OOD/TypicalPattern/index.html
2. http://javarevisited.blogspot.com/2012/06/20-design-pattern-and-software-design.html
3.  https://sourcemaking.com/design-patterns-and-tips

Factory, Singleton, Prototype and Builder Patterns:

http://coding-geek.com/category/design-pattern/

[Cracking the Coding Interview]

Because interviewers are trying to test your capabilities and not your knowledge, design patterns are mostly beyond the scope of an interview. However, the Singleton and Factory Method design patterns are widely used in interviews, so we will cover them here. There are far more design patterns than this book could possibly discuss. A great way to improve your software engineering skills is to pick up a book that focuses on this area specifically. Be careful you don't fall into a trap of constantly trying to find the "right" design pattern for a particular problem. You should create the design that works for that problem. In some cases it might be an established pattern, but in many other cases it is not. 

Singleton Class The Singleton pattern ensures that a class has only one instance and ensures access to the instance through the application. It can be useful in cases where you have a "global" object with exactly one instance. For example, we may want to implement Restaurant such that it has exactly one instance of Restaurant. 

1 public class Restaurant { 

2 private static Restaurant _instance = null; 

3 protected Restaurant() { ... } 

4 public static Restaurant getlnstance() { 

5 if (_instance == null) { 

6 _instance = new Restaurant(); 

7 } 

8 return _instance; 

9 } 

10 }

 It should be noted that many people dislike the Singleton design pattern, even calling it an "anti-pattern:' One reason for this is that it can interfere with unit testing. 

Factory Method The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate. You might want to implement this with the creator class being abstract and not providing an implementation for the Factory method. Or, you could have the Creator class be a concrete class that provides an implementation for the Factory method. In this case, the Factory method would take a parameter representing which class to instantiate. 

1 public class CardGame { 

2 public static CardGame createCardGame(GameType type) { 

3 if (type == GameType.Poker) { 

4 return new PokerGame(); 

5 } else if (type == GameType.BlackJack) { 

6 return new BlackJackGame(); 

7 } 

8 return null; 

9 } 

10 }

Readers–writers problem--Concurrency--Using Mutex

Implement Readers Writer Problem using Semaphores.

Theory:
http://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem

Solution to First Reader Writer Problem --Readers preference
----------------------------------------------------------------
//no reader shall be kept waiting if the share is currently opened for reading

#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>

sem_t mutex,writeblock;
int data = 0,rcount = 0;

void *reader(void *arg)
{
  int f;
  f = ((int)arg);
  sem_wait(&mutex);
  rcount = rcount + 1;
  if(rcount==1)
   sem_wait(&writeblock);
  sem_post(&mutex);
  printf("Data read by the reader%d is %d\n",f,data);
  sleep(1);
  sem_wait(&mutex);
  rcount = rcount - 1;
  if(rcount==0)
   sem_post(&writeblock);
  sem_post(&mutex);
}

void *writer(void *arg)
{
  int f;
  f = ((int) arg);
  sem_wait(&writeblock);
  data++;
  printf("Data writen by the writer%d is %d\n",f,data);
  sleep(1);
  sem_post(&writeblock);
}

main()
{
  int i,b;  
  pthread_t rtid[5],wtid[5];
  sem_init(&mutex,0,1);
  sem_init(&writeblock,0,1);
  for(i=0;i<=2;i++)
  {
    pthread_create(&wtid[i],NULL,writer,(void *)i);
    pthread_create(&rtid[i],NULL,reader,(void *)i);
  }
  for(i=0;i<=2;i++)
  {
    pthread_join(wtid[i],NULL);
    pthread_join(rtid[i],NULL);
  }
}

Solution to 2nd Reader Writer Problem [ Writer's preference ]
----------------------------------------------------------------------------------------
//no writer, once added to the queue, shall be kept waiting longer than absolutely necessary

#include <pthread.h>

#include <sched.h>

#include <semaphore.h>

#include <stdio.h>

#include <unistd.h>

#define MAXTHREAD 10  /* define # readers */

void access_database();     /* prototypes */

void non_access_database();

void* reader(void*);

void* writer(void*);

sem_t q;        /* establish que */

int rc = 0;     /* number of processes reading or wanting to */

int wc = 0;

int write_request = 0;

int main()

{

    pthread_t readers[MAXTHREAD],writerTh;

    int index;

    int ids[MAXTHREAD]; /* readers and initialize mutex, q and db-set them to 1 */

    sem_init (&q,0,1);

    for(index = 0; index < MAXTHREAD; index ++) 

    {

        ids[index]=index+1;                             /* create readers and error check */

        if(pthread_create(&readers[index],0,reader,&ids[index])!=0){

            perror("Cannot create reader!");

            exit(1);                           

        }

    }

    if(pthread_create(&writerTh,0,writer,0)!=0){

        perror("Cannot create writer");     /* create writers and error check */

        exit(1);

    }

    pthread_join(writerTh,0);  

    sem_destroy (&q);

    return 0;

}

void* reader(void*arg)          /* readers function to read */

{

    int index = *(int*)arg;

    int can_read;

    while(1){

        can_read = 1;

        sem_wait(&q);

        if(wc == 0 && write_request == 0)  rc++;

        else                               can_read = 0;

        sem_post(&q);

        if(can_read) {

            access_database();

            printf("Thread %d reading\n", index);

            sleep(index);

            sem_wait(&q);

            rc--;

            sem_post(&q);

        }

        sched_yield();

    }

    return 0;

}

;

void* writer(void*arg)      /* writer's function to write */

{

    int can_write;

    while(1){

        can_write = 1;

        non_access_database();

        sem_wait (&q);

        if(rc == 0)   wc++;

        else          { can_write = 0; write_request = 1; }

        sem_post(&q);

        if(can_write) {

            access_database(); 

            printf("Writer is now writing...Number of readers: %d\n",rc);

            sleep(3);

            sem_wait(&q);

            wc--;

            write_request = 0;

            sem_post(&q);

        }

        sched_yield();

    }

    return 0;

}

void access_database()

{

}

void non_access_database()

{

}