Implementing data structures in coding interviews

In coding interviews, your ability to implement and optimize data structures can make or break your success. These structures are not just theoretical concepts; they are essential tools for efficiently managing and organizing data to solve complex problems. This guide will show you how to apply your knowledge of key data structures in real-world interview scenarios, with practical examples and expert tips to help you stand out and succeed.

1. Getting started: Why data structures matter

In this section, we will cover the basics of data structures. Data structures are important because they directly impact the performance of your code. Selecting the right data structure can significantly improve the efficiency of your solution. For example, using a hash table can reduce the complexity of search operations from O(n) to O(1).

Common data structures

Arrays and lists: Ideal for indexed access
Stacks and queues: Suitable for LIFO and FIFO operations
Linked lists: Useful for dynamic memory allocation
Trees: Binary trees, AVL trees, and binary search trees for hierarchical data
Graphs: Important for representing networks
Hash tables: Excellent for fast lookups
Heaps: Used in priority queues and sorting algorithms

2. Practical implementation in coding interviews

Here are some useful tips and how these common data structures can be implemented during coding interviews.

Arrays and lists

Arrays are a collection of elements identified by index or key. Lists are similar but can grow dynamically. Both are used for storing and accessing elements in a specific order.

Example problem: Given an array of integers, return indexes of the two numbers that add up to a specific target.

def two_sum(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target – num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    return []

# Driver Code
if __name__ == “__main__”:
    # Test cases
    print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]
    print(two_sum([3, 2, 4], 6))       # Output: [1, 2]
    print(two_sum([3, 3], 6))          # Output: [0, 1]

Python

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> TwoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target – nums[i];
        if (numToIndex.find(complement) != numToIndex.end()) {
            return {numToIndex[complement], i};
        }
        numToIndex[nums[i]] = i;
    }
    return {};
}

int main() {
    // Test cases
    vector<int> nums1 = {2, 7, 11, 15};
    vector<int> result1 = TwoSum(nums1, 9);  // Output: [0, 1]
    if (!result1.empty()) {
        cout << “[” << result1[0] << “, ” << result1[1] << “]” << endl;
    }

    vector<int> nums2 = {3, 2, 4};
    vector<int> result2 = TwoSum(nums2, 6);  // Output: [1, 2]
    if (!result2.empty()) {
        cout << “[” << result2[0] << “, ” << result2[1] << “]” << endl;
    }

    vector<int> nums3 = {3, 3};
    vector<int> result3 = TwoSum(nums3, 6);  // Output: [0, 1]
    if (!result3.empty()) {
        cout << “[” << result3[0] << “, ” << result3[1] << “]” << endl;
    }

    return 0;
}

C++

import java.util.HashMap;
import java.util.Map;

public class main {
    
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numToIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target – nums[i];
            if (numToIndex.containsKey(complement)) {
                return new int[] { numToIndex.get(complement), i };
            }
            numToIndex.put(nums[i], i);
        }
        return new int[] {};
    }

    public static void main(String[] args) {
        // Test cases
        int[] result1 = twoSum(new int[] {2, 7, 11, 15}, 9);  // Output: [0, 1]
        if (result1.length != 0) {
            System.out.println(“[” + result1[0] + “, ” + result1[1] + “]”);
        }

        int[] result2 = twoSum(new int[] {3, 2, 4}, 6);  // Output: [1, 2]
        if (result2.length != 0) {
            System.out.println(“[” + result2[0] + “, ” + result2[1] + “]”);
        }

        int[] result3 = twoSum(new int[] {3, 3}, 6);  // Output: [0, 1]
        if (result3.length != 0) {
            System.out.println(“[” + result3[0] + “, ” + result3[1] + “]”);
        }
    }
}

Java

function twoSum(nums, target) {
    let numToIndex = new Map();
    for (let i = 0; i < nums.length; i++) {
        let complement = target – nums[i];
        if (numToIndex.has(complement)) {
            return [numToIndex.get(complement), i];
        }
        numToIndex.set(nums[i], i);
    }
    return [];
}

