Fragen im Vorstellungsgespräch bei TriNet: difference between TCP and UD... |

Frage im Vorstellungsgespräch

Senior Software Engineer-Vorstellungsgespräch Pleasanton, CA (Vereinigte Staaten von Amerika)

difference between TCP and UDP, merge sort


Antwort im Vorstellungsgespräch

1 Antwort


TCP is a reliable point to point protocol for transmission of data. UDP is a best effort protocol and does not guarantee reliable delivery. But UDP is popular when it comes to multicasting data.

Merge Sort is a divide and conquer pattern for sorting data. The idea is to divide the data into two equal parts, merge the sorted parts and do this recursively. Time complexity is O(nlogn) where n is the number of items being sorted. A few salient points:

1. Merge sort typically requires an auxillary data structure to temporarily store a copy of the dataset being sorted. So space complexity of this sorting algorithm is O(n).

2. Merge sort is a 'stable' sort. Meaning the order of equal elements in the input is preserved in the output. This is important for reference type objects. For primitive types, stability is meaningless. Hence, for example, in Java, merge sort is used for reference types and Quick Sort (which is not stable) is used for primitive types.

3. Merge sort is pretty popular for 'external sorting'. When there is limited memory and there is a huge dataset to be sorted, the idea is to break the data into chunks, sort and merge these chunks in a streaming fashion. Can help to get away with limited memory, yet being able to sort huge data.

Java code goes like this:

public class Merge
public void sort(Comparable[] a)
     Comparable[] aux = new Comparable[a.length];
     sort(a, 0, a.length-1, aux);

private void sort(Comparable[] a, int lo, int hi, Comparable[] aux)
     if (hi < lo) return;

     int mid = lo + (hi - lo)/2;

     sort (a, lo, mid, aux);
    sort (a, mid+1, hi, aux);

    merge(a, lo, mid, hi, aux); //


VK am 14.11.2017

Antwort oder Kommentar posten

Um dies zu kommentieren, bitte anmelden oder Konto anlegen.