Binary Heap
Binary heap is used to implement Priority queue. It is an array object, visualized as an almost complete binary tree. Binary heap comes in two flavours Max-Heap Min-Heap A max-heap is an almost complete binary tree, where, value at each node is greater than the value of its children. Similarly, a min-heap is an almost complete binary tree where […]
Almost complete Binary Tree
A complete Binary tree of height h has 2h-1 nodes. Out of these 2h-1 are leaf nodes and rest (2h-1-1 are non-leaf. Read more about complete binary trees here or watch video. Below are all complete binary trees:
Coin heap puzzle
You are blindfolded and 10 coins are place in front of you on table. 5 are having their heads-side up and 5 are having their tails-side facing upward. You cannot tell which way they are by touching the coin. You are allowed to touch the coins and flip them as many times as you want. How […]
Minimum edit distance of two strings
Given two strings of size m and n respectively, find the minimum number of operations required to transform one string into another. The following thee operations are allowed Insert(pos, ch) – Insert a character at a position in the string. Delete(position) – Delete a character from a position in the string. Replace(position, character) – Replace […]
Check if array can be divided in two parts with equal sum
Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example: If Input array is {10, 20 , 30 , 5 , 40 , 50 , 40 , 15} Output: true Divide the array in two parts {0, 20, 30, 5, 40} […]
Print permutations of string replaced with digits
Given a string, print the variation of string as shown below Input String: ‘hat’ Replace one character with numeric one(‘1’): ‘1at‘, ‘h1t‘, ‘ha1‘ Replace two characters with ‘1’ each: ‘11t‘, ‘h11‘, ‘1a1‘ Replace three characters with ‘1’ each: ‘111‘ In all the strings above, wherever the numeric characters are consecutive, add them. So ’11t’ will become ‘2t’, Similarly ‘111’ […]
Helper Function: Return the terminating number in a string
Given a string that is terminating with digits (eg. ‘Kamal1234’). Write a function which accept this string and return the integer at the end. Input String: ‘Kamal1234’ Output (int): 1234 Input String: ‘Moksha023Kam05’ Output (int):5
Helper Function: Convert String to Number
Given a String. Write a function that convert it to number. Such functions are used in larger programs as helper functions. Input: char* str = “0324”; Output: int 324;
Helper Function: Check if character is a digit or not
Write a Simple function that accepts a character and return true if it is a digit else return false:
Helper Function: Reverse a Number
Sometimes we need helper functions in our code. One such helper function needed is to reverse a number. i.e a function which returns me ‘321’ if I pass ‘123’ to it. Implement the following function int reverseNum(int num) The function should accept an integer and should return an integer whose digits are reverse of the original number.
