Hello friends, no matter what is your experience level. You are supposed to know the data structures and algorithm concepts to clear the technical interview round. This is the case for almost all tech companies and at any experience level. In this article, I will list down top 5 basic data structure and algorithm problems.
Reverse a string
Provided a string as input, write a program to reverse the string.
This is one of the most basic interview question, and not very difficult to answer as well. The first thought you may get is to take a new string variable and start traversing the provided string from back. Finally keep adding the characters to the newly created string variable.
But interview may not be satisfied here and may want you to write a solution without using the another string variable.
In that case, you need to follow two pointer solution. As part of this solution, first convert the string to character array. Then you need to take two pointers, one at the start and another one at the end of the character array.
public static string ReverseString(string str) { char[] charArray = str.ToCharArray(); int i = 0, j = charArray.Length - 1; while (i <= j) { char test = charArray[i]; charArray[i] = charArray[j]; charArray[j] = test; i++; j--; } return new string(charArray); }
Insert a node to sorted Linked List
Provided a sorted linked list as shown in the below code, insert the node at the correct position. For example, insert the node with value 5 in the below linked list.
1 -> 2 -> 4 -> 5 -> 6 -> 7
Below is the code to solve the problem.
If the linked list is null, return the node itself.
If the first element of the linked list is more than or equal to the inserted node, prepend the node at the beginning of the linked list.
public static LinkedListNode InsertNode(LinkedListNode node, LinkedListNode nodeToBeInserted) { if (node == null) return nodeToBeInserted; if(node.val >= nodeToBeInserted.val) { nodeToBeInserted.next = node; return nodeToBeInserted; } var beginOfLinkedList = node; var isInserted = false; while (node.next != null) { var previousNode = node; if (previousNode.val < nodeToBeInserted.val && node.next.val >= nodeToBeInserted.val) { nodeToBeInserted.next = previousNode.next; previousNode.next = nodeToBeInserted; isInserted = true; } node = node.next; } if (!isInserted) node.next = nodeToBeInserted; return beginOfLinkedList; }
Compress A String
Provided a string like “aaaabbbbbcccaaaaddddd”, write a method which can return the compressed form of the string. The compressed form of the string would be occurrence of the number of characters with that specific character.
For example the compressed form of the above string would be “4a5b3c4a5d”.
The first though you would get while solving this type of question would be to use a hash table or dictionary. But as you can see from the problem string that it is not mandatory that the characters would be present continuously in the string. There could be occurrence of the same character at different locations.
The best solution would be to have a string builder, count the number of occurrences of the character and append it to the string builder. You would keep increasing the count till the current character is same as the previous one.
public static string CompressAString(string input) { StringBuilder sbReturn = new StringBuilder(); char[] charArray = input.ToCharArray(); int charCount = 1; for (int i = 0; i < charArray.Length; i++) { if (i == 0) continue; if(charArray[i - 1] == charArray[i]) { charCount++; } else if (charArray[i -1] != charArray[i]) { sbReturn.Append(charCount + charArray[i - 1].ToString()); charCount = 1; } } sbReturn.Append(charCount + charArray[charArray.Length - 1].ToString()); return sbReturn.ToString(); }
First And Last index of element in Sorted Array
Provided a sorted array E.g: {1,2,3,5,5,5,5,6,7}. Find the first and Last index of the target e.g. 5 in the array. [3, 6]. Else return [-1, -1].
The first way to come to a solution for the problem is to traverse the whole array. And find the first index where the element exists. And take another inner loop to find the second index as shown in the below code example.
public int[] ReturnFirstAndLastIndexOfTargetInSortedArrayByTraversing(int[] arr, int target) { int[] result = { -1, -1 }; int start; for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { start = i; while (i < arr.Length && arr[i] == target) { i += 1; } return new int[] { start, i }; } } return new int[] { -1, -1 }; }
The above way is bit in efficient as you have to traverse the whole array. The time complexity of the solution is n.
The more efficient solution would be to use the binary search.
public int[] ReturnFirstAndLastIndexOfTargetInSortedArray(int[] arr, int target) { int[] result = new int[2]; if (arr.Length == 0 || arr[0] > target || arr[arr.Length - 1] > target) return new int[] { -1, -1 }; result[0] = FindStart(arr, target); result[1] = FindEnd(arr, target); return result; } private int FindEnd(int[] arr, int target) { if (arr[arr.Length - 1] == target) { return arr.Length - 1; } int left = 0, right = arr.Length - 1, mid; while (left <= right) { mid = (left + right) / 2; if (arr[mid] == target && arr[mid + 1] > arr[mid]) return mid; else if (arr[mid] > target) right = mid - 1; else left = mid + 1; } return -1; } private int FindStart(int[] arr, int target) { if(arr[0] == target) { return 0; } int left = 0, right = arr.Length - 1, mid; while (left <= right) { mid = (left + right) / 2; if (arr[mid] == target && arr[mid - 1] < arr[mid]) return mid; else if (arr[mid] > target) right = mid - 1; else left = mid + 1; } return -1; }
Symmetric Trees
Provided two trees, check if both of them are symmetric or not. Trees are symmetric if they are mirror images of each other.
From the problem statement it seems like a very difficult one but actually it is not.
The simple logic to solve this problem is that, we have to write a recursive method and pass the both side of the node to this recursive method.
public static bool AreTreesSymmetric(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; else if (t1.val != t2.val) return false; else return AreTreesSymmetric(t1.left, t2.right) && AreTreesSymmetric(t1.right, t2.left); }