// Driver Code
// Test cases
console.log(twoSum([2, 7, 11, 15], 9));  // Output: [0, 1]
console.log(twoSum([3, 2, 4], 6));       // Output: [1, 2]
console.log(twoSum([3, 3], 6));          // Output: [0, 1]

JavaScript

Explanation: In the coding problem above, we use a stack to manage the numbers and their corresponding operations. As we iterate through the string, we process each number and operator, applying the previous operator to the current number and storing the result in the stack.

Interview tips: During the interview, highlight the use of the stack to manage intermediate results and explain how different operators are handled. Emphasize the importance of edge cases, such as spaces and multiple digits. Also, explain how the precedence of operators is maintained using stack.

Linked lists

A linked list is a linear collection of elements where each element points to the next. This allows for efficient insertion and deletion of elements.

Example problem: Reverse a singly linked list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# Helper function to create a linked list from a list
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to print a linked list
def print_linked_list(head):
    while head:
        print(head.val, end=” -> “)
        head = head.next
    print(“None”)

# Driver Code
if __name__ == “__main__”:
    # Test cases
    head = create_linked_list([1, 2, 3, 4, 5])
    print_linked_list(reverse_list(head))  # Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

    head = create_linked_list([1, 2])
    print_linked_list(reverse_list(head))  # Output: 2 -> 1 -> None

    head = create_linked_list([])
    print_linked_list(reverse_list(head))  # Output: None

Python

#include <iostream>
#include <vector>

using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int val = 0, ListNode* next = nullptr) : val(val), next(next) {}
};

ListNode* reverse_list(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next_node = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_node;
    }
    return prev;
}

// Helper function to create a linked list from a vector
ListNode* create_linked_list(const vector<int>& arr) {
    if (arr.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); ++i) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print a linked list
void print_linked_list(ListNode* head) {
    while (head) {
        cout << head->val << ” -> “;
        head = head->next;
    }
    cout << “None” << endl;
}

// Driver Code
int main() {
    // Test cases
    ListNode* head = create_linked_list({1, 2, 3, 4, 5});
    print_linked_list(reverse_list(head));  // Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

    head = create_linked_list({1, 2});
    print_linked_list(reverse_list(head));  // Output: 2 -> 1 -> None

    head = create_linked_list({});
    print_linked_list(reverse_list(head));  // Output: None

    return 0;
}

C++

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class main {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

    // Helper function to create a linked list from an array
    public static ListNode createLinkedList(int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to print a linked list
    public static void printLinkedList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + ” -> “);
            head = head.next;
        }
        System.out.println(“None”);
    }

    // Driver Code
    public static void main(String[] args) {
        // Test cases
        ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
        printLinkedList(reverseList(head));  // Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

        head = createLinkedList(new int[]{1, 2});
        printLinkedList(reverseList(head));  // Output: 2 -> 1 -> None

        head = createLinkedList(new int[]{});
        printLinkedList(reverseList(head));  // Output: None
    }
}

Java

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

// Helper function to create a linked list from an array
function createLinkedList(arr) {
    if (arr.length === 0) {
        return null;
    }
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

// Helper function to print a linked list
function printLinkedList(head) {
    while (head) {
        process.stdout.write(head.val + ” -> “);
        head = head.next;
    }
    console.log(“None”);
}

// Driver Code
// Test cases
let head = createLinkedList([1, 2, 3, 4, 5]);
printLinkedList(reverseList(head));  // Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

head = createLinkedList([1, 2]);
printLinkedList(reverseList(head));  // Output: 2 -> 1 -> None

head = createLinkedList([]);
printLinkedList(reverseList(head));  // Output: None

JavaScript

Explanation: In the coding problem above, we iterate through a linked list while reassigning the next pointers to the previous nodes to reverse the linked list, effectively reversing the list’s direction.

Interview tips: During the interview, clearly explain each step in the reversal process, including reassigning pointers. Discuss how the solution’s time complexity is O(n)O(n)O(n) and space complexity is O(1)O(1)O(1).

Trees

Trees are hierarchical data structures with a root node and child nodes forming a parent-child relationship. Binary, AVL, and binary search trees (BST) are common types with specific properties and uses.

Example problem: Given the root of a binary tree, return the inorder traversal of its nodes’ values.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    res, stack = [], []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
    return res

# Driver Code
if __name__ == “__main__”:
    # Test cases
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(inorder_traversal(root))  # Output: [1, 3, 2]

    root = TreeNode(1, TreeNode(2), TreeNode(3))
    print(inorder_traversal(root))  # Output: [2, 1, 3]

    root = None
    print(inorder_traversal(root))  # Output: []

Python

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) : val(val), left(left), right(right) {}
};

