Software Engineering Interview Guide

A linked list is a data structure that can store a collection of items. In other words, linked lists can be utilized to store several objects of the same type. Each unit or element of the list is referred to as a node. Each node has its own data and the address of the next node. It is like a chain. Linked Lists are used to create graphs and trees.

Dynamic memory allocation is referred for Linked lists.

Term Traversal is used to refer to the operation of processing each element in the list.

Together (data + link) is referred to as the Node.

Types of Linked Lists are:

• Singly Linked List
• Doubly Linked List
• Multiply Linked List
• Circular Linked List

Singly Linked lists are a type of data structure. In a singly linked list, each node in the list stores the contents of the node and a reference or pointer to the next node in the list. It does not store any reference or pointer to the previous node.

Applications of Linked Lists are:

• Linked lists are used to implement queues, stacks, graphs, etc.
• In Linked Lists you don't need to know the size in advance.
• Linked lists let you insert elements at the beginning and end of the list.

A doubly linked list nodes contain three fields:

• An integer value and
• Two links to other nodes
• one to point to the previous node and
• other to point to the next node.

Whereas a singly linked list contains points only to the next node.

Both queues and stacks are often implemented using linked lists. Other applications are list, binary tree, skip, unrolled linked list, hash table, etc.

The biggest benefit of linked lists is that you do not specify a fixed size for your list. The more elements you add to the chain, the bigger the chain gets.

Database is an organized collection of related data where the data is stored and organized to serve some specific purpose.

DBMS stands for Database Management System. It is a collection of application programs which allow the user to organize, restore and retrieve information about data efficiently and as effectively as possible.

Some of the popular DBMS's are MySql, Oracle, Sybase, etc.

• Data is stored in a structured way and hence redundancy is controlled.
• Validates the data entered and provides restrictions on unauthorized access to the database.
• Provides backup and recovery of the data when required.
• It provides multiple user interfaces.

Duplication of data in the database is known as data redundancy. As a result of data redundancy, duplicated data is present at multiple locations, hence it leads to wastage of the storage space and the integrity of the database is destroyed.

• One-to-one: One table has a relationship with another table having a similar kind of column. Each primary key relates to only one or no record in the related table.
• One-to-many: One table has a relationship with another table that has primary and foreign key relations. The primary key table contains only one record that relates to none, one or many records in the related table.
• Many-to-many: Each record in both the tables can relate to many numbers of records in another table.

Normalization: Normalization is the process of removing redundant data from the database by splitting the table in a well-defined manner in order to maintain data integrity. This process saves much of the storage space.

De-normalization: De-normalization is the process of adding up redundant data on the table in order to speed up the complex queries and thus achieve better performance.

• First Normal Form (1NF): A relation is said to be in 1NF only when all the entities of the table contain unique or atomic values.
• Second Normal Form (2NF): A relation is said to be in 2NF only if it is in 1NF and all the non-key attributes of the table are fully dependent on the primary key.
• Third Normal Form (3NF): A relation is said to be in 3NF only if it is in 2NF and every non-key attribute of the table is not transitively dependent on the primary key.

Structured Query language, SQL is an ANSI (American National Standard Institute) standard programming language that is designed specifically for storing and managing the data in the relational database management system (RDBMS) using all kinds of data operations.

SQL statements are basically divided into three categories, DDL, DML, and DCL.

• Data Definition Language (DDL) commands are used to define the structure that holds the data. These commands are auto-committed i.e. changes done by the DDL commands on the database are saved permanently.
• Data Manipulation Language (DML) commands are used to manipulate the data of the database. These commands are not auto-committed and can be rolled back.
• Data Control Language (DCL) commands are used to control the visibility of the data in the database like revoke access permission for using data in the database.

• Simple SQL queries can be used to retrieve a large amount of data from the database very quickly and efficiently.
• SQL is easy to learn and almost every DBMS supports SQL.
• It is easier to manage the database using SQL as no large amount of coding is required.

Data Definition Language (DDL) commands:

• CREATE to create a new table or database.
• ALTER for alteration.
• TRUNCATE to delete data from the table.
• DROP to drop a table.
• RENAME to rename a table.

Data Manipulation Language (DML) commands:

• INSERT to insert a new row.
• UPDATE to update an existing row.
• DELETE to delete a row.
• MERGE for merging two rows or two tables.

Data Control Language (DCL) commands:

• COMMIT to permanently save.
• ROLLBACK to undo the change.
• SAVEPOINT to save temporarily.

Record: Record is a collection of values or fields of a specific entity. For Example, An employee, Salary account, etc.

Field: A field refers to an area within a record that is reserved for specific data. For Example, Employee ID.

Table: Table is the collection of records of specific types. For Example, the Employee table is a collection of records related to all the employees.

View is a virtual table that does not have its data on its own rather the data is defined from one or more underlying base tables.

Advantages of Views:

• As there is no physical location where the data in the view is stored, it generates output without wasting resources.
• Data access is restricted as it does not allow commands like insertion, updation, and deletion.

Disadvantages of Views:

• The view becomes irrelevant if we drop a table related to that view.
• Much memory space is occupied when the view is created for large tables.

A relation is said to be in functional dependency when one attribute uniquely defines another attribute.

For Example, R is a Relation, X and Y are two attributes. T1 and T2 are two tuples. Then, T1[X]=T2[X] and T1[Y]=T2[Y]

Means, the value of component X uniquely defines the value of component Y.

Also, X->Y means Y is functionally dependent on X.

To fulfill the criteria of fully functional dependency, the relation must meet the requirement of functional dependency.

