# Category Archives: Ds/Algos

interview questions based on data structures and algotrithms

## Reverse a linked list java code

This is the classic interview question. Generally you won’t encounter this question in the interview of a big tech giant. But I still like this questions very much . And there are many questions based on it. We request you to please do this question and practice both the approaches iterative and recursive. Here’s the… Read More »

## Valid Dictionary Words Algorithm

The problem is like this : Given a string str and a dictionary of words determine if str can be segmented into a space-separated sequence of one or more dictionary words. Example Input: str = “InterviewGeek”, dict = [“Interview”, “Geek”,”hell”] , Output : true Algorithm : For each word in the string check if it’s… Read More »

## Find if 2 Rectangles overlap

Given two rectangles with their base parallel to each other . You have to find whether the rectangles overlap or not. Ex Rect1(2,3,5,6) Rect2(1,3,1,10) Where a rectangle is specified by coordinates of it’s TopLeft (x1,y1) and BottomMRight(x2,y2) coordinates in sequence for rect1 TopLeft(2,3) and BottomRight(5,6). The problem is very simple . Since the rectangle have… Read More »

## Linked list creation and manipulation

Here’s the code to create a linked list. And perform various operations on it. U can use this code for reference . The code is self explanatory.

## Merge Sort Code

Merge Sort belongs to category of divide and conquer algorithms. Which means it divides the problem into  small subproblems, solves them and then combine the solutions of these subproblems to generate solution  of the original problem.Merge Sort compares elements with each other for sorting the list. The steps followed to mergesort are are: Divide the unsorted list… Read More »

## Quick Sort Code

Quick Sort belongs to the category ofdivide and conquer algorithms. Quicksort  divides a large list into two smaller lists around a selected pivot . Quicksort can then recursively sort the sub-lists.It sorts the elements inplace. The steps followed are are: Select an element, called a pivot, from the list. Reorder the list so that all elements with values… Read More »

## Find the median of two sorted arrays

Given two sorted arrays A and B containing N elements each. Give an algorithm to ﬁnd the median of two sorted arrays in O(lgN) time. Ex A={1,2,3} B={1,4,5,6} median=3 . The naive algorithm will be to merge the arrays A and B and return the median .But the time complexity will be O(N) and this… Read More »

## Counting Sort

Counting Sort is not a comparison sort.Counting sort assumes that each of the input element is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in O(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less… Read More »

## Binary Search code

Binary Search finds the position of a specified value (key) in a sorted array.In each step it discards half of the elements to search , thus the worst case running time of binary search is O(log n).Believe it or not 80 out of 100 of the programmers fail to write the correct code for binary… Read More »

## Stack class with Push, Pop, and Min in Constant Time

This is a commonly asked interview question .The problem is like this Design a stack class that supports push, pop, and min ( retrieving the minimum element ) operations in constant time The problem can be solved easily using an extra stack (MinStack) .On each min call you just have to return the element the… Read More »