vector<int> inorder_traversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        res.push_back(root->val);
        root = root->right;
    }
    return res;
}

// Helper function to print a vector
void print_vector(const vector<int>& vec) {
    for (int val : vec) {
        cout << val << ” “;
    }
    cout << endl;
}

// Driver Code
int main() {
    // Test cases
    TreeNode* root = new TreeNode(1, nullptr, new TreeNode(2, new TreeNode(3)));
    print_vector(inorder_traversal(root));  // Output: 1 3 2

    root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    print_vector(inorder_traversal(root));  // Output: 2 1 3

    root = nullptr;
    print_vector(inorder_traversal(root));  // Output: (empty line)

    return 0;
}

C++

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class main {

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    // Helper function to print a list
    public static void printList(List<Integer> list) {
        for (int val : list) {
            System.out.print(val + ” “);
        }
        System.out.println();
    }

    // Driver Code
    public static void main(String[] args) {
        // Test cases
        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        printList(inorderTraversal(root));  // Output: 1 3 2

        root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        printList(inorderTraversal(root));  // Output: 2 1 3

        root = null;
        printList(inorderTraversal(root));  // Output: (empty line)
    }
}

Java

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorderTraversal(root) {
    const res = [];
    const stack = [];
    while (root !== null || stack.length > 0) {
        while (root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
}

// Helper function to print a list
function printList(list) {
    console.log(list.join(‘ ‘));
}

// Driver Code
// Test cases
let root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
printList(inorderTraversal(root));  // Output: 1 3 2

root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
printList(inorderTraversal(root));  // Output: 2 1 3

root = null;
printList(inorderTraversal(root));  // Output: (empty line)

JavaScript

Explanation: In the coding problem above, we use an iterative approach that traverses the tree in an inorder fashion using a stack. We push nodes onto the stack as we traverse to the leftmost node, then visit the nodes by popping them from the stack.

Interview tips: During the interview, emphasize using the stack to handle the traversal without recursion. Explain the importance of inorder traversal and its typical applications. Think about using the system stack to solve the above problem recursively.

Graphs

Graphs consist of nodes (vertices) and edges (connections between nodes). They represent networks, such as social networks or communication systems.

Example problem: Given a 2D board and a word, find if the word exists in the grid.

def exist(board, word):
    def dfs(board, word, i, j, k):
        if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
            return False
        if k == len(word) – 1:
            return True
        tmp, board[i][j] = board[i][j], “/”
        res = dfs(board, word, i+1, j, k+1) or dfs(board, word, i-1, j, k+1) or dfs(board, word, i, j+1, k+1) or dfs(board, word, i, j-1, k+1)
        board[i][j] = tmp
        return res
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, word, i, j, 0):
                return True
    return False

# Driver Code
if __name__ == “__main__”:
    # Test cases
    board = [
        [‘A’,’B’,’C’,’E’],
        [‘S’,’F’,’C’,’S’],
        [‘A’,’D’,’E’,’E’]
    ]
    print(exist(board, “ABCCED”))  # Output: True
    print(exist(board, “SEE”))     # Output: True
    print(exist(board, “ABCB”))    # Output: False

Python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int i, int j, int k) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[k]) {
            return false;
        }
        if (k == word.size() – 1) {
            return true;
        }
        char tmp = board[i][j];
        board[i][j] = ‘/’;
        bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i – 1, j, k + 1) ||
                   dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j – 1, k + 1);
        board[i][j] = tmp;
        return res;
    }
};

