**Problem Statement**

```
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2,
```

]]>**Problem Statement**

```
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
```

This problem seems little tricky but it is very easy to understand once you understand how spiral order works, and this question is often asked on onsite interviews.

So, first of all, let's think about how spiral order works. Spiral order follow four directions: It goes to the right, down, left and up in the order respectively.

To solve this problem, we are just going to follow these four directions order in our matrix and solve it. Read the comments provided in below solution code to understand further more.

```
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//List initialization
List<Integer> list = new ArrayList<>();
if(matrix.length == 0 || matrix[0].length == 0) return list;
//Initialized rowBegin,rowEnd,colBegin and ColEnd
int rowBegin = 0;
int rowEnd = matrix.length -1;
int colBegin = 0;
int colEnd = matrix[0].length -1;
while(rowBegin <= rowEnd && colBegin <= colEnd){
//Traverse right and increment rowBegin
for(int i = colBegin; i <= colEnd; i++){
list.add(matrix[rowBegin][i]);
}
rowBegin++;
//Traverse down and decrement colEnd
for(int i = rowBegin; i <= rowEnd; i++){
list.add(matrix[i][colEnd]);
}
colEnd--;
//The only tricky part here is when we traverse left or up, we have to make sure whether that row or column still exists to prevent duplicates
//Make sure that row exists
//And traverse left and decrement rowEnd
if(rowBegin <= rowEnd){
for(int i = colEnd; i >= colBegin; i--){
list.add(matrix[rowEnd][i]);
}
}
rowEnd--;
//Make sure that column exists
//And traverse up and increment colBegin
if(colBegin <= colEnd){
for(int i = rowEnd; i >= rowBegin; i--){
list.add(matrix[i][colBegin]);
}
}
colBegin++;
}
return list;
}
}
```

We are visiting each elements in given matrix so time complexity is going to be: O(m*n).

We are adding each elements we visit in matrix to list, so space complexity is going to be: O(m*n).

]]>```
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist
```

]]>```
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
```

**Solution Explanation **

This problem is very simple and often asked on phone screen interviews. In this problem, we have to reverse a string which is given as an array of characters.

We can always think of solving it by doing brute force but we are told not to allocate space for another array. So how about we solve this question by iterative swapping using two pointers? let's start one pointer, pointing at start of string and second pointer , pointing at end of the string. Both pointers will keep swapping characters which they are pointing to and move forward towards each other until both pointers meet. At this point, we have met midpoint which means, we reversed the string.

```
class Solution {
public void reverseString(char[] s) {
int i = 0, j = s.length -1;
while(i < j){
char ch = s[i];
s[i] = s[j];
s[j] = ch;
i++;j--;
}
}
}
```

We are visiting each elements in the given array, so time complexity is going to be , O(n) which is linear runtime.

We have not allocated any extra space to store data so our space complexity is going to be, O(1).

]]>**Problem Statement**

```
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,
```

]]>**Problem Statement**

```
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
```

The question here is very simple. It already provided some details like, we are going to only deal with positive numbers and it also mentioned that except for one, every other element is going to appear twice. We can do brute force or we can use map or set but our question specifically mentioned to not use extra space.

What if we use XOR ? The basic idea of using XOR operation is a^c^c =a, which means two xor operations with the same number will eliminate the number by becoming zero and we will be left with a single number which does not have duplicate.

```
class Solution {
public int singleNumber(int[] nums) {
int xor=0;
for(int i=0;i<nums.length;i++){
xor = xor ^ nums[i];
}
return xor;
}
}
```

**Explanation why this technique works:**

Let's say our given array is : [4,1,2,1,2]. This is what we are doing in our code above:

The for loop produces the below output.

=> xor = 4 ^ 1 ^ 2 ^ 1 ^ 2

=> xor = 4 ^ 1 ^ 1 ^ 2 ^ 2 (Rearranging by taking same numbers together, this happens internally, Just FYI)

=> xor = 4 ^ 0 ^ 0 (Same numbers become zero, this happens internally, Just FYI)

=> xor = 4

** Time Complexity **We are iterating through the given array once using the for loop, so time complexity is going to be :** O(n) which is linear runtime**.

**Space Complexity **We are not storing data anywhere here so our space complexity is : **0(1)**.

A two dimensional array in Go require you to explicitly allocate the space for the whole array.

