Given an unsorted array, find the majority element. Majority element is defined as that element which occurs for more than N/2 times. If the majority element exists, there will only be one such element. We can do this in O(N) time by the Boyer–Moore majority voting algorithm.
Problem Statement – Suppose we have a sorted array, and now we rotate it N times, find the pivot element. The pivot element would be the largest element. Also, can you calculate N? Clues – Solution should be O(log N) in time and O(1) in space. Can you think of a binary search based solution […]
Given an unsorted array of N elements, find the kth smallest element. This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array.
Given two sorted arrays, find the intersection (elements present in both arrays). We can do this in O(M + N) time, where M and N are lengths of arrays. What we will do here is similar to the “merging” step in merge sort.
Problem Statement – Given an array of numbers where all numbers appear twice except for one number which appears only once, find that number. Clues – Solution should be O(N) in time and O(1) in space. Use bit operations. Solution – XOR of two same numbers is zero. So, if we take the XOR of […]
Hello people! In this post we will look at one of the most basic Artificial Intelligence algorithm, the MiniMax algorithm. MiniMax algorithm is used to implement basic AI or game logic in 2 player games. The most common scenario is implementing a perfect Tic-Tac-Toe player. So, in this article we will look at how to […]
Hello, people…! In this post, we will explore the next part of object oriented programming in Java which is Inheritance. Inheritance Inheritance is a feature of object oriented programming which allows a class to be created from an existing class. More formally, inheritance is the process by which the new child subclass automatically includes any […]
Hello, people! In this post, we will discuss a commonly used data structure to store strings, the Compress Trie Tree, also known as Radix Tree or Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) Tree. If you remember, the problem with a Trie Tree is that it consumes a lot of memory. So, due to […]
Hello, people…! In this post, we will discuss a new search algorithm, Jump Search, which searches for an element in a sorted array in O(√N) time. It is slower than binary search, then why learn it? What if the interviewer purposely asks you to write a search algorithm with O(√N) worst case complexity? You would […]
Hello people..! In this post, we will see another dynamic programming based problem, finding the minimum edit distance between two strings. Problem – Given two strings A and B, we need to find the minimum number of operations which can be applied on A to convert it to B. The operations are – Edit – Change a […]