Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Phone Book Application

Problem Statement

Write a Java program that implements a phone book using a hash table, with contact names as keys and phone numbers as values. The program should support operations to insert a contact (name and phone number), look up a phone number by name, and delete a contact by name. The hash table should handle case-sensitive names and return appropriate messages for operations on non-existent contacts or duplicate insertions. Test the implementation with sequences of operations, including cases with duplicate names, non-existent contacts, and empty phone books. You can visualize this as a digital phone book where you can add, find, or remove a person’s contact details quickly using their name.

Input:

  • A sequence of operations, where each operation is:
    • insert(name, phoneNumber): Add a contact, return "Added" or "Name already exists".
    • lookup(name): Return the phone number or "Not found" if the name doesn’t exist.
    • delete(name): Remove the contact, return "Deleted" or "Not found".
    • printPhoneBook(): Print all contacts or "Empty" if none exist. Output: For each operation, print the action performed and its result (e.g., "Added John", "Found: 123-456-7890", "Deleted John", or "Empty"). Constraints:
  • The phone book size is between 0 and 10^5 contacts.
  • Names and phone numbers are non-empty strings of up to 100 characters.
  • Names are case-sensitive (e.g., "John" and "john" are distinct).
  • Phone numbers are strings (e.g., "123-456-7890", no specific format required). Example:
  • Input: Operations = [insert("John", "123-456-7890"), insert("Jane", "987-654-3210"), lookup("John"), delete("Jane"), printPhoneBook]
  • Output: 
    Added John
Added Jane
Found: 123-456-7890
Deleted Jane
Phone Book: John: 123-456-7890
  • Input: Operations = [lookup("John"), printPhoneBook]
  • Output: 
    Not found
Empty

Pseudocode

CLASS PhoneBook
    SET hashTable to new HashMap

    FUNCTION insert(name, phoneNumber)
        IF hashTable contains name THEN
            RETURN "Name already exists"
        ENDIF
        SET hashTable[name] to phoneNumber
        RETURN "Added " + name
    ENDFUNCTION

    FUNCTION lookup(name)
        IF hashTable contains name THEN
            RETURN "Found: " + hashTable[name]
        ENDIF
        RETURN "Not found"
    ENDFUNCTION

    FUNCTION delete(name)
        IF hashTable contains name THEN
            REMOVE hashTable[name]
            RETURN "Deleted " + name
        ENDIF
        RETURN "Not found"
    ENDFUNCTION

    FUNCTION toString()
        IF hashTable is empty THEN
            RETURN "Empty"
        ENDIF
        CREATE result as new StringBuilder
        FOR each entry in hashTable
            APPEND entry.key and ": " and entry.value to result
            IF not last entry THEN
                APPEND ", " to result
            ENDIF
        ENDFOR
        RETURN result as string
    ENDFUNCTION
ENDCLASS