If you want a 2-D array with 4 rows and 5 columns of integer type, below is the sample code.

```
arr := make([][]int, 4)
for i := range arr{.
arr[i] = make([]int, 5)
```

]]>A two dimensional array in Go require you to explicitly allocate the space for the whole array.

If you want a 2-D array with 4 rows and 5 columns of integer type, below is the sample code.

```
arr := make([][]int, 4)
for i := range arr{.
arr[i] = make([]int, 5)
}
```

]]>If you are an avid Hacker News user, you would know that there's a hiring comment thread during the start of every month called, `Who is Hiring`

. Hundreds of companies from across the world post job posts as comments to that thread every month hoping to find potential employees.

Unlike many other readers, HN users tend to be more technology focussed, so I thought analyzing the job posts would give some insight into how 2018 in software recruiting has been.

There's a lot of data, so I decided to focus only on the below parameters.

- Locations with most Jobs
- Remote Work - Number of job posts which allow remote work
- Visa - Number of job posts which sponsor visa
- Roles - Top roles that are being hired
- Skills - Popular required skill set across all job postings.

I have scraped all the 12 months of job posts(comments on who is hiring threads) in 2018 using the firebase API and a golang hacker news wrapper library.

To find out all the locations in a job post, I used `geotext`

, a python module which gives you a list of places from the text. After aggregating results from all 12 months job posts, I used Google Places API to get latitude and longitude for each city and visualized on a map using `AmCharts`

.

In 2o18, the top 10 locations with most jobs are below.

```
"San Francisco": 2922
"New York": 1746
"London": 1236
"Toronto": 660
"Boston": 558
"Los Angeles": 498
"Berlin": 474
"Seattle": 456
"Austin": 324
"Amsterdam": 318
```

Unsurprisingly San Francisco beats most cities by a wide margin and close second is New York. Below are all cities with the number of job posts in that city in 2018 visualized on an interactive map.

One of the evolving phenomena since the last 2-3 years is companies embracing remote work. More companies are offering remote work and are being flexible with partial remote.

I did a regular expression search in each job post text to see if a job offers remote work or not. The chart below shows the number of job posts that offer remote work. Total number of job posts in each month is usually around 800-1000, so if you are looking for `%`

a good 12% on average allow remote work.

Silicon Valley and most of the technology companies in the USA rely heavily on foreign workers. With the arbitrary suspension of premium process for H1-B applications, most employees can't easily move and companies can not hire at the same speed.

I did a regular expression search for the term `Visa`

and the below chart shows the number of job postings that sponsors visa. As you the jobs which sponsor visa is less than 5%.

While there are more engineering positions than anything else, I did a count of all roles including the level in software engineers and below is the chart that represents number of job posts over the last year.

```
"Engineering Manager": 271,
"Principal Software Engineer": 25,
"Product Designer": 243,
"Product Manager": 425,
"Program Manager": 35,
"QA": 353,
"Senior Software Engineer": 818,
"Software Engineer": 2975,
"Staff Software Engineer": 10
```

I was really curious to see the popular skills over the last year. I generated the count by using a pre-defined dictionary of skills and below are the counts and a chart that represents the top skills asked for in 2018.

**Edit**: After posting to HN, I realized some of the skills has false positives during regex search, so until they are updated, please consider these as direction in general, but not as the accurate count. Apologize for the inconsistent data.

Edit 2: The regex false positive issue is resolved. Fixed it by using word boundaries on regex `\\b<word>\\b`

.

```
html, 277
python, 273
.net, 216
react, 211
php, 124
docker, 92
android, 89
c, 80
golang, 79
postgres, 69
ios, 67
javascript , 64
git, 61
ruby, 54
django, 53
kubernetes, 51
angular, 49
rails, 48
java, 40
linux, 39
typescript, 31
rust, 29
shell, 26
swift, 23
scala, 22
react.js, 21
css, 21
julia, 20
vue.js, 20
excel, 16
kotlin, 13
elixir, 13
graphql, 13
spring, 11
sql, 11
reactjs, 10
erlang, 9
perl, 7
lua, 6
mysql, 6
haskell, 5
apache, 4
vuejs, 4
objective-c, 2
```

Just curiously I checked for number of job posts which offered free lunch over the last year and below is the chart representing it.

