Interface in java

What is an Interface? An interface is a description of a set of methods that conforming implementing classes must have. An interface may never contain method definitions. One benefit of using interfaces is that they simulate multiple inheritance. All classes in Java must have exactly one base class. A Java class may implement, and an Read More →

Remove duplicate characters in a string

Given a string, Write a program to remove duplcate characters from the string. Input String : crazyforcode Output String : crazyfode Algorithm : 1. For each character, check if it is duplicate of already found characters. 2. Skip duplicate characters and update the non duplicate characters. Method 1 Using Extra Space. Time Complexity : O(N) Read More →

Boys and Girls

boys girls google interview puzzle

Question: In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) Answer: “very simple”. Half the couples have boys first, and Read More →

C program to reverse a string

For example if a user enters a string “crazyforcode” then on reversing the string will be “edocrofyzarc “. We show you two different methods to reverse string the first one we make our own function to reverse string using pointers and in second, reverse string using recursion. Method 2 : Using recursion In recursion method Read More →

Maximum sum in contiguous subarray

This is very famous interview question. Given an array A of integers (both positive and negative) and you need to find the maximum sum found in any contiguous subarray of A. Example A = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2] Answer is 30. There are many solutions to this problem. Method Read More →

Quick Sort

QuickSort is based on divide-and-conquer approach. QuickSort is inplace sorting algorithm.A sorting algorithm is said to be in-place if it requires very little additional space besides the initial array holding the elements that are to be sorted. The key to the Algorithm is the Partition Procedure, which rearranges the subarray a[p..r] in place. Partition selects Read More →

Ant and Triangle Problem

Ants and triangle puzzle

Puzzle: Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide? Puzzle Solution: So let’s think this through. The ants can only avoid a collision if Read More →

Write a program to count nodes in a tree

Approach: Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable. If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, Read More →

Write C code to count the number of leaves in a tree

leaf nodes in binary search tree

In a binary search tree, a node which contains blank left and right children’s that particular node is called as a leaf node in a tree. Here We are going give a c program for finding the number of leaf nodes in a tree. In a c Program we explained recursively how to find leaf Read More →

Print letters followed by their frequency (Run Length Encoding)

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding. Example: Input aaabcc Output a3b1c2 Algorithm: 1.Pick the first character from the string and print it. 2.Count the number of subsequent occurrences of the picked character and then print the count. 3.Pick the next character Read More →

Write a function to get the intersection point of two Linked Lists (Y Shape)

Method 1 (Brute Force) Using 2 for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will Read More →

Write a program to detect loop in a Linked List

linkedlistLoop

Floyd’s Algorithm: This problem can be solved by using two pointers, slow pointer and fast pointer.Both these pointers will point to head of the linked list initially. Increment slow pointer by 1 node and the fast pointer by 2 nodes. If there’s a loop, the fast pointer will meet the slow pointer somewhere.We’ll discuss in Read More →