<\/span><\/h2>\n\n\n\nFor higher roles at TCS, interviewers usually look for experienced candidates who have an advanced understanding of technical principles, problem-solving abilities, and leadership skills. Here are some of the advanced TCS coding interview questions and answers for experienced candidates:<\/p>\n\n\n\n
Q31. Write a code to design and implement a Least Recently Used (LRU) cache.<\/h3>\n\n\n\n Sample Answer: <\/strong>An LRU (Least Recently Used) Cache stores a fixed number of items. When the cache reaches its capacity, it removes the least recently used item to make room for new data. In this implementation, we use Python’s OrderedDict from the collections module to maintain the order of insertion. The move_to_end() method allows us to efficiently update the order when items are accessed. The following code illustrates how to design and implement a LRU cache.<\/p>\n\n\n\nfrom collections import OrderedDict\n\nclass LRUCache:\n def __init__(self, capacity: int):\n self.cache = OrderedDict()\n self.capacity = capacity\n\n def get(self, key: int) -> int:\n if key not in self.cache:\n return -1\n self.cache.move_to_end(key)\n return self.cache[key]\n\n def put(self, key: int, value: int) -> None:\n if key in self.cache:\n self.cache.move_to_end(key)\n self.cache[key] = value\n if len(self.cache) > self.capacity:\n self.cache.popitem(last=False)\n\n# Example usage:\n# cache = LRUCache(2)\n# cache.put(1, 1)\n# cache.put(2, 2)\n# cache.get(1) # Returns 1\n# cache.put(3, 3) # Evicts key 2\n# cache.get(2) # Returns -1\n<\/code><\/pre>\n\n\n\nQ32. How can you find the Kth largest element in an unsorted array?<\/h3>\n\n\n\n Sample Answer: <\/strong>To find the kth largest element in an unsorted array, we can use Python’s heapq library. The heapq.nlargest(k, nums) function returns the k largest elements from the list in sorted order. We can simply return the last element of this list to get the kth largest element. Here\u2019s how we can find the Kth largest element in an unsorted array.<\/p>\n\n\n\nimport heapq\n\ndef kth_largest(nums, k):\n return heapq.nlargest(k, nums)[-1]\n\n# Test case\nprint(kth_largest([3, 2, 1, 5, 6, 4], 2)) # Output: 5\n<\/code><\/pre>\n\n\n\nQ33. Write a program to implement trie data structure.<\/h3>\n\n\n\n Sample Answer: <\/strong>A Trie is a tree-like data structure used to store strings, often used for tasks like autocomplete or spell checking. Each node represents a character, and the edges between nodes represent the sequence of characters in a string. Here is the code to implement a trie data structure:<\/p>\n\n\n\nclass TrieNode:\n def __init__(self):\n self.children = {}\n self.is_end_of_word = False\n\nclass Trie:\n def __init__(self):\n self.root = TrieNode()\n\n def insert(self, word: str) -> None:\n node = self.root\n for char in word:\n if char not in node.children:\n node.children[char] = TrieNode()\n node = node.children[char]\n node.is_end_of_word = True\n\n def search(self, word: str) -> bool:\n node = self.root\n for char in word:\n if char not in node.children:\n return False\n node = node.children[char]\n return node.is_end_of_word\n\n def starts_with(self, prefix: str) -> bool:\n node = self.root\n for char in prefix:\n if char not in node.children:\n return False\n node = node.children[char]\n return True\n\n# Example usage:\n# trie = Trie()\n# trie.insert(\"apple\")\n# trie.search(\"apple\") # Returns True\n# trie.starts_with(\"app\") # Returns True\n<\/code><\/pre>\n\n\n\nQ34. Write a program to implement Dijkstra\u2019s algorithm to find the shortest path in a graph.<\/h3>\n\n\n\n Sample Answer: <\/strong>Dijkstra’s algorithm finds the shortest paths between nodes in a graph. It starts with the source node and repeatedly updates the shortest distance to its neighboring nodes. Here\u2019s how we can implement Dijkstra\u2019s algorithm to find the shortest path in a graph.<\/p>\n\n\n\nimport heapq\n\ndef dijkstra(graph, start):\n distances = {node: float('inf') for node in graph}\n distances[start] = 0\n priority_queue = [(0, start)]\n \n while priority_queue:\n current_distance, current_node = heapq.heappop(priority_queue)\n \n if current_distance > distances[current_node]:\n continue\n \n for neighbor, weight in graph[current_node].items():\n distance = current_distance + weight\n if distance < distances[neighbor]:\n distances[neighbor] = distance\n heapq.heappush(priority_queue, (distance, neighbor))\n \n return distances\n\n# Test case\n# graph = {'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1}}\n# print(dijkstra(graph, 'A')) # Output: shortest paths from 'A' to all nodes\n<\/code><\/pre>\n\n\n\nQ35. Write functions to serialize and deserialize a binary tree.<\/h3>\n\n\n\n Sample Answer: <\/strong>Serialization converts a binary tree into a string format, which can be stored or transmitted. Deserialization converts the string back into a binary tree. The approach used in the sample involves Depth-First Search (DFS) to traverse the tree and capture the node values. The following function illustrates how we can serialize and deserialize a binary tree.<\/p>\n\n\n\nclass TreeNode:\n def __init__(self, val=0, left=None, right=None):\n self.val = val\n self.left = left\n self.right = right\n\ndef serialize(root):\n result = []\n def dfs(node):\n if not node:\n result.append(\"None\")\n return\n result.append(str(node.val))\n dfs(node.left)\n dfs(node.right)\n \n dfs(root)\n return ','.join(result)\n\ndef deserialize(data):\n values = iter(data.split(','))\n def dfs():\n val = next(values)\n if val == \"None\":\n return None\n node = TreeNode(int(val))\n node.left = dfs()\n node.right = dfs()\n return node\n \n return dfs()\n\n# Example usage:\n# tree = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))\n# serialized = serialize(tree)\n# deserialized = deserialize(serialized)\n<\/code><\/pre>\n\n\n\nQ36. How can you find the median of two sorted arrays of different sizes?<\/h3>\n\n\n\n Sample Answer: <\/strong>To find the median of two sorted arrays, we can merge them and then find the median of the combined array. This approach assumes merging is acceptable for simplicity. Here is the code to implement this:<\/p>\n\n\n\ndef find_median_sorted_arrays(nums1, nums2):\n nums = sorted(nums1 + nums2)\n mid = len(nums) \/\/ 2\n return (nums[mid] + nums[~mid]) \/ 2\n\n# Test case\nprint(find_median_sorted_arrays([1, 3], [2])) # Output: 2.0\nprint(find_median_sorted_arrays([1, 2], [3, 4])) # Output: 2.5\n<\/code><\/pre>\n\n\n\nQ37. Create a code to find all possible paths between two nodes in a graph.<\/h3>\n\n\n\n Sample Answer: <\/strong>This problem is about finding all paths from a start node to an end node in an undirected graph, which is represented using an adjacency list. The following code demonstrates the possible paths between two nodes in a graph.<\/p>\n\n\n\ndef all_paths(graph, start, end, path=[]):\n path = path + [start]\n if start == end:\n return [path]\n paths = []\n for node in graph[start]:\n if node not in path:\n new_paths = all_paths(graph, node, end, path)\n for new_path in new_paths:\n paths.append(new_path)\n return paths\n\n# Test case\n# graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}\n# print(all_paths(graph, 'A', 'D')) # Output: [['A', 'B', 'D'], ['A', 'C', 'D']]\n<\/code><\/pre>\n\n\n\nQ38. Given two words and a dictionary, find the shortest transformation sequence from start to end.<\/h3>\n\n\n\n Sample Answer: <\/strong>In this problem, we need to find the shortest transformation sequence from a start word to an end word. Here, each word in the sequence must differ by exactly one letter, and each intermediate word must be in the given word list. Here\u2019s how we can find the shortest transformation sequence from start to end.<\/p>\n\n\n\nfrom collections import deque\n\ndef word_ladder(beginWord, endWord, wordList):\n word_set = set(wordList)\n queue = deque([(beginWord, 1)])\n \n while queue:\n word, length = queue.popleft()\n if word == endWord:\n return length\n for i in range(len(word)):\n for char in 'abcdefghijklmnopqrstuvwxyz':\n next_word = word[:i] + char + word[i+1:]\n if next_word in word_set:\n word_set.remove(next_word)\n queue.append((next_word, length + 1))\n \n return 0\n\n# Test case\n# wordList = [\"hot\", \"dot\", \"dog\", \"lot\", \"log\", \"cog\"]\n# print(word_ladder(\"hit\", \"cog\", wordList)) # Output: 5\n<\/code><\/pre>\n\n\n\nQ39. Write a program to find the kth smallest element in a Binary Search Tree.<\/h3>\n\n\n\n Sample Answer: <\/strong>The BST property ensures that in an inorder traversal, the elements will be visited in ascending order. By performing an inorder traversal, we can find the kth smallest element. Here is the code to find the kth smallest element in a Binary Search Tree.<\/p>\n\n\n\nclass TreeNode:\n def __init__(self, val=0, left=None, right=None):\n self.val = val\n self.left = left\n self.right = right\n\ndef kth_smallest(root, k):\n def inorder(node):\n return inorder(node.left) + [node.val] + inorder(node.right) if node else []\n \n return inorder(root)[k - 1]\n\n# Example usage:\n# root = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))\n# print(kth_smallest(root, 1)) # Output: 1\n<\/code><\/pre>\n\n\n\nQ40. How can you implement a Min-Heap data structure from scratch?<\/h3>\n\n\n\n Sample Answer: <\/strong>A Min-Heap is a binary heap where the parent node is smaller than its children. The heap property ensures that the smallest element is always at the root. Here\u2019s how we implement a Min-Heap data structure from scratch.<\/p>\n\n\n\nclass MinHeap:\n def __init__(self):\n self.heap = []\n\n def insert(self, val):\n self.heap.append(val)\n self._heapify_up(len(self.heap) - 1)\n\n def extract_min(self):\n if len(self.heap) == 0:\n return None\n if len(self.heap) == 1:\n return self.heap.pop()\n root = self.heap[0]\n self.heap[0] = self.heap.pop()\n self._heapify_down(0)\n return root\n\n def _heapify_up(self, index):\n parent = (index - 1) \/\/ 2\n if index > 0 and self.heap[index] < self.heap[parent]:\n self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]\n self._\n<\/code><\/pre>\n\n\n\nPro Tip: <\/strong>Aside from the technical roles, TCS also offer jobs in the business process services domain. Check out our guide on BPS job interview questions at TCS<\/a>.<\/p>\n\n\n\n