Hope this helped in giving you some insight into the job posts on Hacker News. I will open source the code used to analyze all this after cleaning up by this weekend, currently it's a combination of Golang, Python, Amcharts, Highcharts to analyze and visualize the hiring data. Follow me on Github to get notified when the repo is up or check back this post over the weekend for the repo link.**Update : **Added a very initial version of the code here to help people understand the process/logic i followed for the blog post. Running the code doesn't automatically generates the charts, but hoping to get the repo into that stage in sometime, so it could be reused for other kinds of analytics projects.

Interviewing is hard. You could be an awesome web developer who could roll out an app over the weekend and still fail at a job interview for a web developer position.

Sounds little crazy, isn't it?

That is because the whole interviewing is skewed towards new grads who has taken data structures and algorithms course and has a fresh memory of the problems. White boarding is the common interviewing technique where you will be given an algorithmic problem solving question and expect you to solve an optimized `O`

solution in 45 mins to 1 hour.

If you are a developer with a full time job and are planning to switch to a new company, you are out of luck. Unless you have 3-4 months to prepare for interviews, you would have tough time clearing interviews with the top tech companies or start-up's. And if you decide to spend time preparing for the algorithms and data structure problems, you will need a good resource which lets you focus on problem solving rather than overwhelming you with a lot of content.

Leetcode, Lintcode, Hackerrank, Hackerearth and Interviewbit are some of the leading preparation platforms. Of all these, Leetcode is the most famous one because of its vast collection of questions and a company focussed preparation style. Like if you are interviewing with Amazon, there's a company category with Amazon's name and under it are all the questions that were asked in the interviews for candidates over the years. These questions are crowd sourced and so they build up to the extent of having almost all questions asked by Amazon.

Leetcode monetizes its platform by charging users around $35 a month or $159 per year. The monthly charge is little significant and the yearly fee seems like a stretch. Users always have this dilemma that they would only need the membership for 2 months and plan to wrap up their preparation in that time. While it is true that you would only need it for 2 months in an ideal scenario, real life job hunting is far from ideal. Your job search will usually stretch for 3-4 months and you end up paying $140 for 4 months. At this point, a yearly membership seems more reasonable and value for your money.

The premium allows you to unlock 2 very important features. First is to filter the questions by company category and the second is access to their premium questions which are frequently asked in many interviews.

Lintcode is a very similar platform to Leetcode, some say it is a clone. But I think it is a very good alternative. Their UI/UX is pretty great and they too have categories with company names. It actually used to be a free platform until the last few months. I guess they realized that their platform is strong enough to force people to pay, they made some of the features available only under their lintcode vip.

While hackerrank, interviewbit are really good platforms. Leetcode and Lintcode have become more popular partly to their offering of allowing users to see all questions asked by a certain company.

Of these two, Leetcode wins partly because they have a better collection, a very active community and the price is not so different from what lintcode charges.

Given a string, Find the longest palindromic substring.

Understanding the question here is very simple, given a string `RENTNOW`

, the substring `NTN`

is a palindrome of length 3, and that would be the result.

Before we think of any optimized solutions, let's see how

]]>Given a string, Find the longest palindromic substring.

Understanding the question here is very simple, given a string `RENTNOW`

, the substring `NTN`

is a palindrome of length 3, and that would be the result.

Before we think of any optimized solutions, let's see how we can brute force this to find the longest palidromic substring.

My first intution is to start from each character and check for all substrings from that character. So when you start from `R`

the substrings would be,

```
R E N T N O W
R, RE, REN, RENT, RENTN, RENTO, RENTOW
```

None of the above are palindromes except the single character `R`

of course. So we can keep `R`

as the current max palindrome and continue doing the same for all other characters.

The time complexity for this would be O(n^3), since we will be using two loops to accomplish this. Below is the java solution for longest palindromic substring.

```
class Solution {
public String longestPalindrome(String s) {
String max_str = "";
int maxlen = 0;
for(int i=0;i<s.length();i++){
for(int j=i;j<s.length();j++){
if(isPalindrome(s.substring(i, j+1))){
if((j+1-i)>maxlen){
maxlen = j+1-i;
max_str = s.substring(i, j+1);
}
}
}
}
return max_str;
}
public boolean isPalindrome(String s){
for(int i=0;i<s.length()/2;i++){
if(s.charAt(i)!=s.charAt(s.length()-i-1)){
return false;
}
}
return true;
}
}
```

