Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

public class MinimumCostToConstructRoad {
        public class GraphMinHeap<T> where T : IComparable {
            T[] hp = null;
            Hashtable keytoIndex = null;
            int Size = 0;
            public GraphMinHeap (int size) {
                hp = new T[size];
                keytoIndex = new Hashtable ();
            }
            public int GetParentIndex (int i) {
                return i - 1 / 2;
            }
            public int GetLeftChildIndex (int i) {
                return 2 * i + 1;
            }
            public int GetRightChildIndex (int i) {
                return 2 * i + 2;
            }
            public void Enqueue (T data) {
                this.keytoIndex.Add (data, Size);
                this.hp[Size] = data;
                if (this.Size > 0) {
                    this.HeapifyUP (this.Size);
                }
                this.Size++;
            }
            public T Peek () {
                if (this.Size == 0) {
                    throw new Exception ("Heap is empty");
                }
                return this.hp[0];
            }
            public T Dequeue () {
                if (this.Size == 0) {
                    throw new Exception ("Heap is empty");
                }
                var result = this.hp[0];
                this.Size--;
                if (this.Size != 0) {
                    this.Swap (0, this.Size);
                    this.HeapifyDown (0);
                }
                return result;
            }
            public bool IsContain (T key) {
                return this.keytoIndex.Contains (key);
            }
            public void DecreaseKey (T key, T newValue) {
                if (this.keytoIndex.Contains (key) == false) {
                    throw new Exception ("Key not found in heap");
                }
                int keyIndex = (int) this.keytoIndex[key];
                this.keytoIndex.Remove (key);
                this.hp[keyIndex] = newValue;
                this.keytoIndex.Add (newValue, keyIndex);
                this.HeapifyUP (keyIndex);
            }
            public bool IsEmpty () {
                return this.Size > 0;
            }
            public void Swap (int i, int j) {
                T temp = this.hp[i];
                this.hp[i] = this.hp[j];
                this.hp[j] = temp;
                this.keytoIndex[this.hp[i]] = i;
                this.keytoIndex[this.hp[j]] = j;
            }
            public void HeapifyUP (int i) {
                while (true) {
                    if (i <= 0) {
                        break;
                    }
                    int parentIndex = this.GetParentIndex (i);

                    if (this.hp[i].CompareTo (this.hp[parentIndex]) >= 0) {
                        break;
                    }
                    this.Swap (parentIndex, i);
                    i = parentIndex;
                }
            }
            public void HeapifyDown (int i) {
                while (true) {
                    int leftChildIndex = this.GetLeftChildIndex (i);
                    int rightChildIndex = this.GetRightChildIndex (i);
                    if (leftChildIndex > this.Size) {
                        break;
                    }
                    int minChildIndex = leftChildIndex;
                    if (rightChildIndex < this.Size &&
                        this.hp[rightChildIndex].CompareTo (this.hp[leftChildIndex]) <= 0) {
                        minChildIndex = rightChildIndex;
                    }
                    if (this.hp[i].CompareTo (this.hp[minChildIndex]) <= 0) {
                        break;
                    }
                    this.Swap (i, minChildIndex);
                    i = minChildIndex;

                }
            }

        }
        public class SimpleVertex : IComparable {
            public int Weight {
                get;
                set;
            }
            public int Data {
                get;
                set;
            }
            public List<SimpleEdge> Edges {
                get;
                set;
            }
            public SimpleVertex (int data) {
                this.Data = data;
                this.Weight = int.MaxValue;
                this.Edges = new List<SimpleEdge> ();
            }

            public int CompareTo (object obj) {
                var other = (SimpleVertex) obj;
                if (this.Weight == other.Weight) {
                    return 0;
                } else if (this.Weight > other.Weight) {
                    return 1;
                } else {
                    return -1;
                }
            }
        }
        public class SimpleEdge {
            public SimpleVertex Source {
                get;
                set;
            }
            public SimpleVertex Destination {
                get;
                set;
            }
            public int Weight {
                get;
                set;
            }
            public SimpleEdge (SimpleVertex source, SimpleVertex destinaion, int weight) {
                this.Source = source;
                this.Destination = destinaion;
                this.Weight = weight;
            }
        }
        public class SimpleGraph {