A functional dependency 'A' and 'B' are said to be fully functional dependent when removal of any attribute say 'X' from 'A' means the dependency does not hold anymore.

E-R model is an Entity-Relationship model which defines the conceptual view of the database. The E-R model basically shows the real-world entities and their association/relations. Entities here represent the set of attributes in the database.

Entity: Entity can be anything, be it a place, class or object which has an independent existence in the real world.

Entity Type: Entity Type represents a set of entities that have similar attributes.

Entity Set: Entity Set in the database represents a collection of entities having a particular entity type.

Weak Entity set is the one whose primary key comprises its partial key as well as the primary key of its parent entity. This is the case because the entity set may not have sufficient attributes to form a primary key.

Attribute: Attribute is described as the properties or characteristics of an entity. For Example, Employee ID, Employee Name, Age, etc., can be attributes of the entity Employee.

Relation: Relation is a two-dimensional table containing a number of rows and columns where every row represents a record of the relation. Here, rows are also known as 'Tuples' and columns are known as 'Attributes'.

Sequence of operation performed which changes the consistent state of the database to another is known as the database transaction. After the completion of the transaction, either the successful completion is reflected in the system or the transaction fails and no change is reflected.

Join is the process of deriving the relationship between different tables by combining columns from one or more tables having common values in each. When a table joins with itself, it is known as Self Join.

• Indexes are not present.
• Stored procedures are excessively compiled.
• Difficulty in interfacing.

a) Inner JOIN: Inner JOIN is also known as a simple JOIN. This SQL query returns results from both the tables having a common value in rows.

b) Natural JOIN: This is a type of Inner JOIN that returns results from both the tables having the same data values in the columns of both the tables to be joined.

c) Cross JOIN: Cross JOIN returns the result as all the records where each row from the first table is combined with each row of the second table.

d) Right JOIN: Right JOIN is also known as Right Outer JOIN. This returns all the rows as a result from the right table even if the JOIN condition does not match any records in the left table.

e) Left JOIN: Left JOIN is also known as Left Outer JOIN. This returns all the rows as a result of the left table even if the JOIN condition does not match any records in the right table.

f) Outer/Full JOIN: Full JOIN return results in combining the result of both the Left JOIN and Right JOIN.

Data dictionary is a set of information describing the content and structure of the tables and database objects. The job of the information stored in the data dictionary is to control, manipulate and access the relationship between database elements.

Primary Key: Primary Key is that column of the table whose every row data is uniquely identified. Every row in the table must have a primary key and no two rows can have the same primary key. Primary key value can never be null nor can it be modified or updated.

Composite Key: Composite Key is a form of the candidate key where a set of columns will uniquely identify every row in the table.

A Unique key is the same as the primary key whose every row data is uniquely identified with a difference of null value i.e. Unique key allows one value as a NULL value.

Different data models are:

• Relational model
• Network model
• Hierarchical model

• After the execution of 'DELETE' operation, COMMIT and ROLLBACK statements can be performed to retrieve the lost data.
• After the execution of 'TRUNCATE' operation, COMMIT, and ROLLBACK statements cannot be performed to retrieve the lost data.
• 'DROP' command is used to drop the table or key like the primary key/foreign key

This is a coding problem that requires identifying consecutive odd numbers in a linked list and reversing them.

Find the second largest element in an array using a single loop with O(N) time complexity.

This is a sliding window problem to find the maximum sum of a subarray of given size.

Determine if a Binary Search Tree is a reflection (mirror image) of another BST.

Detect if a linked list forms a circle (the last node points back to any previous node).

Use Floyd's Cycle Detection Algorithm (Tortoise and Hare) to detect cycles in a linked list.

Find the first character in a string that appears only once.

Implement the Fibonacci sequence using recursion.

Explain the traversal mechanism and implementation of Bubble Sort and Selection Sort algorithms.

Implement the merge sort algorithm using divide and conquer approach.

Delete a node from a linked list when you only have access to that node (not the head).

You are given a singly linked list e.g 1->2->3->4->5. Suppose that your head is pointing on 4. You have to delete the 5th Node. Note: You cannot move the pointer backwards.

You have two unsorted arrays. You have to merge two arrays in the sorted manner. (Need Best Solution).

Determine if a string reads the same forwards and backwards.

You are given an array. Find the pair of numbers whose sum is equal to 5.

You are given a linked list with a head pointer only. Your task is to add a new node to the linked list at the end. (Note: You have only one pointer pointing at head)

E.g 1->2->3->4->5

New node will be appended after 5.

Interviews usually start with the question "Tell us something about yourself". This is the very beginning of your interview where you have to be very precise about your answer because interviewers are expecting many things from you out of this question.

Your answer should reflect:

• Your Information
• Your past education
• Your FYP (optional)
• Your past industrial experience
• If you don't have any industrial experience then mention your FYP and self projects and learnings

Try to get to know about the company for which you are applying and before appearing in the interview. Get to know about them by visiting their website or LinkedIn profiles. This will help you to answer the question "What do you know about us?"

This is a common interview question that requires you to demonstrate your knowledge about the company and align your career goals with their mission and values.

Confidence is the key to pass an interview. Show confidence in your abilities and answers.

Try to avoid narrating stories rather than actual answers. Be concise and direct in your responses.

Don't hesitate to tell interviews you don't know the answer. Just be formal saying "I am not sure about the answer for this question but I'll go through it later".

Interviewers usually end the interview by asking you "Do you have any questions?". Try to show them your interest. Come up with questions and feel free to ask them.