We could accomplish the same thing we did above by reducing one loop. We can do this by expanding the string at center and check for palindrome. This way, we optimize for not finding one, but instead to detect there's no palindrome and exit.

```
R E N T N O W
```

We will use a helper function which gets the index of two characters. It then expands to the right and left until we detect there's no palindrome.

Below is the Java implementation,

```
class Solution {
public String longestPalindrome(String s) {
if(s==null || s.length()==0) return "";
int start = 0, end = 0;
int len1 = 0, len2 = 0;
for(int i=0;i<s.length();i++){
len1 = expandStringAtCenter(s, i, i);
len2 = expandStringAtCenter(s, i, i+1);
int len = Math.max(len1, len2);
if(len > end-start){
start = i -(len-1)/2;
end = i+len/2;
}
}
return s.substring(start, end+1);
}
public int expandStringAtCenter(String s, int left, int right){
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R-L-1;
}
}
```

The time complexity for longest palindromic substring is now O(n^2).

]]>Given an string or expression which only consists of characters like

`(`

,`)`

,`[`

,`]`

,`{`

,`}`

. Validate if the string has balanced parentheses.

A string has balanced parentheses, if every open bracket has an associated closed one and they exist in the right order.

As the problem statement explains, a string

]]>Given an string or expression which only consists of characters like

`(`

,`)`

,`[`

,`]`

,`{`

,`}`

. Validate if the string has balanced parentheses.

A string has balanced parentheses, if every open bracket has an associated closed one and they exist in the right order.

As the problem statement explains, a string is valid if it has balanced parentheses, for example,

`()[]{}`

is valid and `(()[]`

is not, because the second string doesn't have a closing `)`

.

Based on the above example, we can make a simple inference that number of opening and closing brackets have to be same for a string is balanced. While this is a necessary condition, this is not sufficient. Consider the below example,

`([)]`

this string is not valid because of the order.

For the order to be valid, the last opening bracket should have a matching closed one. So we could follow the below kind of algorithm.

- Parse the string and read one character at a time.
- If the character is an opening bracket, put it in a bucket
- If the character is a closed one, find if it's matching opening bracket is at the top of the bucket, if it is, remove it from the bucket.
- At the end of the parsing it, if the bucket is not empty, then the string doesn't have balanced parentheses or valid parentheses.

To convert this to Java code, we could `Stack`

data-structure in place of the bucket since it provides us the same functionality and we could store the mapping of open to closed brackets in hashmap which allows us to compare if a bracket in the bucket is the matching one.

Below is the Java implementation for balanced parentheses,

```
class Solution {
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
if(map.containsKey(c)){
stack.push(c);
} else if(!stack.empty() && map.get(stack.peek())==c){
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
}
```

####### Time Complexity for balanced parentheses

We only read the string once, so the time complexity is O(n), but we use a map and stack for storage, so space complexity O(size_of_string).

Given two integers, calculate the hamming distance between them.

Hamming Distance between integers is defined as the number of indexes where the two bits differ.

For example, given integers x = 2 and y=5, the hamming distance between them is,

```
X 0 0 1 0
Y 0 1 1 0
HD 0 1 0 1 Total - 1
```

As you see the integers 2 and 5 differ in only 1 bit position, so the hamming distance between them is 1. If you look at this, basically we are doing a XOR operation on each bit and returing the total value as hamming distance.

So, we can just do an XOR between the two given integers and do a bit count and return the value.

Below is the java implementation for hamming distance cacluclation between two integers,

```
public class HammingDistance {
public static void main(String[] args){
HammingDistance hd = new HammingDistance();
System.out.println("Hamming distance between 2 and 5 is "+hd.hammingDistance(2,5));
}
public int hammingDistance(int x, int y) {
int xor = x ^ y;
return Integer.bitCount(xor);
}
}
```

Once we have the xor of the 2 integers, we need the number of 1's in the resultant binary version. To calculate that we use a inbuilt java method Integer.bitCount.

Alternatively, you can also manually calculate the bit count by continously right shifting the resultant xor value and doing an '&' with 1.

Below is the code to avoid using the inbuilt java method and find out the number of 1's,