// Driver Code
int main() {
    Solution solution;

    vector<vector<char>> board1 = {
        {‘A’,’B’,’C’,’E’},
        {‘S’,’F’,’C’,’S’},
        {‘A’,’D’,’E’,’E’}
    };
    cout << boolalpha << solution.exist(board1, “ABCCED”) << endl;  // Output: true
    cout << boolalpha << solution.exist(board1, “SEE”) << endl;     // Output: true
    cout << boolalpha << solution.exist(board1, “ABCB”) << endl;    // Output: false

    return 0;
}

C++

public class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {
            return false;
        }
        if (k == word.length() – 1) {
            return true;
        }
        char tmp = board[i][j];
        board[i][j] = ‘/’;
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i – 1, j, k + 1) ||
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j – 1, k + 1);
        board[i][j] = tmp;
        return res;
    }

    // Driver Code
    public static void main(String[] args) {
        Solution solution = new Solution();

        char[][] board1 = {
            {‘A’, ‘B’, ‘C’, ‘E’},
            {‘S’, ‘F’, ‘C’, ‘S’},
            {‘A’, ‘D’, ‘E’, ‘E’}
        };
        System.out.println(solution.exist(board1, “ABCCED”));  // Output: true
        System.out.println(solution.exist(board1, “SEE”));     // Output: true
        System.out.println(solution.exist(board1, “ABCB”));    // Output: false
    }
}

Java

class Solution {
    exist(board, word) {
        for (let i = 0; i < board.length; ++i) {
            for (let j = 0; j < board[0].length; ++j) {
                if (this.dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    dfs(board, word, i, j, k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[k]) {
            return false;
        }
        if (k === word.length – 1) {
            return true;
        }
        const tmp = board[i][j];
        board[i][j] = ‘/’;
        const res = this.dfs(board, word, i + 1, j, k + 1) || this.dfs(board, word, i – 1, j, k + 1) ||
                    this.dfs(board, word, i, j + 1, k + 1) || this.dfs(board, word, i, j – 1, k + 1);
        board[i][j] = tmp;
        return res;
    }
}

// Driver Code
const solution = new Solution();

const board1 = [
    [‘A’, ‘B’, ‘C’, ‘E’],
    [‘S’, ‘F’, ‘C’, ‘S’],
    [‘A’, ‘D’, ‘E’, ‘E’]
];
console.log(solution.exist(board1, “ABCCED”));  // Output: true
console.log(solution.exist(board1, “SEE”));     // Output: true
console.log(solution.exist(board1, “ABCB”));    // Output: false

JavaScript

Explanation: In the coding problem above, we use depth-first search (DFS) to determine if a word exists in a 2D grid. The function iterates through each cell in the grid and initiates a DFS when the first character matches. The DFS explores all possible paths from the current cell, checking boundaries and character matches and temporarily marking cells to avoid revisiting them. If a path successfully matches all characters in the word, it returns True; otherwise, it backtracks and restores the cell’s value. If no path matches, the function returns False, indicating the word cannot be formed in the grid.

Interview tips: During the interview, discuss the use of DFS for exploring paths and backtracking to restore the state of the grid. Highlight the importance of edge cases and constraints.

Hash tables

Hash tables use a hash function to map keys to values, allowing for fast data retrieval. They are highly efficient for lookup, insert, and delete operations.

Example problem: Given a list of strings, group anagrams together.

from collections import defaultdict

def group_anagrams(strs):
    anagrams = defaultdict(list)
    for s in strs:
        anagrams[tuple(sorted(s))].append(s)
    return list(anagrams.values())

# Driver Code
if __name__ == “__main__”:
    # Test cases
    print(group_anagrams([“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]))  
    # Output: [[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]

    print(group_anagrams([“”]))  
    # Output: [[”]]

    print(group_anagrams([“a”]))  
    # Output: [[‘a’]]

Python

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

vector<vector<string>> group_anagrams(vector<string>& strs) {
    map<string, vector<string>> anagrams;
    for (string s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        anagrams[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& pair : anagrams) {
        result.push_back(pair.second);
    }
    return result;
}

// Helper function to print the result
void print_result(const vector<vector<string>>& result) {
    for (const auto& group : result) {
        cout << “[“;
        for (const auto& word : group) {
            cout << word << ” “;
        }
        cout << “] “;
    }
    cout << endl;
}

// Driver Code
int main() {
    // Test cases
    vector<string> test1 = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”};
    print_result(group_anagrams(test1));  
    // Output: [[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]

    vector<string> test2 = {“”};
    print_result(group_anagrams(test2));  
    // Output: [[”]]

    vector<string> test3 = {“a”};
    print_result(group_anagrams(test3));  
    // Output: [[‘a’]]

    return 0;
}

C++

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;

public class main {

    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagrams = new HashMap<>();
        for (String s : strs) {
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            if (!anagrams.containsKey(key)) {
                anagrams.put(key, new ArrayList<>());
            }
            anagrams.get(key).add(s);
        }
        return new ArrayList<>(anagrams.values());
    }

    // Helper function to print the result
    public static void printResult(List<List<String>> result) {
        for (List<String> group : result) {
            System.out.print(“[“);
            for (String word : group) {
                System.out.print(word + ” “);
            }
            System.out.print(“] “);
        }
        System.out.println();
    }

    // Driver Code
    public static void main(String[] args) {
        // Test cases
        String[] test1 = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”};
        printResult(groupAnagrams(test1));  
        // Output: [[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]

        String[] test2 = {“”};
        printResult(groupAnagrams(test2));  
        // Output: [[”]]

        String[] test3 = {“a”};
        printResult(groupAnagrams(test3));  
        // Output: [[‘a’]]
    }
}

Java

function groupAnagrams(strs) {
    const anagrams = new Map();
    for (const s of strs) {
        const key = s.split(”).sort().join(”);
        if (!anagrams.has(key)) {
            anagrams.set(key, []);
        }
        anagrams.get(key).push(s);
    }
    return Array.from(anagrams.values());
}

// Helper function to print the result
function printResult(result) {
    result.forEach(group => {
        process.stdout.write(“[“);
        group.forEach(word => {
            process.stdout.write(word + ” “);
        });
        process.stdout.write(“] “);
    });
    console.log();
}

// Driver Code
// Test cases
const test1 = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”];
printResult(groupAnagrams(test1));  
// Output: [[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]

