imageIcon.js with dry run(*** Standard Interview question for some companies***)
/*Image Icon Match
You are given a 1D image. The image is a sequence of pixel values.
You are also given an icon of a particular size.
The icon is a sequence of 2 pixels. Find the number of times this icon appears in the image.
Input
First line contains n, the number of pixels in the image.
This is followed by n lines, each containing one positive integer denoting a pixel, j, 0 <= j <= 255.
This is followed by m, the number of pixels in the icon.
This is followed by m lines, each containing one positive integer denoting a pixel k, 0 <= k <= 255.
Output
An integer i i >= 0, denoting the number of times the icon appears in the image.
Example
Input:
10
7
27
31
8
9
10
25
8
9
11
2
8
9
Output:
2
The first line is 10 i.e. 10 pixels in the given image 7, 27, 31, 8, 9, 10, 25, 8, 9, 11
is the given image After this, the line contains 2, i.e. 2 pixels in the icon 8, 9
is the given icon. 8, 9 appears twice in the image. So 2 is the answer.
*/
let fs = require("fs");
let data = fs.readFileSync(0, 'utf-8');
let idx = 0;
data = data.split('\n');
function readLine() {
idx++;
return data[idx - 1].trim();
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
// This parts is only for taking input of Image
const noOfPixelsInImage = parseInt(readLine()); // 10 is the no. of pixels in the given image
let image = []; // we will push all the image elements in this array
for (let i = 0; i < noOfPixelsInImage; i++) {
image[i] = (parseInt(readLine()));
}
// console.log(image); [
// 7, 27, 31, 8, 9, yellow color elements
// 10, 25, 8, 9, 11
// ]
// This part is only for taking Inputs of Icon
const noOfPixelsInIcon = parseInt(readLine()); // 2 is the no. of pixels in the given icon
let icon = []; //we will add/push all the icon elements here.
for (let i = 0; i < noOfPixelsInIcon; i++)
{
icon.push(parseInt(readLine()));
}
// console.log(icon); [ 8, 9 ] yellow color elements
// This part is the actual operation
let j = 0, i = 0; // J is the pointer for image and i is the pointer for icon and both i
// and j are initialisation for the while loop.
let count = 0; // since initially there is no count of icon in image
while (j < noOfPixelsInImage) // 0)0<10 true , This is main while loop
1)1<10 true,
2)2<10 true,
3)3<10 true,
4)4<10 true,
5)5<10 true,
6)6<10 true,
7)7<10 true,
8)8<10 true,
9)9<10 true,
10)10<10 false, exit the main while loop and console.log the
count variable i.e, 2.
{
if (image[j] == icon[i]) // 0) 7== 8 false move to else & j++,
1) 27 ==8 false move to else & j++,
This is first if statement 2) 31== 8 false move to else & j++,
3) 8 == 8 true assign x as 3 and move into the inner while
loop
4) 9==8 false move to else & j++
5) 10==8 false move to else & j++
6) 25==8 false move to else & j++
7) 8==8 true assign x as 7 and move into the inner while loop
8) 9==8 false move to else & j++
9) 11==8 false move to else & j++
{
let x = j; // 3) x=3 , 7) x=7
while (j < noOfPixelsInImage && image[j] == icon[i]) // 3) 3<10 true && 8==8 go in loop
3.1) 4<10 true && 9==9 go in loop
This is Inner while loop 3.2) 5<10 true && 10== undefined
false exit the loop & go to if
condition
//7) 7<10 true && 8==8 go in the loop
7.1)8<10 true && 9==9 go in the loop
7.2)9<10 true && 11==undefined false
exit the loop and go to if condition
{
j++; // 3.1) j++ is 4 && value is 9
i++; 3.1) i++ is 1 && value is 9
3.2) j++ is 5 && value is 10
3.2) i++ is 2 && value is Undefined
// 7.1) j++ is 8 && value is 9
7.1) i++ is 1 && value is 9
7.2) j++ is 9 && value is 11
7.2) i++ is 2 && value is undefined
}
if (i >= icon.length) // 3.2) i=2>= icon.length(2) true
// 7.2) i=2>= icon.length(2) true
{
count++; // 3.2) increment count to 1
// 7.2) increment count to 2
}
j = x + 1; // 4) j= 3+1 i.e, j is 4 now and now continue the main while loop
// 8) j= 7+1 i.e j is 8 now and now continue the main while loop
i = 0;
}
else { j++; } // 1) J++ i.e, j=1 now
2) j++ i.e, j=2 now
3) j++ i.e, j=3 now
5) j++ i.e j=5 now
6) j++ i.e j=6 now
7) j++ i.e j=7 now
9) j++ i.e j=9 now
10)j++ i.e j=10 now
}
console.log(count);
//////////////////////////////////////////////////////////////////////////////////////////////
TERMINAL:
Comments
Post a Comment