```
public class HammingDistance {
public static void main(String[] args){
HammingDistance hd = new HammingDistance();
System.out.println("Hamming distance between 2 and 5 is "+hd.hammingDistance(2,5));
}
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int bitCount = 0;
for(int i=0;i<32;i++){
bitCount += (xor >> i) & 1;
}
return bitCount;
}
}
```

]]>LinkedList is a linear data structure which allows to insert and remove elements at the front and rear in constant time.

LinkedLists are typically of two types,

- Single LinkedList

Each node has a reference to the next node. - Doubly LinkedList

Each node has a reference to previous and next nodes.

LinkedList is a linear data structure which allows to insert and remove elements at the front and rear in constant time.

LinkedLists are typically of two types,

- Single LinkedList

Each node has a reference to the next node. - Doubly LinkedList

Each node has a reference to previous and next nodes.

Doubly Linked Lists are used extensively in various computer science domains like caching, binary trees etc.

A Single Linkedlist typically has a node reference to the next node and a value, on the other hand the doubly linked list has two references, previous and next, pointing to different nodes.

```
class DNode{
DNode prev, next;
T val;
}
```

The doubly linked list allows typical operations like adding or removing elements to the lists, search ane element in the list.

```
package src.DSFullImplementations;
/*
* Author: Venkatesh Thallam
*
*/
public class DoubleLinkedListImpl {
/*
* Node definition with two pointers
*/
class DNode {
DNode prev, next;
int val;
DNode(int val) {
this.val = val;
prev = next = null;
}
}
/*
* Head points to the first element of the list and tail to the last
*/
DNode head, tail;
DoubleLinkedListImpl() {
this.head = this.tail = null;
}
public static void main(String[] args) {
DoubleLinkedListImpl list = new DoubleLinkedListImpl();
list.add(10, null);
list.add(20, 10);
list.add(30, 10);
list.add(40, 30);
list.print();
System.out.println("List size is " + list.size());
list.remove(30);
list.print();
list.remove(20);
list.print();
}
/*
* Adds an element after certain element. If ele is null, it inserts at the
* front
*/
public void add(int val, Integer ele) {
/*
* If target node is head
*/
if (head == null) {
head = tail = new DNode(val);
} else if (head.val == ele || ele == null) {
DNode temp = new DNode(val);
temp.next = head;
head.prev = temp;
head = temp;
}
/*
* If target node is tail
*/
else if (tail.val == ele) {
DNode newnode = new DNode(val);
tail.next = newnode;
newnode.prev = tail;
tail = newnode;
} else {
DNode newnode = new DNode(val);
DNode temp = head;
while (temp.next != null && temp.val != ele) {
temp = temp.next;
}
newnode.next = temp.next;
newnode.prev = temp;
temp.next = newnode;
}
}
/*
* Removes the specified element
*/
public void remove(int ele) {
/*
* If target node is head
*/
if (head.val == ele) {
head = head.next;
head.prev = null;
}
/*
* If target node is tail
*/
else if (tail.val == ele) {
tail = tail.prev;
tail.next = null;
} else {
DNode temp = head;
while (temp.next != null && temp.next.val != ele) {
temp = temp.next;
}
if (temp != null) {
temp.next = temp.next.next;
temp.next.prev = temp;
}
}
}
/*
* Checks whether a certain element is true
*/
public boolean search(int ele) {
DNode temp = head;
while (temp != null) {
if (temp.val == ele) {
return true;
}
temp = temp.next;
}
return false;
}
/*
* Returns the number of elements in the linked list.
*/
public int size() {
DNode temp = head;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
/*
* Prints the elements in the list
*/
public void print() {
DNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
}
```

The time complexity is similar to that of single linkedlists.

]]>Queue is a linear datastructure that stores elements with first in first out(FIFO) ordering. That is, the element which gets added to the queue leaves before all the elements added after it.

The most typical example is a real world queue, where you line to get into a public

]]>Queue is a linear datastructure that stores elements with first in first out(FIFO) ordering. That is, the element which gets added to the queue leaves before all the elements added after it.

The most typical example is a real world queue, where you line to get into a public transit or at a movie theater, people get out of the queue prior to all the others who enter after them.

Queue is one of the most used data structure in computer science and is used in various operations or algorithms like,

- CPU Scheduling Algorithms
- Tree Traversals
- Process Synchronization or Message Delivery Systems

Most of the modern day systems communicate with each other using message queues where one system enqueue's or inserts the message to the queue and other system listens to it and deque's the message. There are various implementations of this type like Apache Kafka, Rabbit MQ, IBM MQ etc.