            private Dictionary<int, SimpleVertex> vertices = new Dictionary<int, SimpleVertex> ();
            public int NumberOfVertices {
                get;
                set;
            }
            public List<SimpleVertex> GettAllVertices () {
                return this.vertices.Values.ToList ();
            }
            public SimpleGraph (int numberOfVertices) {
                this.NumberOfVertices = numberOfVertices;
            }
            public void AddEdge (int x, int y, int weight) {
                SimpleVertex source = null;
                if (this.vertices.ContainsKey (x)) {
                    source = (SimpleVertex) this.vertices[x];
                } else {
                    source = new SimpleVertex (x);
                    this.vertices.Add (x, source);
                }
                SimpleVertex destinaion = null;
                if (this.vertices.ContainsKey (y)) {
                    destinaion = (SimpleVertex) this.vertices[y];
                } else {
                    destinaion = new SimpleVertex (y);
                    this.vertices.Add (y, destinaion);
                }
                var edge = new SimpleEdge (source, destinaion, weight);
                source.Edges.Add (edge);
            }
            public IList<SimpleEdge> GetMST (SimpleGraph graph) {
                // map of vertex to edge which will give minimum weight to this vertex
                var vertexToEdge = new Dictionary<SimpleVertex, SimpleEdge> ();
                // store final result
                List<SimpleEdge> result = new List<SimpleEdge> ();
                // binary heap + map data structure
                var pq = new GraphMinHeap<SimpleVertex> (graph.NumberOfVertices + 1);
                // insert all vertices to pq
                foreach (var vertex in graph.GettAllVertices ()) {
                    pq.Enqueue (vertex);
                }
                var startVertex = graph.GettAllVertices () [0];
                // decrease the weight of startvertex to 0
                startVertex.Weight = 0;
                pq.DecreaseKey (startVertex, startVertex);
                // iterate till heap + map datastructure has element in it.
                while (pq.IsEmpty ()) {
                    // get miniumu weight value from pq
                    var current = pq.Dequeue ();

                    //get the corresponding edge for this vertex if present and add it to final result.
                    //This edge wont be present for first vertex.
                    if (vertexToEdge.ContainsKey (current)) {
                        result.Add (vertexToEdge[current]);
                    }
                    // iterate through all the adjacent vertices
                    foreach (var edge in current.Edges) {
                        //check if adjacent vertex exist in heap + map and weight attached with this 
                        // vertex is greater than this edge weight
                        var neighbour = this.GetVertexForEdge (current, edge);
                        if (pq.IsContain (neighbour) && neighbour.Weight > edge.Weight) {
                            //decrease the value of adjacent vertex to this edge weight.
                            neighbour.Weight = edge.Weight;
                            pq.DecreaseKey (neighbour, neighbour);
                            //add vertex->edge mapping in the graph.
                            vertexToEdge[neighbour] = edge;
                        }
                    }
                }
                return result;
            }
            private SimpleVertex GetVertexForEdge (SimpleVertex vertex, SimpleEdge edge) {
                if (edge.Source.Equals (vertex)) {
                    return edge.Destination;
                } else {
                    return edge.Source;
                }
            }
        }
        /*
        
        Time complexity : Heap + Map data structure  has foure functions
        1) Enqueue : O(logV)
        2) Dequeue : O(logV)
        3) Contain : O(1)
        4) DecreaseKey : O(logV)
        In wrost case it migth need to stroe entire vertices to heap + map data structure
        O(Elog(V))
        Space Complexity: Storing MST edges in list , map to keep track vertex to edge and heap + map data structure
        So in wrost case it will be O(V + E). Because we might end up stroing all edges of graph.

         */
        public int getMinimumCostToConstruct (int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[, ] roadsAvailable,
            int numNewRoadsConstruct,
            int[, ] costNewRoadsConstruct)

        {
            var graph = new SimpleGraph (numTotalAvailableCities);
            for (int i = 0; i < roadsAvailable.GetLength (0); i++) {
                graph.AddEdge (roadsAvailable[i, 0], roadsAvailable[i, 1], 0);
            }
            for (int i = 0; i < costNewRoadsConstruct.GetLength (0); i++) {
                graph.AddEdge (costNewRoadsConstruct[i, 0], costNewRoadsConstruct[i, 1], costNewRoadsConstruct[i, 2]);
            }
            var mstedges = graph.GetMST (graph);
            int result = 0;
            foreach (var edge in mstedges) {
                result += edge.Weight;
            }
            return result;
        }
    }

- Anonymous January 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Kruskal's to find out the MST. Use a DSU to maintain already connected nodes. Initialize DSU with already built nodes.

- happysingshappy January 10, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More