Applied Materials SDE Interview Questions, Process, and Tips

Array is a collection of elements stored in contiguous memory locations while linked list is a collection of nodes linked by pointers.

• Arrays have fixed size while linked lists can grow or shrink dynamically

• Insertion and deletion is faster in linked lists than arrays

• Accessing elements in arrays is faster than linked lists

• Arrays are better for random access while linked lists are better for sequential access

An array of key-value pairs is the best data structure for a dictionary.

• Use a hash table or a balanced tree to implement the dictionary.

• Keys should be unique and immutable.

• Values can be any data type.

• Access time should be O(1) or O(log n) depending on the implementation.

• Examples: Python's dict, Java's HashMap, C++'s unordered_map.

Hashing is a technique to map data to a fixed-size table. Time complexity of searching a hash table is O(n) in worst case.

• Hashing is used to store and retrieve data quickly

• It uses a hash function to map data to a fixed-size table

• In the best case, searching a hash table takes O(1) time

• In the worst case, all the data maps to the same index and searching takes O(n) time

• Collision resolution techniques like chaining and ope

A linked list is used to store and manipulate a collection of data elements in a linear order.

• Linked lists are commonly used in computer science for implementing data structures like stacks, queues, and hash tables.

• They are also used in operating systems for managing memory allocation.

• For example, a linked list can be used to implement a music playlist where each song is a node and the links between nodes represent the...read more

Implement a stack using a linked list

• Create a Node class with data and next pointer

• Create a Stack class with top pointer

• Push new nodes to the top of the stack

• Pop nodes from the top of the stack

• Check if the stack is empty before popping

BST stands for Binary Search Tree, a data structure used for efficient searching and sorting operations.

• BST is a tree-like data structure where each node has at most two children.

• The left child of a node contains a value less than the parent node, while the right child contains a value greater than the parent node.

• BST allows for efficient searching and sorting operations with a time complexity of O(log n).

• Examples of a...read more

Program to check if a binary tree is a BST

• Traverse the tree in-order and check if the values are in ascending order

• Use a min-max range for each node to check if it satisfies the BST property

• Recursively check if the left and right subtrees are BSTs