Queue data structure provides the following methods,

**Enqueue**

Adds a element to the rear of the queue**Deque**

Removes the element at the front of the queue**isEmpty**

Returns true if queue is empty or false if it's not**Front**

Returns the front element of the queue**Rear**

Returns the rear element of the queue.

A queue is typically implemented using an array or linked list. When you use an array, the elements has to be moved during enqueue or deque operations to make room for the new elements which can be expensive.

Ideally we will need a constant operation time for inserting and deleting which can be acheived by using a linked list with references available to head and end of the tail.

Using a linked list, we will use the below psuedo code for various queue operations,

**Enqueue**`if tail is null create new node, assign head and tail to it else create a new node, assign its next to tail assign tail to the new node`

**Deque**`if head is null return null else store the head value in a temp assign head to it's next return temp value`

**isEmpty**

```
return if head is null
```

**Front**

```
if head is null
return null
else
return head's value
```

**Rear**

```
if rear is null
return null
else
return rear's value
```

Below is the full java implementation of queue using linkedlist,

```
/*
* Author: Venkatesh,Thallam
*
* Queue data structure implementation using single linked list
*/
/*
* Node Definition for the underlying linked list we use to implement stack
* */
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public class QueueImplementation {
Node head, tail;
QueueImplementation() {
head = null;
tail = null;
}
public static void main(String[] args) {
QueueImplementation queue = new QueueImplementation();
queue.enqueue(10);
queue.enqueue(15);
queue.enqueue(25);
queue.dequeue();
System.out.println("queue front is " + queue.front());
System.out.println("queue rear is " + queue.rear());
System.out.println("queue size is " + queue.size());
queue.dequeue();
queue.dequeue();
System.out.println("queue size is " + queue.size());
}
/*
* Adds an element to the rear of the queue
*/
public void enqueue(int val) {
if (tail == null) {
head = tail = new Node(val);
} else {
Node newnode = new Node(val);
tail.next = newnode;
tail = newnode;
}
}
/*
* Removes an element at the front of the queue and returns the element
*/
public Integer dequeue() {
if (head != null) {
head = head.next;
}
return null;
}
/*
* Checks if the queue is empty or has elements.
*/
public boolean isEmpty() {
return head == null;
}
/*
* Returns the number of elements of the queue
*/
public int size() {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
/*
* Returns the front element of the queue
*/
public Integer front() {
if (head != null)
return head.val;
else
return null;
}
/*
* Returns the rear element of the queue.
*/
public Integer rear() {
if (tail != null)
return tail.val;
else
return null;
}
}
```

The time complexity for each of the queue operations is below,

- Enqueue - O(1)
- Deque - O(1)
- isEmpty - O(1)
- Front - O(1)
- Rear - O(1)
- Size - O(n), since this requires checking all values of stack.

Stack is one of the most used data structures in computer science. It is a linear data structure which supports ordering of elements in Last In First Out order(LIFO).

The very typical real world example is a stack of plates, where new plates are put on the top of

]]>Stack is one of the most used data structures in computer science. It is a linear data structure which supports ordering of elements in Last In First Out order(LIFO).

The very typical real world example is a stack of plates, where new plates are put on the top of the existing ones and the top ones are the first one to be removed.

There are numerous applications which involve stack in computer science, some of them are,

- Compilers/Run time environments, which use it to store recursive calls.
- Tree Traversals
- Software Applications which provide Undo/Redo operations like text editors.
- Evaluation of mathametical notations like Infix/Postfix etc.

Stack provides the following basic operations,

**Push**

Pushes the element to the top of the stack.**Pop**

Pops or removes the top element of the stak.**Top**

Returns the top element of the stack.**isEmpty**

Returns true if the stack is empty or returns a false otherwise.**Size**

Returns a integer value which is the number of elements currently in the stack.

Typically stack is implemented using,

- Array or a Dynamic Array
- Linked List

The major operations in a stack involve adding and removing elements at the top, if we use an array to implement it, we will end up moving the array elements one step to the right every time there's a push or pop operation which is very expensive.

On the other hand, a linked list allows addition and removal of an element at the start in constant time. Hence we will use a single linkedlist to implement a stack.

We can start with an empty linkedlist where 'head' is null, use it to append elements or remove for push and pop operations.

**Push**

