Data Structures and Algorithms
Question 1: How do you reverse a linked list using recursion (Java)?
I found the answer on this stackoverflow post “Reversing a linked list in Java, recursively”. This can be solved answering the following questions:
- What is the reverse of
null(the empty list)?
- What is the reverse of a one element list? the element.
- What is the reverse of an n element list? the reverse of the second element on followed by the first element.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Question 2: How do you find a length of a linked list?
Traverse through all the elements until you find the last node which points to
Question 3: How do you find the middle of a linked list using only one pass?
- Maintain two pointers as you traverse through the linked list.
- Increment Pointer 1 on every node and only increment Pointer 2 on every 2nd node.
- When you reach the end of the list, Pointer 2 will be pointing to the middle of the list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Read more here.
Question 4: Does a given linked list have a loop?
This is solved similarly to the question above “Question 3: How do you find the middle of a linked list using only one pass?”:
- Maintain 2 pointers as you traverse through the list.
- Increment Pointer 1 on every node and only increment Pointer 2 on every 2nd node.
- If Pointer 1 and Pointer 2 point to the same node, the list has a loop.
Question 5: An integer array has numbers from 1 to 100, there is a duplicate in the array. Find the duplicate.
- Add all the numbers stored in the array.
- Find the expected sum of all the numbers if there were no duplicates. The sum is represented by a formula
- Subtract the actual sum from the expected sum. The answer is the dulicate number.
- This works if there is 1 duplicate in the array, for multiple duplicates use a Hash Map, where the number is the key and the the occurence is the value. Any values larger than 1 will reveal the duplicates.
Question 6: What is the difference between a Stack vs a Queue?
A Stack is
LIFO (Last In First Out) structure and a Queue is a
FIFO (First In First Out) structure.
Question 7: What is a Binary Search Tree?
They are also sometimes called ordered or sorted binary trees, are a class of data structures used to implement lookup tables and dynamic sets. They store data items, known as keys, and allow fast insertion and deletion of such keys, as well as checking whether a key is present in a tree. In a binary search tree:
- Every left node is smaller than the root element.
- Every right node is larger than the root element.
- There are no duplicates in the binary search tree.
Question 8: How would you sort and array using a Bubble sort?
Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. Worst Case performance is
O(n^2), best case is
- Start comparing first and second element
arraythen swap numbers e.g.
array = arrayand
array = array.
- Repeat with the next two element,
arrayand so on until you reach the end of the list
- This is referred as one pass and at the end of first pass largest number is at last.
- Repeat this comparison again starting from
arraybut this time going till second last pair only
array[n - 1].
In a Bubble sort we need
n - 1 iteration to sort
n elements at end of first iteration largest number is sorted and subsequently numbers smaller than that.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Question 9: How would you check if a number is a palindrome?
Using a modulo we can determine if a number is a palindrome:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
Question 10: Describe a Selection Sort?
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has
O(n^2) time complexity, making it inefficient on large lists. It performs worse than the similar insertion sort.
- Divide the list into two parts: the sublist of items already sorted and the sublist of items left to be sorted. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
- Find the smallest or largest element in the unsorted sublist.
- Exchange places with the leftmost unsorted item.
- Repeat 2 & 3 until no unsorted items left.
Question 11: Describe a Shell Sort?
The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. It is similar to the Insertion sort that allows the exchange of items that are far apart. Worst case performance is
O(n^2), best case is O
(n log2 n). Picking the correct gaps is difficult, they should be reducing until the gap is 1.
Question 12: Describe an Insertion Sort?
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
- For each item, remove form unsorted and place in the correct place in teh sorted list or sub-list
- Move up all larger elements if required to place the item in the correct place.
Question 13: Describe a Quick Sort?
This is an efficient sorting algorithm. The steps are:
- Pick an element, called a pivot, from the array.
- Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way).
- After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
- The last element is ussually chosen as the pivot, but this will yeild a wort case complexity on an already sorted array or on an array of identical elements.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Question 14: Describe a Merge Sort?
A merge sort is an
O(n log n) comparison-based sorting algorithm. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
Conceptually, a merge sort works as follows:
- Divide the unsorted list into
nsublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Question 15: Describe a Heap Sort?
Heap sort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort.
Question 1: Explain what are selectors in CSS?
Selectors enable selecting an element to which a style is to be applied. There are different types of selectors, like
Question 2: Explain a CSS box model?
Each element is represented as a rectangular box. Each of these boxes is described using the standard box model. Each box has four edges: the margin edge, border edge, padding edge, and content edge.
There are two types of box model,
Question 3: What are pseudo classes and what are they used for?
Pseudo classes are similar to classes, but they are not defined in the markup. Some examples are
:first_line. They are used to call a specific action on an element, for example changng the link colour after it is visited, or changing a link colour when it is hovered.
Question 4: How do you optimize a website’s assets?
Some of the ways to optimize assets are:
- Make fewer HTTP requests
- Use a Content Delivery Network
- Add an Expires header
- Gzip components
- Put CSS at the top
- Move scripts to the bottom
- Remove duplicate scripts
Question 5: What are the 3 different ways to apply CSS?
Question 6: How is the float property implemented in CSS?
Floats allow an element to be positioned horizontally, allowing elements below the floated element to flow around it. Several floating elements can be placed together to make a gallery type layout. To prevent subsequent elements from flowing around the floated element, pass in the clear property, followed by the side you wish to disable (i.e., ‘left’, ‘right’, ‘both’).
Question 7: What is the purpose of the z-index and how is it used?
The z-index helps specify the stack order of positioned elements that may overlap one another.
Question 8: What’s the difference between standards mode and quirks mode?
One prominent difference between quirks and standards modes is the handling of the CSS Internet Explorer box model bug. Another notable difference is the vertical alignment of certain types of inline content.
If the browser decides that the document is modern, it’ll render it in standards mode. This means that, as a rule, CSS is applied in accordance with the CSS2 specification. If the browser decides that the document is old-school, it’ll render it in quirks mode.
Question 9: Graceful degradation vx progressive enhancement?
Graceful degredation - making sure that everythign still works to some level in an older browser, providing with basic functionality of the site.
Progressive enhancement - starting off with the oldest browsers in mind and adding in better functionality for browsers that can handle it.
Degrading gracefully means looking back whereas enhancing progressively means looking forward whilst keeping your feet on firm ground.