FUNCTION testPhoneBook(operations)
    CREATE phoneBook as new PhoneBook
    FOR each operation in operations
        IF operation.type equals "insert" THEN
            CALL phoneBook.insert(operation.name, operation.phoneNumber)
            PRINT result
        ELSE IF operation.type equals "lookup" THEN
            CALL phoneBook.lookup(operation.name)
            PRINT result
        ELSE IF operation.type equals "delete" THEN
            CALL phoneBook.delete(operation.name)
            PRINT result
        ELSE IF operation.type equals "print" THEN
            PRINT "Phone Book: " + phoneBook.toString
        ENDIF
    ENFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testPhoneBook(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a PhoneBook class with: a. A HashMap<String, String> to store name-phone number pairs. b. insert: Add contact if name doesn’t exist, return status. c. lookup: Return phone number or "Not found". d. delete: Remove contact by name, return status. e. toString: Return comma-separated string of contacts or "Empty".
  2. In testPhoneBook: a. Create a PhoneBook instance. b. For each operation:
    • insert: Call insert, print result.
    • lookup: Call lookup, print result.
    • delete: Call delete, print result.
    • print: Call toString, print phone book.
  3. In main, test with sequences including: a. Normal operations (insert, lookup, delete). b. Empty phone book operations. c. Duplicate name insertion. d. Lookup and delete non-existent contacts. e. Single contact operations.

Java Implementation

import java.util.*;

public class PhoneBookApplication {
    // PhoneBook class to manage contacts
    static class PhoneBook {
        private HashMap<String, String> hashTable;

        public PhoneBook() {
            hashTable = new HashMap<>();
        }

        public String insert(String name, String phoneNumber) {
            if (hashTable.containsKey(name)) {
                return "Name already exists";
            }
            hashTable.put(name, phoneNumber);
            return "Added " + name;
        }

        public String lookup(String name) {
            if (hashTable.containsKey(name)) {
                return "Found: " + hashTable.get(name);
            }
            return "Not found";
        }

        public String delete(String name) {
            if (hashTable.containsKey(name)) {
                hashTable.remove(name);
                return "Deleted " + name;
            }
            return "Not found";
        }

        public String toString() {
            if (hashTable.isEmpty()) {
                return "Empty";
            }
            StringBuilder result = new StringBuilder();
            int index = 0;
            for (Map.Entry<String, String> entry : hashTable.entrySet()) {
                result.append(entry.getKey()).append(": ").append(entry.getValue());
                if (index < hashTable.size() - 1) {
                    result.append(", ");
                }
                index++;
            }
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        String name;
        String phoneNumber;

        Operation(String type, String name, String phoneNumber) {
            this.type = type;
            this.name = name;
            this.phoneNumber = phoneNumber;
        }
    }

    // Tests phone book operations
    public void testPhoneBook(List<Operation> operations) {
        PhoneBook phoneBook = new PhoneBook();
        for (Operation op : operations) {
            if (op.type.equals("insert")) {
                System.out.println(phoneBook.insert(op.name, op.phoneNumber));
            } else if (op.type.equals("lookup")) {
                System.out.println(phoneBook.lookup(op.name));
            } else if (op.type.equals("delete")) {
                System.out.println(phoneBook.delete(op.name));
            } else if (op.type.equals("print")) {
                System.out.println("Phone Book: " + phoneBook.toString());
            }
        }
    }

    // Main method to test phone book
    public static void main(String[] args) {
        PhoneBookApplication manager = new PhoneBookApplication();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();

        // Test case 1: Normal operations
        testCases.add(Arrays.asList(
            new Operation("insert", "John", "123-456-7890"),
            new Operation("insert", "Jane", "987-654-3210"),
            new Operation("lookup", "John", null),
            new Operation("delete", "Jane", null),
            new Operation("print", null, null)
        ));

        // Test case 2: Empty phone book
        testCases.add(Arrays.asList(
            new Operation("lookup", "John", null),
            new Operation("delete", "John", null),
            new Operation("print", null, null)
        ));

        // Test case 3: Duplicate name
        testCases.add(Arrays.asList(
            new Operation("insert", "Alice", "111-222-3333"),
            new Operation("insert", "Alice", "444-555-6666"),
            new Operation("print", null, null)
        ));

        // Test case 4: Non-existent contact
        testCases.add(Arrays.asList(
            new Operation("insert", "Bob", "222-333-4444"),
            new Operation("lookup", "Charlie", null),
            new Operation("delete", "Charlie", null),
            new Operation("print", null, null)
        ));

        // Test case 5: Single contact
        testCases.add(Arrays.asList(
            new Operation("insert", "Eve", "555-666-7777"),
            new Operation("lookup", "Eve", null),
            new Operation("delete", "Eve", null),
            new Operation("print", null, null)
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            manager.testPhoneBook(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Added John
Added Jane
Found: 123-456-7890
Deleted Jane
Phone Book: John: 123-456-7890

Test case 2:
Not found
Not found
Phone Book: Empty

Test case 3:
Added Alice
Name already exists
Phone Book: Alice: 111-222-3333

Test case 4:
Added Bob
Not found
Not found
Phone Book: Bob: 222-333-4444

Test case 5:
Added Eve
Found: 555-666-7777
Deleted Eve
Phone Book: Empty

Explanation:

  • Test case 1: Adds John and Jane, looks up John, deletes Jane, prints remaining contact.
  • Test case 2: Attempts lookup and delete on empty phone book, prints "Empty".
  • Test case 3: Adds Alice, tries to add Alice again (fails), prints single contact.
  • Test case 4: Adds Bob, tries lookup and delete for non-existent Charlie, prints Bob’s contact.
  • Test case 5: Adds Eve, looks up Eve, deletes Eve, prints empty phone book.

How It Works

  • PhoneBook:
    • Uses HashMap<String, String> to store name-phone number pairs.
    • insert: Adds contact if name doesn’t exist, returns status.
    • lookup: Returns phone number or "Not found".
    • delete: Removes contact if name exists, returns status.
    • toString: Returns comma-separated string of contacts or "Empty".
  • testPhoneBook: Executes operations, printing results.
  • Example Trace (Test case 1):
    • insert("John", "123-456-7890"): hashTable={John:123-456-7890}, returns "Added John".
    • insert("Jane", "987-654-3210"): hashTable={John:123-456-7890, Jane:987-654-3210}, returns "Added Jane".
    • lookup("John"): Returns "Found: 123-456-7890".
    • delete("Jane"): Removes Jane, hashTable={John:123-456-7890}, returns "Deleted Jane".
    • print: Returns "John: 123-456-7890".
  • Main Method: Tests normal operations, empty phone book, duplicate names, non-existent contacts, and single contact.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
InsertO(1) averageO(1)
LookupO(1) averageO(1)
DeleteO(1) averageO(1)
To StringO(n)O(n)

Note:

  • n is the number of contacts in the phone book.
  • Time complexity: O(1) average for insert, lookup, delete (HashMap operations); O(n) for toString (iterate all entries).
  • Space complexity: O(1) for insert, lookup, delete (constant space); O(n) for toString (StringBuilder output).
  • Worst case: O(n) time and space for toString with large phone books.

✅ Tip: Use a HashMap for fast O(1) average-case operations. Ensure names are treated case-sensitively to avoid confusion between similar names (e.g., "John" vs. "john").

⚠ Warning: Check for duplicate names before insertion to prevent overwriting existing contacts. Handle empty phone book cases to avoid null pointer issues during lookup or deletion.