```
if head is null
create node with input value
assign head to the new node
else
create node with input value
point's new node's next to head
make the new node as head
```

**Pop**

```
if head is null
return null
else
store head value to temp
point head to the head's next
return the temp
```

**Top**

```
if head is null
return null
else
return head's value
```

**isEmpty**

```
return head==null
```

Below is the full java implementation for stack using linkedlist,

```
/*
* Author : Venkatesh Thallam
*/
/*
* Node Definition for the underlying linked list we use to implement stack
* */
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public class StackImplementation {
Node head;
StackImplementation() {
head = null;
}
public static void main(String[] args) {
StackImplementation stack = new StackImplementation();
stack.push(8);
stack.push(28);
stack.push(38);
stack.push(48);
stack.push(68);
stack.pop();
stack.push(98);
System.out.println(stack.size());
System.out.println(stack.isEmpty());
System.out.println(stack.top());
}
/*
* Pushes an element to the top of the stack
*/
public void push(int val) {
if (head == null) {
head = new Node(val);
} else {
Node newhead = new Node(val);
newhead.next = head;
head = newhead;
}
}
/*
* Pops the top element and returns it
*/
public Integer pop() {
if (head == null)
return null;
else {
Integer poppedval = head.val;
head = head.next;
return poppedval;
}
}
/*
* Returns a boolean that tells if a stack is empty
*/
public boolean isEmpty() {
return head == null;
}
/*
* Returns the total elements currently in the stack
*/
public int size() {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
/*
* Returns the top element of the stack.
*/
public Integer top() {
if (head != null)
return head.val;
else
return null;
}
}
```

The time complexity for each of the stack operations is below,

- Push - O(1)
- Pop - O(1)
- Top - O(1)
- isEmpty - O(1)
- Size - O(n), since this requires checking all values of stack.

Given an a list of n integers which are non negative and represent an elevation map of various buildings where the width of each bar/building is 1, Find out how much water can be saved in between them when it rains.

Given an array{1,0,2,2,4,0,1,5,2,1,6,1}as input, the output should be11

Imagine a series of buildings on the street where each building is of width 1 block and there are empty block spaces between some buildings. Also the heights of the buildings vary. When it rains, the free blocks between buildings and space between buildings can hold some water. The solution involves finding the amount of water between these buildings.

The most intutive brute force would be to find out at each block find the tallest one on the left and on the right and find out the difference between them.

For example, consider this,

```
1 0 2
```

At '0', the difference between tallest one on the left and tallest one on the right is 1 (2 -1 ) which is the amount of water that can be saved in this combination.

Solving this would take finding max on the left and right at each index and so is exponential.

The brute force implementation looks like this,

```
public class TrappingRainWater {
public static void main(String[] args) {
int[] heights = {1,0,2,2,4,0,1,5,2,1,3,1};
System.out.println(bruteForce(heights));
}
public static int bruteForce(int[] heights){
int result = 0, maxleft = 0, maxright = 0;
int size = heights.length;
for(int i=1;i<size-1;i++){
maxleft = 0; maxright = 0;
for(int j=i;j>=0;j--){
maxleft = Math.max(maxleft, heights[j]);
}
for(int j=i;j<size-1;j++){
maxright = Math.max(maxright, heights[j]);
}
result += Math.min(maxleft, maxright) - heights[i];
}
return result;
}
}
```

When you run the above code, you would get the output as 11 which is the expected answer. But this would take O(n^2) time.

Let's try to optimize this. The concept we used was to find out left max and right max at each point, but instead we could use a single left max, right max while we traverse the array. We can use two pointers starting from the start and end, update the current max value for both and left if there's a new max, else find the difference of current element with max value.

Below is the Psuedo code for the above logic,

```
left = 0, right = len(arr)-1
maxwater = 0
while left < right
if(heights[left] < heights[right)
if(heights[left]>leftmax)
leftmax = heights[left]
else
maxwater += leftmax - heights[left]
else
if(heights[right] > rightmax) rightmax = heights[[right]
else maxwater += rightmax - heights[right]
```

And below is the full java implementation for Trapping Rain Water,

```
class TrappingRainWater {
public int trap(int[] height) {
int left = 0, right = height.length-1;
int maxleft = 0, maxright = 0;
int result = 0;
while(left <= right){
if(height[left] < height[right]){
if(height[left]>=maxleft) maxleft = height[left];
else result += maxleft - height[left];
left++;
}
else{
if(height[right]>=maxright) maxright = height[right];
else result+=maxright-height[right];
right--;
}
}
return result;
}
}
```

