A celebrity/influencer is a person who doesn’t know anybody but is known to or followed by everybody. Given N peoples and a matrix for known or following information then find the celebrity or influencer among the group of N peoples. Formally speaking, Given a matrix of following between N users (with ids from 0 to […]
Author Archives: Zrzahid
Given a string (haystack) and a pattern (needle). Find all the anagrams of the pattern that are contained in the string. For example: str = “abateatas” and pattern = “tea”. Then output should be the anagrams of “tea” contained as a substring in str. So, the desired output = {“ate”, “eat”, “tea”}. A quick bruteforce […]
Given an array consisting of N Numbers. Divide it into two Equal partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum. If number of elements are odd difference in partition size can be at most 1. The problem is a specialization of SubSet Sum problem which decides whether we […]
Find the element which repeated more than n/2 times in an given array of integers. For example, A=[2, 2, 3, 2, 3, 3, 1, 3, 1]. We can clearly see that 3 is the majority. A quick an dirty solution would be to either use a Hashmap to count frequency of each element and keep […]
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last. Example Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}; Output = {0, 0, 0, 0, 0, 1, 1, 1, […]
Given an array of integer, find duplicates which are within k indices away. Find duplicates within K manhattan distance away in a matrix or 2D array. Return true or false if such elements exists. For example, a=[1, 2, 3, 1, 3, 5] then for k ≤ 1 return false as no duplicates in k index away. For […]
The first difference is the syntax. Other than that, the major differences are: C++ * OOP is optional. * Compiled: produces non-portable native code. * Manually managed memory. Garbage collection libraries are available. * Source can be written to be portable, so a correctly written program can be compiled for any platform where a C++ […]
Given an array of Integer. Find number of smaller elements at each position. Array may have duplicate elements. The brute force solution for this problem would be to traverse the array from right to left and count number of smaller element on the right in O(n^2). Faster Implementation I have described in a previous post how to […]
Given an integer array, count the number of inversions. Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse […]
Given an infix expression with binary operators convert it to reverse polish notation (RPN) and evaluate the expression. For example, the RPN form of the expression 3+2 is 32+. Similarly RPN for 3+4*2/(1-5)*2/3 is 342*15-/2*3/+ and the value of the expression is 1.66. We can convert an infix expression to a reverse polish notation expression […]