Edit Distance – DP Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Input: str1 = “cat”, str2 = “cut” Output: Read More →

Graph – Breath First Search

breath first search

Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes. 1) Define a GraphNode 2) Define a Queue 3) Breath First Search uses a Queue Output: value: 2 value: 3 value: 5 Find value: 5 value: 4

Graph Data Structure

Graphs A tree only allows a node to have children, and there cannot be any loops in the tree, with a more general graph we can represent many different situations. A very common example used is flight paths between cities. If there is a flight between city A and city B there is an edge Read More →

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is Read More →

Decode Ways Leetcode Java

Problem: A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ – 1 ‘B’ – 2 ‘Z’ – 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12″, it could be decoded as “AB” (1 2) or Read More →

Min Stack Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) — Push element x onto stack. pop() — Removes the element on top of the stack. top() — Get the top element. getMin() — Retrieve the minimum element in the stack. Solution: the StackMin class which keeps the Read More →

Finding All the Subsets of a Set – Backtracking Problem

Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] We use the backtracking method to solve Read More →

Given a triangle, find the minimum path sum from top to bottom

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = Read More →

Robot in an MXN grid

Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . How many possible unique paths are there? Approach 1(Recursion): Let NumberOfPaths(m, n) be Read More →

Determine if a Sudoku is Valid

Determine if a Sudoku is valid The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. Because the number range of sudoku is 1-9, so each number in each row, Read More →

Adobe Interview Questions – Set 4

Hi, I was recently interviewed for MTS at Adobe. Here is my interview experience: 1)Online aptitude test 2)Online technical test : It comprised of C MCQs and coding question(in any language). Coding questions were: Q1. To check if the parenthesis are balanced. Q2. Matrix has rows in the form of 1’s followed by0’s.Find the row Read More →

Oracle Interview Questions – Set 3

Interview Experience of ORACLE (OFSS) College NIT Trichy Eligibility Criteria :- >=6 Pointer Out of 10 Four Student got Selected here I am sharing one of them. Hi all, Hope you all are preparing well. Sharing my experience for OFSS. It should be enough for you for this firm at least. There are three rounds Read More →