SDE - 1

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.

A cycle occurs when a node's next points back to a previous node in the list.

Example:

In the given linked list, there is a cycle, hence we return true.

You have been given an undirected graph with 'N' vertices and 'M' edges. The vertices are labelled from 1 to 'N'.

Your task is to find if the graph contains a cycle or not.

A path that starts from a given vertex and ends at the same vertex traversing the edges only once is called a cycle.

Example :

In the below graph, there exists a cycle between vertex 1, 2 and 3. 

Note:

1. There are no parallel edges between two vertices.

2. There are no self-loops(an edge connecting the vertex to itself) in the graph.

3. The graph can be disconnected.

For Example :

Input: N = 3 , Edges =  [[1, 2], [2, 3], [1, 3]].
Output: Yes

Explanation : There are a total of 3 vertices in the graph. There is an edge between vertex 1 and 2, vertex 2 and 3 and vertex 1 and 3. So, there exists a cycle in the graph. 

Implement a Trie Data Structure which supports the following three operations:

Operation 1 - insert(word) - To insert a string WORD in the Trie.

Operation 2-  search(word) - To check if a string WORD is present in Trie or not.

Operation 3-  startsWith(word) - To check if there is a string that has the prefix WORD.

Trie is a data structure that is like a tree data structure in its organisation. It consists of nodes that store letters or alphabets of words, which can be added, retrieved, and deleted from the trie in a very efficient way.

In other words, Trie is an information retrieval data structure, which can beat naive data structures like Hashmap, Tree, etc in the time complexities of its operations.

The above figure is the representation of a Trie. New words that are added are inserted as the children of the root node. 

Alphabets are added in the top to bottom fashion in parent to children hierarchy. Alphabets that are highlighted with blue circles are the end nodes that mark the ending of a word in the Trie.

For Example:-

Type = ["insert", "search"], Query = ["coding", "coding].
We return ["null", "true"] as coding is present in the trie after 1st operation.

 Interface vs abstract class, heap memory vs stack memory, collections, Exception Handling etc.

 Difference between Merge Sort vs Quick Sort.

- Brief Introduction of myself, my current location, my education details
- Information about my current Organisation
- Why do I want to join Samsung?
- My strengths & weaknesses