## Sort an Given Array in the order defined by another array

Objective: Given an array of integers, write an algorithm to sort it according to the order defined by another array.

Input: An Array of Integers

Example:

```Input Array : 2 6 9 1 4 4 2 1 10 13 5 7 8

DefinedArray : 1 2 4 6

Output : 1 1 2 2 4 4 6 5 7 8 9 10 13
```

Appraoch:

Method 1: Sort and Search

## Sort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.

Objective: Given an array of intergers, sort it such that the odd numbers appear first followed by the even numbers . The odd numbers in ascending order and the even numbers in descending order.

Input: An Array of Integers

Example:

```Input Array : 1 2 3 4 5 6 7 8 9 10
Output : 1 3 5 7 9 10 8 6 4 2
```

## Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern

Objective: Given a binary Tree, Do Level Order Traversal in Zig Zag pattern OR Print in Spiral

Input: A Binary Tree

Output: Order Traversal in Zig Zag pattern OR Print in Spiral. Level Order Traversal in Zig Zag pattern OR Print in Spiral

Better Solution :

## Find the first repeated element in an array by its index

Objective: Given an array of integers, find out the first repeated element. First repeated element means the element occurs atleast twice and has smallest index.

Input: An Array

Output: The first repeated element

Examples :

```Array {1,1,3,4,6,7,9} first repeated Number : 1
Array {7,2,2,3,7} first repeated Number : 7
Array {5,3,3,3,3,3,3,3,4,4,4,5,3} first repeated Number : 5
```

## Given two binary trees, check if one binary tree is a subtree of another

Objective: Given two binary trees, check if one binary tree is a subtree of another

Input: Two binary trees

Output: True or false based on whether one tree is subtree of another

Example: Tree is subtree of another tree example

Approach:

We know that to indentity any binary tree can be represented as the combination of either inorder and preorder traversal OR inorder and postorder traversal OR inorder and Level order traversal.

## In a Binary Tree, Create Linked Lists of all the nodes at each depth.

Objective: Given a Binary tree create Linked Lists of all the nodes at each depth , say if the tree has height k then create k linked lists.

NOTE : This problem is very similar “Print binary tree, each level in one line

Input: A binary tree

Output: K linked lists if the height of tree is k. Each linked list will have all the nodes of each level.

Example:

## Level Order Traversal, Print each level in separate line.

Objective: Given a Binary tree , Print each level of a tree in separate line.

NOTE : This problem is very similar ” Create Linked Lists of all the nodes at each depth “

Input: A binary tree

Output: Each level of binary tree, in one line

Example:

## Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

```Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10
```

Approach:

## Remove Duplicates from an Unsorted Linked list

Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

```Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3
```

Input: An unsorted linked list

Output: Linked list with no duplicates.

Approach:

• Create a Hash Map
• Take two pointers, prevNode and CurrNode.
• PrevNode will point to the head of the linked list and currNode will point to the head.next.

## String Compression using count of repeated characters – Run Length Encoding

Objective: Write an algorithm to compress the given string by using the count of repeated characters and if new compressed string length is not smaller than the original string then return the original string.

Example:

```Input String : ssssuuuummmmmmiiiittttttttttttt
Compressed String : s4u4m6i4t13

Input String : Jaain
Compressed String : Jaain (Since compressed string is length is greater than original string)
```

Input: A String

Output: either A compressed string or original string whichever us smaller.

Approach:

## Replace all spaces in a String with ‘%20’

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and the true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

Example:

`Input String :`

I am Sumit Jain

`Output String : `

I%20am%20Sumit%20Jain

` `

Approach:

## Find Whether Two Strings are Permutation of each other

Objective: Given Two Strings, check whether one string is a permutation of other

Input: Two Strings

Output: True or false based on whether strings are permutations of others or not.

Example:

```"sumit" and "tiums" are permutations of each other.

"abcd" and bdea" are not permutations of each other.

```

Approach:

Method 1: Time Complexity – O(nlgn)

## Find Intersection Point in Two Linked List

Objective: Given Two linked lists, check whether both lists intersect each other, if yes then find the starting node of the intersection.

An intersection point means the end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List

Output: Intersection Node or point

Example:

Approach:

## Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

Objective: Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective order.

Example

``` : Input :  1 -2 3 -4 5 -6 7 -8 9 -10

ReArranged Output :  -2 -4 -6 -8 -10 1 3 5 7 9
```

Input: An array with positive and negative numbers

Output: Modified array with positive numbers and negative numbers are on each side of the array.

Approach:

Method 1. One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.

Method 2: Divide and Conquer

## Find a pair of numbers from an array whose sum equals k

Objective: Write an algorithm to find out whether in a given array there exists or not two numbers whose sum is exactly equals to a given number. This problem has been asked in Amazon and Microsoft interviews.

Input: An array arrA[], A number k

Output: True or false based upon we have found any two numbers in array arrA[] whose sum is equal to k

Approach:

Method 1: Using Binary Search