const test2 = [“”];
printResult(groupAnagrams(test2));  
// Output: [[”]]

const test3 = [“a”];
printResult(groupAnagrams(test3));  
// Output: [[‘a’]]

JavaScript

Explanation: In the coding problem above, we can efficiently group anagrams by sorting each string and using the sorted tuple as a key in a hash table.

Interview tips: During the interview, explain the choice of using sorted tuples as keys and how the hash table facilitates efficient grouping. Discuss the time complexity, which is dominated by the sorting step.

Heaps

Heaps are specialized tree-based structures that satisfy the heap property. They are used to implement priority queues, where the highest (or lowest) priority element is always at the front.

Example problem: Find the kthk^{th}kth largest element in an array.

import heapq

def find_kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

# Driver Code
if __name__ == “__main__”:
    # Test cases
    print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # Output: 5
    print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # Output: 4
    print(find_kth_largest([1], 1))  # Output: 1

Python

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int find_kth_largest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> min_heap;
    for (int num : nums) {
        min_heap.push(num);
        if (min_heap.size() > k) {
            min_heap.pop();
        }
    }
    return min_heap.top();
}

// Driver Code
int main() {
    // Test cases
    vector<int> test1 = {3, 2, 1, 5, 6, 4};
    cout << find_kth_largest(test1, 2) << endl;  // Output: 5

    vector<int> test2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    cout << find_kth_largest(test2, 4) << endl;  // Output: 4

    vector<int> test3 = {1};
    cout << find_kth_largest(test3, 1) << endl;  // Output: 1

    return 0;
}

C++

import java.util.PriorityQueue;

public class main {

    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    // Driver Code
    public static void main(String[] args) {
        // Test cases
        int[] test1 = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(test1, 2));  // Output: 5