The time complexity is O(n^2) for the brute force, O(n) for the optimized approach.

]]>Given two integer arrays, arr1 and arr2, find K pairs of elements such that (x,y) where x is the value from the first array and y is the value from the second array who sum is the smallest.

For example, give the input,

arr1 = {1, 3, 4}, arr2 = {2, 6, 9}, K=3

Output would be [[1,2],[3,2],[4,2]]

Given that there are two integer arrays each with size 'm' and 'n', the number of different pair of elements would be m*n.

From m*n number of pair of elements, we need to find K pairs of elements whose sum is the lowest.

The keyword here is 'K' min number of pairs, which says we have to use a heap and since it's min number of pairs, we use a min heap. We will use a priority queue, with an integer array as the input element and a comparator which orders the elements based on the difference in the sum of the array elements.

```
//Order elements based on the sum of the first 2 array elements.
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)-> a[0]+a[1] -b[0] -b[1]);
```

Since the array elements are already in sorted order, we will add the combination of all the elements of first array and the first element of second array initially. This will allow us to limit the number of elements in the priority queue to K.

```
//We add the third element as an index to which element from the second array we are pointing to
for(int i=0;i<arr1.length && i<k;i++) queue.offer(new int[]{arr1[i], arr2[0], 0});
```

Now we can process the elements in the queue until the queue is empty or K is greater than 0 and add each pair to the result set. After we add each element to the result set, we add a new pair by using the third element as index in the integer array pair.

Below is the full java implementation of the find K pairs with smallest sum:

```
class FindKSmallestPairs {
public static void main(String[] args){
int[] nums1 = {1, 3, 4};
int[] nums2 = {2, 6, 9};
System.out.println(new FindKSmallestPairs().kSmallestPairs(nums1, nums2, 3));
}
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
int nlen1 = nums1.length, nlen2 = nums2.length;
List<int[]> res = new ArrayList<>();
if(nlen1==0 || nlen2==0 || k==0) return res;
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0]+a[1]-b[0]-b[1]);
for(int i=0; i<nlen1 && i<k ; i++) queue.offer(new int[] {nums1[i], nums2[0], 0});
while(k-- > 0 && !queue.isEmpty()){
int[] cur = queue.poll();
res.add(new int[]{cur[0],cur[1]});
if(cur[2]==nums2.length-1) continue;
queue.offer(new int[]{cur[0], nums2[cur[2]+1], cur[2]+1});
}
return res;
}
}
```

The time complexity is O(K logK).

]]>Given an array of integers, find out two indices such that the sum of the numbers at that indices matches K.

For example, {4, 6, 8, 1, 9} and K = 15, the output would be [1,4]

The questions is rather simple and is one of

]]>Given an array of integers, find out two indices such that the sum of the numbers at that indices matches K.

For example, {4, 6, 8, 1, 9} and K = 15, the output would be [1,4]

The questions is rather simple and is one of the most frequently asked interview questions ever.

Given an integer array, finding two numbers which sum up to K can be done in brute force, by checking every array element with every other. You quit, when you find two numbers which sum up to K. The worst case complexity is O(n^2).

Pseudocode for bruteforce

```
for i=0 to len-1
for j=1 to len-1
if(arr[i]+arr[j] == K)
return i,j
```

We can also do this in a single pass of the array by using some extra space, a hashmap. The solution involves checking if the difference of K and the current element exists in the map, if it does return those values, else add the new array element to the map.

Pseudocode for single pass solution using hashmap

```
Map<Integer,Integer> map;
for i=0 to len-1
if(map contains key K-arr[i])
return i and map.get(arr[k]-i)
else
map.put(arr[i],i)
```

This solution works great and reduces the worst case time complexity by half. Below is the full java implementation for Two Sum problem,

```
public class TwoSumImpl {
public static void main(String[] args){
int[] arr = {4, 6, 8, 1, 9};
int[] result = new TwoSumImpl().twoSum(arr, 15);
}
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> result = new ArrayList<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
result.add(i);
result.add(map.get(target-nums[i]));
break;
}else{
map.put(nums[i],i);
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
```

The time complexity is O(n) and space complexity is O(n).

]]>