        int[] test2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest(test2, 4));  // Output: 4

        int[] test3 = {1};
        System.out.println(findKthLargest(test3, 1));  // Output: 1
    }
}

Java

const MinHeap = require(‘./MinHeap’);

function findKthLargest(nums, k) {
    const minHeap = new MinHeap();
    
    for (const num of nums) {
        minHeap.add(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

// Driver Code
// Test cases
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));  // Output: 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));  // Output: 4
console.log(findKthLargest([1], 1));  // Output: 1

class MinHeap {
    constructor() {
        this.heap = [];
    }

    add(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    poll() {
        if (this.size() === 1) {
            return this.heap.pop();
        }
        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return root;
    }

    peek() {
        return this.heap[0];
    }

    size() {
        return this.heap.length;
    }

    _heapifyUp() {
        let index = this.heap.length – 1;
        while (this._parent(index) >= 0 && this.heap[index] < this.heap[this._parent(index)]) {
            this._swap(index, this._parent(index));
            index = this._parent(index);
        }
    }

    _heapifyDown() {
        let index = 0;
        while (this._leftChild(index) < this.heap.length) {
            let smallerChildIndex = this._leftChild(index);
            if (this._rightChild(index) < this.heap.length && this.heap[this._rightChild(index)] < this.heap[smallerChildIndex]) {
                smallerChildIndex = this._rightChild(index);
            }
            if (this.heap[index] < this.heap[smallerChildIndex]) {
                break;
            }
            this._swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }

    _parent(index) {
        return Math.floor((index – 1) / 2);
    }

    _leftChild(index) {
        return 2 * index + 1;
    }

    _rightChild(index) {
        return 2 * index + 2;
    }

    _swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
}

module.exports = MinHeap;

JavaScript

Explanation: In the coding problem above, we use heap to find the kthk^{th}kth largest element. The nlargest function retrieves the kkk largest elements from the list, sorted in descending order, and we return the last one, which is the kthk^{th}kth largest element in the original list.

Interview tips: During the interview, highlight the efficiency of using heaps for this problem and explain how the heap classes simplify the implementation. Discuss the time complexity, which is O(nlog(k))

3. Tips for success in coding interviews

Following the below-mentioned tips during the interview will help you approach coding interviews with confidence and efficiency:

Understand the problem: Take time to fully understand the problem statement.
Choose the right data structure: Select the data structure that best suits the problem’s requirements.
Optimize for time and space: Consider both time and space complexities.
Practice common patterns: Familiarize yourself with common problem-solving patterns.
Explain your thought process: Clearly communicate your thought process to the interviewer.
Test your code: Test your code with various inputs to ensure its correctness.

Understanding the problem ensures you solve the correct issue while choosing the right data structure and optimizing for time and space enhances performance. Practicing common patterns allows for quick application, and explaining your thought process demonstrates logical reasoning. Testing your code ensures accuracy and robustness, ultimately leading to more effective and efficient solutions during interviews.

Data structures for coding interviews

To effectively prepare for coding interviews, many candidates opt for specialized courses that teach data structures for coding interviews. Educative provides a unique and comprehensive course with in-depth coverage and practical focus. You can explore the course variants available in different programming languages below:

4. Conclusion

Mastering data structures is your ticket to excelling in coding interviews. Practice is key to making these concepts second nature, and our mock interviews can be a game changer. We offer a variety of mock interview sessions, including those focused on data structures, to help you tackle different problem types. During these sessions, pay close attention to the interviewer’s feedback to identify areas for improvement and sharpen your skills. Remember, clearly communicating your approach is just as important as finding the solution. Ready to level up? Dive into mock interviews, challenge yourself with new problems, and watch your skills grow. Good luck, and happy coding!

Adeel Qayyum
January 13, 2025

Implementing data structures in coding interviews

1. Getting started: Why data structures matter

Common data structures

2. Practical implementation in coding interviews

Arrays and lists

Linked lists

Trees

Graphs

Hash tables

Heaps

3. Tips for success in coding interviews

Data structures for coding interviews

4. Conclusion

Leave a Reply Cancel reply

Need help preparing for the interview?